Generative grammars as a form of procedural content generation

Summary

本视频讨论了生成语法在游戏开发中的应用，特别是在程序生成内容方面。生成语法是一种基于规则的文本生成技术，可以通过替换特定词汇来创造多样化的内容。视频中通过一个简单的地下城生成示例，展示了如何使用生成语法来设计游戏关卡，包括房间布局、任务和故事情节。此外，还提到了生成语法在命名、世界构建等方面的潜力。尽管生成语法在处理空间和非线性布局方面存在局限性，但它为创造个性化游戏体验提供了强大的工具。

Takeaways

• 📚 生成语法在游戏开发中有广泛应用，如语言解析器、文本预测等。
• 🎲 生成语法可以定义为一系列规则，用于如何以及何时替换某些词语。
• 🗺️ 通过生成语法，可以创建随机或定制化的程序生成内容。
• 🏰 例如，可以生成类似塞尔达游戏中的线性地牢体验。
• 🔄 通过迭代替换，可以生成具有不同房间和事件的复杂地牢布局。
• 📈 生成语法允许设置最小和最大地牢大小等具体规则，以创造更精致的体验。
• 📝 生成语法可以用于描述玩家动作、任务、故事节拍和命名人、地点等。
• 📚 有研究者使用生成语法来分析MMORPG任务模式，并生成具有不同复杂性和吸引力的任务。
• 🔄 生成任务时，可以结合动机、策略和行动序列来增加任务的深度和多样性。
• 🌐 生成语法的一个限制是它是一维的，没有空间或非线性概念。
• 🔍 尽管生成语法有局限性，但它的规则基础替换概念对于内容生成仍然非常有价值。

Q & A

什么是生成语法？

生成语法是一种广泛的研究领域，与语言解析器、文本预测等相关。在游戏开发中，可以将其定义为一系列单词或句子，以及关于何时以及如何替换某些单词的规则。

生成语法在游戏开发中有哪些应用？

生成语法在游戏开发中可以用于创建程序生成的内容，如随机或手工定制的地下城布局、任务生成、玩家行为描述、故事情节生成以及命名人、地点和事物等。

如何使用生成语法来创建一个地下城体验？

可以通过一个基本模板句子开始，然后根据规则替换其中的“房间”单词，例如将其替换为谜题、战斗遭遇或宝藏房间等，直到所有“房间”都被替换。

生成语法如何实现更具体的游戏内容定制？

可以通过定义更具体的替换规则，例如最小和最大地下城大小，以及更具体和规则驱动的替换，来创建更具手工艺品感的体验。

生成语法在任务生成中的应用是什么？

生成语法可以用于创建基于结构分析的任务生成器，通过分析MMORPG中的任务模式，使用生成语法来生成不同复杂度和吸引力的任务。

生成语法在游戏开发中的主要局限性是什么？

生成语法的主要局限性在于它是一维的，没有空间或非线性的概念，这使得在创建复杂的空间布局时会变得混乱。

如何克服生成语法在空间布局上的局限性？

可以通过使用生成语法的多维表亲——图重写技术来设置空间和非线性布局，这是一种更好且更常用的方法。

生成语法的人类可读性有什么优势？

生成语法的人类可读性意味着非程序员，如关卡设计师或玩家，可以手动编写内容，然后由系统解析，这使得内容创建更加灵活和易于操作。

在生成语法中，如何确保生成的内容不会导致不可能的空间？

需要编写规则来确保生成的空间是合理的，并且在出现问题时进行调试，这可能需要在生成过程中进行多次迭代和调整。

生成语法系统在编码时应该考虑哪些因素？

在编码时，应该考虑如何表示单词或对象的列表，如何迭代列表以满足生成条件，以及如何实现递归替换函数以优化迭代过程。

生成语法在游戏设计中如何与其他生成方法结合使用？

生成语法提供了基于规则的替换概念，这使得它可以与任何生成方法结合使用，同时仍然能够为玩家提供深思熟虑的体验。

Outlines

00:00

📚 游戏开发中的生成语法介绍

本段讨论了生成语法在游戏开发中的应用，尤其是其在创造多样化的游戏内容方面的潜力。生成语法是一种定义词汇序列和替换规则的系统，可以用来生成如地牢、任务等游戏内容。通过举例说明，如何将一个基本的地牢模板通过替换规则转换成具有不同房间和事件的复杂地牢。此外，还提到了生成语法在文本预测、语言解析等领域的应用，并强调了其在游戏设计中的灵活性和可定制性。

05:00

🔍 生成语法的局限性与多维扩展

这段内容讨论了生成语法在处理一维内容时的局限性，尤其是在空间和非线性布局方面的挑战。举例说明了如何通过生成语法描述地牢中的门解锁过程，但指出这种方法在处理空间布局时会变得复杂。作者提到了生成语法的多维扩展——图重写技术，这是一种更常用且能够处理空间和非线性布局的方法。最后，作者提到了实现生成语法系统的可能性，但没有提供具体的代码，而是建议从简单的列表和迭代开始，并根据需要进行调整。

Keywords

💡生成语法

生成语法是一种用于语言解析、文本预测等领域的研究领域，它通过一系列规则来定义如何以及何时替换某些词汇。在游戏开发中，生成语法可以用来创建随机或手工定制的程序生成内容。例如，可以用来生成地牢的不同房间类型，如谜题室、战斗遭遇或宝藏室。

💡地牢体验

地牢体验通常指的是游戏中的地下城探险部分，玩家需要通过解决谜题、战斗等方式来完成挑战。在视频中，地牢体验被用作生成语法的一个应用实例，通过替换基本模板句子中的“房间”词汇，可以创造出多样化的地牢布局。

💡规则替换

规则替换是生成语法中的核心概念，它允许开发者定义一系列规则来指导如何替换文本中的特定词汇。这使得生成的内容既可以是完全随机的，也可以是根据特定规则定制的。例如，可以设置最小和最大地牢大小的规则，以创造更符合预期的游戏体验。

💡程序生成内容

程序生成内容（Procedurally Generated Content）是指游戏内容不是预先设计好的，而是通过算法在游戏运行时动态生成的。这种方法可以创造出独一无二的游戏体验，并且可以极大地扩展游戏的可玩性和重玩价值。在视频中，生成语法被用来实现程序生成的地牢和任务。

💡非线性游戏

非线性游戏是指游戏的进程不是单一线性的，玩家可以根据自己的选择和行动来影响游戏的发展。生成语法在处理非线性游戏时存在局限性，因为它是一维的，没有空间或非线性的概念。这在视频中被提及为生成语法的一个主要限制。

💡多维表亲

多维表亲指的是生成语法的扩展形式，它可以处理多维空间和非线性布局的问题。在视频中，提到了这种形式作为解决生成语法一维限制的解决方案，但具体的技术和方法将在后续的视频中讨论。

💡图重写技术

图重写技术是生成语法的一种多维形式，它允许开发者定义复杂的规则来生成和修改游戏世界中的元素。这种技术可以处理空间布局和非线性流程，是生成语法的一个更高级的应用。在视频的结尾部分提到，将在下一次讨论中详细介绍图重写技术。

💡任务生成器

任务生成器是一种利用生成语法来自动生成游戏任务的工具。在视频中提到的一个原型任务生成器基于对四个大型多人在线角色扮演游戏（MMORPGs）中的任务模式进行分析，使用生成语法来创建不同复杂度和吸引力的任务。

💡动机与策略

动机与策略是任务生成器中用来定义任务结构的两个关键组成部分。动机是指任务背后的原因，如知识、征服和声誉；策略则是实现动机的行动计划，如监视某人、杀死敌人或获取稀有物品。这些元素在任务生成器中被用来创造多样化的任务内容。

💡世界构建

世界构建是指创造一个游戏世界的过程，包括定义其地理、文化、历史等元素。在视频中，提到了如何通过定义世界的规则和文化来驱动内容生成，从而增强游戏世界的连贯性和深度。例如，可以通过设置特定地区的方言和法律来影响任务的生成和玩家的选择。

Highlights

Generative grammars have a limited use in game development compared to graph grammars.

Generative grammars can be defined as a sequence of words or sentences with rules for word replacement.

An example of using generative grammars is to create a small dungeon experience with different room types.

Generative grammars can be applied to language parsers, text prediction, and more.

The process involves iteratively replacing words in a sentence with possible alternatives.

Generative grammars allow for procedurally generated content that can be as random or handcrafted as desired.

The technique can be used to describe dungeon layouts, player actions, quest narratives, and even naming conventions.

Generative grammars are human-readable and can be used by non-programmers to manually write content.

A paper on a prototype quest generator uses generative grammars to create quests based on MMORPG quest patterns.

Quests are modeled with motivations, strategies, and actions that can be procedurally generated.

The method can incorporate world-building elements like regional dialects and cultural behaviors.

Generative grammars are one-dimensional and do not account for spatial or non-linear aspects of game design.

The limitations of generative grammars can be overcome with multi-dimensional graph rewriting techniques.

The implementation of generative grammars can vary greatly depending on the use case and desired outcome.

A basic implementation could involve a list of words and a loop for iterative replacement.

More sophisticated implementations might use recursive functions for word replacement.

The concept of rules-based replacement is a valuable tool for content generation in games.

The next discussion will explore graph rewriting techniques, which are more suitable for spatial and non-linear layouts.

Transcripts

today's discussion started out as an

introductory section as part of a larger

discussion on graph grammars or graph

rewriting if you prefer but i came to

the realization that i really wanted to

talk about each a bit more than would

make sense for one video so here we are

generative grammars have a bit of a

limited use in game development

especially since graph grammars can do

everything they can do and more but i

came across some interesting uses for

them that i think is worth discussing

plus the concepts introduced here will

carry over nicely into graph grammars so

let's dive in generative grammars are a

fairly broad area of study with

applications related to language parsers

text prediction and more and i found it

a little hard to succinctly define the

term without getting overly academic but

i think as far as we're concerned in

regards to game development we can

define the concept simply as a sequence

of words or sentence with rules

regarding how and when to replace some

words with other words a bit vague i

know but bear with me as it'll make a

lot more sense with an example so let's

say we want to generate a small linear

dungeon experience not unlike a zelda

dungeon if we wrote out the flow of the

level using words we could start with a

basic template sentence like this the

entrance boss and exit in this case will

be fixed since we know we always want to

start with a simple entrance room so the

player can take in our awesome

atmospheric design for the level and end

with a big climactic boss fight but what

about room that's not very descriptive

or interesting so let's take a look at a

few options we have to replace a room

with something better as a good start we

could replace our template room with a

puzzle of some kind a combat encounter

or we could have a treasure room to

reward the player with gold or a

valuable item and there's no reason we

have to stick with a measly three rooms

so perhaps we could also replace a room

with multiple rooms if we limit

ourselves to never replacing room with

more than two words at a time mostly

just so i don't have to write down too

much we get these possible permutations

now we can scan our sentence and replace

every instance of the word room with one

of the possible replacements since we

can potentially add additional rooms

with each replacement we'll do this scan

and replace over and over until all

instances of the word room have been

replaced we could alternatively show off

our programming chops and do a recursive

solution for every replacement so that

we only have to iterate over the

sentence once either way is fine as long

as we end up without any empty rooms in

our layout since this is a completely

random operation though we are equally

likely to end up with something simple

and boring or something extremely long

and grinding and everywhere in between

not the greatest algorithm but here's

the cool thing about generative grammars

we can code up any rules we want for

replacement we start with random

replacements because that's easy but

that was completely arbitrary we could

require minimum and maximum dungeon

sizes for instance and consider these

more specific and rule driven

replacements that will create a more

quote handcrafted experience we can get

as specific as we want even making very

specific custom content that will be

swapped into the level just to add a

little bit of randomization to it so

hopefully by now you've got a pretty

good idea of what this technique can

offer procedurally generated content

that is as random or as handcrafted as

you want it to be going for more of a

roguelike experience just define some

interesting patterns like mini boss

leads to treasure and let the generator

work from there want to make all of your

games content manually but just make

each player's experience slightly

different get very specific with when

and how you do replacements and of

course this method doesn't have to be

just for describing how dungeon rooms

will be laid out since we can use any

strings we want to describe content we

could describe actions the player will

take for a quest we could generate story

beats based on a set of archetypes and

patterns and of course naming people

places and things is another good use

case we can define basic rules like

adjective and noun to get simple names

or use geographic properties about the

location to make a more cohesive world

taking into account regional dialects

for instance there's really no limit to

what you can do or describe since

everything is just words joined together

at the break points you decide grammars

also come with the cool benefit of being

human readable and therefore also

ridable with a system like this a

non-programmer such as a level designer

or a player could manually write what

they want and have the system parsed

pretty cool and so now let's talk about

my favorite implementation of generative

grammars that i've come across there's a

paper a prototype quest generator based

on a structural analysis a quest from

four mmorpgs that is really cool i

highly recommend you check it out for

yourself as it's a pretty approachable

read but here's the gist of it the

authors analyzed hundreds of quest

patterns in mmorpgs and used generative

grammars to procedurally generate quests

of varying complexity and intrigue they

modeled quest as a combination of

motivations such as knowledge conquest

and reputation alongside a series of

strategies for satisfying that

motivation such as spying on someone

killing an enemy or obtaining a rare

item each strategy is then broken down

to a sequence of actions that can be

replaced to generate content each action

can then be further broken down into sub

quests or sub-actions that let you layer

in complexity as an example maybe the

quest starts out with a farmer saying my

finest cow has been stolen please get it

back for me but you end up having to

investigate the location it was last

seen discover tracks leading to

abandoned hideout kill or negotiate the

information of what they did with the

cow buy or steal the cow back and then

protect it for more bandits on your way

back to the farmer sure it's not going

to win any awards for writing but it's

better than uh

yeah plus you could layer in lots of

lore and let that drive the decisions

you make to help reinforce your world

building maybe this part of the world is

the only area bandits are found in and

they're highly motivated by money

therefore they tend to be behind crimes

with a financial lien and their quests

always have an option to buy your way

out of a situation maybe nobody steals

in the desert province just because they

have harsher penalties for it or they're

just more careful about it when they do

and you'll need to do more spying and

smooth talking to gather information the

point is there's a lot of ways you could

go with this idea if you define the

rules people and cultures of your world

and use that to help drive the content

generation so all of this sounds great

but i did lie earlier because there is

one big limitation to this method and

that is the fact that it is one

dimensional there's no concept of space

or non-linearity you can model nonlinear

gameplay if you want but it gets messy

really quickly consider this example

sentence to describe unlocking one door

in a dungeon it's a lot of words for

what is probably a tiny section of our

dungeon and once we map out the whole

thing it'll be hard to follow sure we'll

code up a nice parser and let it do most

of the work but debugging will be

painful with lots of work to mentally or

maybe even physically map out the space

when an issue arises plus we still have

to figure out how to spatially fit

everything together and code up rules to

ensure that we don't make impossible

spaces the solution is the

multi-dimensional cousin of generative

grammars that i mentioned at the

beginning of this video i'm going to

save that for another time just be aware

that there is a better and more commonly

used way to set up spatial and

non-linear layouts and by now you may be

curious about what the implementation of

a generative grammar system may look

like but i'm afraid there's no code this

time as there's just too many ways you

could code it up and the use case will

really drive the implementation my

immediate thoughts which i kind of

mentioned earlier would be to start with

a list of words or objects representing

words if you need to keep some metadata

attached to each entry and just use a

simple while loop to iterate the list

over and over until all your conditions

for generation are met if you want to

get a bit more sophisticated you could

recursively call a replacement function

on words that qualify for replacement so

that you only have to iterate the list

once you might still need a few more

passes in case you want to make

adjustments to things like placing a

mini boss at the middle of the finalish

dungeon but again that's why i'm not

offering a code solution and instead

just kind of pointing you in the general

direction that i would start with and

that's an introduction to the concept of

generative grammars for game development

hopefully you found it interesting and

got some good ideas out of it but at the

very least the concept of rules-based

replacement should be something to keep

in mind when generating content as it

makes it easy to use whatever generation

method you want while still providing

thoughtful experiences for the player

next time we'll take this concept

multi-dimensional and look at graph

rewriting techniques