NPC movement with Neo4j

TriadCity’s sophisticated "subsumption architecture" for NPC behaviors depends on accurate, comprehensive knowledge of game world geography. Unlike traditional MUDs where NPC movement is statically confined to home zones and is largely random, TriadCity is alive with highly individualized NPCs capable of purposeful navigation throughout the City.

For years the code enabling this directed movement has been a simple homegrown weighted graph mapping all possible paths from every point A to every other point B. Weights were based primarily on movement costs by alignment. Separate graphs were computed for Evil, Good and Neutral paths, plus specialized graphs for Cops and for residents of the Capitoline neighborhood — two categories of NPCs with restricted movement possibilities. The graphs were computed at server boot, following instantiation of all Rooms and the Exits linking them. They were static: unchanging after initial computation, essentially freezing NPC knowledge of world geography at the state of its existence at boot. And they were monolithic: an NPC could look up a path from the Neutral graph, or the Cop graph, but not a hybrid NeutralCop graph. For a long time this was "good enough for now." While inflexible, it enabled accurate if not always subtle NPC navigation from any arbitrary origin to any chosen destination. NPCs simply looked up their path and, following Dijkstra, off they went.

TriadCity eventually outgrew this simple design. We want to be able to accurately model arbitrary restrictions on NPC paths, for example, excluding NPCs from certain streets based on Role, or gender, or other classification. It's important for NPCs to react to more than one category of restriction. And we want their movement behaviors to be as "human" as possible, so, not necessarily always taking the shortest possible path, if the shortcut for instance leads through someone's private garden, or in one pub door and out another. Usually real people would go around the garden, or stay on the sidewalk outside the pub. We grew especially frustrated with our simple system's inability to track dynamic changes to the game world at runtime. It would have required a major project to extend our down & dirty proprietary code to handle these features.

Instead, we've chosen the excellent NoSQL graph database Neo4j as our solution. While the approach is essentially the same — a weighted graph based on Dijkstra — Neo4j's comprehensive query-ability allows us enormous flexibility at runtime. It easily enables the kinds of ambitions described above, with impressively little code.

We run Neo4j in embedded mode. Easy-peasy, since our server's written in Java. The database is populated during server boot after Rooms and Exits are loaded. Nodes are Rooms, Relationships are built from outbound Exits leading to destination Rooms. The algorithm's straightforward. Iterate the Rooms, define a Node for each; iterate a second time, catalog each Room's outbound Exits, look up the destination Room each Exit leads to, find the Node representing that destination, and define a Relationship between the origin and destination Nodes. We only need one RelationshipType: LEADS_TO. As each Relationship is defined we flag it with boolean properties representing the restrictions we want to impose: isNoCops, isNoBeasts, isNoHumans, isNoDeathSuckers, isPerformerOnly, isCapitoline, hasDoor, and so on; these properties belong to Exits and destination Rooms, so we simply look for them and set the flags appropriately. At runtime, NPC path lookups are via a PathFinder built by passing GraphAlgoFactory's static dijkstra() method a custom CostEvaluator which looks for the boolean property flags defined on Relationships and totals costs accordingly. For example if the calling NPC has the Cop Role, and a Relationship is flagged isNoCops, the CostEvaluator will assign a prohibitive cost to that Relationship — we arbitrarily use 100,000 — effectively removing it from consideration. When PathFinder searches for the least-cost path it'll choose one which bypasses that expensive Relationship. Managing the scenario where we want NPCs to go around a pub although the shortest path leads through it is straightforward: we simply assign a cost of 100 to all Relationships flagged hasDoor, so that generally NPCs will prefer not to move through doors unless they're the only paths available. Nice.

Implementing Neo4j required just a single class of about 300 lines, and took about half a working day including time spent tuning the costs.

Runtime performance is excellent. The Neo4j solution takes longer to bootstrap — about 5 seconds for 18,000 Rooms on my MacBook Pro, compared to just a few milliseconds for our deprecated home baked version. But, its runtime lookup performance is superior. We judge overall AI processing load by tracking average completion times of our one-per-second Behaviors pulse which triggers Behaviors throughout the game world. Average Behavior computation on my laptop was steady in the range of 120 to 150 milliseconds with the old grapher; with Neo4j it's been consistently around 80, an efficiency gain of 50% or better. Memory use looks about the same.

So far, runtime movement appears to be perfect. Everybody goes where they're supposed to, and they now do it with the subtle enhancements highlighted above. Importantly for us, it's now very easy to tune movement by simply adding new property flags to Relationships and looking for them in our custom CostEvaluator. And, we can easily enhance the system to adapt to runtime changes in the game world itself, for example when builders add new Rooms or 4d mazes rearrange themselves.

I'm impressed with how easy it's been to include Neo4j in our project. The API is intuitive and very nicely documented. I was able to take and tweak a Dijkstra example from the Neo4j web site with very little effort. Very pleased!