Programming Contest: Mars Rescue.

[Alex Tweedly]

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 
>without crashing into walls and furniture. More info about Strabo 
>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