article

I encounterd this useful algorithm during a course at coursera.org. It has many applications, and I hope this article is useful to you.

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**

This algorithm is part of a course given **Kevin Wayne & Robert Sedgewick** from Princeton University.

You can follow this course for FREE at

Union-Find Java example code:

To investigate two points, (A) and (B), on a grid graph.

- Construct a
*"grid"*of nodes - Connect each node with it's neighbors, if the path is not blocked between them
- Query reachability

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

finderInstance.connected(idA, idB);

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

info@hofware.nl | ||

Telefoon | 06 4072 2423 | |

KvK | 62595407 | |

Hofware 2015 - Hoflaan @ Arnhem

Foto 'John Frost Bridge' door Maarten Takens