Last post described our trivial algorithm for generating multiple rooms in our tile world. We now need to connect them with tunnels so the player has a way to get from one room to another.
For this post I wanted to roughly document the implementation journey, including any errors and faulty attempts, so I took notes (and screenshots) while writing the code. The post was obviously written after everything worked, but I tried to stay true to the real-time notes and not change anything. Let’s see what we ended up with.
We start simple. Let’s first pick a random tile along one of the four walls of a room and place a door there.
Ignore the “height” of the top wall, we’ll deal with that later. Now that we have a way out of each room, we can use our A* algorithm we already have implemented for path finding to connect the rooms together. We’re dealing with a small amount of rooms here so let’s just do a naive N^2 loop and attempt to connect each room to every other room by running A* from door to door.
Ugh, what happened? Looking a bit closer at the code, the problem seems to be that each tunnel is created without knowledge of previous tunnels. We can update the A* grid after each tunnel and set lower weights for the tunnel tiles. This will cause each consecutive A* run to favor previous tunnel tiles over empty tiles when close by.
Better, but not by much. Turns out there was another bug in the first attempt at generating the level. The A* algorithm looks for empty tiles to place down a tunnel on, but we actually had no empty tiles because I was populating the entire tilemap with a transparent tile instead of just leaving a gap. To the A* algorithm this was just another tile that occupied each location.
That was one bug, but observing the screenshot above actually shows a second issue: tunnel tiles are replacing wall tiles. This shouldn’t be happening. The A* algorithm should detect walls as obstacles and avoid them.
Staring at the code long enough proved once again to be useful. We were performing both the room generation and room connections in the same function without updating the tilemap itself between the two operations, but we used the tilemap to check if a tile was empty or not. Easy fix by splitting the function into four parts:
- Generate room
- Populate tilemap
- Connect rooms
- Update tilemap
No more tunnel tiles on top of walls, so at least A* now sees walls as obstacles and that issue is fixed. But, the tunnels still don’t get reused as expected. The idea is for a tunnel tile to have a more favorable weight and be picked over adjacent empty tiles, causing the paths to converge. We were meant to have fixed this earlier when we updated the tilemap after every tunnel, but we never did. We updated the tilemap, but forgot to update the separate A* grid with all the weights. Let’s try again with this fix.
This did something, but not the right thing. It almost looks like each tunnel is trying to avoid other tunnels, since we get those chunky areas with many tunnel tiles next to each other. Maybe I got the weights backwards?
Yup, there we go. I needed to invert the weights for the A* grid nodes to get the correct behavior (i.e. lower is better instead of the other way around). This way the algorithm prefers previous tunnels rather than avoids them and we don’t have a spider web of tunnels anymore.
We have something that looks a bit better now, but it’s a bit awkward when the tunnel goes all the way around the room to reach the door. Let’s see what it looks like if we place a second door on a different wall in each room.
This looks a bit more organic now and we get some interesting shapes. The algorithm just checks connections between each door in each room against every door in every other room. This has two problems. One, it’s not a very fast algorithm. This isn’t necessarily a big issue since we generate the map once and we’re done, but it’s unnecessary. Two, we have the issue of connections not being found, at which point we end up with a door leading nowhere.
There’s one additional complication that we’ve been ignoring. If you zoom in you’ll notice the top wall has a three-tile height due to how the tileset works. This gives the rooms a nice depth but complicates our algorithms a bit. I’ll just get rid of this for now and maybe consider replacing the tileset later.
You may have noticed the last two images show a slightly different room layout compared to previous ones. This is caused by the addition of the second door, which threw off the RNG sequence and influenced the number and shape of rooms. The new layout looks good too, so nothing to worry about. The idea is for the majority of results to look good, otherwise we’re doing something wrong.
Let’s try to optimize the code a bit now. Instead of doing four searches for each room pair trying to connect all doors, we can perform a single search between the room centers.
This gives pretty good results. Not too different from the previous algorithm while being much faster.
You can see how the A* algorithm traces the tunnels through the rooms. We can fix this by updating the tilemap and put the floor tiles back on top of the tunnel tiles. Since we’re doing another pass over the tilemap, we will also take this opportunity to replace any unused doors with the tile for the wall to get rid of doors going nowhere.
We now have a clean looking dungeon with tunnels between the rooms. It’s pretty basic and still somewhat boring, but it’s a good start. If we run a couple of generations we can see what a few different variations look like.
