There are already a couple of well tested and approved pathfinding algorithms available. My current approach is a bit different and is based on my recent 2D Global Line Radiosity and SpaceSyntax experiments.
The basic idea is to simply “search” for the shortest path.
This doesn’t sound very useful and efficient at first but since my render-core can handle billions of ray-scene intersections per second on only modest hardware I found it interesting to give it a try.
This method can also be directly applied to 3D scenes (including Voxel scenes).
Algorithm: Convergence and Spreading
In some of the previous posts I already described the nature of the algorithm and its characteristics in more detail.
The following screens show the chaotic generation of paths of random length. The main target is a small white rectangle on the lower left of the map.
In the first image it seems like random rays are emitted from the target and make their way randomly through the scene.
How it really works is: Random rays are generated for every pixel in the map to gather the shortest distance (+ the current ray length) at the found intersection. The pixel data gets updated if this new distance is shorter then the one currently stored.
This issue described here is fixed by now due to much better samping. As a result much less passes are required to get an even better coverage and convergence rate.
As shown in the following images, there are cases where it takes unreasonably long to get the shortest paths updated. TBH i am not 100% sure if this is due to the nature of the algorithm, or some kind of bug during sampling, etc … . It is not a big concern for me at the moment since a regular path can still be build, but it certainly needs further inspection.
One of the neat things of this method is that it performs better the more targets are in the scene and the bigger the targets are. Similar to my radiosity-renderer, that converges faster the more lights are added to a scene.
In further experiments I am using this process for propagating and integrating other quantities than just distance. For example the least amount of bounces/turns, etc… .
This is the base for more complex global Space Syntax Analysis – in 2D as well as in 3D.