2D walled map generation

Question

I want to make a 2D walled map. the walls must be L,T,+,-,| shaped. (made from vertical and horizontal lines) There must not be a complete closed block (i.e. all parts of the map must be connected). Also the map is actually not tile based. All the data I should generate for the map must be in form of x1,y1,x2,y2. which indicates start and endpoint of a horizontal or vertical line.

One idea was using a DFS maze generation algorithm on different parts of my map in order to get a non-perfect maze that has a lot of entrances and exits. But I think it is not a very good solution. Can Anyone help me to get a working algorithm that results wall in forms of x1,y1,x2,y2 of a horizontal or vertical line start and endpoints.

I think I could say it is a pacman like map but it is not tile based.

For example see this picture:

I drew this with paint and is not a perfect map but I want some algorithm that generates a better looking map like this. this map don't have any closed block.

I should say that I don't really need any graphics. I just need an algorithm that generate start and endpoint x,y of a line.

Answer 1

I'd solve this using a disjoint-set data structure. This lets you group walls into clusters.

Start with one cluster, consisting of the 4 border walls of your map.

Now, take turns choosing a random place to put a wall of random size & orientation. (You could also randomly place T, L, or + corners, or just let those emerge organically from placing walls)

Before you place the new wall(s), check to see what other walls the new structure would touch (a spatial partition data structure can help you accelerate this check if you have hundreds of walls or more, but for a few dozen a brute force check is probably fine). You might want to add some range tolerance to this check, so walls that pass so close that nothing can fit between them still count as touching.

Now we have a set of walls that we would connect together if we placed this new wall structure. Here's where we use the clustering technique: check whether any two of these walls are already from the same cluster. If so, they're already connected somewhere else, and making a new connection here will create a closed loop. This disqualifies our candidate wall placement, so we try again with a new random choice of placement/size/shape.

If all of the walls we're touching are from different clusters (including the case where we're not touching anything at all), then we can proceed to place this new wall structure, and merge all the clusters we're touching into one (including making a new cluster for the new walls if they're not touching any existing ones).

This guarantees you never create a closed loop of walls.

Answer 2

You can use a modified recursive division maze algorithm. The regular algorithm works like this:

1. Begin with an (empty) rectangular area.
2. Bisect the area randomly with a horizontally or vertical wall. Note this generates two new rectangular sub areas.
3. Cut a door in the wall at a random location.
4. If they are big enough, repeat the process on each of the sub areas generated in step 2.

Side note: while this algorithm is typically described recursively, it can be implemented with a regular loop & a dynamically sized list. Also, while this algorithm is typically applied to cells, you can just as easily apply it to decimal coords.

As for the modifications, you need to make the following changes:

1. When a vertical wall meets a horizontal wall (or vice versa) check it to see if there are any other walls on that same side. If so, then cut the new wall so that it is an acceptable distance from the existing wall.
2. Apply modification 1 whenever a new wall would meet the outside perimeter.