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