MUD procedural generation: drawing the walls

This is the second post in a series on procedural generation for a MUD, which is a text-only MMO, or a multiplayer Zork. The eventual goal is to create a large, varied MUD containing multiple cities, towns, and wilderness biomes, and a wide array of NPCs and items, as the basis for more personalized and customized work.

Last time, we spoke about placing towers for the city walls. Let’s create the walls themselves.

I tried several strategies for creating the walls.

The first strategy was to start at one tower and dig to the adjacent room that was closest to the next tower. That didn’t quite go the way I wanted:

(The red dots are rooms; the black lines are where the walls should be.)

I wanted the walls to travel in close approximations of straight lines. Here, we get a row of ordinally connected rooms followed by a row of cardinally directed rooms, producing a large “ear”.

The next strategy was to find an unvisited neighbor to the most recently added wall, and, of those neighbors, take the one that is closest to the line between the two towers. This also didn’t work and got stuck in an infinite loop.

The third strategy was to follow the line, stopping at every half-room step, and rounding coordinates. If there wasn’t yet a room there, we dug out a room and connected it to the previous one.

This was better, but still not great. For instance, a wall would often end up going south, then east, making a hard corner, when it could have gone southeast instead.

Let’s take a step back. In our first strategy, we had a bunch of ordinal links and a bunch of cardinal ones, and that was the shortest path. However, it wasn’t the closest path. Since we’re using effectively a variation of Manhattan movement on a perfect grid, we know that we can rearrange links and get to the same destination in the same number of moves. If we shuffle them so that the ordinals occur at even intervals among the cardinals and vice versa, we’re done.

The victorious solution, then, looks like this:

It’s not quite ideal — you’ll notice that the top wall is straight for most of its length, then juts upward. Overall, though, this is quite acceptable.

The algorithm is pretty straightforward; the main wrinkle is that we’re using floating point math. Floating point credit calculations mean that your accumulator might be ever so slightly off from 1, so you need to check whether the minor direction credits are at least, say, 0.99999 instead of at least 1. If you have access to rational numbers, you should use them here.

Leave a Reply