![](/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) |
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
|
![](/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 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
|
![](/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:
> - 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
|
![](/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:
>> 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
|
![](/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 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
|
![](/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 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
|
![](/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 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'
![maze3.png](/povray.off-topic/attachment/%3C4CE79E93.2060502%40gmail.com%3E/maze3.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) |
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
|
![](/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 <dne### [at] san rr com> 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
|
![](/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 20-11-2010 21:15, Robert McGregor wrote:
> Darren New<dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |