Project Bug Hunt #3: The Doors

By Shamus Posted Tuesday Sep 22, 2020

Filed under: Programming 44 comments

A point of order: In the last entry I talked about deforming the walls to give them some interest. In my final example screenshot, I showed an image of hallways that bulged out in the middle. I didn’t make it totally clear how I planned to use this, and as a result some people were left with the impression that my plan was to have bare bulbous walls everywhere.

The bulbous walls were just a minimum-effort demonstration of the idea. My plan is to have the shape of the wall vary by room type. Maybe the corridors will be wide but short, like the ship in Alien. Maybe some walls will be very narrow and tall like in the first level of System Shock 2. Whatever.

There was also the concern that bare walls would get boring, and I should add greebles. I’m currently planning on using the “furniture” idea for this. Something like this image from System Shock 2:

I'm worried these greebles aren't greebly enough, but we'll see.
I'm worried these greebles aren't greebly enough, but we'll see.

If that doesn’t work out, then maybe I’ll back up and try something else. But let’s try this easy thing first.

With that cleared up, let’s talk about…

The Doors

There are things known and things unknown and in between are the doors.

– Jim Morrison

No, not that kind of Doors. I mean doors between rooms.

If you remember from last time, a room is made up of line segments. Each segment is based on the grid. You can grab an arbitrary line and follow it to the next one, and the next one, and it will take you around the room counter-clockwiseLast entry I said clockwise. Wrong. I’ve lost track of the number of times I’ve gotten that mixed up and created a bug. My brain just really WANTS it to be clockwise I guess. until you go all the way around and land back where you started.

Note: If we’re dealing with an interior support pillar, then the lines go around clockwise. That’s not something I programmed, that’s just a natural result of how the system works. In both cases, you can take the direction the line is pointing, turn left, and be pointing directly into the room.

The red arrows point directly away from the walls. They're called surface normals. They're useful in helping me shape the walls, but they're also required for properly rendering and lighting the walls.
The red arrows point directly away from the walls. They're called surface normals. They're useful in helping me shape the walls, but they're also required for properly rendering and lighting the walls.

Internally, I call these lines of wall segments “chains”. So if you’ve got a room with a lone support pillar in the middle, then the room will have two chains. One chain will be the outer wall, and the other chain will be the outside of the pillar.

So now we need to create doors. That’s not as simple as blowing random holes in the walls. To create a door we need to do a lot of checks:

1) Obviously, we’re only looking at the chains that make up the outer walls. There’s nothing to be gained by attempting to put a doorway to access the void space inside a pillar. You’d just fall out of the level.

2) We need to find a straight section of lines that’s at least 3 segments long. The marching squares system we’re using will create walls that can face any of the four cardinal directions, or the four ordinal directions. You can picture a simple “round” room as being shaped like a STOP sign. Any of those eight sides are fine, but we want to avoid putting a door directly touching one of the corners because we’re going to need to blend a door frame object into the level geometry and if we do that at a corner then we’ll get messy intersections and it won’t look right.

In practical terms, to be a viable candidate for a wall, we’re looking for a line segment that’s the same shape as the one directly before it and the one directly after it. The ones in green are valid here:

3) We’re going to assume that the main corridor is how we’ll move from one section of the level to the next. So any side-rooms MUST have access to the main corridor. If rooms A and B only connect to each other, then the player won’t be able to enter them. So we’re going to place doorways from the perspective of the side-rooms. The corridor will not attempt to make any doorways for itself. Instead the rooms will search around their outer walls, looking for a connection to the main corridor, or access to rooms that have corridor access.

4) Once a room finds a straight section of wall, it needs to look on the opposite side of the wall to make sure the wall is also straight on the flip side.

5) Once we’re happy with a spot, we create a door. This door punches holes in the two rooms, enabling one of them to gain corridor access from the other.

We pass over the list of rooms again and again, until everyone gains corridor access or the process halts. If we go all the way through the list of rooms and nothing changes, then we know we’ve created all the doors we can. If we get to the end of this process and discover that we still somehow have rooms with no access, we can just throw them out and leave their assigned space empty.

One final thing we do is to go over all the chains and do a bit of rounding.

Rounding

You’ll notice that point A (Fig.1) is on the edge of two walls that face different directions. For one wall A is the beginning, and for the previous wall A is the end. To allow them to share this point without leaving a crack / distortion in the wall, we average their normals (Fig.2) so that A is midway between both.

That’s a good start, but we can take this a step further if we want to round the walls even more. Let’s take a few lines between the neighbors of A (the green lines in Fig.3) and turn those lines left to get even more normals. Average everything together. If you have many walls facing the same way (such as all of the line segments on the far left of A in Fig.1) then they’ll all face the same direction, which would be south in this case. But as you approach the corner, the points will begin to gradually curve. This allows us to create a wall with gently sloping curves, as in Fig.4. (The amount of curve is exaggerated here for demonstration purposes.)

And here is what the level looks like:

It wasn't until I took this screenshot that I realized the rounding is perhaps TOO subtle. I should turn up the effect and see how it looks.
It wasn't until I took this screenshot that I realized the rounding is perhaps TOO subtle. I should turn up the effect and see how it looks.

Next I guess we’d better add some floors and ceilings so this can start feeling like a proper level.

I Forgot What I was Doing

At this point in the project, I had to set it aside for a couple of weeks to finish up my SWJFO series and do some general blog maintenanceDid anyone notice that I added a few dozen new entries to the “From the Archives” thing at the end of every post? No? To be honest, me neither. It’s fine. Those things are mostly there for newer readers to get them to hang around and see a little more of the site before they wander off.. When I came back, I’d forgotten a lot of fundamental things.

I’m constantly amazed at how quickly you can forget this kind of stuff. I can still remember names, faces, quotable lines, and bits of music from movies I haven’t seen since the 90’s. But the structure of the code I wrote last week? That might as well have been written by someone else.

Like I demonstrated above, the marching squares system will create divisions within a grid square. But when I got back, I was picturing it incorrectly in my head.

Marching squares should divide grid squares through the center.
Marching squares should divide grid squares through the center.

Note how the blue arrows line up with the grid in the right-hand image. I expected straight sections of wall to be aligned like this, and I assumed that I’d just need to do something special to handle the spots where the wall travels diagonally.

To make the floor. I just made a simple square for all parts of the grid that were inside a room. What alarmed me was that all along the walls, I’d see floor tiles from the neighboring room sticking into this one. The two rooms would have different floor textures, and I could see the ghastly z-fighting between them.

Because I’d forgotten what I was doing, I assumed this was a bug.

Oops. Looks like my walls are off the grid by 0.5 and I didn’t notice. No problem. Easy to fix.

Spoiler: This did not fix it.

Um. Oh! I see. One room is reaching into its neighbor. I’ve probably got an off-by-one error somewhere.

No Shamus, there isn’t an off-by-one error.

Uh? What am I doing wrong? Am I making floor tiles too big? Are my walls the wrong size? Do I have a bug in the code I use to look up what rooms occupy which points on the grid?

No, no, and no.

Oh! The floor object itself has probably been nudged off- center within the Unity scene. Happens sometimes when you mis-click. I’ll make sure the objects are all positioned at the world origin.

C’mon dude. I thought you were smarter than this. Stop wasting our time.

I don’t get it. It’s like each room has half a tile that sticks into the next room, as if I needed to chop the tile in half.

You’re getting closer, dummy.

But marching squares… Oh wait.

YEAH. HOW ‘BOUT THOSE MARCHING SQUARES?

This isn’t a bug in the code. This is literally how marching squares work. They cut cells by dividing them in half or taking off a corner. By definition, EVERY tile around the edge of a room is going to need to be a partial tile.

Once I get my head on straight, I stop and write some code specifically to handle those literal edge-cases. When I’m done…

We don't have door FRAMES yet, so around doors we have this gap in the level geometry. It'll be fixed soon.
We don't have door FRAMES yet, so around doors we have this gap in the level geometry. It'll be fixed soon.

You know, that looks kinda cool. It makes the floor a little more interesting to have a border like this. I think I’ll add a feature so that the artist can assign different textures to the edge and the main part of the floor.

Once I have that working, it’s trivial to fill in the rest of the floor and then make the exact same shape for the ceiling. Then while I’m at it, I might as well slap some polygons inside the door frame. We’ll fill in the door properly once we have furniture, but I just want to avoid having a gap where you can see out of the level.

This is taken from the same vantage point as the screenshots in the previous entry. These pillars come from the black dots on the east side of the map. (See the next image if you don't remember.)
This is taken from the same vantage point as the screenshots in the previous entry. These pillars come from the black dots on the east side of the map. (See the next image if you don't remember.)

Okay. We now have a fully enclosed level. My system is working, and the spaces are interesting yet easy to generate from simple input data. The space can be navigated and I’m happy with the shape of things for now.

Left: The hand-drawn 64x64 image that guides the program in building the map. Right: The resulting level layout.
Left: The hand-drawn 64x64 image that guides the program in building the map. Right: The resulting level layout.

We’re miles from being done, but I think this is a really important milestone.

 

Footnotes:

[1] Last entry I said clockwise. Wrong. I’ve lost track of the number of times I’ve gotten that mixed up and created a bug. My brain just really WANTS it to be clockwise I guess.

[2] Did anyone notice that I added a few dozen new entries to the “From the Archives” thing at the end of every post? No? To be honest, me neither. It’s fine. Those things are mostly there for newer readers to get them to hang around and see a little more of the site before they wander off.



From The Archives:
 

44 thoughts on “Project Bug Hunt #3: The Doors

  1. Philadelphus says:

    Wow, that’s starting to look pretty cool, especially the rounded edges. Even if you never got around to randomly generating the initial level image file, being able to generate a level from an image like that would be a pretty useful feature to have.

    1. Echo Tango says:

      Yeah, using images like that would make the job of creating levels very quick and easy, compared to lining up doors, walls, etc. Plus, it’s nice and separated from the rest of the level-generation, so it could totally be done later, as another project / piece of software. :)

  2. Liam says:

    I like it!

    Needs more bloom :)

    Are you using Unity’s URP or HDRP pipelines?

    1. Shamus says:

      Not using HDRP, but I did set up the post-processing filter into the project and sometimes I mess around with different effects.

  3. ShivanHunter says:

    I really like that last screenshot. I dunno what kind of look you’re going for, but “90’s-looking art assets mixed with modern lighting techniques” is a very cool aesthetic, and I haven’t seen many games really try to explore it.

    1. Echo Tango says:

      I’m also shocked more games don’t do that. So much of the last three decades has been bumping up the amount of graphics, when many of the notable improvements have been when someone created new kinds of graphics. (More polygons, higher-res textures, higher-res bump-mapping, more light-sources, higher-res shadows, mirrors, dynamic textures like raindrops…) These all improved games a lot just by being possible, and the higher-res versions all get diminishing returns. :)

    2. tmtvl says:

      For whatever reason it sort of reminds me of PS1 Metal Gear Solid, and I got a tinge of nostalgia when I saw the picture.

  4. RFS-81 says:

    1) Obviously, we’re only looking at the chains that make up the outer walls. There’s nothing to be gained by attempting to put a doorway to access the void space inside a pillar. You’d just fall out of the level.

    I don’t know, could be useful if you want to break on through to the other side.

    Doors-quoting aside, does your program detect that there’s only void in the pillar from the input bitmap, or does it check that the border is inside another border? Because I think it would be cool if it was possible to have a room fully inside another room, like a lab with a containment chamber or something.

    1. Shamus says:

      Room-within-room is totally possible. In fact, it’s kinda already doing that. The corridor is just a really big room, and as far as the corridor is concerned all those rooms inside of it are just a big pillar.

  5. Abnaxis says:

    Real talk: bug hunting like what happened to Shamus with his floor happens to literally everyone who ever coded, right? I don’t even need to take three weeks off to spend the occasional hour puzzling over a “bug” that really only amounts to me forgetting to think through how an algorithm works for the line…

    1. tmtvl says:

      It has happened, which is why Kathleen Booth invented comments.

      1. Abnaxis says:

        No amount of comments solves the issue. Shamus didn’t need comments to explain how marching squares works, he needed to put his brain in “marching squares” mode. Like, you spend an hour forgetting what you were doing, even though you were just freaking doing it.

        1. Retsam says:

          Yeah, a comment doesn’t help because if Shamus remembered to go read the comment about marching squares he wouldn’t need to read the comment about marching squares.

          I’m not sure what the best techniques to help pick back a project after leaving it for weeks – generally this is more the realm of high-level project documentation and maybe a project management system like Trello or JIRA – if you write up meaningfully detailed description of what you intend to do while you still remember the details, it can make it a lot easier to pick up the work later.

          But of course, when those details are fresh in your mind, it feels like pointless busy-work to spend time writing down stuff you already know for you to read later.

        2. Echo Tango says:

          In general, I find that self-documenting code helps more than comments. Like, maybe the code and data-types are structured such that the train of thought would go,
          “Looks like my walls are off the grid by 0.5. Let me find out where those coordinates are coming from…”,
          “Strange. My wall-generating code is transforming MidCubePoints into world coordinates. Where do those come from?”,
          “My marching-cubes code is using both MidCubePoints and MarchingCubeCorners. Oh, right, that’s how this algorithm works…”
          There’s no guarantees in software, but it could save a lot of time debugging if you can just follow the breadcrumb trail to see what type of data you’re working with, and why it acts a certain way. :)

    2. Jeff says:

      As a terrible programmer, I documented the heck out of things back when I had Software Engineering courses.

      Consequently, it was easy to see exactly what I was thinking. It was also easy for my friend (who went on to become a software engineer, while I’m now in finance) to see where I was going wrong.

  6. Lars says:

    From your door placement algoryth discription, I don’t know how you end up with this result. Why aren’t light green and orange on top interconnected, or why is the green room in middle right not connected to the floor via top wall?
    I just try to understand the result and how it came into existence.

    1. Shamus says:

      If I understand the question:

      The door search begins at a random point, and runs around counter-clockwise until it finds corridor access. So the orange room probably connected to the corridor, and then the green one discovered the orange room before the corridor.

      1. Paul Spooner says:

        Oh neat. And the random starting point depends on the level seed probably? So that you could use a different seed for the same bitmap and end up with different door layouts?

        1. Shamus says:

          Correct. I actually have my seed as a value I can edit in Unity, so I can shove the doors around for testing.

      2. Randint says:

        One thing that I notice is that this algorithm will result in a few generation artifacts, specifically that each valid door space essentially has a weight equal to however many invalid door spaces are between it and the next clockwise valid space.

        This seems to have two effects. The first is that spaces to the left of a corner are going to be at least three times as likely to be selected as the typical middle-of-the-wall or right-of-corner spaces. The second is that for rooms on the edge of the map or adjacent to a void, they are vastly more likely to connect to whatever room is counterclockwise of the void. (This can be seen in the northeast corner, where four rooms are chained into each other)

        Additionally, there’s a somewhat noticeable effect that rooms that connect to another room instead of the main hall will always do so in a southward or westward direction – you’ll never find a case where you’re in a room without a direct access to the hall and have to go north or east. I’m assuming that this is because the algorithm starts in the southwest corner and visits each room in order, so a room will never connect to a non-hall room to the north or east because those rooms haven’t been given a chance at receiving a hall connection yet.

        1. Paul Spooner says:

          Good point. The way to avoid this is to find all the valid door locations first, and then choose one randomly.

      3. RFS-81 says:

        If I understand this correctly, the order in which the rooms are processed matters a lot. The very first room has to connect to the corridor directly. The second room may instead be connected to the first room, etc.

        How do you choose the order?

        What do you do when your algorithm gets to a room that needs other rooms to be connected first?

        1. Shamus says:

          The order of processing rooms is the order in which they were discovered, which…

          Hang on, how DOES that work?

          (One quick trip to the codebase later.)

          So the code that reads in the images scans the image left-to-right, top-to-bottom*. As soon as it finds a pixel of a new color, it creates a room for it. Looking at the top of the last image above, the rooms would be added in the order:

          1) The dark mauve in the upper-left.
          2) The cyan in the center top.
          3) The dark blue just right of center.
          4) The yellow in the upper right.
          5) The orange near the top.
          6) The green near the top.
          7) The white corridor.

          It will process the list of rooms in that order. As it goes over the list, it asks each room:

          1) Psst. Hey buddy. Do you have corridor access? No? Okay, give it a shot now.
          2) After the room tries to connect, the program follows up with: Okay, did anything change?

          When it gets to the end of this list, it asks itself two questions:

          1) Are there rooms still lacking connections to the main corridor?
          2) When I passed over the list, did ANY rooms change? (Like, did anyone create a door?)

          If both are true, then it starts the list over. It keeps doing this until all rooms are connected, or until the process hits a dead end.

          * Might be bottom-to-top. Like I said in the post, it’s a coin flip for me.

          1. RFS-81 says:

            I’m trying to imagine how it would change if you randomized the list of rooms. There would be some more variety, but I’m not sure if you’d notice if you didn’t know what to look for. Long chains of rooms would be less likely, unless forced by the level layout.

  7. tmtvl says:

    I see every room only has one door, now I’m curious if you are gonna add a way to let rooms be a bit more interconnected, to avoid the whole “to get to the bedroom from the kitchen you have to go through the bathroom” feel.

    1. Shamus says:

      In my notes I have an idea for a room that will greedily connect to all available rooms. I’ll probably mess with this when I write the code to generate the level layouts.

      1. RFS-81 says:

        Sounds good!

        If you’re going for “realism”, I think most rooms should aim to be connected directly to the main corridor, but that probably makes the layout more boring.

        Maybe you could also have room types that connect to another type if possible. For example, a prison should connect to a guard station, not directly to the main corridor. Probably makes your life a lot harder when you want to generate the high-level layout, though.

        1. pseudonym says:

          Fire regulations require at least two doors per room, or an escape window, right?

          Will there be windows? That would make the project even more interesting to walk around in as well as much more realistic. Maybe with a view on a procedural night city?

      2. DGM says:

        Rooms that ONLY connect to one other room might also be useful for things like bathrooms and closets.

  8. Cyranor says:

    I’ve been taking some coding classes recently and they stress a lot about pre-planning and commenting and psuedo-code etc. Me personally a lot of the planning went on in my head and I didn’t really ever bother with the psuedocode much. However your example of working on this project then taking a break for 3 weeks and forgetting how some of it worked makes me curious on how your coding style works. Do you make a lot of notes or comments as you go or just kind of wing it? Do you have a lot of this planned out or is it just kind of being created as you go? You do a great job of documenting it all in these posts after the fact but I’m curious what it looks like in the moment.

  9. houser2112 says:

    Fig 2 and 3 in the Rounding section are identical, but the text seems to imply they should be different. Am I missing something?

    1. Shamus says:

      Hm. I didn’t even notice the mistake. Fig2 isn’t supposed to have the green lines yet.

  10. Paul Spooner says:

    It looks like the square corners on axis are getting bulged out a little bit. And the square corners at 45 deg are sharpened? I’ve never seen that in architecture, but it might not be a bad idea. Certainly unusual though.

  11. Draklaw says:

    I’m afraid that smoothing the normals might give you weird result with a proper lighting. It will probably be ok if the light sources are near the center of the rooms, but if you try lights near the walls (as often seen in sci-fi settings), I don’t know, particularly for concave turns. Since you seem to go for a low-poly look, why not using sharp edges ?

    Actually, on your last screenshot (the one with real lighting), the light coming from the room stops abruptly on a sharp edge of the pillar. This is likely because Unity consider the left polygons to be in the shadow.

    Also, is your door-piercing algorithm supporting walls that are not vertical ? It seems from your screenshots that the curvature starts right at the top of the door, so I wonder if it’s a limitation.

  12. Scerro says:

    So, since we’re in programming land…

    Have you ever taken a look at Screeps ( https://store.steampowered.com/app/464350/Screeps/ )? It might be worth a series of programming posts, even though it’s all fairly straightforward and aimed at beginner/intermediate programmers. Also, it’s far easier for readers to also engage with you by starting on their own.

    Also, running a private server is a thing, if there was enough interest for it.

    1. Paul Spooner says:

      I played around with Screeps back at the beginning of 2017. It’s a cool idea, but the lack of fast-forward, and the mandatory always-online (related, no doubt) made it too obnoxious for me. I’d love to play around with a stand-alone version, maybe something like Mindustry, but the MMO angle isn’t a draw for me.

      1. Scerro says:

        That’s where private servers come in, and you can actually make your ticks not take forever. I think their server is open-source.

        The beginner zones on the main servers at least give you a good amount of wind-up time to get solid defenses and a foothold. Plus I believe shard 3 is slowly opening up more areas on the edge of the map, which means you have more new players around you. Not for everyone, I’m sure, but so far I haven’t seen much combat. Plus, restarting is no big deal, your codebase (and GCL) is your most valuable thing and those stay if you die or move on purpose.

  13. Jack V says:

    I like that last screenshot!

  14. GoStu says:

    As someone who’s done engineering, estimating, and construction on buildings, I have to say it’s interesting watching a coder come up with this stuff procedurally. I’m finding myself looking at the procedural output and wondering how I’d frame and build it…

    1. tmtvl says:

      That sounds interesting, drop a comment if you decide to blog about it, I’m sure Shamus and the Twenty Sided readers would find it fascinating.

  15. PhoenixUltima says:

    I had an idea while reading this. Since you used a hand-drawn 2D image to drive the level creation, would it be easier to just write code to generate random 2D images to feed to the procgen engine, instead of trying to randomly generate actual 3D spaces?

    I don’t really know anything about either coding or game design, so ignore this if it’s a dumb idea.

    1. tmtvl says:

      That kind of is where Shamus is going with this.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply

Your email address will not be published. Required fields are marked *