![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/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) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> 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...
That's how to do it. If you turn the wall line segments into loops, You
can treat the maze like a complicated polygon and triangulate it as
such. It's not too hard to do yourself, but there's also libraries that
do it for you. Then just pathfind the resulting mesh.
- Slime
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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'
![amz1.jpg](/povray.off-topic/attachment/%3C4CE0EB89.9090904%40gmail.com%3E/amz1.jpg?preview=1)
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
andrel wrote:
> Took me some time to realize you were supposed to find the way in the
> background.
Me too. But I'd read the algorithm. (It's described on the wiki page for
maze algorithms.)
> Can't you use the fact that the walls separate in two sets (see attach).
Well, only if you want the one path from entrance to exit. That doesn't work
if you want to reach arbitrary goals within the maze - i.e., if you weren't
starting at an edge, for example.
--
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) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 15-11-2010 19:51, Darren New wrote:
> andrel wrote:
>> Took me some time to realize you were supposed to find the way in the
>> background.
>
> Me too. But I'd read the algorithm. (It's described on the wiki page for
> maze algorithms.)
which one?
>> Can't you use the fact that the walls separate in two sets (see attach).
>
> Well, only if you want the one path from entrance to exit. That doesn't
> work if you want to reach arbitrary goals within the maze - i.e., if you
> weren't starting at an edge, for example.
>
True, but I wasn't sure if it should solve also that general case. The
picture did suggest it wasn't.
For a more general approach I guess I would use something like dead end
filling and building a graph of all paths. Something like that is of
course also needed for the special red/blue path.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
andrel wrote:
> On 15-11-2010 19:51, Darren New wrote:
>> andrel wrote:
>>> Took me some time to realize you were supposed to find the way in the
>>> background.
>>
>> Me too. But I'd read the algorithm. (It's described on the wiki page for
>> maze algorithms.)
>
> which one?
http://en.wikipedia.org/wiki/Maze_generation_algorithm
Basically, it's a link to an external site that, if you read between the
lines, you can figure out he draws segments of random length and direction
from various points along the lines.
> For a more general approach I guess I would use something like dead end
> filling and building a graph of all paths. Something like that is of
> course also needed for the special red/blue path.
Yeah, I was just trying to figure out how to *fill* something that's
described with just line segments. Hence, the title of the post.
But turning it into adjacent triangles, some of which have "walls" and some
of which don't, should do the trick.
Or even, if I wanted a slightly different maze, a bunch of random triangles,
some of which are filled in, so the walls are all different thicknesses too.
--
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) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New wrote:
> I'm thinking you could probably triangulate all the areas between
> verticies.
FWIW, it looks like
http://en.wikipedia.org/wiki/Delaunay_triangulation
is getting me on the way. It's the inverse of
http://en.wikipedia.org/wiki/Voronoi_tessellation
which looks like what Pov-ray uses for crackle.
--
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) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 16-11-2010 4:35, Darren New wrote:
> Darren New wrote:
>> I'm thinking you could probably triangulate all the areas between
>> verticies.
>
> FWIW, it looks like
> http://en.wikipedia.org/wiki/Delaunay_triangulation
> is getting me on the way.
I was thinking about that too,but you can not guarantee that existing
walls are part of the triangles. You need an additional program to flip
edges until all are in the correct order.
I think this may also work:
(first close the exit in order to get one graph)
create a list by a depth first search over the entire tree and note
every node number going down and up.
make an emty list of triangles
repeat
- find three consecutive points that form a triangle with a positive area
- add that triangle to your list of triangles
- remove middle point from list
until list contains 2 elements (both sides of the entrance)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 16-11-2010 4:35, Darren New wrote:
> Darren New wrote:
>> I'm thinking you could probably triangulate all the areas between
>> verticies.
>
> FWIW, it looks like
> http://en.wikipedia.org/wiki/Delaunay_triangulation
> is getting me on the way.
you can use it to generate such a maze though
Post a reply to this message
Attachments:
Download 'amaze.png' (28 KB)
Preview of image 'amaze.png'
![amaze.png](/povray.off-topic/attachment/%3C4CE28F38.6050602%40gmail.com%3E/amaze.png?preview=1)
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 16-11-2010 15:03, andrel wrote:
> On 16-11-2010 4:35, Darren New wrote:
>> Darren New wrote:
>>> I'm thinking you could probably triangulate all the areas between
>>> verticies.
>>
>> FWIW, it looks like
>> http://en.wikipedia.org/wiki/Delaunay_triangulation
>> is getting me on the way.
>
> you can use it to generate such a maze though
Probably even more useful if I include the triangles.
Algorithm:
- generate random points in a field (in this case surrounded by lines of
fixed border points, and I removed points to close to one another to get
a more even distribution).
- create a delauney triangulaton
- find all edges of the triangles
- pick a starting triangle
- repeat
- find a triangle that was not used yet and shares an edge with this one
- if you can not find one try another used triangle until you do
- remove the edge
- mark new triangle as used
- pick a new used triangle (I first try this new one, seems to give
nicely complicated mazed, other choices give other mazes.)
- until all triangles are used
remaining edges form the walls of a maze.
Post a reply to this message
Attachments:
Download 'amaze2.png' (30 KB)
Preview of image 'amaze2.png'
![amaze2.png](/povray.off-topic/attachment/%3C4CE2AA7C.7050707%40gmail.com%3E/amaze2.png?preview=1)
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |