# Programming Contest: Mars Rescue.

Alex Tweedly alex at tweedly.net
Tue Jan 18 20:05:30 EST 2005

```Roger.E.Eller at sealedair.com wrote:

>Andre,
>
>That sounds like allot of fun! The objective of plotting the shortest path
>sounds very similar to what Strabo Pathfinder does. Strabo is a program
>used by robotics enthusiasts to map out the rooms of their home to allow a
>robot (we'll assume that it is a mars rover) to move freely on the map
>Pathfinder can be found at:
>
>http://www.wehali.com/robotics/strabo.htm
>
>Anyways, the algorithms used to plot the shortest route is one that are
>Dijkstra and A* (commonly used in games). I have no clue as to how it
>works, but I would love to see the algorithm recreated in transcript.
>
>
Dijkstra is designed to find the shortest path through a graph (i.e.
between a number of nodes) given a link-state database and variable link
weightings.
I think to apply it to this problem, you'd need to make each cell a
node, and you'd have a fairly dense link-state because each cell is
connected to each of its neighbours; this would mean you'd run a rather
large (and space- and time-consuming) Dijkstra calculation. (Note that
the most common use of Dijkstra is in ISIS and OSPF routing - where the
general guideline is to keep each area down to 50 or fewer nodes).

This problem looks to me much more like a Hightower routing problem (see
various CAD papers from the 60s and 70s - I know this makes it too old
to be fashionable :-) I think either a Lee-Moore style expanding cell or
Hightower-style line-probe algorithm would be perfectly able to solve
this problem with  far fewer resources than an SPF calculation.

In either case, the tricky part will be mapping the acceleration /
steering constraints onto the ideal shortest-path solution you find.

-- Alex.

--
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.300 / Virus Database: 265.7.0 - Release Date: 17/01/2005

```