On 15-11-2010 7:23, Darren New wrote:
> Say you have something like this, as a list of endpoints, not as a raster:
>
> http://www.puz.com/sw/amorphous/theory/amz1.jpg
>
> Any idea how one would go about finding the paths amongst this? I.e.,
> given just the endpoints of the line segments as floats, and without
> rasterizing it, how would you find your way from any point in the maze
> to any other point?
>
> In a raster-based maze, you can just flood fill out from your goal,
> incrementing the distance for each step, and then trace back along
> descending distances. (I.e., use a flood-fill to set the value in each
> room to be the distance to the exit, then always turn towards lower
> numbers.)
>
> But that technique assumes you have a fixed set of positions to test.

I almost forgot that this threat started with this question.

Attached is your a-mazeing planet.  All 'mountains' (grey) and all 
'rivers' (blue) are connected. There is also exactly one path between 
two mountain-nodes and between two river-nodes. (I think the last two 
lines are equivalent, but I don't feel like proving that ATM.)
If your maze is the rivers, walk over the mountain ranges. If the 
mountains are the maze use the boat.
Both are simple connected trees, so to find your way around any tree 
traversal routine will do.
I hope this answers your question ;)

Post a reply to this message

Attachments:
Download 'darrenworld.png' (491 KB)

Preview of image 'darrenworld.png'