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.

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

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message