In my attempts to create mazes for Karel, I came across several interesting ways to create mazes. It's fun to write different algorithms and let Karel walk around to see what kind of patterns occur in the mazes, and to see the shapes of the paths in it, because even though the mazes are generated 'randomly', each algorithm results in different kinds of patterns.

The maze in this video was created with my own version of Kruskal's algorithm: Start with 40x40 independent sets with 1 rooms. Randomly look for 2 sets that are 'neighbours', but with a wall seperating them, join those sets and remove the wall. After each step the number of sets is reduced by one, so it continues untill there is only 1 set that contains all the rooms.

In case you are interested, here you'll find some more algorithm descriptions, and images of the resulting mazes: [ Ссылка ]

In case you have paid very close attention and notice the generated maze doesn´t look anything like the maze Karel walks in; the whole maze is mirrored along the x-axis, because 0,0 in my array is the top left and 1,1 in Karels world is the bottom left...

свернуть