More dungeon layout experiments

After my simulated annealing experiment, I had a few more ideas for dungeon level generation.

Fake force-directed graph layout

Force-directed graph layout is a neat way to layout graphs in a way that looks nice when rendered. Here are some very nifty realtime implementations in Javascript:

d3
https://github.com/mbostock/d3/wiki/Force-Layout.

Springy
http://getspringy.com/demo.html

These types of layout algorithms work by treating the nodes of the graph as charged particles which repel each other, and the edges as springs connecting them. The spring forces oppose the repulsive forces. The algorithm is essentially a two-dimensional physical simulation. After the forces reach equilibrium, or after some number of iterations, the nodes and edges naturally tend to be laid out in a visually pleasing way.

I tried a similar technique for generating and laying out out a dungeon map. I start by generating a random tree of a limited depth. Next, I assign a randomly sized rectangle to each tree node. The rectangles are spread out in 2D space in a way that guarantees they will not overlap (using a simple minimum bounding box).

Now, the edges of the tree which connect the rectangles are treated like springs. Unlike in the graph layout algorithm, there are no repulsive forces between the rooms. I wanted them all to glob together under the forces of the springs.

Rather than implementing a full physics simulator, I just created a cheap hack which translates each rectangle towards its parent in the tree until there is a collision. The algorithm iterates until it reaches logjam.

The results are not too bad, but it tends to result in large disconnected sections. I also construct a search tree at the end to find the connected rooms.

In the process, I knocked together some Python classes for representing and rendering 2D geometry, including a 2D vector, rectangle, minimum bounding box, grid-based collision detection, and a general purpose tree. I'm sure there are plenty of better implementations out there already, but it was fun.

Roomspray

After finishing the force-directed implementation, I had a simpler idea based on the initial layout step. The initial layout step used an expanding minimum bounding box to spread out rooms in a disconnected way.

Instead, I wanted a way to track exactly where the edges of the current rooms were, and connect new rooms directly onto the existing rooms.

Since I already had vectors, rectangles, collision detection etc from the force-directed layout algorithm, I just needed an efficient data structure for keeping track of the edges of the current map.

I decided to use a list of vectors sorted by angle, pointing from the origin at empty spaces on the grid adjacent to existing rooms. Rooms are added sequentially at random vectors. Each time a room is added, the vector list is updated to reflect the boundaries including the new room.

I like this method because it's simple, and I think it could be easily modified to generate effectively infinite maps procedurally "just in time" as a player explores the map by shifting the origin to follow the player.

In implementing this I learned that Python doesn't have an efficient sorted list implementation built in. It does have a package for binary searching a sorted list, which is fine for looking up entries in a static list. However, inserting and deleting at an arbitrary index in a Python list has O(n) performance according to the documentation.

Generally a sorted list is backed by a balanced binary tree for O(log(n)) performance for inserts, deletes etc. I used the blist package for this.