Pathfinding to everywhere
Publication date: 30 August 2012Originally published, in a shorter version, 2012 in Atomic: Maximum Power Computing
Last modified 25-Sep-2012.
The glory of mathematics is that it's completely abstract, by definition, but can apply to a very large number of real-world situations. The classic kid's Algebra Objection - "when am I ever going to use this?" - can have some surprising answers.
Take pathfinding, for instance.
Pathfinding is part of "graph theory", the mathematics of connected objects, which is about as broadly applicable as the name suggests. Any things that are connected physically, logically or even in some cases figuratively, with paths between them that can be traversed in some way, is amenable to graph-theory analysis.
In computer games, pathfinding is what lets an entity in a game - a unit in an RTS...
... or a monster in an RPG - get from one place to another, without being guided through every navigational choice by the player.
Pathfinding in 3D action games frequently just cheats. Since it's easy to break down most 3D-game maps into relatively few chunks each of which has relatively few paths to other locations, invisible pathfinding rails, known as "navigation meshes" or "navmeshes", can be baked into each map. So even if you've got Serious Sam monster-hordes, they'll all be able to get where they're meant to with no need for CPU-intensive thought. In open maps like the countryside in a sandbox game and the numerous open arenas in the Serious Sam series...
...entities can usually just run in a straight line to wherever they want to be (like, close to the player, in order to try to kill you), and turn only if they strike a cliff or tree.
This simplification of pathfinding and other AI functions is what made, for instance, the enemy soldiers in Half-Life seem so clever. Put a bunch of those soldiers in a small room with no behaviour hints and briefly show them Gordon Freeman through a door, and they'll immediately erase any perception of intelligence by declaring a festival of friendly fire that the monsters in Doom would consider stupid.
(Pathfinding algorithms can also be used in reverse, as it were, to create features in randomised game maps - mazes, rivers and so forth.)
RTS games have to be smarter about pathfinding, because there can be large numbers of units trying to get from A to B...
...and they're probably not allowed to walk through each other. Getting each unit to dynamically figure out where bottlenecks are and whether they should wait their turn to go through or take a longer route - which could easily be useless, suicidal or both - creates a combinatorial explosion of pathing decisions which can easily take up way too much CPU power, even on a cutting-edge PC.
Pathing techniques that can get a bunch of robot warriors through a narrow mountain pass can be used for other things, as well.
(Heck, Frozen Synapse...
...even looks like a computational-geometry simulation.)
An unexciting but very important application for pathfinding algorithms is computer network routing, on anything from a home LAN (where routing is generally trivially simple) to the whole Internet (where it really, really isn't).
It's normal for there to be several routing steps just between you, a home Internet user, and your ISP's servers. The billions of nodes on the entire Internet connect in ever-shifting patterns, as particular routes get clogged or broken. An enormous amount of routing hardware works collaboratively to connect as much of the Internet as possible via the fastest routes possible.
Simple pathfinding algorithms are also used in any paint program that has a flood fill, or its more modern descendant the magic-wand selection tool, both of which can be thought of as "pathfinding to anywhere", starting wherever you clicked.
Flood fill affects all contiguous pixels the same colour as the one you clicked on, flowing up and then down from the selected pixel (or down and then up, or occasionally both ways at once). The magic wand does the same thing, but with a configurable allowance for how different pixel-colour can be and still be selected. This looked pretty impressive when I first watched it happen in Opal Paint on the Amiga in 1993, but modern computers are so fast that you can't see it any more.
Road navigation is a problem somewhere between flood-fill and Internet routing in complexity, because the graph of roads and towns stays pretty much static. But it has some of the real-world problems and complications of network routing, and can have more disastrous results for end-users who find themselves in a two-hour traffic jam, or directed up a dirt road and over a cliff that their GPS didn't know about.
A lot of the extra complexity comes from the fact that real-world networks usually don't have paths between nodes that're all the same, so relatively simple shortest-path calculations aren't useful. Real-world networks are, instead, usually "flow networks", in which connections between nodes have limitations in the amount and direction of traffic they can handle. Flow-network pathing can be used in a game to let an army plan to avoid a traffic jam before it actually happens, or by municipal planners to lay out traffic lights and roadworks to minimise real traffic jams, or for lots of other applications. Water and sewage transport, electricity grids, meteorology, and plenty of applications in biology and zoology as well.
Even today, computer simulation of complex analogue systems like this can be very challenging. Game programmers can't just say "OK, every unit evaluates every possible way it can get from A to B, negotiates with all of the other units to avoid jams, and then heads off". Doing that, if you've got more than a very few units, is about as easy as forecasting the weather two weeks in advance. If two friendly armies are ordered to follow paths that intersect, you need some very crafty maths to prevent a ridiculous traffic jam, or a computer-choking combinatorial explosion of calculations. Or both.
But we've actually been computer-simulating very complex systems, like the forces and control inputs affecting a car, or the behaviour of national economies, since well before the invention of the transistor. The trick is to make an analogue computer, not a digital one. If you're modelling something that behaves like a fluid flowing through various tubes and constrictions and valves and pumps and reservoirs, just build an analogous collection of plumbing, put some water in it, and start computing!
The most famous "water computers" were the Monetary National Income Analogue Computers (MONIACs; they were also rather wonderfully known as "Financephalographs"), invented in 1949.
(Image source: Flickr user psd)
They were meant to be educational simulators, but turned out to be at least as good at predicting economic events as human economists, not that that's saying much. More practically, the baffling maze of hydraulic hardware in an automatic gearbox is, in essence, an analogue computer running a gear-selection and clutch-control program dictated by its structure.
Sometimes the theory of finding paths through graphs of nodes applies obviously, as in network routing and GPS navigation. But it's lurking in loads of other areas. Blood circulation. Shifts in animal populations. What people buy, and what sellers charge. And, yes, the sometimes-sensible, sometimes-idiotic movements of Mammoth tanks and Belltower mercenaries.
So, in this case, the Algebra Objection can be answered: "Is ten times a day enough for you?"
