Tuesday, September 15, 2020

Procedural Buildings: Improvements to Interiors

I've continued to improve 3DWorld's procedural building interiors over the past few weeks. I added some new room objects and models, some of them based on suggestions from other people. I'll describe the additions to houses and office buildings, and show some pictures in the approximate order in which I added them.


Bedrooms were often too large and sparse. One way to use the available space in larger bedrooms is by adding closets against one wall. There are large closets with 4 panels of folding doors, and smaller closets with a single door that opens. Closets can span the entire length/width of a room or only part of it. Closets must be placed to avoid blocking windows, doorways, or access to furniture such as beds.

Here are two screenshots showing a large closet and a small closet. I haven't yet added door handles to large closets.

Bedroom with a large closet in the back.

Bedroom with a small closet in the far corner.

Next I added trim along the edges where walls meet the ceiling and floors. Then I added trim around doors and windows. This makes it easier to tell where the wall and ceiling meet for buildings like the one below that have the same wall and ceiling textures. The screenshot above also shows trim along the walls and door.

House interior with wall trim around floors, ceilings, windows, and doorways.

Note that this trim accounts for a large number of polygons when you add up all the small quads needed, especially around all of the windows. Sure, they're only individual untextured white cubes, but there are more of these in a building than any other object (except for maybe books). This does finally add real 3D geometry for windows, which are cut into the zero width exterior walls using textures. As an optimization, trim is only generated and drawn when the player is very close to a building. Office buildings don't have quite as much trim.

Kitchens needed a bit more work. The kitchen sink was previously only a basin with no faucet. I added a simple two-cube faucet as a placeholder until I find a better model. I also added a dishwasher under the counter next to the sink if there was enough space. The most difficult part was disabling the cabinet doors around the dishwasher and adjusting their positions so that they start and end on either side of the dishwasher with no clipped or small doors.

Kitchen cabinets, counters, sink, dishwasher, and stove. The dishwasher has a shiny metal handle.

I decided that I liked railings better than straight vertical walls for the smaller sets of stairs that appear in houses and some other building types. It took a bit of work to add support for arbitrarily oriented cylinders, but I now have that working. I also added specular color support to the building materials system so that railings reflect light like proper shiny metal objects. You can see this used on the dishwasher handle above as well. This looks much better (and safer) than stairs with no railing at all. Here is an example screenshot, with the railings in beautiful gold.

Simple cylindrical railings have been added to open stairs.


When I was happy with houses, I moved on to improve office buildings. All those cubicles looked pretty bare. I decided to find a 3D model of a rolling office chair and place one in most cubicles with a random rotation. Right now the chairs are untextured black materials because I couldn't find a free model in a supported format that had proper materials with textures. This doesn't look too bad though, especially considering my chair at work is completely black with little texture.

A large office building room containing cubicles and rotating office chairs.

Adding chairs makes offices look better. But they're not lit very well with a single light in the center of the room. I increased the number of lights for some rooms using an X by Y grid of lights based on room size. Smaller rooms still have a single light, but larger rooms can have a 2x1 or 2x2 array of lights. There may be rooms with more than 2x2, but I haven't come across any yet.

Large offices can now have multiple light sources, usually an array of 2x1 or 2x2.

Desks were too empty, even though some had books on them. I decided to reuse the TV model as a computer monitor to put on some desks. I downloaded several screenshots and used one of my own desktop to create illuminated texture images on some of the monitors. These desktops are a mix of Windows, Linux, and MacOS. Monitors are more common in offices but can also be placed in houses. For now I haven't attempted to make the operating system consistent within a building.

Office desk with a monitor on it, turned on and showing a desktop.

The next step was improving bathrooms. Those individual tall sinks looked fine in residential bathrooms, but larger office bathrooms usually have a single long slab containing multiple sinks. I reused the kitchen sink code with some modifications for these bathrooms. Now the sinks are part of one counter with multiple basins and faucets, as seen below. Also, office bathrooms can have multiple lights as well.

Individual sinks have been replaced with a single long counter with built-in sinks for office bathrooms. They can now also have multiple lights.

I finally found a usable free urinal 3D model to place in the men's restrooms. I even added short walls between the urinals for privacy. Now they look like a proper men's restroom.

The Men's restroom now contains urinals.

I made various other fixes and improvements as well. Some houses have brown wooden front doors instead of white front doors. Straight stairs have walls on the sides or railings to keep people from falling off. The room object placement algorithm has been adjusted again to take into account clearance around objects to prevent the player and AI from getting stuck/blocked. Refrigerators are no longer placed in locations that block windows. Oh, and houses now have a number of bathrooms that scales with the size and number of total rooms in the house.

Friday, August 21, 2020

Procedural Buildings: More Room Details

This post continues my work on procedural room object placement from the previous few posts. I don't have too much new technical content to show this time since most of the work was in the details of room classification, room partitioning, object selection, and model placement. This is easiest shown with images. If you want to see the details, have a look at the 3DWorld buildings code on GitHub.

Here is an overview of the recent changes I've made. Office building bathrooms now have multiple bathroom stalls and sinks. Large office rooms are sometimes divided into rows of cubicles. Some office buildings have illuminated exit signs, and some houses have welcome signs above their doors. I assigned a room in some of the larger houses to be the library. I added kitchen sinks, and cabinets and counters with doors and handles. I added nightstands and dressers to bedrooms. I also finally started implementing interiors for the office buildings within city blocks, which is incomplete and not shown here.

I put a lot of time and effort into populating houses while leaving other types of buildings somewhat neglected. To start off, I decided that having a single toilet and sink in an office building bathroom was too little. We don't want to see the employees lining up in the hallways! These rooms often have a large amount of space, enough to fit several stalls and sinks. Each bathroom above a minimum size is now assigned a row of stalls with toilets and a row of sinks along one or both walls. I even had to add interior room occlusion culling to avoid drawing the hundreds of toilets and sinks in a large office building.

Office building bathroom with three stalls, two sinks, and a trashcan in the back corner. Yes, I need to change the floor from carpet to tile.

Some office buildings contain very large open rooms. It seems odd to place only a single table with chairs in the center of the room, or a pair of desks with chairs along one wall. The building where I work has many of the large rooms filled with rows of cubicles, and offices in the central area of the building. I modified the room population algorithm to divide some of the rooms above a minimum size into multiple rows and columns of cubicles, as many as could be fit while allowing all of them to be accessible through the aisles. Cubicles near windows have shorter walls to let in more sunlight.

Large office room divided into cubicles, some of them against the windows.

Very large office room with a center row of cubicles. Maybe it should have more than one light?


What else do buildings have? How about signs, both on the interior and the exterior. I added illuminated "Exit" signs, "Women" and "Men" restroom signs, and "Welcome" signs to some houses. Exit signs are visible in dark rooms and can be either red or green. I plan to add more types of signs to the exterior walls and roofs of buildings eventually.

This office has a green illuminated exit sign above the door. Others have red exit signs.


Office buildings look much more interesting now, though there's still plenty of work to be done. It's time to move back to houses. I really like the look of bookcases filled with books, and I put quite a bit of time into this feature. Up until this point, a room could contain at most one of these. I added a new room of type "library" to upper floors of houses that have a table with chairs and as many as five bookcases. The bookcases are currently all randomly sized and placed. Maybe later I'll go back and make their sizes and spacing more consistent with an organized home library.

Some houses have an upper floor library, basically a room with lots of books on shelves.


Kitchens with only a table, chairs, refrigerator, and stove seem too bare. Most kitchens have counters with cabinets above and below. Also, don't forget the kitchen sink! I added code to attempt to place counters and cabinets around the walls of the kitchen wherever there's space. Cabinets have upper and lower rows with many doors, each with a handle. Everything is formed from simple cubes, which makes it a lot easier to create these objects and fit them into the gaps in the room. Then I choose a location to cut a cubic hole into the counter to make the bowl of the kitchen sink. Sorry, no faucet yet.

A kitchen with table, refrigerator, stove, sink, counters, and cabinets. The sink is the hole in the far counter to the right of the stove.


Bedrooms were next. At this point they only contained a bed and possibly a bookshelf and/or trashcan. Bedrooms are the most common room in a house, accounting for nearly half the total rooms. Many of them are large and have plenty of space for additional furniture. I placed dressers and nightstands in bedrooms using code similar to kitchen cabinets. Each object has between two and three rows of drawers, with 2-4 drawers in each row for dressers.

I used the same rough wood texture as most of the other furniture. At some point I'll need to go back and add a larger variety of high quality wood textures that vary by house or room. Or at least vary the color and texture scale a bit.

Here are some example screenshots of bedrooms.

Bedroom with bed, dresser, and nightstand. These use similar code to kitchen cabinets.

Bedroom with bed, dresser, nightstand, bookshelf, and picture

A different bedroom with bed, dresser, and nightstand. The dresser has multiple drawer sizes.

I also attempted to add potted plants to living and dining rooms. The pots looked fine, but the plant leaves didn't work out well. I tried to reuse my procedural plant generation code that creates landscape vegetation, which was using a different shader from building interiors. Building shaders don't yet support full alpha testing and alpha blending. It's easy to enable, but will result in early Z (depth) testing getting disabled, which hurts the frame rate. Buildings have very high depth complexity when considering all of the walls and ceilings, and the fragment shader is heavy with lighting and shadow calculations.

After adding all of these new room objects, I found that it was easier for the player to get stuck. Some rooms had furniture placed close enough together that the player couldn't cross from one side to the other. My solution was to ensure there was a player diameter of clearance in front of most objects, meaning the side facing away from the nearest wall. This seemed to work very well. I can no longer find a room that can't be crossed. I wonder if the AI people can also navigate these rooms?

Tuesday, July 21, 2020

Procedural Buildings: Room Assignment

I've definitely made a lot of progress in 3DWorld's procedural cities. I started with placing cities, then I populated them with buildings, then I added building interior walls, floors, and rooms. Next I added room lighting, details, furniture, and people. Now it's finally time to officially assign purposes to rooms and populate them with the correct furniture, appliances, and other objects according to room type.

I added bathrooms and then bedrooms to houses a few weeks ago. This past month I added hallways, offices, kitchens, living rooms, and dining rooms. I also added bathrooms and kitchens to some types of office buildings. Bathrooms previously had toilets, but now they have sinks and tubs as well. Bedrooms continue to have beds, bookcases, and sometimes desks placed in them. Kitchens currently have refrigerators and stoves, while living rooms have couches and TVs added against their walls. Kitchens, dining rooms, and living rooms also have tables and chairs. Residential offices have desks with a chair and sometimes a bookcase, while commercial offices contain up to two desks and a whiteboard. Any house rooms can have pictures, rugs, trashcans, and lights.

Walls, floors, and rooms are generated when each building is created. Interior details are only generated and drawn when the player gets within a specified distance of the building. This distance is relatively large to prevent visual artifacts as furniture and appliances pop in. Smaller and more numerous items such as books and pillows are generated and drawn at a closer distance to reduce their resource usage. Generation time has a minimal overall impact on framerate, except for when the player is moving at maximum speed through a densely populated area of the map.

Before we get into room assignment, let me show off my book/bookcase improvements. If you look at the bookcase below you'll see that some of the books are leaning against other books. This is something new I added since the last post. However, books can only lean to one side within an individual bookcase.

Bookcase with some tilted books.

Saturday, June 13, 2020

Procedural City: Furniture for Building Interiors

I'm continuing to work on object placement within the rooms of 3DWorld's procedural buildings. First I need to show some updates to the furniture I added in the previous post. Then I'll get into the fun topic of toilets.


The books in my bookcases looked pretty plain because they were nothing more than colored cubes. I've changed them into several cubes representing the front and back covers, pages, and spine. Pages are white and the rest of the book is colored. Now they look more like books and less like colorful boxes.

Bookcase containing colorful books with covers and pages.

Next, I added pictures to the front covers of some books. This applies to books in bookcases and individual books placed on desks and tables. These are the same set of pictures/images that are hanging on the walls of rooms. Maybe at some point I can find more book-like pictures online. Not all books have cover images.

Bookcase containing books with images on some of their covers.

A book on a table with an image on its cover.

The final step was to add titles to the spines of books. I should be able to use the existing text drawing system in 3DWorld to add titles. This is the same system I use for drawing text message overlays, the framerate counter, game stats, debug visuals, etc. Text is drawn one character at a time using a font texture atlas and and array of adjacent textured quads, one per character. That leads to a ton of geometry, but I only need to generate text for books in the nearest building.

The only question is where to get the book titles from. I did a lot of online research into text generation, but it doesn't look easy to create reasonable sounding book titles. The best I could come up with was a website listing 1000 (actually 997) must-read books. I used this list of book titles as a pool of available text labels for adding to the pines of books placed on bookcases, desks, and tables. Extra long titles are wrapped onto two lines of text. Titles use colors opposite on the spectrum from the book cover's color.

Books on a bookcase with titles randomly selected from 1000 real book titles found online.


I added beds to building interiors a few weeks ago. The first version of beds used textured cubes for everything, including the pillows. As someone pointed out, these made beds look like they were made out of Legos. I went back and replaced these 5 sided (bottom not visible) shapes with something rounder with more triangles. I used a 2D, fifth root power falloff for the edges with 25 square root (nonlinear) spaced samples in each dimension. This is more expensive to draw, but looks much better. Pillows now have a smooth curve that blends into the bed sheets below rather than having hard edges.

The pillows on beds are now rounded shapes rather than cubes.


I finally got around to adding true instanced 3D models to 3DWorld's procedural building interiors. Up until now, all of the building interior models were procedurally generated on-the-fly when needed. (I don't count people and cars in this category because they're dynamic and not part of building interiors.) The main difference between room models and dynamic models is that the room models are generated as needed when the player is near a building, compared to people and cars which are all placed at scene load time.

I've been working on adding specific rooms to houses, starting with bedrooms in the previous post. Next on my list was bathrooms, which at the very least need a toilet. That's not something I can easily generate with code because toilets have too many complex curves. I downloaded a 3D toilet model online and got to work. I tried various experiments with this toilet model, some of which were interesting. I suppose the remainder of this post is going to be mostly about silly things I did with toilets.

First up, what happens if I use a toilet model for cars and pedestrians, and have 3DWorld attempt to animate the toilet as a person? Since the animation is procedural, it should in theory apply to any 3D model. Well, it did pretty much exactly what I expected, with hilarious results!

Are toilets furniture? I'm not sure, but it's time to add them to my procedural buildings. For now they're only added to houses. Maybe sometime later I can add office bathrooms. I'm categorizing them as "room objects" in the code, along with tables, chairs, bookcases, desks, beds, and lights. Toilets are placed in rooms categorized as bathrooms. Once again there are a large number of constraints on which rooms can be used as bathrooms. In fact, there may be more constraints for bathrooms than for bedrooms. Some of them are demonstrated below for amusement.

1. A room can't be both a bathroom and a bedroom:

The bedside toilet, for those who prefer not to leave the bedroom to use the bathroom. (The toilet is also probably too large and has been reduced in size after the screenshot was taken.)

2. A bathroom can only have one door, and it can't have stairs or an elevator in it:

All the privacy of having the bathroom at the center of the house and containing the stairs. At least the opaque windows give some privacy, right? (More on them below.)

3. Bookcases shouldn't be placed in bathrooms:

A bookcase strategically placed to allow for some light bathroom reading. Well, maybe it could be in reaching distance from the toilet.

4. Bathrooms shouldn't have an exterior door. We don't want visitors entering the house through the bathroom. (Sorry, I don't have an image for this one.)

There are also constraints on room sizes, number of bathrooms in a house, etc. I won't list everything because I don't have nice pictures of the other items.

Once all of these conditions are checked, it's time to place a toilet in a corner of the bathroom away from the door. This exposes another problem though. The toilet is often placed near a window, and can be easily seen through the window from outside the building. That certainly doesn't look right!

A properly placed toilet, except for the fact that it's next to a big transparent window.

Something must be done to address the lack of privacy when the toilet is placed near a window. So, what can we do about this? Real bathrooms use windows with frosted glass, swirly patterns, or glass blocks to prevent people from looking in but still allow the light to enter from outside. These windows have glass that refracts light in a complex way, distorting the light pattern to prevent people from seeing through them. They're often smaller than regular house windows as well.

I can't easily vary the size of windows per-room, and it's too expensive to create a proper refractive material. I'm not sure exactly how to do this in a way that looks right for all indoor and outdoor lighting conditions either. For example, the window should be bright in the day time when the sun is out and dark at night. I don't really want to have to regenerate the window when the room lights are turned on or the time of day is changed. I also can't make it partially transparent because then people can still see though the window. The best I came up with was adding a generic texture of an array of glass blocks.

I replaced the window with some frosted glass blocks to give the bathroom more privacy.

There are some minor issues here. The lighting/color is fixed, independent of time of day. It's that sort-of-light-but-not-bright color in between what you would get at night and what you would get during the day. The window is probably larger than it should be. Also, the blocks don't align with the corners of the window. Fixing the alignment is very difficult. The glass block texture is actually slightly behind the wall and covers the entire wall, which avoids having to figure out how many windows there actually are in this room and where they're located. It's also more efficient to draw one quad per wall rather than one per window, though there is often only one window in a bathroom. This is good enough for now.

I suppose I'll have to add sinks next. Maybe I can also add mirrors that have real reflections. I'm not sure what to do about the player's reflection since there's no player model, but I should be able to reflect everything else in the room.

Sunday, May 24, 2020

Procedural City: Adding Content to Building Interiors

Work continues on building interiors for 3DWorld's procedural cities. I had previously added stairs, elevators, lights, tables, chairs, rugs, pictures, and whiteboards. This time I've added trashcans, bookcases, desks, and beds. I'll briefly describe how I place and draw these room objects below, with plenty of images to show what they look like inside buildings.


Trashcans and recycling bins are common in both residential and commercial buildings. They're also simple and easy to draw - at least that's what I originally thought. They required implementing some new features, for example curved surfaces. (Yes, round room lights are also curved cylinders, but they're emissive so I didn't really have to get the normals right for lighting.)

Another difficulty is that I needed to implement two sided lighting so that their interior and exterior surfaces were lit correctly since they have no thickness. I could add a thin rim around the edge to connect the sides and give it some volume, but I don't currently have the code to draw that geometry. It would also take even more triangles. I initially enabled two sided lighting, but it was too much work for the fragment shader and reduced framerate. So I changed the code to add each triangle/quad twice with different normal sign and winding direction. Back face culling was enabled to ensure only the face oriented toward the camera was drawn.

Trashcans are placed in the majority of rooms. They are randomly selected from three different sizes, three different aspect ratios, and several colors (including blue for recycling bins). In addition, some building floors use trashcans with flat sides and others use rounded sides/cylinders. They are always placed near a wall or corner of the room away from doorways and other placed objects. Trashcans have collision detection enabled and cast shadows. Here are two example screenshots.

Flat sided trashcan in the corner of a room of a house.

Small cylindrical recycling bin by the wall in an office.

Adding trashcans to most rooms requires a great deal of total geometry across the set of nearby visible buildings. Some large office buildings have more than a thousand trashcan placements. This was having some effect on framerate, so I had to optimize the drawing code by removing hidden faces, using indexed triangle rendering, disabling shadows when distant, etc. To make it easier to test my optimizations, I temporarily placed up to 20 trashcans in each room. Now a single office building could have more than 10K of them! Here's a wireframe view showing all the trashcans in an office building.

Wireframe model showing a large office building with an excessive number of trashcans and recycling bins.

Most of the cost was in the shadow pass, where a shadow map was created for each of the up to 40 shadow casting lights every frame. Each shadow map had to draw every trashcan in the building because there's no per-building subdivision/acceleration structure for them. I thought about adding one, but I ended up caching shadow maps between frames when they weren't changing (no dynamic shadows from the player or people in the building). This helped a lot. With shadow map caching, my other trashcan drawing optimizations were probably not needed. I'm sure they'll help with non-shadow rendering though.


Next I added bookcases to houses/residential buildings. These can be placed in any room where there's space, as long as they don't block doorways, stairs, or elevators and don't intersect other room objects. I had to update the code that hangs pictures on the walls to avoid placing a picture behind a bookcase. They're relatively narrow and the placer is successful most of the time.

Each one has between three and five shelves, with randomly placed books on most shelves. Books are simple cubes with a variety of colors, sizes, and thicknesses. There are some gaps and the possibility of a fallen over book in the larger gaps. I like the way bookcases and books look, even though the books are simple and untextured. Here are some representative images.

Procedurally generated bookcase with a random selection of colorful books on the shelves. One book on the bottom shelf has fallen over.

Procedural bookcase with random books in a room with a table and rug on the floor.

In the future I might add books placed at angles, leaning on other books, which requires a bit more math. I could add more geometry to show the pages vs. the covers. I did this for books placed on desks below. I might even add pictures and/or words to the covers.


Desks were next on my list of furniture to add. They're similar to tables, but with a higher aspect ratio and only one chair. These are placed more often in building offices, and in smaller rooms of residential buildings where there's no space for a table. Some offices have two desks, but the rest of the rooms have at most one. They're pushed against a wall in a location that doesn't block any doorways, stairs, or elevators. I reused most of the code from tables to save work.

Here's are screenshots of a residential building desk and an office with two desks.

Home office with desk, chair, bookcase, recycling bin, picture on the wall, and rug on the floor.

Large windowless office with two desks with chairs, large whiteboard, and trashcan in the corner.

I placed a randomly sized and colored book on some of the desks, right in front of the chair. These books actually have separate cover vs. pages geometry. Maybe at some point I'll use these models in bookshelves. I might also put titles and pictures on the covers.

Desk with a red book placed in front of the chair, waiting to be read.

Some desks that are against interior walls (no windows) have taller backs. These may become bookshelves, mirrors, whiteboards, or cork boards in the future. I'll have to think about what I want to hang from their back walls. For now they're extra wooden spaces.

A tall office desk that can be used as a bookcase, mirror, whiteboard, cork board, etc. in the future.


The logic for selecting bed placement was actually pretty complex. Beds are placed only in bedrooms, compared to other room objects such as chairs, desks, bookcases, trashcans, rugs, and pictures, which can be placed in most room types. There are more rules governing assignments of bedrooms than most other rooms and placed objects. For example:
  • Bedrooms are in houses/residential buildings only, not offices
  • No beds in building parts assigned to garages and sheds 
  • No beds in rooms flagged as offices or hallways
  • No beds in rooms with stairs or an elevator
  • Bedrooms should not have an exterior building door (front door) when on the ground floor
  • Rooms can have either a bed or a table, not both (bookcases are okay to mix in)
  • No beds in rooms that are too small to fit them, or too large to be bedrooms
We also have the usual placement constraints and some placement constraints specific to beds:
  • Beds can't block doorways (same as other furniture)
  • Must be space to at least one side of the bed where a player/AI can walk
  • Must be space to navigate around the bed from one doorway to a doorway on the other side of the room
  • Headboard should be against a wall if possible (soft requirement), but need to leave a bit of extra space if along an exterior wall with a window.
I attempted to implement all of those checks and special cases, which required adding a bit more query functionality for buildings. Since beds are only used in houses, which have a smaller number of floors, this doesn't affect runtime or framerate as much as something like a desk which can have a thousand placements in a single large office building. Bed geometry is simple though, at least compared to bookcases full of books.

Beds have a frame with legs, headboard, foot board, mattress, and pillows. Most of the bed is made of a wood material. The sheets and pillows have fabric textures and some randomly chosen colors applied to them. Large beds have two pillows, while narrower beds have a single pillow. For now, all the parts of the bed are drawn with cubes. Here are some examples of beds with various sheet textures.

Bed with two pillows and plain white sheets placed along a wall in the bedroom.

Another bed with patterned/textured sheets and a single pillow next to a bookcase.

A bed with fancy red sheet texture against a wall with windows.

Those are all the features I've added since the last post. I won't get into the various other optimizations and bug fixes this time. There are many more room items to add. I can think of dressers, couches, TVs, lamps, and kitchen items. Offices need cubicles and computers. Maybe indoor potted plants as well? I'm sure it will be tricky designating a room of the house as the kitchen.

Saturday, April 25, 2020

Procedural City: Room Decorations

It's time to add more decorations to the rooms in my procedural buildings. The walls and floors look too plain, so that's a good place to start. First up is office buildings. I added hardwood floor textures to houses, but office buildings are still using simple gray floors. I downloaded five office carpet textures and added them to the pool of randomly selected floor textures for non-house buildings. Here is an example.

One of the new office building carpet textures. This one even has a normal map!

Next up are houses. The hardwood floor textures look good, but I need to add some variety. How about fancy rugs covering some of the floors? I found five rug textures online, and added support for selecting random rugs and placing them in some rooms. Rooms that are otherwise empty (no table or chairs) have a higher chance of getting a rug so that they're not totally empty. These rugs are randomly sized and positioned randomly somewhere near the center of the room.

A house with rugs on the floors of some rooms.

That's good for floors, so it's time to work on the walls. The most obvious decorations to add to walls are framed pictures, and what better pictures to use than my library of 3DWorld screenshots. I added ten full resolution 1920x1024 screenshots of various scenes including nature, reflections, a procedural universe, and buildings. I even threw in one of my skybox images, which wasn't created by me. (Note that these images are large and haven't been added to the 3DWorld GitHub project.) Here is a room with a nebula picture on one wall and a reflective Sponza Atrium picture on the the other wall.

A house with pictures on the walls and rugs on the floors.

But wait! Why limit pictures to existing images? Why not allow the player to create their own photos for hanging up on the walls? Sure, let's do that, just for fun. I added a hotkey to take a screenshot and add it to the building photo library, which replaces the initial screenshot images. Now the user can populate rooms with their own selected artwork.

A picture showing a screenshot of buildings taken a few seconds earlier, complete with "yellow status text of authenticity". Hey, dude, get out of the photo!

In fact, you can take screenshots of these pictures and create new pictures. The nesting of screenshots is unlimited.

A picture showing a screenshot of a picture of a screenshot. I had to shine the flashlight on it because it was somewhat dark due to the downward direction of the room light.

Here's another example.

A screenshot I took of the nearby city placed as a picture on the wall.

That's good for houses, but office buildings don't have many pictures on their interior walls. What they do have are offices, and many offices have whiteboards. I can conveniently reuse the picture system with a blank white texture and an added ledge to form a whiteboard.

An office with a whiteboard on the wall and a new carpet texture.

That's good enough for now. This was actually a pretty easy task, at least compared to some of the other work I've done on buildings such as navigation for people. At this point it's unclear what I should add next. I suppose more room furniture and smaller details is always useful.

Monday, April 6, 2020

Procedural City: AI Navigation for People in Building Interiors

I've continued to work on procedural city building interiors over the past few weeks. Let me start with something simple, then get into AI navigation later. I added more ceiling and floor textures, for example hardwood floors for houses. This improves the look of all my future indoor house screenshots. These changes also make it more pleasing to debug the wayward AI by watching people walk around for several minutes at a time. At some point I'll go back and add better textures to office buildings as well. Here are some examples:

House with normal mapped light hardwood floor, and ceiling tiles.

House with dark hardwood floor, and a plaster/stucco ceiling texture.

Next, I added animated people who use AI path finding to navigate between rooms of a building. As expected, this was quite time consuming and difficult to get right. It was more difficult than path finding for city pedestrians to avoid buildings and other objects, but it was probably easier than pedestrian street crossing and car avoidance logic. I haven't finished the logic for people to ascend/descend stairs, so for now they stay on a single floor of their building.

People don't exit buildings either. At least, they're not supposed to. When I first implemented moving people it didn't work as expected. (It rarely does.) What I had were people who walked straight out of their buildings, through the sky, to the center of the map. Like this:

Failed attempt at people path finding AI. The all walk out of the buildings and into the sky in the center of the map.

Yes, the 3D models still have their arms out. I haven't fixed that yet.

I eventually got the basic movement working after many hours of work. People slide across the floor and sometimes walked through walls but at least stayed in their buildings. That's progress, but the whole "slid across the floor" situation could be improved. Yes, I have to make my 3D person model animations work in this context. Here I'm using a different shader that supports indoor room lighting, rather than the city shader I was using for pedestrians. The same shader is used for building interiors and people so that I can draw both groups per-building without switching shaders. It already has animation support that I can enable because it shares a base class with the city pedestrian shader. Surely it will work if I just enable animations, right? Let's see...

Accidentally animating buildings using the animation system meant for models of people.

Yeah, I was afraid of that. The building interiors are "animated" as well; meaning, they rotate in some odd way around some random point of the building that the animation system detects as the "legs". That screenshot doesn't really do it justice. In reality, the buildings are all spinning around madly so that you can't even tell what's going on. It's just a mess of polygons flying around that you can only make sense of with a static screenshot. In fact, you can't even see the people through all of the building walls. Well, it makes for an interesting image anyway.

One hack that fixes it is to always set the animation time to zero before drawing buildings. That works well enough for now. Onto the problem of people walking through walls and furniture.

Wait, there's one more thing I need to go back and fix. I quickly realized that halfway open doors would be a problem. I never bothered to include them in collision detection with the player/user because they generally got in the way and prevented the player from walking around in some rooms. There were too many rooms where the combination of a table + chairs in the center plus doors on each side made the room impassible to the player. The AI collision detection ignored doors as well, for similar reasons.

How does this work in the real world? Most of the time, people will open doors as far as they can be opened to get them out of the way. That's either opened 90 degrees until they hit a perpendicular wall, or almost all the way to 180 degrees until they hit the wall containing the doorway. I can do the same here. The room generation and door placement algorithm can determine how far the door can be opened, and open it just short of that value. 15 degrees seemed to work well; large enough to get them out of the way, but small enough that they (or rather their non-existent doorknobs) don't intersect the wall. Now doors are usually open like this:

A man walking into a room through the doorway. The door has room to fully open, so it stays out of the way. Compare this to the 90 degree open doors in the two screenshots at the top of this post.

That's much better. People hardly ever walk through doors now! But they walk through furniture and stairs all the time, and occasionally still walk through walls. And each other. I need to implement path finding through the room graph with collision avoidance for furniture. The first step is to construct a graph of the room connectivity through doorways and stairs. An added bonus is that I can now use this graph to perform connectivity analysis and find all of the buildings where the rooms aren't 100% connected to each other. I can print out their locations for debugging and go find them in the scene.

Okay, that was a lot of work. I thought the floor planning algorithm was pretty good, but apparently there were several bugs that were rare enough that I missed them in my manual building inspection. (I can't quite manually inspect 14K buildings.) Some house cubes/rooms were too small for doors. Some building parts came together at odd positions where walls blocked doorways. Some of them were missing vertical connector stairs that joined stacked floorplans. I was able to fix all but this last category. I have it down to 28 failed placements out of about 14,000 buildings. That's what, 0.2% failed floorplans? Good enough for now. I know where they are if I want to go back and fix them later. These people are asking me to make them stop running into things, I can't make them wait forever.

Right. Finally, after all these changes, I'm ready to start on AI navigation and path finding. I expected this to be interesting, and it was. I copied my A* (A-star) path finding algorithm from the game mode smiley AI waypoint navigation code and made it work with the building room graph. After many many iterations I had a system where my 50,000 people could walk from their current position to the center of a different room in the same building through doorways without walking into walls. It's fast too, only around 3ms for 50K people! If you're interested, the code can be found here in my 3DWorld GitHub project.

Two people of different sizes walking through a room to an adjacent room.

The first part of the algorithm finds the high-level path from the starting room to the destination room by traversing the graph through rooms and doorways. A valid destination point is chosen randomly within the destination room so that it doesn't intersect any placed objects. Once the destination is reached, the AI waits there for a few seconds and then selects a new room to walk to. That part didn't take too long to get right, but it took a long time to smooth the path and push it away from walls and door frames so that people didn't partially intersect them. I had to use a collision radius for each person and shrink room boundaries by that value. This must be done for individuals because some of them have different sizes/radius values.

The next step is planning a valid path from one doorway to another across a room. I started trying to write an A* algorithm for this, but eventually I gave up on that approach. It didn't work and was too difficult to debug. The solution I went with involved picking one or two random points within the room that didn't intersect any geometry. Then the path finder tried to connect the two doorway endpoints with one or both of these points to form a valid path that didn't intersect any of the objects. The shortest valid path was used as the final solution. If there was no path, the path finding failed and the person stood there for one second. After that time was up, the path finding algorithm started again with a new random destination and path.

Since failures seemed to be rare, this kept everyone moving. I couldn't find anyone who seemed like they had somewhere they could go but weren't moving. The only people who couldn't move were those placed in single room houses or in a corner of a room blocked by a table with chairs. My fixes for these cases were to not place people in garages and sheds, and to allow them to walk through geometry on the first segment of their first path. In theory, it shouldn't be possible for them to get stuck again. If they got into that spot, they should be able to get back out (unless pushed by another person).

That handles collisions with static objects. The next task was preventing people from walking through each other like they're ghosts. This was a bit more difficult. People are dynamic, so they can't be included in the path planning system, which determines the entire path ahead of time for each new destination. What I did here was to check for collisions with every person in the same building with a higher ID than the current person. These other people have "priority." The new position of a person is determined by adding their velocity times the elapsed time to their current direction vector, which is a smoothed version of the direction to the next path point. If the new position collides with another person, then no movement is made. If the existing position also collides, then the target person is moved along the collision vector away from the collider. This applies to people who are standing still waiting to choose a new destination as well.

That somewhat works, but it introduces a new problem. People can now push each other into furniture, through walls, and even outside of buildings. I fixed this by clamping their locations to the valid walkable areas of each room. This results in some model intersections, but it's better than intersections with room and wall geometry. I had the room path finding algorithm ignore a person's starting position if it was inside room geometry to allow them to escape once pushed inside tables and chairs. This situation is relatively rare, so it's unclear if my solution always works.

I could go on and on about this system, but I think that's enough details for now. I'll try to add some videos later. There are still some finishing touches I need to add first.

Here is one final image showing the wireframe of a building with people walking around inside of it.

Wireframe view of buildings with people walking inside them.

There is a lot more work to do. I would like to have people ascend and descend stairs to reach different floors of a building. I did some experiments with stairs where people are teleported up or down one level. It works, and the path finding can handle it, but it doesn't look good. I need to figure out how to make them walk up and down the stairs. The hard part here is that they need to start at different ends of the stairs depending on whether they're going up or down, and that's not something I can easily add to the room graph. Maybe I need two different graphs, or two sets of edges corresponding to "up" and "down"? I'll continue to improve it later.

There's one more fun thing I should mention. At one point I occasionally saw people who stood there spinning in circles forever. It took me a long time to figure out why they had this odd behavior. After adding lots of debug code and printouts, I realized they were trying to stand on a very exact spot on the ground. Each time they took a step they overshot their target, then turned and tried to step in a different direction. Their minimum turning radius made sure they could never quite get to the correct spot. If they ended up a very specific distance from the target it caused them to spin in circles. The fix for this was to add a term that decreased their step length when their target position wasn't directly in front of them. This reduced their speed while turning and made their steering more accurate at the ends of their paths.