Global Distance Map

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).

Global Distance Map – IsoLine Shading

 

 

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.

Random Walk, Pass 4

Random Walk, Pass 8

Random Walk, Pass 16

Random Walk, Pass 32

 

 

 

Maze Test

Random Walk, Pass 32

Random Walk, Path + Distance

 

 

Artifacts, Discontinuities

 

Update

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.

 

New Version

Random Walk, Pass 64, New

Random Walk, Pass 64, Iso, New

 

Old Version

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.

Random Walk, Pass 8

Random Walk, Pass 64

Random Walk, Pass 512, stuck at discontinuity

Random Walk, Pass 2288, discontinuity slowly getting fixed

Random Walk, IsoLines

 

 

Targets

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.

Random Walk, Multiple Area Targets

Random Walk, Multiple Area Targets, IsoLines

 

Extension

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.