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