Gamedev Grievances #30: When Corridors Get Edgy

You know you’re a truly hardened indie game developer when you spend three hours trying to figure out how to stop your roguelite from generating corridors along the edges of rooms – and are hardly surprised it took you that long.

Here’s the deal…

The dungeon generation scripts for Ambience have gone pretty much untouched since I first wrote them nearly a year and a half ago (scary, I know). The general strategy is:

  1. Choose a few centre locations for rooms.
  2. Blow up some rooms at those points.
  3. Connect all the room centres with corridors going vertically, then horizontally from A to B. Simple, but effective.

Except… sometimes the game would try and connect two rooms with a corridor which would run along the edge of another room. This doesn’t sound like much of a problem, and when the player’s standing in the middle of a room, it isn’t.

Version 1. So far, everything looks good…

But, when the player moves to the edge of the room…

Did I say everything looks good? Yeah, scratch that.

“Ahhh! What happened?! Why can’t I see? Why is everything so DARK????”
— The player (probably)

In all seriousness, though, finding yourself suddenly wading through fog in the middle of a large room is more than a bit off-putting. To try and fix this, I experimented a bit with the line of sight algorithms and tried to get the game to fix the problem after the corridors had been dug out, with little success.

So I dusted off the corridor generation script. This script was actually surprisingly simple to begin with: where there’s a wall (or water) tile, dig out a corridor – first vertically, then horizontally.

Version 1 of the passage creation code (vertical corridor part; the horizontal corridor part follows and is analogous).

While this was simple, it wasn’t very smart. It couldn’t tell what it was digging next to – sort of like a prison escapee trying to dig a tunnel to freedom, only to end up going around in circles. So I rolled up my sleeves and got to work answering the question: How do I tell this script not to dig out corridors next to pre-existing rooms?

Checking perpendicular directions

The initial solution seemed easy enough: check the tiles perpendicular to the direction of “digging”. If one or both of these adjacent tiles is a room tile, don’t dig out a new corridor tile, but move on to check the next tile instead.

Version 2 code.

This turned out – well, okayyyy, I guess

Version 2 result.

The script still didn’t know not to dig out corridor tiles at the corners of rooms – hence the isolated corner tiles at the bottom-left and bottom-right. The script also didn’t know not to dig out tiles at the “turning point” of the digging operation, when the direction switched from vertical to horizontal – hence the single-tile bite out of the wall at the bottom.

(You can trace out the original path of the corridor fairly easily on the minimap. Notice how the corridor comes down from the top-left, hits the bottom-left corner, and goes out the bottom-right of the room.)

I fixed the latter problem first, by checking whether there were any adjacent corridor tiles when the digging “turning point” was reached.

Version 3 code.

The result:

Version 3 result.

Hey, nice! We got rid of the isolated single corner tile and the bites out of the room edges all in one go!

The only thing that still bugged me (no pun intended) was the corridors terminating at the corners of the room. While this was passable, it made the dungeon layout a bit too labyrinth-like and not very easy to traverse. So I decided to extend the corner-corridors by a single tile to connect properly with the room.

Making connections

In my first attempt at making the room connections, I checked for no room tiles adjacent to the previous cell that had been dug out (or checked), to determine whether the current cell should be dug out as a corridor tile.

Version 4 code.

This didn’t work out quite as I had hoped, as you can see:

Version 4 result.

Yep, this is the same room as before, believe it or not! The main problem here was that the script refused to dig out the entrances to corridors along the flat faces of the room. This actually made the extended corner connections the only connections between rooms, which was perhaps a little drastic. (Yeah, just a little.)

In my next attempt (round 5), I rearranged the logic a bit and went back to checking the tiles adjacent to the current tile. But I also let it dig out a corridor if the previous tile had exactly one room tile next to it in any direction, including diagonal directions. This would (hopefully) extend the corner corridors as well as dig out the flat-wall entrances.

Version 5 code.
Version 5 result.

The result here was striking: while the upper-left corridor tile had been dug out (and the upper-right one too!), the bottom-right corridor remained stubbornly closed off. (Oh, and the script took another bite out of the wall at the bottom, too. Perhaps it was hungry.)

This was the “a-ha!” moment when I remembered that the corridors were only being dug out in a single direction. In this case, the wall-edge corridor was being dug out from top-left to bottom-left to bottom-right, in that order (remember?) But the script was only checking the current and previous tiles, and not the next tile, to work out if it should dig out the current tile as a corridor (remember that too?)

In short, this meant that the script would always dig out the corner when entering a room, but never when leaving the room.

Looking Both Ways

So for my next trick – er, I mean revision of the script, I made the script look both forwards and backwards to decide whether to dig out a corridor tile. This would ensure that all corner corridors would be dug out successfully.

Version 6 code.
Version 6 result.

Looks much better! The only thing left to do was to get rid of the little “bite” of corridor tiles at the bottom-left corner, and my work was finally done!

The final version of the code.
The final result! (The overall floor layout looks pretty neat as well!)

The Learning Curve

Three hours is a long time to spend on a single problem – certainly long enough to give it the infamous title of “gamedev grievance”. So what did I learn from this ordeal?

  1. Find a systematic way of solving problems. At first I wasted a lot of time “guessing and checking” numbers of adjacent tiles, but when I stepped back and thought about the problem logically and systematically, I found a solution more quickly – and I could explain how and why it worked, making debugging much easier later on.
  2. Remain flexible and open-minded. Sometimes the first approach to solving a problem isn’t the best one, like desperately trying to fix up pre-dug corridors. In fact, the new solution (such as cracking open an old script with the boys) might be totally different to the way you’d “usually” approach such a problem. It’s a good idea to allow for that when debugging and problem-solving.
  3. Draw stuff! Yes, get out a notepad and pen and start drawing combinations of tiles! Think about how your algorithm will respond to any particular scenario you can think of. I found that visualising the room layout and searching for patterns helped me find the solution much more quickly – and even when it didn’t, it gave me new ways of thinking about the problem and new ideas for improving the algorithm.

Be the first to comment

Leave a Reply