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


Sunday, December 25, 2011

Prim's Maze Algorithm in Minecraft

I previously gave a sneak peak of this mini project here.  For an A.I. class we were given an assignment that challenged us to generate random, procedurally generated worlds in MineCraft.  There was more to later versions of the project, but I'm stripping it down to just the terrain generation in the given source code for now.  I believe this is what Minecraft modders will find the most useful (compared to the other, more application specific code I wrote in the project).  Hopefully the source code is understandable enough that other modders will be able to plug this functionality into their own projects.  The handful of java files are well commented and is complemented by a description in this post.  Here's a video demo showing off the algorithm, created via a chat command in the game:

Randomized Prim's Algorithm
A random variant of Prim's Algorithm, is best viewed in this instance not as a graph or tree, but a grid of walls.  We start with a full grid of walls, open one cell in the maze, and then proceed to carve our way out.  We do this by adding all of its "out" neighbors to a "wall list".  While there are still walls in this list, we pick a random one.  If the cell opposite of the wall is not in the maze we make a passage and add its "out" neighbors from the wall list.  Otherwise, we remove it from the list, and repeat this process until the wall list is empty.

Using the Plugin
I'm assuming the users already know how to compile Bukkit plugins themselves.  If not, I've provided a working jar file which can be directly placed into the plugins/ directory of an existing CraftBukkit Server.  The given archive also provides the plugin.yml file, which you need when building for CraftBukkit to load it properly.  The /gen command has the following usage:

/gen [name] [mazeSize] [mazeWallHeight] [mazeSpawnZoneSize] [mazeBorderHeight] [autoTeleport] [iterations]
Default Name: OptimusPrim
Default Maze Size: Random (32, 64, 96, 128, 256, 512).  If you input one yourself it must be a non zero multiple of 16.
Default Maze Wall Height: 3
Default Maze Spawn Zone Size: 16
Default Maze Border Height: 16
Default Auto Teleport: true (the way java parses this is "true"/"false" not 0/1)
Default Iterations: -1 (-1 iterates until done, custom positive values iterate until a specified cutoff.  Used for dev testing only to show "stepwise" increments of the algorithm.)

If you want to reload an existing world you can use the /visit command.

/visit worldname

This is very handy if you don't want to autoteleport to a new world.  Terrain generation can be cumbersome for very large mazes and there may be instances where you want to create a world with the intention of exploring it later (e.g. for comparative purposes).  AutoTeleport is on by default for the /gen command, but if you type the command to the length of that argument and set it to false, you'll need to use the visit command afterwards to spawn in your newly generated world.

The Plugin/Source
The plugin is compatible with the latest version of Minecraft at the time of writing (v1.0).  If you want to rebuild the source you'll need to reference the proper version of Bukkit and setup your own server.  Please refer to their wiki if you need help setting this up.

No comments:

Post a Comment