This is day one of my quest to re implement the random dungeon generator that was shown as part of the kick starter for TinyKeep. I managed to implement a large portion of the generator today after considering a few alternative strategies for its implementation.

The original algorithm generates a large number of random rectangles without regard for any overlap between them, since in the next phase they are all separated. Forces push each rectangle apart and so out of overlap, and after a few iterations leaving a tightly knit bed of scattered rectangles. An alternative I came up with was to randomly place a small rectangle in a region of space known to be free and then inflate it until it reaches a per-determined size limit.

From this messy list of rectangles, a few are chosen to become large rooms of the dungeon. The exact manner of room selection is still not something I have investigated in the original demo, but in my implementation I merely select the largest of the rooms so far generated. I could also randomly select rectangles until one is found that matches some size threshold, and only then will it be added to the room list.

The next stage is to find out what rooms can be linked together. In the original demo, a link is formed between rooms when it will not intersect any other room in the process. To achieve this myself I needed to program a Ray-Box intersection algorithm. I also know this will come in handy in the Tengu Engine, so it is worth my while choosing a good one to implement. I found one in the front of the book “3D Games, Real Time Rendering and Software Technology” by Alan Watt and it was easy to code up a version from the description he gave.

Also since it was hard enough to find a decent 2D RayBox intersection routine on the web, I present my implementation here:

Each potential link between two rooms is tested for intersection with any other rooms, and those links that have intersections are discarded. Thus I now have a list of random rooms, a bed of non intersecting areas to select from, and an edge list linking all of the rooms without intersection. The only hard task left is to find the minimum spanning tree from these edges, and then to turn that reduced edge list back into corridors.