|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |