Graph-Based Dungeon Generator

Hacker News

Share card

Graph-Based Dungeon Generator

Hey HN! I've been working on procedural generation for some time now, and more precisely on procedurally-generated dungeons. I had already explored the basic implementations using binary-space partitioning for example (see https://github.com/halftheopposite/dungeon ), but the results were usually quite primitive and required a lot of post-processing to make the dungeons realistic and playable. This led me to look at alternatives and one of them were graphs. Basing your generator on graphs makes it possible to easily define constraints and to add new rules over time. Finding existing material on the topic is hard, and most existing documentations are either PhD thesis, long white papers, or copy-cats of the same articles and implementations. Luckily, a few person out there have done fabulous work at documenting existing methods and video games analysis such as: - BorisTheBrave ( https://www.boristhebrave.com ) - Watabou ( https://twitter.com/watawatabou ) - Oskar Stålberg ( https://twitter.com/OskSta ) If you have existing documentation I'd love to have as many links as possible! The core challenge to generating a dungeon is placing rooms and corridors given the constraints you define. For example: if you have a node "A" that have two children nodes "A-1" and "A-2", you need to be able to backtrack if one of the two children cannot be placed no matter the number of reties you define. The easiest approach to this is using a breadth-first tree traversal and a queue of treated rooms. However, my current generator has some limitations such as the impossibility to generate circular sections (ex: A → B → C → A) that would make the player's experience much more challenging. I will try to iterate on this in the coming weeks, but any help on the topic would be very welcomed! Anyway, I hope that you enjoy using the generator, looking at the code, giving feedback, creating your game, or whatever you intend to do with it and that this contribution will help others that have trouble kickstarting their own!