I have developed a small demo that generates random dungeons, from minimum spanning trees, that I plan to use in an upcoming game. It'd be a waste to keep it all to my self so I've provided a small demo attached below and released the source code on GitHub (
https://github.com/redsled84/mstdungeon/tree/v0.1). A minimum spanning tree is somewhat of an advanced data structure to produce. If you don't know what it is, simply put, it's a tree whose summed edges have the least amount of weight in a given graph. I implemented Kruskal's algorithm, and the dependent data structure the algorithm uses, disjoint-sets (aka union-find). I generate rooms by repeating the placement of a room until the area it occupies is not occupied by any other room. Generate the graph with Yonaba's Delaunay from each room's center point, spit out the MST with the help of Kruskal, get the paired rooms from the MST, and run Yonaba's Jumper pathfinder (A*) to generate the corridors. Doors are also generated from these corridors and rooms. The method I have developed is inspired from the Procedural Dungeon Generation article published by the developer of TinyKeep (Google it). I don't have a demo that you can run around in because I'm still developing the generation algorithm itself, but I've reached a point where it's simply too cool to not share with fellow LÖVE users. There are options (GUI made with SUIT) you can play around with, however they will cause major FPS drops if the values become too high (dependent on your computer). Feel free to ask any questions and I'll be happy to answer them
. Also, please share any tips or recommendations you might have. Thanks!
P.S. if you want an implementation without all the tile coloring and just the rooms, corridors, and doors, I'd be happy to provide you with one (PM me)!
- Only dungeon displayed
- Screenshot from 2016-07-26 17-41-18.png (103.78 KiB) Viewed 2897 times
The gradient looking thingy at the bottom of each corridor and room is something I whipped up to make them look like they're protruding from an abyss.
- Options displayed
- Screenshot from 2016-07-26 17-41-58.png (116.77 KiB) Viewed 2897 times
