Graph Grammar based Procedural Generation for a Roguelike

Summary

视频展示了一种用于生成roguelike游戏中的熔岩地形技术。该技术基于Voronoi单元算法，通过随机漫步在六边形网格上生成房间和走廊。通过图语法规则，系统能够创建出具有不同连通性和复杂性的地形。视频中还介绍了如何通过设置规则和限制来控制地形的生成，以及如何使用JavaScript实现Voronoi图。最终，这些技术在LOVE引擎中得到了应用，创造出多样化的游戏环境。

Takeaways

• 🔥 介绍了一种用于roguelike游戏的新型熔岩生成技术。
• 📐 该技术基于Voronoi细胞算法，从一组点生成凸多边形。
• 🔄 点是通过在六边形网格上进行随机漫步生成的。
• 🎨 颜色代表不同的游戏元素，如房间、走廊、墙壁等。
• 📊 通过图语法规则来构建和变化这些多边形。
• 🔄 图语法规则包括左侧的连接图和右侧的替换图。
• 🎲 规则的应用是随机的，可以设置限制以控制生成结果。
• 🔄 通过添加新的规则，可以创造出更复杂的房间和走廊结构。
• 🔄 规则可以细分和优化，以生成更多样化的关卡。
• 🚫 避免走廊交叉，除非明确要求。
• 🙏 感谢了多位专家和同事对项目的贡献和启发。

Q & A

这段视频中展示的是什么技术？

视频中展示的是用于生成roguelike游戏地图的熔岩生成技术，它基于Voronoi单元算法，通过一组点生成凸多边形。

视频中提到的随机漫步是如何工作的？

随机漫步是通过在六边形网格上进行随机移动来生成房间点，这些点随后用于Voronoi单元算法来创建地图。

视频中的颜色代表什么？

颜色代表了地图的不同元素：房间用不同颜色表示，走廊用蓝绿色表示，灰色墙壁代表花岗岩，而周围的土壤和草地则用其他颜色表示。

视频中提到的图语法规则是什么？

图语法规则由左侧的连接图和右侧的替换图组成。在生成过程中，左侧的图会被右侧的图随机替换，以创建房间和走廊。

如何控制生成的地图的连通性和循环性？

可以通过设置图语法规则的应用次数或者通过给房间分配标签来控制地图的连通性和循环性。

视频中提到的“碰撞体积”是什么？

“碰撞体积”是指房间的圆形表示，它确保两个房间之间总是可以创建走廊。

视频中展示的地图生成器如何处理房间的布局？

地图生成器在生成过程中会移动房间，使它们不相交，然后尽可能地将它们紧密地聚集在一起。

视频中提到的“死胡同”是如何产生的？

死胡同的产生可以通过调整图语法规则来控制，例如通过限制规则的应用次数或使用特定的规则组合。

视频中提到的“cosmetic”是什么意思？

“Cosmetic”在这里指的是装饰性的，意味着某些线条（如房间边缘）即使重叠，也不会影响地图的有效性。

视频中提到的“subdivide”规则是什么？

“Subdivide”规则是指将一个图形（如四边形）分割成更小的部分，例如将一个四边形分割成四个更小的四边形。

视频中感谢了哪些人？

视频中感谢了David Adams（关于自动生成游戏地牢的论文作者），Raymond Hill（JavaScript Voronoi图实现者），以及Phil Ronson（同事，就地图生成进行了有益的讨论）。

Outlines

00:00

🌋 介绍熔岩生成技术

视频介绍了一种用于roguelikes游戏的熔岩生成技术。该技术不基于传统网格系统，而是使用Voronoi细胞算法，从一组点生成凸多边形。这些点通过在六边形网格上进行随机游走生成，颜色代表房间和走廊。程序还展示了如何通过按钮显示所有单元的边缘，以及如何通过空格键生成不同的例子。技术的核心是图语法规则，这些规则由左侧的连接图和右侧的替换图组成。规则的应用是随机的，可以通过设置标签或限制应用次数来控制。

05:03

📜 图语法规则和水平生成

视频继续解释图语法规则，展示了如何通过添加新规则来控制房间的生成。例如，找到两个相邻的房间并用一个小房间替换它们，或者在房间之间添加额外的走廊。视频中还提到了如何通过设置规则来控制死胡同的数量。此外，展示了如何通过不同的规则集来创建具有不同特征的关卡，例如在中间有一个深渊的关卡。最后，视频感谢了David Adams的启发性论文、Raymond Hill的Voronoi图实现以及Phil Ronson的讨论和支持。

Keywords

💡lava generation technology

在视频中提到的熔岩生成技术是指用于生成游戏环境（如roguelikes）中熔岩区域的一种算法。这种技术不是基于传统的网格系统，而是使用Voronoi细胞算法来创建多边形，从而形成独特的地形。这与视频中展示的地形生成过程紧密相关，是视频的核心内容之一。

💡Voronoi cell algorithm

Voronoi细胞算法是一种数学算法，用于根据一组点生成一系列凸多边形。在视频中，这个算法用于生成房间和走廊的基础结构。每个点代表一个房间，而Voronoi算法则根据这些点生成连接它们的多边形。

💡random walk

随机游走是一种数学统计模型，常用于模拟随机过程。在视频中，随机游走通过六边形网格来生成房间的初始点，这是地形生成的第一步。

💡graph grammar rules

图语法规则是一种形式化的方法，用于描述和生成图形结构。在视频中，这些规则用于定义如何从一个图形结构转换到另一个结构，从而实现地形的动态变化。

💡collision volume

碰撞体积是指在游戏设计中，用于检测物体间是否可以发生物理碰撞的虚拟空间。在视频中，圆圈代表碰撞体积，确保房间之间可以创建走廊。

💡cosmetic lines

在游戏设计中，装饰线（cosmetic lines）指的是那些仅用于视觉效果，而不直接影响游戏玩法的线条。视频中提到，灰色线条和点代表装饰，意味着它们可以重叠，但仍然被视为有效的地形。

💡level generation

地形生成是指在游戏设计中自动创建游戏环境的过程。视频中的地形生成涉及到使用Voronoi算法和图语法规则来动态构建游戏关卡。

💡David Adams

David Adams是游戏设计领域的专家，他撰写了关于自动生成游戏地牢（dungeons）的论文。在视频中，演讲者提到了Adams的工作，表明他的研究对视频内容有重要影响。

💡Raymond Hill

Raymond Hill是JavaScript Voronoi图实现的开发者。在视频中，演讲者提到了Hill的代码，表明他的工作对于实现Voronoi算法在地形生成中的应用至关重要。

💡Phil Ronson

Phil Ronson是演讲者的同事，他们在游戏关卡生成方面进行了深入的讨论。在视频中，演讲者感谢Ronson的贡献，表明他在项目中扮演了重要角色。

Highlights

展示了一种用于roguelikes的新型熔岩生成技术

该技术不基于传统网格系统，而是基于Voronoi单元算法生成凸多边形

房间点通过六边形网格上的随机游走生成

颜色代表不同的房间和走廊，灰色墙壁代表花岗岩

通过按下按钮可以显示所有单元的边缘

按下空格键可以生成不同的地图示例，展示不同的连通性和循环

底层工作原理基于图语法规则，由左侧的图连接图和右侧的替换图组成

图语法规则可以通过房间标签或最大应用次数来限制

通过图语法规则，可以从单一的起点生成复杂的房间结构

房间生成后会移动以避免相交，并尽可能紧密地聚集在一起

展示了如何通过不同的规则集生成具有不同特征的地图

通过特定的规则集，可以生成具有中心空洞的地图

介绍了如何通过规则细分房间以创建更复杂的结构

提到了David Adams的论文，该论文启发了图语法规则的研究

感谢Raymond Hill提供的JavaScript Voronoi图实现

感谢Phil Ronson在主观层面上的讨论和帮助

Transcripts

hello and welcome I'd like to show you

some lava generation technology for

roguelikes that I've been working on

recently if i zoom in over here you can

see that it's not a usual grid based

system it's actually based on a Voronoi

cell algorithm that generates a bunch of

convex polygons from a set of points the

points for these rooms have been

generated by an a random walk through a

hex grid which is where you can see

quite a few hexagons there the colors

are supposed to represent rooms and then

corridors of turquoise for some reason

it's internet my program I'm not an

artist and then the the gray walls

supposed to represent granite and then

this slightly scintillating water is

supposed to be kind of moat but and then

you've got dirt and grass around that

and then granite and a hard wall around

the entire level if I press this button

here you can see edges on all the cells

that are in in the level so it it does

actually build them there's just that

intense look a little bit better if you

only see the ones that you can walk on

now if I press space I can generate a

few different examples this this

particular level is made from the same

raw set but you can see there's quite a

few variations in the amount of

loopiness or connectivity there so the

way it all works underneath is from

graph grammar rules and the graph

grammar rules consists of a left-hand

side which can be a graph connected

graph in particular and it starts with a

single s now the the s vertex will end

up becoming a room and on the right-hand

side we have a substitute graph so

wherever it finds the left it will

replace it with the right and if there's

more than one rule that applies at

particular time then one is chosen

randomly if there's War them one way to

pick to apply a particular rule

they'll pick one of the many ways it

could be applied as well randomly you

can there are a few ways to limit it you

can limit it via either how you assign

the tags on the rooms themselves or you

can limit it based on setting a number

for the maximum number of times of all

can be applied but anyways just enough

talk let's see things so this starts

with single less light all levels do and

then it replaces it with a triangle of

a's so what does this do this creates a

lovely triangle and then once against

the end of the process because it's no

other rules to apply it generates a room

for each of the vertices the circle

represents a kind of a collision volume

said the so that it's always possible to

create a corridor between the two rooms

and the rooms themselves they'll

intersect and let's go back to the rule

now let's add another rule so if we find

two rooms with a called a each let's

replace it with same two rooms we have a

little room between them and then like

another little side offering now

currently in the system if there's any

verses here on the left and they have to

all be connected and then they must also

be present in the right-hand side so

let's have a see what happens there all

right sorry to have saved that

there we go so it's found at two ways

there and replaced it with the kind of

threefold lines around the center so it

looks kind of like a kite flying or

potion bottle falling over and of course

there are more ease now and you can find

more lines of a sari and if I let this

process carry on smoothly you can kind

of get an appreciation for how the level

generator works underneath and at the

end of the process it assigns the broom

and then it science of rooms moves them

all apart from each other so that

they're not intersecting and then tries

to pull them all together as close as

you can and if we go back to the other

view you can see what that looks like

now so we've got loops here with some

dead end rooms

a lot of loops and this is just from a

relatively simple setup that contains

just two rules and you can get quite a

bit of variation from it probably more

dead ends and you've really want but

again that could be controlled by a year

and then putting the rules to control

them or thereby stopping how many times

a ball can be applied so let's have a

look at some other sets of rules that

I've done here's one I did earlier so

this particular one here tries to have

two circular sets of periphery cells and

then an abyss in the middle the grey

lines and the grey dot here mean that

the room and the edges between them are

cosmetic which means I don't care if if

cosmetic lines overlap or the lines it

will still be counted as a successful

level so let's have a look at that

register sorry in the and the in game

view right so my evil of bitters are

denoted by the rather sad purpley blue

okay again I'm a I'm a program in our

lives just just imagine that's evil for

a second and there we go if I hit space

we can hit create quite a few variants

they're the only rules on this

particular one subdivide so if we see

here it created there's like four

triangles around there so this will

match one of those triangles and create

two or it can match a triangle and

create little side off room now this

exclamation mark see you means this will

only be matched if there is not another

vertex attached to this

that's called sea

I'm using senior left tax just because

we're so this is a set of rules based on

square quad so that's you can probably

just see it roughly in here and then

what it does it subdivide it into four

four quads and let's let me show you the

rules for that so here we go we start

with a quad so it divides it into four

quads the new magenta this means that it

tries to make the lines shorter and

you'll notice here that this side is

created with all A's it matches all A's

here but it replaces it this outside the

bottom-left edge has got all B's on it

this means that it will always try and

subdivide within this corner which this

is supposed to be a test of subdividing

within subdividing

and as you can see

takes a little bit longer than some of

the others because the process not

actually perfect

sometimes the rooms will collide and I

don't I don't put too many artificial

restrictions on the rules so it actually

is possible to come up with all sets

that would never actually generate a

valid level by crossing lines over so

obviously I don't want corridors to

cross unless you explicitly want that

anyway I hope you've enjoyed watching

and say show off my handiwork I would

like to thank David Adams who wrote a

paper called automatic generation of

dungeons for computer games which is the

paper that originally inspired me to

look into graphic grandma rules and

Raymond he'll lose excellent JavaScript

Voronoi diagram implementation

I've bought deliver and this is all

running in lower by the way in in the

love engine and I would like to thank

Raymond Hill because his JavaScript code

for the Voronoi diagram a generation it

was excellent and also might thank last

but not least Phil Ronson who's a

colleague of mine who's had with whom

I've had many enlightening and useful

discussions on the subjective level

generation and this particular project

thank you very much