Consider a pathfinding problem on a undirected grid graph. We want to get from (A) to (B). It would be nice to check if a path exists at all, before launching any time-consuming attempts.
We don't need the path itself, just an answer to the question:
Is B reachable from A?
There is a simple, fast and beautiful algorithm with great scalability that answers this question, called: Union-Find
To investigate two points, (A) and (B), on a grid graph.
The Union-Find code example is able to tell wether 2 nodes are connected. Either directly or through neighbours.
Write a class that instantiates a Union-Finder. Make room for N nodes, where
N = length x width.
1) Visualise the node ordering like follows:
2) Connect nodes using the union method, use ID's considering the ordering above. To make a vertical connection between node-3 and node-10:
EXAMPLE finderInstance.union(3, 10);
3) Query reachabillity between (A) and (B) through the command
The above algorithm is more specifically called:"Weighted quick-union with path compression". The amortized cost [?] per operation for this algorithm is known to be bounded by a function known as the inverse Ackermann function and is less than 5 for any conceivable practical values of N.
An alternative solution is given in the paper "Optimal decremental connectivity in planar graphs", by Jakub Łącki, Piotr Sankowski. Which is said to run in constant time per query/operation. PDF download is at the right. Anyone tried this? Please let us know in the comments below.
The above can be applied to VectorRacer as well. For instance: to check if a track is valid before computing AI paths.
Consider the car accelerating and then immediatly braking each time. Moving 1 position and then comming to a full stop.
This stop-and-go driving removes the momentum from the equation and simplifies to the above grid graph problem.
You wouldn't be fast riding like this, but for that we have different algorithms :)