An introduction to graph rewriting for procedural content generation

Graph rewriting is a great way to generate interesting procedural content for games, suitable for generating both grid-based and non-grid-based maps, quest structures, and more. In this introductory video, we'll look at what a graph is, how graph rewriting can be used to generate content for games, and what some common techniques and usages look like.
Intro: 00:00
What is a graph?: 00:42
Graph rewriting: 02:30
Generating a graph: 04:09
Common uses: 05:26
Text version: shaggydev.com/2022/11/20/grap...
And here's a few links you might want to check out regarding implementation:
Metazelda Algorithm: web.archive.org/web/202106281...
Graph Grammar based Procedural Generation for a Roguelike: • Graph Grammar based Pr...
Unexplored's generation method: www.aiandgames.com/2021/01/28...

[@NateyC214]

Simple explanations and pleasing diagrams, who could ask for more?

[@Microphunktv-jb3kj]

7:20 , what game is this ?

[@Kazner0h]

How could I *not* subscribe with such wonderful visuals and editing? Great video

[@haydenap]

Always look forward to your videos. This has been really interesting, thanks for including extra links.

[@_gamma.]

Great overview! 👏

[@nickvatanshenas9251]

Great editing and explanations

[@pixtrick]

That was exactly what i was looking for. On top of that, that was brilliantly explained. Thanks mate

[@joelgomes1994]

Your channel is pure gold, nice job!

[@TheShaggyDev]

Glad you enjoy it!

[@realMenta]

Thanks

[@pavlovsdoguk]

your stuff on Graph rewriting is awesome. Subbing for this content.

[@TheShaggyDev]

Thanks! If there's any other proc-gen topics that you're interested in, let me know! I keep a big list of topics and pull from it when I'm deciding what content to cover.

[@pavlovsdoguk]

@@TheShaggyDev Right now I'm working on a game that uses graph rewriting, but I've been very interested in Wave Function Collapse and genetic algorithms

[@Sean-gx1sf]

Damn, first image is the FTL map; you know your stuff

[@TheShaggyDev]

FTL is one of my favorites! Gotta include it, at least visually, for anything related to proc gen.

[@pokelizardo2298]

Great explination, a nice introdiction to graph rewriting. What would you say are biggest pros and cons of graph rewriting for pcg compared to other techniques?

[@TheShaggyDev]

Glad you liked it! Biggest pro for me is the flexibility it offers, since you can control the generation as tightly as you want and can generate anything from quests to maps to building structures (which I came across but didn't cover in this video). As opposed to generation techniques that are just for grid-based maps or just for X, you could really dive deep into this technique and reuse it in a lot of ways. Biggest con imo is just the complexity involved. A lot of people aren't too familiar with graphs or don't work with them very often, and making good procedural content is hard enough without also having to deal with an unfamiliar data structure. You'd also probably need some custom tooling to make it easy to generate a large number of interesting replacements and rules to use.

[@pokelizardo2298]

@@TheShaggyDev thanks a lot. I am currently working on my bachelor thesis on the usage of graph grammars and graph rewriting and both this video and your video about generative grammars were a godsend. After drowning in research papers it was nice to have a concise and understandable video with all the necessary information. Keep up the good work.

[@TheShaggyDev]

@@pokelizardo2298 That's awesome to hear, thank you! And yeah, I had to read a fair number of papers for this one as well, but I guess I have to choice to skip those that are too boring 😅

[@_mickmccarthy]

Nice! I spent quite some time running through Joris Dormans' papers on graph grammars, could've used these videos around 5 years ago! ;) Keep up the awesome work! Not sure if you've come across it before, but there's a great Zelda dungeon generator project based off his work created by someone called Beck Lavender. Definitely worth checking out if you haven't already. P.S. Haven't yet watched the whole video (but did see Unexplored get a mention!), so apologies if it's already covered!

[@TheShaggyDev]

Oh cool! I had missed this one somehow, thinking Metazelda was the only major Zelda algorithm. Gonna read into it more!

[@deeri638]

How would you store a graph in Godot? Its the multi paths that Im not sure about, a simple tree is just children, but when a node can have multiple connections how would you store that

[@TheShaggyDev]

There's a proposal open to add graphs to Godot (github.com/godotengine/godot-proposals/issues/3848), but otherwise you'd need to make the structure yourself. Khan Academy (and other places) has some discussion on what that might look like: www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

[@deeri638]

@@TheShaggyDev thanks, Ill take a look at the khan academy link. Saw that proposal and was looking at if A* would work, still wrapping my head around how to position everything

[@Aleamanic]

what is that game at 0:39 in the video?

[@TheShaggyDev]

Tile Cities!

[@SpudMackenzie]

Heads up, the metazelda link in the description appears to have died.

[@TheShaggyDev]

Thanks for letting me know! Replaced it with a Wayback Machine link.

[@McHumaty]

7:26 name of this game?

[@TheShaggyDev]

Rogue Fable III !

[@user-rt6zg3wn8q]

2:30 what is the name of this game??

[@TheShaggyDev]

Curse of the Dead Gods. Decent roguelite

[@Nesetalis]

This video feels like the underpants gnomes... "first I have some nodes, then replace nodes by color and connections." "???" level design!" What is the aim of these replacements? Now that you have a random smattering of colored nodes, what are you doing with those nodes to generate rooms? Are edges corridors? Doors? Are hallways a node? And not once do you mention how you might program something. What is the underlying data type, how is it structured, how is memory allocated? What is the processing and memory cost of generating one of these graphs? Implementation detail, even as an example would be nice.

[@G69G71]

hi, do you have discord?

[@TheShaggyDev]

Afraid not at this time, at least for Shaggy Dev related stuff. I may look into setting up a server at some point, though...

[@G69G71]

@@TheShaggyDevok, thx anyways