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

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'

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

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

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

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

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

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'

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'

andrel wrote:
> Algorithm:

That was actually the algorithm I came up with, just about. I was goign to 
use the normal Kruskal algorithm
http://en.wikipedia.org/wiki/Maze_generation_algorithms
except with triangular rooms.

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

Got that working. (It was surprisingly harder than it looks. :-)

> - create a delauney triangulaton

Working on figuring that out next.

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

Yep, that's Prim's algorithm.


I was also thinking, just stylistically, to treat triangles like walls also, 
so you could have a much bigger triangle with walls of varying widths. This 
will let me have (say) a maze of cliffs and crags (i.e., where instead of 
walls you have deep chasms), or a maze of paths through water or lava or 
something you can't really cross.

This is the unit test for my rectangular maze code:
http://www.youtube.com/watch?v=X2mkwcfEd_8

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

Post a reply to this message

On 16-11-2010 18:16, Darren New wrote:
> andrel wrote:
>> Algorithm:
>
> That was actually the algorithm I came up with, just about. I was goign
> to use the normal Kruskal algorithm
> http://en.wikipedia.org/wiki/Maze_generation_algorithms
> except with triangular rooms.
>
>> - 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).
>
> Got that working. (It was surprisingly harder than it looks. :-)

Was it?

>> - create a delauney triangulaton

That is where using Matlab comes in handy.

>
> Working on figuring that out next.
>
>> - 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
>
> Yep, that's Prim's algorithm.

Possibly, it was the most obvious way to me. I am not surprised that 
somebody else though of it before. ;)

>
> I was also thinking, just stylistically, to treat triangles like walls
> also, so you could have a much bigger triangle with walls of varying
> widths. This will let me have (say) a maze of cliffs and crags (i.e.,
> where instead of walls you have deep chasms), or a maze of paths through
> water or lava or something you can't really cross.

I think you (and me) should use in in POV somewhere.


> This is the unit test for my rectangular maze code:
> http://www.youtube.com/watch?v=X2mkwcfEd_8
>

Haven't got a clue what is going on.

Post a reply to this message

andrel wrote:
> - create a delauney triangulaton

BTW, do you have code to do that sitting about? I've found various 
algorithms, but the speed with which you threw that together seems 
impressive. :-)

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

Post a reply to this message

andrel wrote:
>> This is the unit test for my rectangular maze code:
>> http://www.youtube.com/watch?v=X2mkwcfEd_8
>>
> 
> Haven't got a clue what is going on.

That's why it's not a public link yet.

1) Create all the rooms with possibly-destructable (grey) walls.

2) Caller marks some rooms as "pre-open" (green), blocked (red) or post-open 
(blue).  So, the top left green might be a tennis court, the bottom left 
green might be a drive and parking lot, the red in the middle might be a 
building, the other red might be a swimming pool with a path around it, and 
the blue might be where a part of the maze burned down after it was built. 
So "green" acts as one big room, while "blue" has the possibility of adding 
loops to the maze.

3) Mark blocked walls and walls open inside a blocked area.

4) Repeatedly pick a grey wall and examine the rooms on either side. If the 
rooms are connected, make the wall black. If they're not, make the wall 
white, then flood fill the smaller area to mark it as connected to the 
larger area (the yellow). Stop when you've examined all walls.

5) Blow up any walls son the border of a blue room, even if that means 
creating a new connection between rooms already connected.

Then, some demos of the path-finding:

A) Pick a goal room in Cyan.
B) Flood-fill from that room with the distance to the goal.
C) Put a logo in another room.
D) Repeatedly move the logo to the adjacent room with the lower
    distance until you get to the goal.


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

Post a reply to this message

On 16-11-2010 18:38, Darren New wrote:
> andrel wrote:
>> - create a delauney triangulaton
>
> BTW, do you have code to do that sitting about? I've found various
> algorithms, but the speed with which you threw that together seems
> impressive. :-)
>

D=delaunay(X,Y);

sorry, I though I said I was using Matlab ;)  I think it is even in the 
standard library.

Post a reply to this message

On 16-11-2010 18:38, Darren New wrote:
> andrel wrote:
>> - create a delauney triangulaton
>
> I've found various
> algorithms, but the speed with which you threw that together seems
> impressive. :-)

The speed may also be explained by having experience with these 
functions, doing a lot of triangulations and writing toolboxes to 
support that. Actually I was home today to create a number of meshes 
though they are mostly quads and not triangles. This was a nice break 
from mousing all the time. And I did create programs to build and solve 
mazes before, but haven't we all?

Post a reply to this message

On 16-11-2010 18:16, Darren New wrote:
> I was also thinking, just stylistically, to treat triangles like walls
> also, so you could have a much bigger triangle with walls of varying
> widths. This will let me have (say) a maze of cliffs and crags (i.e.,
> where instead of walls you have deep chasms), or a maze of paths through
> water or lava or something you can't really cross.

well, here is your own special planet where there is just one path 
between each point on the surface ;)

Post a reply to this message

Attachments:
Download 'maze3.png' (333 KB)

Preview of image 'maze3.png'

andrel wrote:
> well, here is your own special planet where there is just one path 
> between each point on the surface ;)

Sweeeet.  I bet you could make some sort of sci-fi out of that concept.

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

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> andrel wrote:
> > well, here is your own special planet where there is just one path
> > between each point on the surface ;)
>
> Sweeeet.  I bet you could make some sort of sci-fi out of that concept.
>
> --
> Darren New, San Diego CA, USA (PST)
>    Serving Suggestion:
>      "Don't serve this any more. It's awful."


Pretty cool, and sci-fi for sure; it's a similar concept to how the great river
on Riverworld must be, covering the entire planet surface with a single river
having huge unclimbable cliffs on each side, all the way to the source.

-------------------------------------------------
www.McGregorFineArt.com

Post a reply to this message

On 20-11-2010 21:15, Robert McGregor wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> andrel wrote:
>>> well, here is your own special planet where there is just one path
>>> between each point on the surface ;)
>>
>> Sweeeet.  I bet you could make some sort of sci-fi out of that concept.
>>
>> --
>> Darren New, San Diego CA, USA (PST)
>>     Serving Suggestion:
>>       "Don't serve this any more. It's awful."
>
>
> Pretty cool, and sci-fi for sure; it's a similar concept to how the great river
> on Riverworld must be, covering the entire planet surface with a single river
> having huge unclimbable cliffs on each side, all the way to the source.
>

My idea was indeed that it could be used in a sci-fi scene, except I 
hadn't a clue what the context should be. That is why I did not spend 
much time on the details of this scene.
If anyone has a great idea or wants to use such a tree of lines that 
span a sphere or plane, just ask. For me it was fun to prove that it 
could be done, that's all. I guess I am not going to take this further.
Unless someone got another challenge...

Post a reply to this message

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'

andrel wrote:
> I almost forgot that this threat started with this question.

Very cool. Thank you. :-)

> I hope this answers your question ;)

No, but the rest of the thread did. :-)

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

Post a reply to this message