In this post I am exploring a lazy, (somehow) entertaining method to do path-finding.

The idea of this can be captured simply:

Walking randomly will take us anywhere

If an actor is walking randomly on a terrain, no matter where they actually mean to go, they will eventually get there – whether the target is moving or not. A more interesting variant of the above involves stigmergy. An example of stigmergy is provided by ants dropping a ‘scent’ on the ground for other ants to follow. In this case the environment is used by agents to share information, which is pretty much what stigmergy is about(*).

Pathfinding using particles

I am not suggesting actors should be roaming randomly, however. Instead, here’s the idea:

• Actors and items (targets) function as particle emitters
• Particles travel randomly onto a navmesh (this could also work with waypoint interpolation)
• Whenever a particle reaches a new site (another triangle on the nav-mesh), its age is increased.
• To reach a target, agents follow particles ‘back to the source’.

I have been thinking about this for a while and tried to simplify it in order to avoid overheads. For example, we could actually keep track of the distance from a particle to the source, or integrate signals (that is, two particles referring the same target cannot co-exist on the same site); or a particle could maintain a ‘history’ of visited locations. All this stuff would require more memory, more reallocations and more development time, so until we have a good reason to add this or that (e.g.: we actually believe this will somehow benefit in some way), there’s no reason to worry about this or that.

Interfaces

Before going further, it’s probably useful to figure a few interfaces that clients will use to interact with the path-finding system.

• SPListener is used by a client to observe particles from an agent’s neighborhood. The interface identifies the type (the kind of object detected, e.g. bread, a flower, a rat etc…) of the particle and it’s source – agents only receive signals from their immediate neighborhood on the navmesh.
• SPEmitter is implemented by clients that act as sources. A registered emitter can return it’s location on the navmesh and it’s type, so we can generate particles from that location.
• SPNetModel is implemented by the navmesh (or a wrapper) and is used as ‘propagation model’. In other words, it is used to retrieve the neighbors of a given site on the mesh. It is also used to retrieve listeners local to a site.

Finally SPSystem allows clients to perform the following actions:

• Register an emitter
• Update particles
• Configure the number of particles maintained by the system

System behavior

At each iteration, the system will perform the following operations:

1. Generate new particles. Typically new particles will override older particles, and this happens at a set rate.
2. Update all particles. Each particle will be moved to a new (randomly selected), nearby site and it’s age is increased by 1.
3. Notify listeners. Every time a particle has reached a new site, listeners interested at the same location will be notified.

What’s the point of doing all this when we already have A*?

Compared to regular path-finding, this method probably has disadvantages. For one, it hardly warrants an agent will use the shortest route to reach a target. However, it does have a interesting features:

• We directly control the balance between resource allocation and accuracy. By controlling the number of particles and the frequency of updates, we control memory allocation and CPU overheads.
• We don’t need to worry about the number of agents or targets, or how often agents need to use path-finding. The overhead of notifying agents is marginal. Adding emitters doesn’t directly increase processing overheads.
• Performance degrades gracefully. We may lose in accuracy and liveliness if we under-allocate resources, but at least there’ll be something going on with agents roaming around and homing onto their targets ‘more or less randomly’. So we can scale down overheads on lower performance devices, or temporarily reduce update rates if we want to allocate more resources to, say, rendering, or something else.

(*)This method has been used in games for quite a long time. Recording the PC’s ‘track’ on the terrain may be one of the oldest, cheapest and most reliable ways to do path-finding.