The importance of custom-built solutions

It's only been somewhat recent that we've seen a massive surge in game development middleware. It used to be, not long ago, that games were entirely custom-built from the ground up. These days you can find an off-the-shelf product for nearly every task in game development, and you might even wonder where you would be without them.

But sometimes, you have a use-case so wierd, so uncommon, that there's just no product for you. You've tried everything, from the industry-tested AAA products to the backwaters-of-the-internet open source solutions, but nothing works.

And that's when you custom-build it.

I just recently encountered this while developing an open-world game project. The problem? How to make my AIs intelligently navigate a huge open world with pathfinding.

At first, as anyone would, I thought to myself, "There's such a HUGE number of pathfinding solutions for Unity. This should be a piece of cake!".

And that's where I was partially wrong. Yes, there's lots of them, but not a single one of them designed for even marginally big game worlds and also in my budget.

My first try was Unity's own pathfinding, basically a port of Recast. It failed right out of the gate, since it couldn't even export the scene data to be voxelized within a reasonable length of time.

My second try was Aron Granberg's pathfinding. I never had much luck with this one in the past, but I gave it another shot. Still no luck - it's grid generator seemed to have severe trouble generating a graph for such a large terrain.

Eventually I realized I needed something highly customized to my needs - something I wouldn't be able to solve with money. Time to break out the elbow grease and the thinking caps.

The problem here is that my world is designed a bit like Arma 2. There's a big 10km^2 island, upon which are various buildings which can be entered. Said buildings will NOT be separate zones, but luckily will be fairly simple (just a few rooms and hallways, not more than a couple stories, etc).

I figure I can divide this into separate graphs, which are somehow linked: A grid graph for my outdoor area, and a waypoint graph for my indoor areas. These will be linked with special navigation nodes (which I'll call "offmesh links" for lack of a better term).

My outdoor grid graph is simply generated based on the terrain's heightfield and "occluder boxes" (which I would use to punch holes in the terrain navigation grid). One really nice property of A* is that it does not explore much more than it needs to - so if my AIs are only chasing nearby opponents, even with a huge world there's still a fairly light workload on the pathfinder. I've also decided that I will not make the grid fine-grained enough to represent trees - it would take up a hell of a lot more memory than I would like, and I can just stick in some simple obstacle avoidance to navigate around trees. I've found a 512x512 grid represents my terrain quite nicely then, if I don't care about trees. I also added a cutoff to the pathfinder - if it explores more than 1000 nodes, it simply quits. This number is large enough that the AI can pathfind halfway across the map (I specifically tested this), but still small enough that if the AI tries reaching an unreachable island it will exit out long before it exhausts the search space.

One thing I needed was to make my pathfinding algorithm as generic as possible. To that end, I created interfaces for INode, IGraph, and ICostEstimator. A node has a position in the game world, a G and H cost (I don't really care about costs for traversing individual nodes, but that would be trivial to add), a graph it belongs to (entirely optional - for instance, offmesh links are technically INodes but do not belong to a graph), and neighboring nodes. A graph simply contains nodes and can locate the node nearest a particular point. A cost estimator estimates the H cost between a given node and the goal node (currently implemented are Manhattan and Euclidean).

Waypoint nodes have explicit neighbors - baked at design time by raycasting to waypoints in the same graph. Grid nodes, on the other hand, have implicit neighbors - these are calculated on the first request and cached for subsequent calls.

My waypoint graph also has a bounds property, which represents the extents of the graph. This is used in order to locate the nearest INode to a given world position - first all waypoint graphs in the scene are queried to check if their bounds contain the point. If one does contain the point, it is queried for the closest waypoint. The terrain grid is also queried for the closest point (which is found by quantizing the point and converting this to a 2D grid index). Whichever of the two points is closest is chosen.

This is used for two purposes - one, for pathfinding (first the start and end nodes are located, then pathfinding is performed), and two, for offmesh links.

Offmesh Links as mentioned before are a way to link my grid and waypoint graphs together. An offmesh link is a special type of node with exactly two neighbors. On startup, these neighbors are located by finding the nearest nodes to two points, and then the offmesh link is registered as a neighbor with both nodes (and therefore becomes a shared neighbor of both). By, for instance, placing one side of the offmesh link inside a building, and the other outside the building, the inside one will locate a waypoint, and the outside one will locate a grid cell. These two are then linked together via a shared neighbor. These nodes would be placed, for example, at the entrances of a building. The nice feature is that they don't care which type of nodes they link, so it's entirely possible to link two grid cells (for example, if there's a teleporter). If I wanted, I could also associated extra data with an offmesh link such as an enum of what type it is (for example, I could specify that a particular offmesh link is an elevator, which the AI would respond to by waiting for the elevator to arrive, getting in, waiting for the elevator to arrive at the appropriate floor, and getting out).

It took me two days to accomplish all of this, but it was well worth it. I added some extras as well, such as multithreaded pathfinding (all pathfinding work is offloaded onto a separate worker thread) with callbacks for when a path request is serviced. Pathfinding is reasonably fast, and agents can not only pathfind a fair around the world, but they can also pathfind in and out of buildings. None of this could be provided in a third-party solution, but was fairly quick to accomplish and fits my needs perfectly. It's also pluggable, which means I can reuse it in other projects and extend it (for instance, by adding navmesh support).

And that's why it's important to custom-build stuff - because when you're making a game that few others dare to attempt, you've got no choice but to build it yourself.