{"id":50737,"date":"2020-09-15T06:00:42","date_gmt":"2020-09-15T10:00:42","guid":{"rendered":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=50737"},"modified":"2020-09-15T06:21:16","modified_gmt":"2020-09-15T10:21:16","slug":"project-bug-hunt-2-lets-build-some-walls","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=50737","title":{"rendered":"Project Bug Hunt #2: Let’s Build Some Walls"},"content":{"rendered":"

To recap: The goal of this project is to generate something like an immersive sim<\/a> shooter level. This means designing a level, building the rooms, and “furnishing” those rooms. I don’t know what furniture we’re going to use and to a certain extent it doesn’t matter. We just need to prove that we could fill the rooms with whatever the game calls for, and the furniture needs to be placed in a way that makes sense. <\/p>\n

The Star Trek Enterprise might have a Captain’s chair, beds, a warp core, and an ice cream machineOh, you’ve never seen the Trek Ice Cream machine? Watch the episode where someone uses the toilet. The ice cream is right next door to that.<\/span>, but we shouldn’t see them all next to each other. A fridge doesn’t make sense in the middle of the room and the captain’s chair doesn’t make sense in the corner. My program needs to be able make this logic work without resorting to premade room layouts.<\/p>\n

In addition, we need lighting that works within some reasonable performance constraints. The world needs coherent collision detection so the player doesn’t fall out of the level or get stuck on invisible walls. It needs to be possible for an AI to navigate the space, even if we don’t add proper shooter combat mechanics or proper enemy AI. <\/p>\n

<\/p>\n

Marching Squares<\/h3>\n

So I want to create a procgen shooter level, but I want to keep code complexity to a minimum. This means I have slightly contradictory goals. <\/p>\n

The most obvious and direct way to do this would be to make my levels out of giant cubes on a grid, like in Wolfenstein 3D. That would indeed keep the complexity way down, but that would make for some catastrophically boring levels. <\/p>\n

My plan to sort this out is to use Marching Squares<\/a>. According to Wikipedia: <\/p>\n

“Marching squares is a computer graphics algorithm that generates contours for a two-dimensional scalar field (rectangular array of individual numerical values). A similar method can be used to contour 2D triangle meshes.”<\/p><\/blockquote>\n

I actually explained marching squares back in 2012<\/a>:<\/p>\n

I messed up this image when I originally made it. In the final two diagrams, there should be one more little triangle at the very top, just left of center.<\/div>
I messed up this image when I originally made it. In the final two diagrams, there should be one more little triangle at the very top, just left of center.<\/div><\/p>\n

Basically, you fill in a grid with on \/ off values. An on<\/b> value would be “inside a room” and an off value would be “void space between rooms”. Marching Square logic then fills in walls between the two, creating an enclosed space. It’s more complex than grid-based levels and it gives you beveled corners rather than sharp angles. It’s a little more complex than grids, but far more interesting to look at. I don’t know if this is the correct way to go, but it seems like a good place to start in terms of code complexity vs. visual interesting-ness..<\/p>\n

If the 2D layouts are still too boring, there’s always the possibility that we could stack sections on top of each other and connect them with lifts \/ ramps \/ staircases. The logic would still be 2D (and thus low in complexity) but we’d have some vertical motion for the player.<\/p>\n

And if none of that works out, we could always dump Marching Squares and try (say) Marching Cubes<\/a>. I’ve done both<\/a> in the past and I still remember how they work, so implementation should be easy. I can do either, but we might as well start with the easy one first.<\/p>\n

Top-Down, or Bottom-Up?<\/h3>\n

In the end, we’re (hopefully) going to have code that will cut the level into sections, sections that cut themselves into corridors and rooms, and rooms that fill themselves with furniture.<\/p>\n

It seems like you’d want to start at one end or the other. Maybe we start at the bottom and get the furniture code working, then create a room to contain the furniture, then make a section made of multiple rooms, then several such sections to make a level. Or maybe we should start at the other end and work our way down to furniture.<\/p>\n

While it seems counter-intuitive, I kinda want to start in the middle. I want to focus on building rooms, since that’s where the Marching Squares stuff is going to happen. I want to get that system working, or discard it early if it doesn’t work out. I might need to iterate on it a bit, and that will be easier if it’s not tied to a bunch of other systems yet.<\/p>\n

But if rooms come from levels, then how can I generate rooms without generating the level first?<\/p>\n

Well, I’m going to cheat. I’m going to use a hand-made 64×64 png for my map. Something like this:<\/p>\n

<\/p>\n

Okay, that’s annoyingly small and probably impossible to see on a mobile device. Here’s a larger version:<\/p>\n

<\/p>\n

Black is void space, white is a corridor, and any other color is a room. So for now my “level editor” is a simple image editor. Someday layouts will come from code, but for now we have this. This has the added benefit of allowing me to create controlled tests. If I notice that (say) the north-facing walls in rooms are missing, then I’d be stuck wondering if it was a problem with the level generator, the room generator, or the code that turns those shapes into polygons. But here I can test the room code while knowing exactly what the level is “supposed” to look like.<\/p>\n

There’s a lot to say about getting this project set up and laying the foundation, but I’m in a hurry to get to the bits where I can start showing you screenshots. Once I have something to show, we can backtrack and talk about the finer points. I don’t want to spend three entries on theory before we draw our first polygon.<\/p>\n

So here is the first map, along with the image that was used to generate it.<\/p>\n

Left: My hand-made 64x64 pixel data. Right: The resulting level layout.<\/div>
Left: My hand-made 64x64 pixel data. Right: The resulting level layout.<\/div><\/p>\n

I’m cheating a bit here in order to show you this map. I didn’t add the feature to draw the layout like this until much later in the project, but I’m using it here because it makes all of this easier to follow. I really regret not adding it sooner. At the time I thought “Bah. I don’t need a map. That’s a fancy luxury feature. I don’t want to get distracted twiddling with novelty features rather than doing Real Work™!” That mindset was a mistake. Getting the basics working was a fiddly job, and I did the whole thing blind. When something went wrong, I had to figure it out by looking at lists of numbers and calculating in my head what things “should” look like. If I’d had the map available, I could have glanced at it to see what the program was TRYING to build, which would give me a lot of clues about where the process was breaking down.<\/p>\n

Anyway, let’s switch back to the present tense so we can resume the pretense that I’m telling you about this stuff as I do it.<\/p>\n

But How Does it Work?<\/h3>\n

For this image, the camera is positioned in the North-East corner of the space. Those soda-can shapes on the left are pillars. Those come from the vertical line of black dots in the source image.<\/div>
For this image, the camera is positioned in the North-East corner of the space. Those soda-can shapes on the left are pillars. Those come from the vertical line of black dots in the source image.<\/div><\/p>\n

The program passes over this little image and looks at the pixels. “Okay, this blue pixel belongs to room #3, this white belongs to the corridor, this green pixel is room #12, etc.” When I’m done, I have a grid of room assignment numbers. Since 1 pixel = 1 meter, this grid represents 64×64 meters of game space. <\/p>\n

Earlier I said that Marching Squares uses points that are on\/off. I’m doing a bit of a variation on that here. I pass over the grid for Room #1. All points that belong to #1 are “on”, and any points that don’t are “off”. I use these on\/off points to generate line segments, and I give those line segments to the room-building code. I pass over the grid once for each room, creating the 1D line segments that will (eventually) become the walls.<\/p>\n

The trick here is that I’m passing over the grid left-to-right, top-to-bottom, because that’s the easiest way to traverse a grid. But the RoomBuilder code doesn’t care about the grid. It wants the line segments ordered so that it can trace around the perimeter of the room. All rooms will inevitably form closed loops. <\/p>\n

So I have the room builder code sort the line segments to put them in order, so that running through the list will take you around the perimeter of the room clockwise. <\/p>\n

When it’s done, I can look at which way the lines face and use that to find the angle looking into the room, perpendicular to the wall.<\/p>\n

Okay. Now if this was a C++ project I’d need to stop here and spend the next two days hammering together shaders, a lighting system, and shadow casting code. But this is Unity and someone else did all that work for me. So let me slap down a huge plane so we have something to stand on, put a texture on the walls, and then turn on the lighting system and see what we get.<\/p>\n

Maybe someone could have used a larger texture here? Don't worry, I've already sent an angry note to the art team about it.<\/div>
Maybe someone could have used a larger texture here? Don't worry, I've already sent an angry note to the art team about it.<\/div><\/p>\n

No doubt you’re about to demand to know when you can pre-order this magnificent thing. But before you begin throwing money at your screen, I should warn you that the rooms are fully enclosed so we can’t travel between them. There’s no ceiling, the light comes from nowhere, and it would be physically impossible to make the texture mapping more boring.<\/p>\n

Extruding<\/h3>\n

Making the level entirely out of extruded 2D shapes would probably get way too boring. I mean, what we’re building right now is basically the original Doom, but without elevation changes. As it is now, the floor will always be perfectly flat and the walls will always be perfectly vertical. We need a little interest somewhere<\/b>, but I don’t want to make anything too complicated just yet.<\/p>\n

My plan here is to add the ability to shape walls. We can give the walls a set of 2D points that would act as a profile, controlling the depth of the walls. Essentially, we’re extruding up out of the floor to make walls, but then extruding outward from the walls to get… slightly more lumpy walls?<\/p>\n

As things are now, all walls are infinitely thin. We don’t have doors yet, but if we did and you stood in a doorway, you could position yourself so that you were looking at the wall edge-on and see that it has zero thickness. We can fix this by pushing the polygons away from the wall. If I pull this wall outward by (say) 0.2m, and the adjacent room does the same, then we’ll have created a gap between the rooms that’s 0.4m thick. Now if we change that thickness as we go up the wall, then it will (hopefully) give the wall an interesting shape.<\/p>\n

Like I said, we do this using coordinate pairs to define height and thickness. A number pair like 0.2, 0.0 says that “at the bottom of the wall (0.0 height), make the wall 0.2m thick.” The coord 0.5, 2.0 would say “At two meters off the ground, the wall is 0.5m thick”. And so on. So I’m going to make the wall bulge outward at 2m off the ground, and then get thin again.<\/p>\n

Also, the art team has finally gotten around to adding a proper texture to the walls. (You know how those people are.) The result looks like this:<\/p>\n

Better than a poke in the eye, I guess.<\/div>
Better than a poke in the eye, I guess.<\/div><\/p>\n

Eventually this wall shape will come from a settings file, but for now It’s all hard-coded.<\/p>\n

I know it’s hard to get a sense of scale without recognizable objects in the scene. If it helps, the walls are 3 meters tall.<\/p>\n

I’m not sure what you’d properly call this type of shaping. Like a lathe maybe?<\/p>\n

In any case, I’m not sure if this is going to be interesting enough, but we’re going to experiment with it and see how it turns out.<\/p>\n","protected":false},"excerpt":{"rendered":"

To recap: The goal of this project is to generate something like an immersive sim shooter level. This means designing a level, building the rooms, and “furnishing” those rooms. I don’t know what furniture we’re going to use and to a certain extent it doesn’t matter. We just need to prove that we could fill […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-50737","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/50737","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=50737"}],"version-history":[{"count":15,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/50737\/revisions"}],"predecessor-version":[{"id":50752,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/50737\/revisions\/50752"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=50737"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=50737"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=50737"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}