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?

Took me some time to realize you were supposed to find the way in the 
background.

> 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.
>
> You could rasterize this, perhaps at very high resolution or something,
> staying away from the walls by some number of pixels, and then go from
> there, but that seems even more overkill than generating the thing in
> the first place.
>
> I'm thinking you could probably triangulate all the areas between
> verticies. I.e., build a list of triangles between verticies that don't
> contain any other verticies, and then use the center of each triangle or
> something to represent the "cells", then flood-fill from there as
> appropriate. Does that sound like it would work out? It sounds like a
> lot of brute-force to find those triangles given nothing but the segment
> endpoints. I wonder if you could build the maze that way in the first
> place, plopping down a bunch of randomish triangles and *then* drawing
> edges. Hmmmm...

Can't you use the fact that the walls separate in two sets (see attach). 
E.g. by using that every triangle visited by your path contains 2 blue 
and one red vertex (or vice versa).

Post a reply to this message

Attachments:
Download 'amz1.jpg' (321 KB)

Preview of image 'amz1.jpg'