This is take two on global distance field Pathfinding.
I could improve the previous version a lot in terms of performance and quality. The technique changed a bit, now it is a mix of raycasting and gathering/flooding which results in very quick coverage of the whole map and very accurate results.
The whole algorithm runs in realtime on the GPU and is implemented in OpenGL/GLSL and processing/Java.
From DistanceField to FlowField
Also new in this version is the use of flowfields.
The main output of the algorithm is a global distance field, which stores at each pixel the actual global distance of the shortest path from that pixel to the (nearest) target.
The flowfield is created by getting the gradients of the distance field. This can simply be done by computing the difference of the top-bottom and left-right neighbors at each pixel. For better results the diagonal neighbors can be included and neighbors can have different weights -> Sobel Filter.
https://github.com/diwi/PixelFlow/.../flowfield_create.frag Sobel Horizontal, X-Gradient -1 0 +1 -2 0 +2 -1 0 +1 Sobel Vertical, Y-Gradient +1 +2 +1 0 0 0 -1 -2 -1
The result is a vector-field, where each pixel stores the direction/velocity (2d vector) of the gradient, in contrast to the distance field, which stores the global distance (scalar).
A flow-field (a.k.a vector field, velocity field, etc…) can further be useful for particle simulations, smooth paths, streams etc…
It is of course still a multipass algorithm. The number of required passes is however very small so realtime simulation on dynamically changing scenes and targets (multiple) is feasible.
Particle Simulation, Streamlines
There is also a nice new feature that adds particle simulation to simulate pathfinding in a more natural way.
This also enables the visualization of streamlines by simulating particles spawned on a regular grid accross the map and draw their trails.
The streamlines are costly in rendering. But it is no issue to simulate and render millions of particles in realtime. (This is a new algorithm I am currently working on).