1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.


Tuesday, October 25, 2011

Randomized Prim's Algorithm and MineCraft

I recently implemented a procedural maze generation algorithm for MineCraft.  Using the Bukkit/CraftBukkit API with my own Chunk Generator I was able to create some awfully vast and daunting mazes inside the game.  Due to the way the API likes to write things one chunk at a time, I had to create the maze on the first chunk, store it statically, and convert the units of later chunks to create the blocks correctly.  The results were pretty encouraging:

A Bird's Eye View of a Procedurally Generated Maze

I used a variant of the Randomized Prim's Algorithm.  The basic algorithm, as described on Wikipedia is actually one of the most clear and concise explanations I have found.  The problem I had with most algorithms I found was that they used lines for walls rather than blocks themselves, which simply won't work in a 3D world of this sort (but are fine for things like online Java Applets).  Nonetheless, resources like Think Labyrinth and Daedalus are excellent references for exploring this line of algorithms.

No comments:

Post a Comment