in biogrid, devblog, pathfinding

Deep Distance Field Pathfinding

 

Fancy name aside, here’s a tiny writeup on the custom steering-based pathfinding system I developed for BioGrid and implemented on the GPU using OpenCL.

I wanted to avoid using classic algorithms like A*, because the number of creatures and potential effectors on a creature might be rather large, especially considering that the creatures themselves will be dynamically scripted by the players.

I won’t know what kind of behaviour a creature will prioritize – will it try to evade predators? How skittish is it? Does it move in herds? How dense herds? Does it need to find a mate to reproduce? Is it picky?
I need a generic system for all sorts of overlapping, combined spatial queries, and this is where distance fields and Voronoi diagrams come into play.

In the opening clip, there are 4 different species in the world, trying to form a flock with members of their species. The only input a creature has into a system is the fact that it has a specific smell, or an aura that will propagate around it.

Here’s this map visualized on a bunch of pigs:

A wolf would only need to constantly check the 9 cells around itself and keep moving toward the cell that contains the maximum amount of “pig” to reach its closest meal.

 

Note that this “hill-climbing” doesn’t work if you’re trying to find the closest member of your own species – every step leads downwards from the top of the creature’s own hill. But then again, the data map already contains quite a bit of information that can be processed further – the propagation forms something like an approximate Voronoi diagram over time:

There is a way to find neighbours of Voronoi seeds – it involves computing a dual graph of the Voronoi – known as Delaunay triangulation.

However, my Voronoi diagram is not even close to accurate – it’s propagated, not computed in one step, so the best we can do here is an approximate triangulation.

I find the borders between the Voronoi cells and propagate information out from there again into a different data map – essentially making a new Voronoi diagram from the borders of a Voronoi diagram:

Now, if a creature moves towards the closest border, the first Voronoi diagram changes, which in turn is used to compute the second diagram, and  it’ll eventually lead the creature to the closest member of its own species.
But this system doesn’t have to be limited to just species – I can also propagate traits, like “female”, “wounded”, “small/medium/large” and similar. This provides a method of refining the creature’s query, giving them rich layers of data that’s cheap to access and shift through. They can be affected by several stimuli at once – a flock of herbivores moving towards a food source while keeping together and avoiding predators, all at the same time.

It’s a pretty wasteful method to compute – if I have 128 species on a 512×512 map, I need to update 128 512×512 maps, and at least a few dozen times per second! Basically, there’s a bunch of brute-force work here just screaming for optimization.

So far, I’ve managed to mitigate the costs by updating the maps incrementally and outsourcing the propagation workload to the GPU. I upload the “seed” data and get back arrays full of propagated distance fields, ready for use:

Write a Comment

Comment