God is in the details.
Ludwig Mies van der Rohe
A very fast overview of our fast AI
One of our main goals in Project Highrise has always been to make buildings feel alive, filled with people whose daily comings and goings create an irresistible bustle. In addition to the aesthetic feel of that, the people’s daily activity drives the economy of the building.
Our “living building” objective requires a large number of people. We gave ourselves a performance goal: the game needed to be able to run with 1000 NPCs at 60 FPS on a reasonably recent desktop-grade personal computer.
1,000 NPCs at 60 FPS. Click to make the madness larger.
This posed an interesting implementation challenge. We’re a tiny team with only one programmer whose job is not just AI, but also to build the entire rest of the game as well. So we needed a system that was very fast to build, required very little ongoing maintenance once it was built – and primarily, helped us reach our goal.
We wanted to have our people live very stereotyped, routinized lives – following a predictable daily routine that will give rise to that feeling of a bustling highrise building. We also wanted to have a lot of designer control over those daily routines, to enhance the fiction of the game – so that worker and resident behavior would match their socio-economic status, but at the same time, have a lot of variety and quirks for “flavor”.
This is called an “action selection” problem, which is something that game character AI has to do all the time: figure out “what should I be doing at the given point in time?” In Project Highrise, we built this in layers. First we build individual actions (like “go somewhere” or “sit down”), which are simple and atomic. We then assemble those actions into stereotyped scripts, which are descriptions of simple daily activities such as “going to the office”, “going to a sit-down restaurant and sitting down to eat”, “processing a repair request from a tenant”, and so on. Finally, those scripts are then be bundled together into various daily schedules, with simple logic for picking the right script based on current conditions such as time of day, and equally simple “working memory” (which remembered, for example, where the character wants to go, where their current job is, where their current home is, and so on). In terms of computational cost, this selection process is trivially inexpensive.
So an office worker at a basic office only has a few things to do in their daily schedule:
{ from 8 to 16.5 tasks [ go-work-at-workstation ] }
{ from 16.5 to 8 tasks [ go-stay-offsite ] }
From 8 am until 4:30 PM. they go do work at their office. Then at 4:30, they go “offsite” (by that we mean “home”). While at the office, there could be several things that could impact their routine. For example, if the office is run down, the worker will react negatively. If there are too many stairs they have to climb to get there, that will make them upset. And there are many more things that might impact the happiness or unhappiness of the worker.
They also can have a series of one-time actions that are possible, so for example the basic office worker that we looked at above also has this:
{ at 12 prob 0.5 tasks [ go-get-lunch ] }
That means that at noon, there’s a 50% chance that the officer worker might want to go get lunch. So is there a place to get lunch? If there is, great! The worker will head there and buy lunch, and the restaurant will benefit from being patronized by a customer. If there’s no place to have lunch or the lines are too long, then the worker will get unhappy. We can control all of that behavior by simply adding the one-time event of “go-get-lunch” into the daily schedule.
We can then begin to chain these things together to make more complicated schedules that have more complex outcomes. Let’s look at how we schedule an resident who works out of the apartment in a home office:
{ at 10 prob 0.5 tasks [ go-get-coffee ] }
{ at 10 prob 0.25 tasks [ go-get-breakfast ] }
{ at 13 prob 0.25 tasks [ go-get-lunch ] }
{ at 16 prob 0.1 tasks [ go-run-errand-2h ] }
{ at 19 prob 0.5 tasks [ go-visit-retail ] }
{ at 20.5 prob 0.25 tasks [ go-get-dinner ] }
This is a much busier day than our office drone. There are probabilities that they’ll want to at various times of day get a coffee, get breakfast, get lunch, go shopping and get dinner. Plus maybe a few errands here and there.
These schedules represent the ideal routine for each resident or worker. Players must try to accommodate these routines. If they succeed, the people will be happy. It’s when the routines break down that unhappiness begins to seep in. Unhappy apartment residents may soon seek a new home. Unhappy office workers may contribute to an office moving out.
With the action selection question answered, we moved on to pathfinding. Once our (potentially) hundreds of people had decided what to do, how would they go there without causing a huge hit to performance?
The game takes place on what is essentially a 2D grid – a cut-away side view of a building, which can be, say, ~100 stories tall and several hundred tiles wide , depending on the scenario. A naive implementation of A* pathfinding on the raw grid representation quickly turned out to be insufficient, with hundreds of NPCs trying to navigate the grid at the same time.
So we reformulated pathfinding so that, instead of using a simple grid, we built a specialized compact graph representation, which had support for the user changing the path graph all the time (as they built, altered or expanded their highrise). Based on the game’s design, the pathable space divided up into distinct floor plates, which were contiguous sequences of tiles on the same floor, such that the character could do a straight-line movement inside a floor plate. Additionally, each floor plate was connected with those above or below it via stairs, escalators, or elevators, together known as connectors. Floor plates and connectors became nodes and edges in our high-level graph, respectively, and movement inside each floor plate became trivial.
A path! A path! Click for larger.
This search space reduction was significant: for an example of a dense building 100 stories tall by 150 tiles wide with four elevator shafts, we reduced the space from 15,000 graph nodes to only 100, with 400 edges between them. This made pathfinding performance fast enough that we could still just run A*, but on a much more compact data model.
Finally we wanted to take care of the worst case scenario, which is when a lot of people accidentally all want to perform pathfinding at the same time (imagine a movie theatre, when the movie ends and everybody wants to go home). If this happens on a single frame, even an efficient pathfinding system would have a lot of work to do – and in order to maintain 60 FPS, we must limit each frame to take ~16ms in order to prevent framerate hiccups. So we resolve that by implementing a simple job queue system with a limiter, such that in the case of that worst-case scenario, we spread the queue of pathfinding requests over multiple frames, instead of doing them all at once.
And there’s a very fast overview of our fast AI! Next time we’ll talk about the design side of things, and the kinds of design variety that we can get out of this system.
(PS. If you want to read more about our AI, we’re going to have a much more detailed paper coming up in the upcoming book “Game AI Pro 3”: http://www.gameaipro.com/ )
