Friday 4:30 p.m.–5 p.m.

Castle Anthrax: Dungeon Generation Techniques

James King

Audience level:


Come and learn the techniques used for generating random dungeon-like levels for games. You don't have to know what Rogue is to enjoy this talk. Prepare yourself for a plethora of Monty Python references and we'll have some fun.


#Castle Anthrax# ##Introduction## You will learn what a "Rogue-like" is. We will dive into a few sample dungeons in search of the grail (to give you an idea of what various procedurally generated dungeons look like). Be brave, Sir Galahad! ##Data-Structures## We'll start out with some terminology to frame our problem. Then we cover some basic data-structures that are commonly used when generating dungeons and discuss their trade-offs. ##Algorithms## This is where the action happens. We will cover three broad topics in level design and dive right in: ###Maze Generation### Good dungeons have twisting corridors and labyrinthine passages. You will learn depth-first-search and Prim's algorithm. We will discuss the differences in the results they produce and how that can affect the design of the level and gameplay. ###Feature Placement### Mazes aren't really dungeons. A good dungeon has rooms, doors, and pits (and beacons!). We will look at a few examples of some interesting features from other games. And then we will dive into some techniques for generating your own. We'll cover Poisson Noise, cellular automata, and placement techniques such as binary space partitioning for adding unique features to your levels. ###Constraint Solving### Not every dungeon produced by your program is going to be worth playing. Fortunately there are techniques we can employ to hint to the computer when it has produced a dud. This is an entire area of CS research but we will briefly discuss some quick hacks you can use to generate better levels. ##Sir Lancelot, to the Rescue!## You may be tempted to write your level generator from scratch (and you should give it a try some time). However for those in need of rescuing there are libraries in Python to get you started and give you some quick results to experiment with. ##Conclusion and Q&A## Finally we will take a look at a demo of some of the techniques we've seen throughout the talk. And we can open up the floor to a discussion about using procedural techniques in game design, Python tricks and tips, and (hopefully) answer any questions you may have.