DEV Community

Cover image for Kruskal + Weave Maze
Sean
Sean

Posted on

Kruskal + Weave Maze

Maze Generation.

I am adding an "impenetrable" maze around the main game that players may stumble onto.

I thought this would be straight forward. I implemented the easiest algorithm (back tracking) and then added code to solve the maze. That is when I discovered the easiest solution does not produce the branching variety I want.

So then I went on a deep dive into maze generation algorithms. This is a deep rabbit hole.

I've settle on the most interesting (and likely most difficult) algorithm: Kruskal + Weave.

You can see it in action here:
https://weblog.jamisbuck.org/2011/3/17/maze-generation-more-weave-mazes.html

Now I just need to graft the ruby logic into my existing c++ maze logic...

Top comments (0)