AVWW Interior Generator (Technical Overview)

[x4000]

Original: http://christophermpark.blogspot.com/2011/05/avww-interior-generator-technical.html



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 -- i am spam, 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.

(Continued below)

[x4000]

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.

(Continued Below)

[x4000]

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.

[Invelios]

Wow, that's all pretty cool. Glad you got something working for interior maps. I have to agree with you on the fantastical vs realistic part, fantastical is usually just way more interesting. I also think it's really cool that you would write up a post on the more technical side of how you are making these maps. I find it very interesting, probably because I'm studying computer science at college and really like learning more about it.

[x4000]

Glad you like it! In the past I've always hand-crafted terrestrial environments that I've created in games, so learning to think procedurally when it's not outer space or raw nature has been interesting for me.  The real world is a surprisingly poor model for fun environments unless you change certain things. 

Which, thinking about film and literature, even that bears that sort of sentiment out when it comes to any sort of action-oriented sequence.  There's always unlikely obstacles and obstructions, etc.  If movie high speed chases were just literally driving down a straight highway at high speed and weaving through traffic from behind, that would be not very Hollywood, right?

So that's been the biggest and most interesting lesson of all for me, through this.  Knowing how to do procedural content is one thing, but knowing how to make it really shine and create exciting places is another.  I think it's coming along well.

[dumpsterKEEPER]

Thanks for sharing that process. I've always found the programmatic generation of spaces like this to be fascinating reading, even though I've never actually had a need to implement one myself

[Professor Paul1290]

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).

While making interiors less traversable and usable than they would be in real-life can make things more challenging for the player, I think it is worth keeping in mind that this can be a double-edged sword.
Often, an interior that doesn't let the player travel from point A to point B that easily won't allow anything else to travel through that easily either, including NPCs and objects.

Of course, this can depend on what kinds of enemies and challenges the game is going to have. If it's mostly stationary traps and simple monsters that stay put until the player enters the room then charge straight at them then this isn't really an issue.

However, if you decide later to introduce more active and mobile obstacles or enemies that wander around more, patrol from room to room, or try to seek out the player in various ways then having a less easily travelled map can be somewhat limiting. An enemy that somehow tries to get to you from a from the next room over can be less threatening if he has to pass through five other rooms and only has one possible route to reach you. A more easy to use (may or may not be realistic) building with multiple easy to use ways to go from point to point can provide more possible places for the player to encounter a more mobile enemy, or perhaps even skillfully avoid it.

Again, I don't know what kinds of enemies and obstacles you have planned for the game so this might not really apply here.
If the game is more about stationary traps and obstacles that the player has to run into and enemies that generally stay within their own rooms or move from room to room with relatively simple pathfinding (which is probably the case in a Zelda-inspired game such as this) then having a more challenging to navigate map can be very beneficial.
However, such maps may limit the effectiveness of more active, mobile, and intelligent enemies and obstacles.

[x4000]

With simple pathfinding, enemies can navigate a maze faster and better than you can. This was something that was central to most types of zombies in Alden Ridge, and I have some abnormally efficient algorithms for doing pathfinding over complex mazes with even as many as 300 enemies (most I tested) on an &00 MHz laptop in realtime.

All that said, mostly I don't plan to do much with pathfinding here for enemies -- we use it extensively in region generation, and several settlement-related things use it for the world map, but enemies that pursue you endlessly are only so interesting. It made sense in Alden Ridge because it emphasized the traps, but traps are a lot less central here for most gameplay styles.

Most enemies would be consigned to individual rooms or corridors, and there's loads of space for them to do their thing. There's others that will be able to do things like pass through walls in some cases, or others I'm sure which will pathfind, though. The goal is to have a huge variety of more or less everything we can think of, eventually, but the general core of enemy behavior is going to be closer to Zelda or Demon Stalkers than anything else. Though things like group tactics are something we want to put in at least to a small degree if we can.

The other thing to note is that our goal is also variety. Outdoors are still more open than interiors, and that leads to two kinds of gameplay. Underground areas will be somewhat in between. At some point I hope to do very narrow pure mazes, and I imagine that pathfinding enemies would be crucial there. To me, varying up the environments like that leads to more varied and interesting action gameplay and tactical scenarios.

So no worries! But good thinking.

[c4sc4]

That was an interesting read. I like that you thought about making interiors seem logical, ie no bedrooms opening to a kitchen, instead of just taking the easy approach of saying that is how buildings are designed in the game world.

[x4000]

Thanks!  Yeah, the result is "pretty logical but alien because it's not constrained by normal rules of construction," but not "completely a random soupy mess."  I want this to feel like another world following some rhyme and reason consistent to that world, rather than just something that's obviously procedurally generated.

[TheDeadlyShoe]

I had a bedroom that opened on to a kitchen once 

[Teal_Blue]

   Professor Paul wrote:  "If the game is more about stationary traps and obstacles that the player has to run into and enemies that generally stay within their own rooms or move from room to room with relatively simple pathfinding (which is probably the case in a Zelda-inspired game such as this) then having a more challenging to navigate map can be very beneficial. However, such maps may limit the effectiveness of more active, mobile, and intelligent enemies and obstacles."

And Chris mentioned what came to my mind almost instantly, although of course, haha, i am not a coder, just a casual player, but there must be something there that clicks when looking at problems like that.

Which was to have some enemies, perhaps 'Bosses'? Be able to go through walls, Either 'through' them in a sense of a ghost-like enemy or boss, or 'break them down' for massively strong enemies or bosses.

I am guessing of course, but maybe in any given 'building' there will be a possibility of zero or 1 of those kinds of enemies. And i am guessing as well, that once the physical breach was made that the other more 'normal' enemies could now follow through the new opening. Of course that wouldn't apply to following the 'Ghost' Bosses as no physical opening would be created.



Nice write up though, i am afraid i don't understand all the 'programming' stuff, but as a player it is interesting to 'see' the workings behind the curtain, so to speak.



Thank you for a very interesting post!

-Teal

[Ixiohm]

I like these more technically aimed posts very much, thank you x4000 for making these write-ups I’m looking forward to dissecting your code for this app once your release it Once again thanks, and keep up the good work.

[Gallant Dragon]

You know, on the subject of more intelligent enemies:

I had an interesting idea: what if there was a sort of "assassin" type enemy who would track the player through a building, always staying in the darkness until the player is injured or somehow preoccupied with something else, and then use that moment when the player is vulnerable to strike?

[x4000]

Glad the technical post was a hit -- I look forward to posting the code (and having it done to that point, frankly ).

In terms of enemies that pass through walls, there's a couple of models I have in mind for that, but I don't want to spoil them because I think those are going to be ones worth experiencing in-game for the first time.  There are tons of things we talk about, but a few things we try to hold back for the sake of fun when a player is actually playing the game.

I like the idea of an assassin type of enemy quite a lot.  Probably out of scope for 1.0, honestly, but we're planning on developing this for a long time.  To me, that sounds like some sort of miniboss or something like that -- something that runs an evil outpost, or lurks somewhere in an evil overlord's lair.