|
![](/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) |