Building AI People Using Elevators

It's time to get back to writing some AI logic for buildings. I wrote a system for building AI people to use stairs a year or so ago. Then last month I added support for ramps such as those found in parking garages so that zombies can follow the player to more locations. Now, I've written the logic for AIs to use office building elevators.

But why? Well, it seems like an interesting challenge. I'm not aware of any current games where the AI can properly use a fully functional elevator. I've seen simple bots that can ride an elevator up and down between two floors. I've seen AI companions that can follow the player into an elevator, such as in FNAF Security Breach. And I've also seen scripted cut-scenes where a NPC (non-player character) will use an elevator. I've definitely never seen a game where both the player and AI can use an elevator that goes between more than two floors, and specifically where multiple AIs can co-use the same elevator with different destinations.

There are also some gameplay reasons to have AIs use elevators. Previously, it was always safe for the player to escape zombies by calling and jumping into an elevator. The player could even hide from zombies in an elevator because they treated them as colliders and wouldn't enter the car. Now it's no longer safe to escape through an elevator. Maybe the doors will open and a zombie will be inside, or maybe a zombie will be waiting to enter the elevator as it stops on a floor. There's definitely some risk now in elevator usage. This is good, as it makes the game more unpredictable and surprising for the player.

Building AI Behavior

3DWorld's elevators and building AI people are entirely separate and can only interact with each other through button presses and sensors. Both run internal finite state machines, have timers to trigger various future events, and support animated motion. Therefore, I can implement this by writing proper elevator usage for the AI and proper behavior for the elevator as two separate tasks. Elevators can currently be used by the player, so I can keep this simple behavior to start with and update the AI to use elevators through the same button interface as the player.

The first step is to decide if the AI wants to use an elevator based on a random dice roll. If so, we find the nearest reachable elevator, in case there are multiple elevators in the current office building. An elevator destination isn't available if this person is in some area such as a basement that can only be reached by stairs. The AI will also choose a destination floor that's reachable by the elevator and not equal to the current floor. Then the path goal is set to a point in front of the elevator doors near the call button(s). Once the person has reached this point, the correct call button is pressed to summon the elevator to that floor. When it arrives and the doors are fully open, the person can enter, turn, and press the destination floor button. When the elevator arrives at the destination and doors are fully open, the person can exit to a point in front of the elevator, and then select a new non-elevator destination. The elevator itself takes care of moving between floors and opening and closing doors so that the person AI doesn't need to worry about this.

It was challenging to get this system working properly. One common failure mode involved people getting stuck somewhere or in a state that they couldn't get out of due to the interactions of other AIs or failed elevator behavior. To prevent this, I added a maximum wait time of 60s for people. If the elevator doesn't arrive in that time, they give up and select a new non-elevator destination. This may result in elevators stopping at floors where no one is waiting, but I guess that's realistic.

Here's a video showing an AI person using an elevator at this stage. I follow this person into the elevator but don't interact with it myself. I haven't made the elevator lights update for people yet; this was added later and will be shown in the next video.

 

This system works fine when there's only one AI using the elevator. It breaks down when another AI, or even the player, tries to use the same elevator. This is because my elevator controller is too simple. It only keeps track of the most recent destination floor button that was pressed, and ignores the current up vs. down state of the elevator. It's sort of like a remote controlled car that is only intended to be used by the player. It will go up and down as the player desires and can change direction at any point. Our simple elevator controller isn't up for this task and must be rewritten.

New Elevator Controller

The new elevator controller must use a queue to track call button presses and execute them in the order they were activated so that the first person to press a button gets the elevator. This isn't how real elevators work, but it's the simplest next step and moving in the right direction (pun intended). A simple call button queue is enough to fix the problem of the player getting into the elevator with the AI, pressing a different floor button, then having the AI get stuck when the elevator stops on the floor the player selected rather than the floor they expected. Now the elevator will first go to the AI's floor, where it will get off, before moving to the player's floor. This works similarly with multiple AIs trying to use the elevator, though there are still some issues. Well, many issues, as you'll see below. Now the player can get in and press all of the elevator buttons, and it really will tie up the elevator and trigger that 60s wait timeout for most of the people who are waiting. Just like in real life.

One problem is that a simple queue may result in the person in the elevator riding up and down following the sequence of call buttons pressed by others waiting for elevators. A real elevator controller will give priority to buttons pressed by riders from inside the elevator, so this is what I did. However, it does raise the question of whether or not the elevator is "fair" to all riders. For example, say someone is waiting on floor 1, but there's a steady stream of people going back and forth between floors 2 and 3 such that someone is always in the elevator. Does one of the floor 2 <=> 3 riders have to take an extra stop down to floor 1, or does the floor 1 rider have to wait forever? How does a real elevator behave? I'm actually not quite sure how my elevator works in that situation; the code has grown too complex to figure this out.

Next, there was the problem of elevators passing through called floors without stopping and constantly changing directions. Real elevators will stop on intermediate floors that have people waiting as they pass through them. I changed this as well, and things were working much better.

One more problem is that people were getting on the elevator when it was moving in the wrong direction. For example, they wanted to go up, and got on when the elevator was going down. It's not too big of a deal with only one elevator, but it does cause problems when I start introducing a maximum capacity for elevators (see below). This is another limitation of my simplified elevator controller: It was missing separate up vs. down call buttons. Once I added these, the elevator would pass through a floor without stopping if it was going in the direction opposite the call button. But now I had a problem where the elevator arriving on a floor that had both the up and down call buttons active would reset both states so that neither call button was active. Fixing this required tracking up vs. down calls as separate events and changing the queue to be able to split and merge them. In addition, I now had to track/calculate the next direction the elevator was to move after the stop so that I knew which call button state to reset. This took quite some time to get right, and at one point had a bug where elevators would get stuck on a floor with the doors repeatedly opening and closing in an infinite loop.

Multiple People in Elevators

Up to this point, people inside the elevator would simply stand at the center of the elevator car facing the doors and stack up on top of each other. I added a capacity value to elevators and started it at 1 to make things easier. This solved some problems, but now required me to handle people wanting to enter the elevator when it was at capacity. Here there are two cases to consider: whether or not someone was getting off on this floor. If the person was getting off, then the elevator had extra capacity, and I only needed to handle the two people crossing each other through the elevator doors. I used the common practice of having the person in the elevator exit first, then the person waiting enter the elevator. However, the person who was exiting would sometimes push the waiting person out of the way, and that person wasn't able to enter the elevator before the doors closed. The solution to this was to add door sensors that will open the doors back up when someone intends to pass through them. (Note that here I'm checking for the <enter elevator> state rather than checking that the person is physically between the elevator doors. This avoids needing logic for re-pressing the call button if the doors have fully closed by the time the person reaches them.) Similarly, since we're overriding the timing of the elevator, I had to add a new constraint that the elevator can't move until the doors have closed completely.

Now to handle the second case where the elevator arrives at capacity, someone is waiting to enter, and no one is exiting. There are two acceptable behaviors for the AI who is waiting. They can either give up waiting, select a new non-elevator destination, and walk away. Alternatively, they can continue waiting and re-press the call button once the elevator has left the current floor. If they were to immediately re-press the call button it would cause the doors to remain open forever. I think this is standard elevator behavior, at least when there are no explicit door open/door close buttons. This situation requires adding more timers and state to the AI state machine. In the end I couldn't decide which approach was better, so I had the AI pick one based on a random coin toss. This way a group of people waiting for the elevator will have a subset of them walk away if there's no space.

But that's not enough! One of the people walking away could either be stuck between others who are waiting, or will push someone out of the way, possibly through the walls of the elevator. Okay, the person being pushed now needs to actively move to avoid being pushed into the elevator. I don't know  how to handle the case of someone getting stuck between others, so I guess for now they stay suck and will unintentionally wait for the elevator (in some mid-animation state with a foot up) until their neighbors either get onto the elevator or give up waiting and walk away.

I forgot about the case where people push each other around trying to get to the designated waiting area in front of the elevator doors. This is actually more likely to push someone into the elevator than the case above. While the resulting behavior will work all of the AIs out eventually, it makes a mess and looks unnatural. In reality people will form lines waiting, so let's do that. When a person bumps into someone who is waiting at the same elevator they're trying to get in, they stop at their current location and wait from there. That ... actually works really well. Ah, finally some solution to a problem that works and doesn't require solving multiple smaller or less common problems.

Wow, that was a lot of work! We're done, right? Not so fast. I haven't discussed how to avoid stacking people on top of each other when the elevator capacity is greater than one. The way I handled this for swarming rats was to check the destination of each rat against the destinations of all previous rats and assign it a unique position. The offset relative to the other rats was chosen consistently so that they moved as a formation. Unfortunately, I can't use this on people in elevators because they're not a coherent group. We have people incrementally entering and leaving the elevator, so we can't pre-assign everyone a slot. It has to be fully dynamic. The first person stands in the center. When someone else enters, the original occupant moves to one side and the new arrival takes the other side. That all seems reasonable, at least until we consider the case of people exiting. What if the person in the back needs to get off at this floor but someone is in front of them in the way? Does the person in front have to move to the side, or temporarily exit the elevator to let the person in the back out? Consider how complex this situation is in real life. I have no idea how to implement this in the code and I'll leave that for some later time. Moving on...

Here's another video where I have 20 different person AIs attempting to use a single elevator in a 19 story office building. The elevator capacity has been set to 1 to keep people from intersecting each other when inside the elevator. However, they may still cross through each other when entering and exiting the elevator, as is seen in the beginning of the video. It's either this, or one person pushing the other, possibly into the elevator with them. I have a config file option/variable to select between these two behaviors. Currently people give up waiting for the elevator after 60s, which is why the elevator sometimes stops on a floor with no one waiting on it. Also, at the end I can't properly click on the elevator button with the Windows gaming overlay recording enabled for some reason.

In case anyone is curious about the clicking sounds, that's the automatic office room lights switching on when motion is detected and switching off again after 30s. I should limit the sounds to only play when the player is on the same floor of the building as the light. ... Done.

I put some more thought and experimentation into the problem of people passing through each other when entering and exiting the elevator. My first attempt was to check if someone else was waiting in front of the elevator where the person exiting the elevator was intending to walk. If so, the tangent to the collision point is calculated and the destination is adjusted in this direction. That works in some cases, but in others causes the person exiting the elevator to circle around and eventually merge with the person waiting to get in! I'm not sure what the problem is, but I would rather try a different approach than debug that one. Next, I tried to have the exiting AI stop and turn when they collided with someone who was waiting. This sometimes resulted in the AI blocking the way of the other person and getting pushed back into the elevator when that person entered. Neither of these solutions would work in the case where the front of the elevator was blocked by a group of people like in the screenshot below.

You Shall Not Pass!

In this case, we need to have the waiting people move out of the way first. But we can't simply have the "primary blocker" (person in the center) move to the side, because other people are already there. So ... it has to be some complex chain of movement? Sigh. I'll continue to think about this later.

Okay, later has come and gone. I *think* I have it working for the case when there are only two people. The person in the elevator walks forward until they're clear of the elevator, then chooses a point to the nearest side of the person standing at the center, if there is one. Since we're not turning until we're outside of the elevator, this should prevent us from clipping through the doors when exiting or getting pushed back inside (as the exterior walls act as colliders). There should always be enough space between the person waiting and the elevator doors that we can walk around them, assuming the line forms behind or to the side of the first person rather than in front of them. That should probably hold true. This solution appears to work well when one person is waiting either at the center or to the side. Unfortunately, when there are two people standing side-by-side like in the screenshot above, the AI exiting the elevator will usually walk through one of the side people. I suppose that's good enough for now.

New Elevator Display

One final change I made was adding a floor number and direction display on each floor, outside the elevator by the door and above the call buttons. This will show the current floor the elevator is on and arrows indicating which direction it's moving when not stopped. Since I already had text drawing support, I made the arrows out of 90 degree rotated "<" and ">" angle bracket characters. Maybe it would have been better to reuse the turn arrow textures from city streetlights? I don't know, at least it fits with the drawing style of the numbers.

Here is a screenshot of an elevator interior control panel, in case you didn't catch it in one of the videos.

Interior of elevator with 19 floors.

And a screenshot of the elevator exterior showing the two call buttons, floor display, and up/down indicators. Sorry the screenshot is somewhat dark. This particular office doesn't have a ceiling light in front of the elevator.

Exterior of elevator viewed from floor 12 with it currently on floor 13 and going up.

That's it for this post. I'm not sure what the next step is. I might attempt to add support for multiple people in the elevator (capacity > 1), or possibly find a better solution for people crossing through each other when a pair is entering and exiting the elevator.

Procedural Buildings: Extending Basements/Underground Rooms

Months ago, I added basements to 3D World’s procedural buildings, including both houses and office buildings. I quite liked the darker underground rooms. They gave zombie gameplay mode a scarier feel, and the lack of windows made it more difficult for the player to navigate this area. Now I've taken it one step further by adding "extended basements" to houses, which are a series of underground rooms connected by mazes of hallways. I like to call this the dungeon.

The first version consisted of a tree of branching hallways, where each hallway had up to four other hallways connected to it at right angles with doors. Then I assigned the dead end (leaf) rooms as other types such as storage rooms, bathrooms, card rooms, etc. Since it can be pretty disorienting to walk around here, I enabled the placement of rugs and pictures on the walls to make the hallways more recognizable. Each room also has a row of lights spaced out along the ceiling that the player can turn on and off.

Each room is placed with a variety of constraints to keep it from intersecting other objects. One constraint is that the entire ceiling area must be under the surface of the mesh. I was initially worried about tree roots poking into the occasional room, so to handle that I simply don't draw trees (or any vegetation) when the player is in the basement. Next, I had to make sure none of the rooms intersected other rooms or the house's basement. Finally, I had to check for intersections with other buildings, including their extended basements. It's okay for these extended basement mazes of nearby buildings to wrap around each other. They sometimes do just that.

Now this is more tricky than it would seem because building generation is multi-threaded and in theory two threads can be attempting to add basements to adjacent buildings at the same time. Of course the probability of that is likely very small, given that there are 16,000 total buildings to be processed in a random order. My partial fix for this is to block off the area around a building until all of its rooms are placed, which should at least avoid intersections with the main building and basement. However, it may not matter anyway, since only the building the player is currently in is drawn when they're in a basement. In theory there could be two basements on top of each other and the player will never know - though I guess I won't know for sure what happens until I come across that situation.

But how do we determine which building the player is actually in when their location is inside two overlapping rooms from different buildings? My fix for this is to keep track of the building the player is currently in, and only allow it to be updated if the player leaves the building. This way it's not possible to move from one building to another in two consecutive frames without being outside all buildings for a frame in between. While that works well, it may interfere with my future plans of connecting the basements between multiple buildings as a way for the player to move between buildings underground. That's an area for future work.

This looked good, but it was too difficult to get cornered by a zombie at a dead end. I decided to add loops to make it more like a maze and less like a tree. Any placed hallway that happens to fully intersect or cross a previously placed room will now connect to it with a door. This means that some of non-hallway leaf rooms are no longer dead ends, which increases the variety of these floorplans.

But that wasn't enough. What's better than a dungeon-like maze of underground hallways and rooms? How about a multi-level maze! So I went about adding stairs and multiple floors, and after a long time spent debugging failed basements I was able to get it to work. I have the number of floors limited to 3 in the config file to keep the extended basements sane, though there's no hard limit other than that the lowest floor needs to be above sea level. Lower levels are added by inserting stairs at the end of a hallway and ending the stairs at the entrance to a new hallway one level below. Lower levels are allowed to cross under upper levels and reconnect with hallways and stairs that lead back up. Some stairs have railings to add variety.

Here are some screenshots of extended basements shown from above, to give a better idea of their overall layout. I've disabled the terrain and grass so that they're visible. All surfaces have back face culling enabled, which is why the ceilings aren't visible. Keep in mind that rooms weren't intended to be viewed through the terrain like this, so the lighting is all wrong (among other problems).

Building extended basement viewed from above, with terrain, grass, and ceilings hidden. 2 levels.

Another extended basement viewed from above, with terrain, grass, and ceilings hidden. 3 levels.

Huge underground basement complex on multiple levels that runs underneath other buildings.

Generating and drawing these added rooms wasn't too bad, but that's only a fraction of the work. I had to make room lighting, shadows, and indirect lighting work. Ray casting and collision detection were more difficult when there are no exterior walls to bound these rooms. I had to make the AIs for building people understand how to navigate down here, follow the player, and cross between the house and its extended basement. Note that the structure down here is very different from the packed rectangular areas of the above ground parts of the buildings. There's empty space (or I would assume dirt) between these rooms, and that's a great place for the AI to get stuck. Finally, I had to make rats, snakes, and spiders properly handle these areas. This means I actually have to make these rooms work with 4 different AI systems! Overall I was able to share most of the code, but I did have to add quite a few special cases to the code.

Here are some screenshots of extended basements shown in the intended way where the player is inside the rooms rather than looking down with X-ray vision. You can't see too much at any given time due to the narrow hallways and right angle turns.

Extended basement with three levels (two sets of stairs) along the same hallway.

Extended basement hallways and rooms with a person, a rat on the floor, and railings for the stairs.

Even extended basements contain bathrooms, with mirror reflections.

I'm sure there are many future extensions of this system. As mentioned above, I would like to consider connecting the basements of adjacent houses that happen to be at the same elevation. It may also be interesting to add more basement and parking garage areas to office buildings in a similar way. I made some of the basement lights flicker, but I'm sure there are other interesting effects that I can add to increase the spooky atmosphere of basements.