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.

Monday, December 19, 2011

Learning A Functional Language

Paradigms Matter -- a lot.  If all you've used is an imperative language I recommend giving a functional language a spin.  You probably won't use it on your next major project and have no issues continuing to use the languages you already know and love (C/C++/C#).  I'm a member of this camp myself and am by no means an evangelist for any particular paradigm.  However, I sincerely believe you'll be a better programmer if you force yourself to think outside the box of the imperative/OOP paradigms once in a while.  In general, the more paradigms you know, the more ways you'll have at your disposal to solve various problems.  Since languages like C++ and Python are multiparadigm, in many languages there's nothing stopping you from adapting a more functional style than the one you already use.

If nothing else, spending a week or two using Haskell or Lisp will make you more mindful of the inherent problems with mutable states. I've seen some severe hyperbole thrown around that this predictability removes the need for debugging altogether.  This is completely false, but in many instances functional languages involve more predictable routines which can decrease the time spent scratching your head in the debugger.  Allow me to explain:

Referential Transparency
Referential Transparency is a property of functions/expressions that could be replaced by the known return value and have no change in the program's execution. In laymans terms, functions have no side effects, and there is no mutable state or variables. The benefit of this style is a significant increase in predictability. Given a function, if I pass the same arguments to that function I will always get the same result. It won't matter at which point the function is called and will never be dependent on potentially corrupted data.

How many times have you had to debug a function in C++ that caused a crash when the problem was really propagated elsewhere?  If the answer is: way too many, perhaps you should consider writing more self encapsulating and fault tolerant functions.

Easily Implemented Parallelism
When there are no global variables or states which could be simultaneously accessed by multiple threads, a lot of the pains inherent from multithreaded programming can be avoided from the get-go.  Since everything is headed in this direction, it doesn't hurt to brush up on it for a change.

A lot of comparable programs in functional languages might feel handicapped by this purity. For example, certain applications which need to represent state (e.g. a atm machine which lets users withdraw/deposit funds) will likely be more  complex if processed as a concatenation of self encapsulating functions.  In addition, responsible imperative programming may have very good reasons to cache global variables, which, in many cases, greatly increase maintainability and speed.  The lazy evaluation frequently implemented in functional languages also makes predicting time and space costs very difficult.

What's interesting about functional languages is that they could make for a decent scripting language.  In my experience using Haskell, there are numerous cases where you merely specify what you want or are looking for, rather than how to get it.  Unfortunately, the extensive unfamiliarity with this style means most of the 'rapid prototyping' benefits sought by these languages will be lost learning a new one.  In addition, virtually every game script is heavily reliant on object state.  That's why it goes into script in the first place.

I'm a few days into my adventures with Haskell and hope to produce another post with code and examples explaining how curried functions, lambdas, and folds can be very useful for any kind of programming.

Additional Reading
Real World Haskell (Online Book)
Learn You a Haskell (Online Tutorial)
Functional Programming In Games (PDF Thesis Paper)
Why Functional Programming Matters (PDF Explanation)
Why learning Haskell/Python makes you a worse programmer (counter argument)