Prim's Maze Algorithm in Minecraft

Overview
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.

Download The Minecraft Prim Maze Generator Plugin

Learning A Functional Language

Overview
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.

Caveats
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.

Potential
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)

Speaking of Battlefield

During the recent release of a certain FPS game, I remembered that 4 years ago when I was still in high school I whipped together a map using the BF2 Editor.  It certainly wasn't the best toolset around, but it was a very fun multiplayer game that did a lot of things right.  The intensity of certain maps, from Karkand to Wake Island, was very difficult to match.  Since there is some disappointment over the lack of mod tools given with BF3, it's worth remembering that the previous game sported some very, very good modifications.

In their defense, there are legitimate security concerns that will need to be addressed.  In addition, based on what I've read about the Frostbite Engine (ppt), it is very heavily threaded and uses no scripting language of any kind.  I don't doubt that modding such an environment will be more difficult, but given the raw persistence and skill we've seen from modders in the past, are threads and intrinsics really just too hard to justify a lack of tools?

Before I spiral into a totally incoherent rant let me just present this old project of mine.  I was 16/17 at the time and tried to make a genuinely balanced map with no aerial vehicles of any kind.  Before I entered college (for a Game Design and Development Degree) my programming knowledge was rather minimal and almost entirely self taught.  Now I'm a much better programmer, a much better designer, and occasionally making my own tools from the ground up for my own projects.  I think I could handle it.  But the broader point is, even if I couldn't, it still wouldn't be a waste to release the tools.  Circa ye olden days of 2007, where I had none of these honed skills, and I was still able to produce stuff like this:

This map had virtually no significance to the modding community but studios sometimes forget that it doesn't have to.  At the time, projects like this were for me.  Becoming a professional game developer is a long journey that involves failing a number of times before you get something right, let alone make something significant that other people will care about.  Nonetheless, this journey is very important for the industry.  It's a process the guys at DICE understand all too well.  So if you remember what it was like trying to break into the games industry, you'll know how critical the modding community is to aspiring developers.  It probably wasn't too long ago that you had a portfolio site like this one too.

Dead Sea Map Project Page

Update to CDS

Doxygen Documentation Makes Learning the API Much Easier

With new found (but short lived) free time over the break, I got around to committing a major new release of the CDS Library.  In addition to a host of new functions and finished structures, I made everything compatible with ANSI C and implemented Doxygen Documentation.  Other annoyances, such as const correctness have been ironed out, and all of the examples have been rewritten in a way that tries to teach new users how everything works.  CDS is still relatively new, and could benefit from more iterations and tweaking.  However, at this time it is pretty solid given the time constraints.  Functionality, style, and typenames are much more consistent now.  As usual, you can always find the latest version of CDS on GitHub. 

Browse CDS on GitHub

You can refer to my first post on CDS for more information here. Enjoy!

Below is a simple example program demonstrating the usage of a cds_dynamic_array:

int main(void) {
     /* create the array */
     cds_dynamic_array *array = NULL;
     unsigned int size = CDS_DEFAULT_DYNAMIC_ARRAY_SIZE; /* 4 by default */
     cds_result cr = cds_dynamic_array_create(&array, size); /* notice the address of the pointer is passed in */
    
     /* checks for an error, prints and returns 1 if something failed
      * we do this (in this example) repeatedly for safety
      */
     if (cds_error_check(cr)) return 1;
 
     /* add the strings to the container */
     char * presidents[] = {"washington", "jefferson", "roosevelt", "reagan", "clinton", "obama"};
     unsigned int numPresidents = 6;
     unsigned int i;
     for (i = 0; i < numPresidents; ++i) {
          cr = cds_dynamic_array_push_back(array, presidents[i]); /* will need to reallocate when i == 4 */
          if (cds_error_check(cr)) return 1;
     }
 
     /* print out the array */
     cds_log("Displaying the contents of the dynamic array...\n");
     logArray(array, 1);
 
     /* try adding past the current size of the array */
     void *curValue;
     cds_log("Adding some more strings to the container...\n");
     char *otherPresidents[] = {"adams", "bush", "coolidge", "kennedy"};
     unsigned int numOtherPresidents = 4;
     /* since the default size is 4, we've grown once, 4 * 1.5 = 6 */
     /* therefore, on the next insertion, the array will need to grow */
     /* we can use a custom growth function, to resize things differently */
     for (i = 0; i < numOtherPresidents; ++i) {
          cr = cds_dynamic_array_push_back_gf(array, otherPresidents[i], &arrayDoubleGrowth);
          if (cds_error_check(cr)) return 1;
     }
 
     /* lets try printing the array using an iterate function */
     cds_log("Printing the contents of the array using the iterate function...\n");
     cr = cds_dynamic_array_iterate(array, &printString2);
     if (cds_error_check(cr)) return 1;
 
     /* accessing the last element first just for the sake of printing it */
     unsigned int count = cds_dynamic_array_count(array);
     cr = cds_dynamic_array_get(array, count - 1, &curValue);
     cds_log("Removing the last element in the collection: %s", (char *)curValue);
 
     /* remove the element at the end of the array */
     cr = cds_dynamic_array_pop_back(array);
     if (cds_error_check(cr)) return 1;
 
     /* this will remove the element from the container, but give it as a pointer */
     cr = cds_dynamic_array_pop_back_data(array, &curValue);
     if (cds_error_check(cr)) return 1;
     cds_log("Removed: %s from the back of the array\n", (char *) curValue);
 
     /* remove functions will rely on pointer addresses by default
      * we know that roosevelt's address is in the array so this will work */
     cr = cds_dynamic_array_remove(array, presidents[2]);
     if (cds_error_check(cr)) return 1;
 
     /* if we want to remove with value equality, we must use the cmp functions 
      * so while "adams" is in the array, this is a new address
      */
     char adamsStr[] = "adams";
     cr = cds_dynamic_array_remove(array, adamsStr);
     char resultString[CDS_RESULT_MAX_STR_LEN];
     cds_result_string(cr, resultString);
     cds_log("Attempt to remove the same string at a different address: %s\n", resultString);
 
     /* if we use our strcmp equivalent, this can be done with the proper function */
     cr = cds_dynamic_array_remove_cmp(array, adamsStr, &cmpStr);
     cds_result_string(cr, resultString);
     cds_log("Attempt to remove the same string using the comparison function: %s\n", resultString);
 
     logArray(array, 0);
 
     /* you can also remove elements by index (with safe bounds checking) */
     cds_log("Removing from index 2...\n");
     cr = cds_dynamic_array_remove_at(array, 2);
     logArray(array, 0);
 
     /* The dynamic array supports multiple removal behavoirs
      * By default it is shift down, which maintains the relative order of elements
      * if remove_at(2) CDS_SHIFT DOWN: a b c d e f becomes a b d e f
      * It also supports replacing the removed element with the element at the end
      * This disrupts the relative order of elements, but is more efficient than shifting large arrays
      * if remove_at(2) CDS_REPLACE_WITH_LAST a b c d e f becomes a b f d e
      */
     cds_log("Removing from index 2 using CDS_REPLACE_WITH_LAST\n");
     cr = cds_dynamic_array_remove_at_rb(array, 2, CDS_REPLACE_WITH_LAST);
     logArray(array, 0);
 
     /* Reverse the relative order of elements */
     cds_log("Reversing the order of elements in the dynamic array...\n");
     cr = cds_dynamic_array_reverse(array);
     logArray(array, 0);
 
     cds_log("Deleting the dynamic array...\n");
     cr = cds_dynamic_array_delete(&array);
     if (cds_error_check(cr)) return 1;
     cds_log("Deletion successful...\n");
     return 0;
}

Blasteroids

Blasteroids is a reinterpretation of the popular game Asteroids.  It was built as a Flash project for school.  It controls like the original: you propel in your pointed direction, you wrap around the screen, and you press spacebar to shoot a projectile.  It features new artwork, and special seeker asteroids that explode and deal extra damage on impact.  Shooting them early can trigger an explosion which will damage any surrounding asteroids.  The game also features variable levels of difficulty selectable before the beginning of the game.

A remake of an old classic

Flash embedding and Blogger don't always seem to get along.  On top of that many browsers are dropping support for Flash.  It was more relevant when I was in college almost a decade ago.  To deal with this I've added a zip of the .fla and associated files to dropbox.  You can download it here to run it locally.

Resonance

My sophmore year I spent ~9 weeks working on a project called Resonance.  Our lead's pitch was green lit, and we quickly went to work on the project.  I was one of the two lead programmers on the game, working on low level rendering, animation, physics, and the like.  My fellow programmer also dedicated a significant amount of time helping me with these things and writing the game logic for all the game objects.  You can find more details about the game, including our design document and first playable on the lead's blog here.  Here's some footage of the first level in the game, which was mostly designed by myself (with feedback from the group and our professor).

 

Said level was built with the game editor I created.  Of course, I owe a lot of credit to the designers and artists who helped make it possible.  Here's some footage of the editor, with a voice over by yours truly explaining some details about the way it operates and the lessons I learned from creating it.
NOTE: I apologize for the audio quality.  You will likely have to turn up your volume to hear me clearly in these two videos.

 

And here's part two of the editor related videos showing the completed level used for the gameplay footage above, only this time loaded into the game editor.

A lot of the lessons learned from this project have directly influenced my XNA Game Engine (which I may introduce here sometime in the near future).

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.

Introducing CDS (The C Data Structures Library)

CDS was a side project to demonstrate I can write efficient data structures in a procedural language like C.  It currently supports all types (with void pointers) with the following data structures:

• dynamic array (cds_dynamic_array)
• singly linked list (cds_slist)
• doubly linked list (cds_dlist)
• stack (cds_stack)
• queue (cds_queue)
• binary search tree (cds_binary_tree)
• hash table (cds_hash_table) 

CDS tries to use consistent practices amongst the entire code base.  Every custom type, function, and macro starts with the cds_ or CDS_ prefix.  Data structure functions are typically structured in the following way: cds_datastructurename_function().  Therefore, to push_back an element onto a dynamic array you would call cds_dynamic_array_push_back(array, data);  This tends to make function calls and type names long, but is good practice, keeps things consistent, and avoids polluting the namespace.

Every data structure function returns a cds_result enum.  Every error code that could be thrown in any of the provided functions is a cds_result.  This keeps results more informative, consistent, and performance friendly.  Rather than returning -1 or NULL when an error occurs, it returns more specific information (e.g. CDS_BAD_ALLOC).  This is better practice because a number of things can potentially go wrong with a given operation, and this tries to ease the amount of time spent guessing.

Common operations include:
    create: allocates the given structure
    clear: removes the elements from the given structure
    delete: deletes the given structure (but not its elements)
    delete_all: deletes the given structure and its pointers to other elements
    add/push_back/insert/etc: adds the pointer to the structure
    remove/pop_back/pop/etc: removes a pointer from the structure
    count: get the current count of the structure
    find: search for a pointer address or do a value comparison via a cds_cmp_func
    iterate: passes every data type in the container safely to the given cds_visit_func

Assertions are given but not fully apparent in all of the code.  They can be compiled out of runtime code since they use optional macros.  There is support for custom memory allocators and log functions that can be interchanged easily at run/compile time so long as they match the function format of their stdlib equivalents.  Other intricacies include custom growth behavoirs, type specific comparisons, and more through function pointers, enums, and macros.

This code is still unfinished and in a relatively early state.  Since school and work keep getting in the way I'm releasing it now but intend on improving it later.  The code is free for non commercial use and commercially with permission (contact email given in the README).  Use at your own risk!

Browse CDS on GitHub

Here's a sample program example demonstrating cds_stack.  You'll see similar semantics for the rest of the data structures too.

UPDATE: I've revisited the library and am no longer so strict on the "every function returns an error result" philosophy.  Sometimes it is excessive and  actually makes code more error prone.  However, a vast majority of the functions still follow the old format.
UPDATE 2: CDS has received a significant new release, with full ANSI C compatibility, Doxygen Documentation, new functions, rewritten examples, and a host of bug fixes.  You can read about it here.

/* Create the stack */
cds_log("Running the stack test...\n");
cds_stack *stack = NULL;
cds_result cr = cds_stack_create(&stack);
if (cds_error_check(cr))
        return 1;
 
/* Add the values to the stack */
cds_log("Adding the usual values...\n");
int values[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
unsigned int n = 10;
unsigned int i;
for (i = 0; i < n; ++i) {
        cr = cds_stack_push(stack, values + i);
        if (cds_error_check(cr))
                return 1;
}
 
logStack(stack, 1);
 
/* Clean up the stack */
cds_log("Popping everything off the stack...\n");
int *top = NULL;
/* if you want to allow null values in your stack 
 * use cds_stack_count() instead */
while ((top = cds_stack_top(stack)) != NULL) {
        cds_log("Pop: %d\n", *(int *)top);
        cr = cds_stack_pop(stack);
        if (cds_error_check(cr))
                return 1;
}
 
/* if you call pop on an empty stack it returns CDS_UNDERFLOW */
cds_log("The stack is now clear.  Count: %u\n", cds_stack_count(stack));
cds_log("If you try to pop an empty stack, it will return: ");
cr = cds_stack_pop(stack);
char resultString[CDS_RESULT_MAX_STR_LEN];
cds_result_string(cr, resultString);
cds_log("%s\n", resultString);
 
/* you can also iterate on a stack like all the other data structures 
 * but we don't do that here
 */
cds_log("Deleting the stack...\n");
cr = cds_stack_delete(&stack);
if (cds_error_check(cr))
        return 1;
cds_log("Deletion successful...\n");

Procedural Terrain Generation

Windows Forms Launcher Window

I've often been interested in groups of algorithms that offer procedural generation of gameplay environments.  There is a rather wide range for these algorithms, both in computational time and complexity.  Some algorithms, such as Diamond Square are rather trivial to implement.  Others, such as the algorithms behind the MMO Love, are obviously much more in depth.  Since I'm about to explore a hybrid of these algorithms (Perlin Noise and others) I figured I'd resort back to an old project I worked on concerning terrain generation.  The idea of the project was to act as a tool to demonstrate how certain algorithms worked and compare them (as well as get some more experience with OpenGL 4).  The final launcher looked something like that on the right.  A drop-down of the algorithm, a radio select rendering mode, and algorithm specific settings.  The user could launch multiple windows and compare the differences.  This served as a rather effective tool for differentiating different methods and the effect of algorithm variables on the output (e.g. generating a terrain map with a decay rate of 0.3 instead of 0.7).  With a simple rotating camera and variable zoom levels, the user could inspect the final results of their work.

Diamond Square with high variation and low decay

It was nice to have effective proof of the weaknesses these algorithms have.  For example, Diamond Square in it's normal form, is prone to artifacts (especially with typical linear congruential number generation) and frequently builds mountains.  We also found sequential random additions was decent at generating rolling hills, but not smooth ones that often resembled cones.

All in all, procedural worlds won't replace the mapmaker anytime soon, but they are a powerful tool, and can serve as a nice base that can be tweaked and remodeled later.  I'd recommend game programmers become familiar with Diamond Square and Perlin Noise at the very least.

With a greater decay and lower variation

Wireframe View

  Go To the Project Page

SRT Moved to GitHub

Since Git as a VCS has become more prominent and the popularity of the service GitHub has (rightfully) skyrocketed, I finally got around to putting the Simple SDL RayTracer onto GitHub.  Not everyone in the industry uses SVN so it's high time I got comfortable with something else too.  If you've been holding off on Git because the clients have been bad I don't really blame you.  But they have gotten much better since I first tried them out, especially on Windows, and are frequently being offered as plugins for IDEs if that's the sorta thing you're into.