AVWW Interior Generator (Technical Overview)

I'll have a full developer diary #11 (no video this week, though) posted in the next day or so.  However, first I want to talk about interior floorplan generation.  This is something that I'm going to release as an open source example program in a month or two, once it's fully polished.

This past week has been both the most productive and the most mind-numbing that I can remember in a long time, for me.  That's a really odd combination, no?  Well, there's a reason that I've been putting off the interior floorplans work for A Valley Without Wind since March.




Discarding The Map-With-Variances Approach
Initially I had thought I would do a map-with-variances approach for interior floorplans, basically a similar version to what we are doing for external overworld chunks.  The problem is, while outside wilderness areas are nice and blobby and organic and lend themselves well to that sort of approach, interior floorplans really don't.  The first time somebody sees the bathroom opening directly into the kitchen, or finds a conference room that can only be accessed by passing through a small storage closet, the jig is up.

Then there's the problem that I have to model building interiors based on exteriors that are pre-rendered.  What I mean is, the vague shape of a building (ignoring windows) needs to be the same as the outer shape you're seeing in the overworld chunks.  If the exterior walls are angled in the pre-rendered image for outside, they have to be angled inside, too.  If the door is in the front center of the building, then it has to be there on the inside, too.  If your building is rectangular or square, tall or short, and on and on.  And that's before you get into function, even -- houses look one way inside, office buildings another, etc.

We've only got maybe three dozen building graphics so far, and lots more are planned, but already we have a staggering number of combinations of shapes, which was going to make that map-with-variances approach an incredibly intensive amount of content generation, as well as profoundly disappointing to players that expect something procedural.  Externally, our map-with-variances approach works so well because it augments the procedural generation techniques, providing more variance through complex human-created inputs than a pure-procedural approach is likely to make.  Internally, the variances would be too small because of the need to make the whole structure make some sort of human-constructed sense.

Examining Existing Fully-Procedural Approaches
So my next thought was to just go fully procedural for the interior of the buildings, after all.  I started cooking up some ideas for how to do this, and then decided to do some research.  And that quickly shot holes in pretty well all of my ideas.  Turns out that this has been a much-studied problem, and there is even one guy who did his masters thesis on how to model 3d house interiors -- just houses, not any other kind of building.  There were some other scholarly papers on other forms of building interiors, but most of those were behind paywalls and were likely to be full of examples in math, not code.  I think in code, not math.

This was mostly stuff for 3D models, though, anyway -- much more complex than I wanted.  I turned instead to roguelikes, which are a very well-understood form of interior generation, with a lot of different kind of algorithms.  Last fall I got into procedural maze-generation algorithms for some of the latest AI War map types, and these roguelike algorithms were only somewhat more complex on the whole.

The problem is that the maps they create are full of holes.  If you've ever seen a roguelike, you know what I mean: most dungeons have a room, with some hallways off of it connecting to other rooms, and all of this is floating in this big, empty blackness.  The overall extents of the rouguelike dungeons tend to be unpredictable, there's all sorts of non-accounted-for holes all throughout the map, and it definitely doesn't conform to any sort of exterior building shape.

Perhaps the simplest example of these approaches was one by Jason LaPier.  Here's his Javascript example that you can play with in your browser, and here's his blog post about it.  I was attracted to his approach because it was very simple and was able to take in human-created data points in the form of room shapes, which would allow for a lot of flexibility even after the initial algorithm was complete.  However, it still suffered from all the drawbacks (for my purposes) of any roguelike algorithm, in that it created a roguelike-looking dungeon.  Which wasn't my goal.

Setting: Creating Unique Architecture
Before I continue on with my technical explanation, there's something else that I'd like to note: namely, that as I was looking at all these methods for making both fantastical and realistic building interiors, I realized how much more interesting the fantastical ones were.  Houses and offices are actually kind of boring buildings, when you get right down to it.

That's why you see games like Left 4 Dead having all sorts of passages blocked off and destroyed, and parts of the buildings collapsed, etc.  Normally most buildings are meant to be as easily-traversal and non-maze-like as possible, for the sake of usability.  We want people who enter an office building to be able to get from point A to point B as quickly and simply as possible, in the real world.  In the game world, it's far more interesting for players if the path from point A to point B is as convoluted and challenging as possible (well, within reason).

This is something I'd run into in the exterior areas, too.  Normally, in real life, when you're in a big field of grass or in the woods... you can just pretty much walk any way you want.  Sometimes there are bushes, but you can go through them if you really want to.  And going around is rarely far.  Most of a grassy field is going to be hugely boring to you, because it's all just the same grass, essentially.  What made the exteriors in AVWW suddenly take on a life of their own is when I started to diverge from reality -- making lots of little streams, lots of chasms, and various other obstacles to get in your way.

Suddenly the exteriors felt mildly to majorly maze-like (depending on the area), and were a lot more fun and interesting to explore even without having more interesting points of interest yet.  That was a really key thing for me to learn.  And if you look at something like Minecraft, you can also see how effective the terrain-generation is there, too, even with very few types of terrain.  This is also something that really adds to the attraction of roguelikes, I think -- because their dungeons are very abstract and unrealistic, they are also very maze-like and excitingly unpredictable.  They feel like somewhere you'd be chasing after dwarves or orcs, not like someplace you'd be doing your taxes.

With all this running through my mind, the choice was easy -- this game needs to take a more fantastical turn when it comes to interiors.  Instead of trying to model real house floorplans, let's model house interiors that are as interesting and crazy as possible.  Floorplans that have all the parts you'd expect -- kitchens, bedrooms, bathrooms, etc -- but which are built to be intentionally game-like and thus maze-like.

A lot of games that are trying for realism just use the aformentioned techniques of building damage and rubble to accomplish the same effect, but to me that just wouldn't provide enough procedural variance.  Players can tell when the floorplans are boring but rubble is just moving around.  Of course it's still my upcoming of challenge to actually populate the buildings with interesting things, but right from the floorplans on up I wanted to have buildings that felt unique, unpredictable, and excitingly foreign.  Like a roguelike, then, but without all that soupy blackness between rooms and halls.

Crafting My Own Approach
The things I really liked about LaPier's roguelike example was how he defined his room templates as char arrays that were easily human modifiable, and how he randomly mixed them up on a row-by-row basis to create random variances.  Since he graciously released his Javascript code under the MIT license, I decided to start with those pieces as a core for my work, and go from there.  Instead of doing halls and such in his fashion, I'd do something of my own.

The other challenge that I was going to have was that we use a faux-3D perspective in AVWW that is identical to most SNES RPGs but very divorced from anything roguelikes are doing.  As with most maze-generation algorithms, they assume a flat grid and walls that take up exactly one tile each on the grid

What I had to do was somehow implement walls that had perspective, which meant that side walls would be one wide while top and bottom walls would be three high at minimum, but preferably not more than three high without converting into side walls or a big ceiling block above a certain point.  What a challenge!

This was the other reason that I really liked LaPier's approach: I could build those elements of faux perspective into the room templates themselves, which would give me a good start on having a correct map once they were seeded in.  Then I'd just have to figure out a new way to add doors and hallways, to make sure everything was connected, and to correct all of the literally hundreds or thousands of perspective errors that were likely to result from just plopping everything together in this fashion.

So that's what I sat down to do, a week ago.

The Process
This is the process that the interior generator goes through, in sequence:

1. The type of floorplan is based on an enum, and the size of the overall floorplan in width and height is encoded into the enum name for the sake of brevity.  Note that these sizes are inflated compared to the actual size that the building appears to be on the outside -- common to most RPG games.  That gives us much more interesting interiors, and exteriors that we can actually see the whole of.

2. A random seed is passed to the FillMap method, along with the InteriorGenerationStyle enum.   Given those same two inputs, and the same desired floor (Z Index), the result will always give you the same map, which is helpful.

3. The first mapgen step is to set all of the InteriorGenerationStyle-related variables, which includes defining the broad profile of the building's outer walls to match the exterior.  This also places the exterior doors or ladders.  For side doors, since you can't see those in the exterior graphics in the game, those can be placed at any Y offset along each wall.

4. There are a couple of different room templates that I have defined in a similar style to what LaPier was doing.  Which are used varies by InteriorGenerationStyle as well, and I have four different possible definition types.  W is "provisional wall," C is "provisional blocking ceiling," b is "provisional non-blocking ceiling," period is "generic floor," and blank space is "hallway."  At this stage in the process, that's all we need.  I'm not defining room types, and I'm also not defining possible door-points.

5. For buildings that have more than one floor, it decides how many floors they will have between min/max values for both the upper and lower bounds.  It then clamps the requested floor to the actual floor bounds -- so if you request floor 0 and the max floor is -1, you get floor -1 as your topmost floor (so, this would be an underground building, like the ice age hatch).

6. Now we actually cut staircases between the floors.  Starting at Clamp(0) floor, it starts deciding where to place floors, and then it recursively moves toward the floor you actually requested, collision-detecting and stripping out two-floors-away staircases as it goes.  The result is that you wind up with staircases that are always lined up perfectly and never sitting on top of one another.  Beyond that it's a little hard to explain, so I'll leave the code to speak for itself on how exactly I made that work, when the code is released.

7. Now that we have the outer shape of the building in place, the doors or ladders to the outside, and the interior staircases, it's time to actually start filling in walls and rooms and hallways.  To do this, I use LaPier's method with a few modifications: I don't intentionally leave space between each room, and when there is leftover space I distribute it completely randomly in the X and Y bounds of each row.  I also randomize the list of rooms per row after all of them have been picked, so that there isn't a trend of having smaller rooms to the right of the building.

8.  Step #7 happens in isolation, in a completely different code structure from the actual building I've been building so far.  What I wind up with is an identically-sized LaPier-method overlay of rooms with no external shaping that I can plop down on the staircases, the doors, and the exterior walls that I've defined so far in steps 1-6.  During this step, I never overwrite the actual existing building structure that we've defined in those first six steps.  The staircases, the doors, and the exterior walls cause all sorts of disruptions to the LaPier-style rooms, and that's completely okay as that actually adds substantially to the variance once we combine the two.

9. Now I'm done with the LaPier method, and I have a perfect external shape, random staircases, doors to the outside, and some pretty interesting rooms layered about -- and filler hallways naturally develop based on how I designed the LaPier room templates, too. However, there are no internal doors between any of the rooms or hallways, and all sorts of things are inacessible and invalid.  The perspective of the walls is munged up in many places, because the various room templates haven't been blended together, they've just been set next to one another.  When working with rooms with perspective, that's deadly to the realism.

9.a. From here on out, we enter a master method called CleanUpInteriors, which is what I spent the bulk of this past week creating.  It has 22 steps that it goes through with the "provisional" walls and floors and ceilings, and then it converts all the provisionals to actuals, and then it goes through a further 30 distinct cleanup steps.

9.b. The very first thing that we do in CleanUpInteriors is 8 cleanup steps that get rid of the most obvious problems: walls that are incredibly high or short, ceilings that are placed incorrectly, and so on.



9.c. Next, and optionally, the game looks at all of the defined rooms (any contiguous areas of GenericFloor), and it cuts random doorways between a room and anything that's not part of the room, in a random direction.  Later we'll definitely be more precise about making sure everything is connected in a valid way, but this is a handy way to disrupt things early.  Some InteriorGenerationStyles use it, others turn it off



9.d. Now we go through another 11 of those cleanup steps, some of them quite lengthy.  The goal here is to get things prepped to the point that the overall structure of what is closed off and what is open is now pretty set.  We need to know which tiles the player is allowed to traverse in some fashion in order for our next step to work right.

9.e. Having the data on traversable tiles in hand, now I use a pathfinding algorithm to find all the grouped traversable tiles that are unable to be traversed to one another.  For buildings with two exterior doors, I actually use a pathfinding trick that allows for each door to have a separate set of rooms and hallways that does not connect to the other.  That doesn't always happen, but it can, which is a neat variance.  Sometimes one of the side doors just opens into what amounts to a coat closet, or sometimes it's just half the building, etc.

At any rate, once I have the data on where connections are missing, I add in randomly-sighted doors such that everything is connected.  It makes sure that a valid connection will result from each door so that it doesn't put in excess doors, but where it places that door out of the pool of valid places per contiguous traversable tile set is completely randomized.

9.f. Now we have a fully-traversable interior floorplan, but there are still a lot of details that are messed up, and the cutting of the new doors (and in some cases, hallways) has caused some new minor disruptions.  So it's time for one last cleanup step on the provisional tiles, then the conversion to the non-provisional tiles, and then the final 30 cleanup steps.



9.g. Some of these final 30 cleanup steps added in chasms (for rooms that are completely inaccessible by any means for some reason), and courtyards (for rooms that aren't directly accessible via an interior door or hallway, but instead require going under the edge of a ceiling to get into them.  The chasms and courtyards are fanciful and just part of the AVWW theme; you could easily leave them as hallways or GenericFloor, at your preference, if you're using this algorithm in another game.

10. Now the game has a fully-defined, polished set of interior rooms, halls, chasms, and courtyards, inside an outer structure, with staircases up and down and exits to the outside on a single floor out of potentially many.  FUTURE STEP: All of the rooms are now nicely defined, distinct from the hallways, based on being either GenericFloor groups or Hallway groups.  These GenericFloor groups can instead be changed into more specific floor types, such as Bedroom, Kitchen, Bathroom, Office, etc, etc, etc.

This is actually a comparably straightforward step, although I'll have to be careful not to put bedrooms leading into the kitchen, or bathrooms without any doors.  Anyway, I haven't don this step yet, which is one of the main reasons I'm not yet releasing the code (the other reason being that the numerous cleanup steps need more testing and tuning time, although at this stage they're looking pretty solid).

Post-Process
Once the above process is completed, you have a hard-won array of tiles that define an interior floorplan.  It's devoid of any objects, but it lays out the rooms and doors and stairs and all that good stuff.  It also doesn't really lay out anything specific about the walls or ceilings, etc.

So the game itself has to decide when to draw a front-left-corner ceiling tile, or things of that nature.  These were already things I'd implemented in AVWW when I was creating floorplans by hand in xml, and it's a really straightforward bit of logic (if there is ceiling to your top and right, but not your bottom or left, draw the front-left-corner ceiling, etc).

Also, the game itself will have to go through and actually put in things like tables and beds, ovens and debris, and so on.  But since the algorithm above (with the later addition of step 10) will determine the function of rooms (which tiles belong to the kitchen, etc), that makes for nicely encapsulated, relatively straightforward sub-algorithms.

This algorithm also doesn't do any setting of tilesets -- to choose what the walls, ceilings, or floors look like.  That's yet another thing the game has to do, and something I'd already coded back in March.  That stuff is trivial compared to actually making the floorplans, I can tell you.  But the cool thing is that this represents nesting within nesting within nesting (actually deeper than that, in reality).  So the floorplans are quite unique when just looked at on their own, but when you combine those with different entity-seeding logic in each room and hall, with different tilesets, with different enemy populations, and so on -- you get a pretty insane amount of variance.

Example Floorplans In My Ugly GDI+ Tester Program

Ice Age Hatch Examples 1-4


Little Shop Examples 1-4


Log Cabin Lodge Examples 1-4


Modern Ruins 3 Examples 1-4


In Conclusion
If you're absolutely desperate for an algorithm like this and this is the one you think you want, then shoot me a note and I'll send you the C# code now.  But I'll be officially making the code public under the MIT license in a month or two, once I've got things completely ironed-out and step #10 in there.

The tedious part of all this was getting all the various cleanup steps tested, and tested, and tested.  I had the working exteriors and interior walls put together after a day or two (most of that time spent on research of various interior wall methods), and I figured I was almost done then.  What I didn't figure on was another 2,000 lines of code that would be required for cleanup alone.

In a lot of respects, this sort of cleanup very much reminds me of the sort of work I used to do whenever we had a business client with dirty data in Excel that we needed to scrub and get set up in a properly-validated database.  What I didn't expect in this particular instance is that these cleanup steps add even more to the procedural variance in the floorplans.  Based on everything that gets combined, scrubbed, cut, and so on, you get a ton of room shapes emerging that were never in the base room templates.

Oh, and the other thing that I should mention is that at any time I can add more room templates, and get even more variety without adding new code (same benefit as with the base LaPier method).  Right now I did enough so that I could differentiate the various types of buildings, and so that I could really get a lot of starting variance, but there's lots of room for more later.

All right, that's it for now.  Like I said at the top, I'll do an actual sans-video post on our overall progress on the game at this stage, but this was my big project for this period and it was pretty interesting, so I figured it was best as  its own post.

UPDATE: The source code is now available.