Home | Rules and Guide | Sign In/Create Account | Write a Post | Reddit | #LD48 | #ludumdare on irc.afternet.org (Info)

Ludum Dare 31 — Coming December 5th-8th 2014! — Join the Mailing List!
  • October Ends: in 29 days, 23 hours, 50 minutes, 55 seconds
  • Ludum Dare 31 begins: in 65 days, 0 hours, 38 minutes, 55 seconds
  • (FYI: Clock might be off) | Ludum Dare 31: Real World Gatherings (Now Open!) | October Challenge 2014!


    Serendipity with Cubes – A Postmortem and Timelapse

    Posted by (twitter: @halogenica)
    April 25th, 2012 7:51 pm

    Well, that was fun. :)

    This was my first Ludum Dare competition. I’ve been working on my own game engine for quite some time (has it been a year and a half already?) and I’ve just been trying to figure out what works well and what doesn’t for prototyping. I wanted to put my engine to the test to see if it was really possible to complete a legitimate 3D game with acceptable polish in 48 hours. I can certainly say, I learned half of what I know now about prototyping in that 48 hours. Knowing what is most effective and efficient is difficult, but nothing brings those creative ideas out of you like working under the pressure of a strict deadline. It was like in college, when you were given a month to do your final project, and you just didn’t have time to do it until the very weekend it was due. Staying up all day and all night in the lab, only to take a break around 3 in the morning to hit up the local diner before getting back to work. I don’t know what it says about me that I miss that sort of thing, but I do.

     

    So, lets take a look at the game:

     

    The prompt this compo was “Tiny World”. The first thing I thought of was the phrase “what a small world”, about the coincidence and fortune of running into someone in an entirely different context than you’re used to seeing them. Knowing that I need to keep the scope of the game really small and manageable if I ever expect to complete it on time, I opted to go with a puzzle game (as opposed to an adventure platformer, etc). I’m not very quick at making art, so I opted to cater to my strengths as a more technical graphics coder, and went with my favorite shape, cubes! Brainstorming what gameplay would look like to make many connections, graph theory came to mind. I always had fun experimenting with graph theory even though I’m not an expert mathematician. I got to thinking about the excellent board game “Ticket to Ride”, and wondered what would happen if I put that map onto the surface of a cube?

     

    Now there are a whole lot of ways to impart gameplay rules for “solving” a puzzle based on graph theory, but I figured the most accessable and easiest to implement would simply be to connect two points with some sort of path. Add some sexy colors, nice physics, cute sound effects and bam, you’ve got something presentable. Ok, it’s not exactly that easy, but not that far off. The majority of the time I spent on the game was simply debugging this horrible 3d array data structure I coded. The first step was to determine how to “stitch” the faces together, since I needed to define how the “top left corner” of the front face of the cube matches up with the “top” and “left” faces. I actually drew out a little diagram so it would be easy to follow. Turns out, the “top left” corner of the front face is the “top right” corner of the left face, but the “bottom left” corner of the top face. See below:

                    -----------------
                    |           DIM |
                    |             | |
                    |             | |
                    |      Back   | |
                    |             | |
                    | DIM ------- 0 |
    -------------------------------------------------
    | DIM ------- 0 | 0 ------- DIM | DIM           |
    |             | | |             | |             |
    |             | | |             | |             |
    |     Left    | | |    Top      | |    Right    |
    |             | | |             | |             |
    |           DIM | DIM           | 0 ------- DIM |
    -------------------------------------------------
                  / | 0 ------- DIM |
                 /  | |             |
                /   | |             |
               /    | |   Front     |
     (-.5,.5,-.5)   | |             |
                    | DIM           |
                    -----------------
                    | 0 ------- DIM |
                    | |             |
                    | |             |
                    | |  Bottom     |
                    | |             |
                    | DIM           |
                    -----------------

    After that, I needed to write a puzzle solver. Every time you move swap a little colored cube, you need to check to see if the “path” connecting the two endpoints will be completed and if so, pop all the little colored cubes out and pick a new set of endpoints. Since I was really tight on time and didn’t have time to worry about performance, I just used a simple recursive function that, given a colored cube (starting with the start point), checks the neighboring adjacent cubes and if they’re the same color, and haven’t already been looked at (tracked by the pPathPool list), then call the same function to check all of that cubes neighbors, and so forth. The algorithm ends once it’s compiled a list of all the connected, adjacent cubes of the same color. The path is “solved” if that list contains the endpoint. If you’re a beginner CS major, this code is probably the answer to one of your homework assignments. Use it wisely:

    bool World::CheckPathRecursive(CCube* pCube, bool restrictColor)
    {
        ASSERT(pCube);
        if (restrictColor && m_pStartCube)
        {
            ASSERT(pCube->m_colorEnum == m_pStartCube->m_colorEnum);
        }
    
        bool pathFound = false;
        if (!m_pPathPool->Contains(pCube))
        {
            m_pPathPool->Add(pCube);
            if (pCube == m_pEndCube)
            {
                pathFound = true;
            }
    
            CCube* pTestCube;
    
            // find the face, row and col for the current cube
            for (UINT face = 0; face < NUM_FACES; face++)
            {
                for (UINT row = 0; row < m_dim; row++)
                {
                    for (UINT col = 0; col < m_dim; col++)                 
                    {                     
                        if (pCube == m_pCubeArray[face][row][col])                     
                        {                         
                            if (col > 0)
                            {
                                pTestCube = m_pCubeArray[face][row][col-1];
                                if (pTestCube && (restrictColor == false || pTestCube->m_colorEnum == m_pStartCube->m_colorEnum))
                                {
                                    if (CheckPathRecursive(pTestCube, restrictColor))
                                    {
                                        pathFound = true;
                                    }
                                }
                            }
                            if (col < m_dim-1)
                            {
                                pTestCube = m_pCubeArray[face][row][col+1];
                                if (pTestCube && (restrictColor == false || pTestCube->m_colorEnum == m_pStartCube->m_colorEnum))
                                {
                                    if (CheckPathRecursive(pTestCube, restrictColor))
                                    {
                                        pathFound = true;
                                    }
                                }
                            }
                            if (row > 0)
                            {
                                pTestCube = m_pCubeArray[face][row-1][col];
                                if (pTestCube && (restrictColor == false || pTestCube->m_colorEnum == m_pStartCube->m_colorEnum))
                                {
                                    if (CheckPathRecursive(pTestCube, restrictColor))
                                    {
                                        pathFound = true;
                                    }
                                }
                            }
                            if (row < m_dim-1)
                            {
                                pTestCube = m_pCubeArray[face][row+1][col];
                                if (pTestCube && (restrictColor == false || pTestCube->m_colorEnum == m_pStartCube->m_colorEnum))
                                {
                                    if (CheckPathRecursive(pTestCube, restrictColor))
                                    {
                                        pathFound = true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    
        return pathFound;
    }

    Writing all the algorithms as small little helper functions ended up being EXTREMELY handy. Of course it would, but I was just surprised at how well things were working out. Having a function to “pop” a small colored cube and just watch the physics take care of the rest was really convenient. A small piece of code to check if cubes were adjacent, make random color cubes, check how long the path is between start and end points, or even just highlight or unhighlight the cubes; it all ended up being really useful.

    The most difficult part that I should have improved on was a way to automate testing for solutions. In hindsight, I should have written a debug function that randomly swaps cubes to stress test the solver equation. My initial release had a bug that would crash the game if you ever cleared the entire “top” row of the top face of the cube; there would be an out of bounds access when trying to find the next “valid” cube. Even when I knew there was this bug it was extremely difficult to track down, because it was so hard to reproduce. Having an automated solver would have allowed me to hit the bug much easier.

    There are also lots of aspects of the game I’d like to polish, but none of which would have been appropriate for the 48 hour time limit. It’s a good way to prove to yourself what’s really important in the game. At the very last 2 hours of the compo, I had no music and no title screen. I thought people could do without the title screen, but since my game isn’t the kind that many people can just pick up and start playing without any instruction (at least I worried about that, and given the comments I’ve received about how unclear the goal is at first, it seems other people agree), I decided it was more important to have a page to display rules than it was to have a nice soundtrack in the background. Most people I’ve showed the game to didn’t have the sound on when playing anyway, so hopefully I made the right choice. Still, there may have been some other feature I could have cut out so that I could have a more well rounded game. Maybe the physics was total overkill and the cubes could have just “disappeared”. Or maybe trying to fix the lighting and brighten up the world wasn’t worth the time. Or maybe I should have just been better at programming and not had any of the bugs I had. :)

    Anyway, thank you very much Ludum Dare for teaching me how to prototype FAST, for helping me learn more about what’s important to have an end product you can be proud of, and for proving to me that my game engine really -can- make a worthwhile 3D game in 48 hours!

    I’ve added my timelapse below. I hope someone out there finds it interesting.

    -Mike

     

     

    Leave a Reply

    You must be logged in to post a comment.


    All posts, images, and comments are owned by their creators.

    [cache: storing page]