Gaming Your Way

May contain nuts.

Random Dynamic Levels - Part 1

After a good while of non-techy pimpings I decided to go the x++ route and describe the process of diving into a new game ...

(CE is again on hold due to some gameplay issues I found during testplays - oh well)

There is no name to the game yet, but I can say as much as it will feature random dynamic level creation (as used in Diablo 1 for example), sci-fi themed, using RPG elements and use Unity (though the levels created will look quite different to Diablo, but the idea is the same).
I want to have random levels because that would add to the replay value of the game. I want a single game to last between 15 and 45 minutes. You should be able to start playing and kill the end-boss in that time. After that you should be able just play again, but with different set of maps ...

But to get things rolling a lot quicker I wanted to rapid prototype my ideas using flash/AS3 and then port it to c#.
The reason for this is quite simple: output. In order to "see" what the level will look like without having to worry about how to display them (ie. place 3d walls, create the assets). With using flash i can just grab the data from the generator classes and use the drawing api to quickly throw out a few lines to show the generated data.

Let's dive straight in.

Part 1 - part 1: To cell or to tile ... and is there anything we need before that?

Before I started I thought that it would be nice to move between maps (in case you thought you forgot something), to do so there needs to be a way to store the maps ... I thought of 2 methods:
a) store all visited maps
b) make them reproduceable

I prefer the later one.

So instead of using some built in random number generator I decided to use my "own" that takes a seed and the produces the same set of random numbers when using that seed - perfect.
I found some old AS1 source of some older rnd gen that I could have ported but a quick search showed that there are some more powerfull ones. After bit of research I decided to go with the Mersenne Twister algorithm. As I was too lazy to see if there was an AS3 port, I wrote my own implementation, though you could use any rnd method you want.

The next one was a bit tricky: cell based or tile based?
Tiles are easy to use and to handle, but they are limited to a single spot and mostly do only have a single "state", ie. you can walk on them or not. This might be ok in most cases but for what I have in mind they are too limited.

A cell in my case is a tile with 4 walls (north, east, south and west), if all 4 walls are set, the cell is "closed" ie. a solid rock in a clasical dungeon. The cell also stors a single integer value (so based on it's useage I could store an index in it.
Here is the code for the cell:

package com.gamingyourway.Dungeon {
    
    /**
     * Cell datatype
     * @version 2009 06 24
     * @author nGFX
     */

    public class Cell {
        
        public static const WALL:int = 0;
        public static const OPEN:int = 1;
                
        private var _aWall:Array;    // array of values ... 0=empty ...
        private var _iValue:int;    // stores a single value, ie. room num
        private var _bVisited:Boolean;    // has cell been visited
        private var _bCorridor:Boolean;    // is cell a corridor
        
        
        public function get aWall ():Array { return this._aWall; }
        public function set aWall (value:Array):void { this._aWall = value; }
        
        public function get iValue ():int { return this._iValue; }
        public function set iValue (value:int):void { this._iValue = value; }
        
        public function get bVisited ():Boolean { return this._bVisited; }
        public function set bVisited (value:Boolean):void { this._bVisited = value; }
        
        public function get bCorridor ():Boolean { return this._bCorridor; }
        public function set bCorridor (value:Boolean):void { this._bCorridor = value; }
        
        public function get wallCount ():int {
            
            var i:uint;
            var iCount:int = 0;
            
            for (i = 0; i < this._aWall.length; i++) {
                if (this._aWall[i] == 0) iCount++;
            }
            
            return iCount;
            
        }
        
        public function get isDeadEnd ():Boolean { return (this.wallCount == 3); }
        public function get isUnused ():Boolean { return (this.wallCount == 4); }
        
        /**
         * Creates a new empty (ie. all walls set) cells
         * @param    iValue    used to stor a single bit of info, ie. room num
         */

        public function Cell (iValue:int = 0) {
        
            this._aWall = [0, 0, 0, 0];
            this._iValue = iValue;
            this._bVisited = false;
            this._bCorridor = false;
            
        }
        
        /**
         * sets a single wall
         * @param    iDir    Direction of the wall
         * @param    iWall    value of the wall, 0 is a solid wall, any other value makes it "open"
         */

        public function setWall (iDir:int, iWall:int = 0):void {
            
            this._aWall[iDir] = iWall;
            
        }
        
        /**
         * return the value if the wall in iDIr
         * @param    iDir    direction of the wall to get
         * @return    value of the wall
         */

        public function getWall (iDir:int):uint {
            
            return this._aWall[iDir];
            
        }
        
        /**
         * shortcut for testing if there is a closed wall in iDir
         * @param    iDir    direction to test
         * @return    true if there is a wall
         */

        public function hasWall (iDir:int):Boolean {
            
            return (this._aWall[iDir] == 0);
            
        }
        
        /**
         * if the cell is a dead end, return the direction of the opening
         * @return    the direction of the opening
         */

        public function getDeadEndDir ():int {
            
            var iReturn:int = -1; // not a dead end
            
            if (isDeadEnd) {
                
                if (this._aWall[Dir.NORTH] != 0) iReturn = Dir.NORTH;
                if (this._aWall[Dir.EAST] != 0) iReturn = Dir.EAST;
                if (this._aWall[Dir.SOUTH] != 0) iReturn = Dir.SOUTH;
                if (this._aWall[Dir.WEST] != 0) iReturn = Dir.WEST;
                
            }
            
            return iReturn;
            
        }
        
        /**
         * returns a string representation of the cell
         * @return    a string for the falls of this cell
         */

        public function toString ():String {
            
            var i:uint;
            var strReturn:String = "";
            
            for (i = 0; i < this._aWall.length; i++) {
                strReturn += this._aWall[i].toString();
            }
            
            return strReturn;
            
        }
        
        
    }
    
}

 

Part 1 - part 2 - Storage and creation

To store the maps generated I wrote a simple Mapa datatype, it'll store a 2d array of cells along with some very basic methods to deal with the data.
The map type also stores width and height in an rectangle, to have an easy way to check if a point lies within the boundaries of the map.
Aditional methods so far:

hasCellInDir (pPos:Point, iDir:uint):Boolean
getNextPos (pPos:Point, iDir:uint):Point
getSurroundingCells (pPos:Point, bUsed:Boolean = false):Array


To create a map (let's call it dungeon for the sake of easiness) I didn't include the methods need to create a dungeon in the map class, instead I wrote a DungeonGenerator class, that returns a filled map class. This way I can mess around with the creation process without messing with the map class.

Part 1 - part 3 - Let's start with a simple maze ...

The most simple representation of a dungeon I can think of is a maze. Mazes are incredibly easy to create and they work oh so well with cells.

The walkthrough to create a maze:
1. create a map of "solid" cells
2. pick a random solid cell as starting point
3. get surrounding solid cells and pick a random one
4. knock the walls between these cells, store the "old" cell in a stack for later use
5. use the cell picked in 3 as new starting point and start over
6. if the current cell has no solid neighbours, pop one from the stack
7. repeat until there are no more solid cells


Easy, eh?

package com.gamingyourway.Dungeon {
    import de.drygoods.Random.MersenneTwister;
    import flash.geom.Point;
    
    /**
     * Dungeon generator
     * @version 2009 06 24
     * @author nGFX
     */
    public class DungeonGenerator {
        
        private var _Dungeon:Dungeon;
        private var _rnd:MersenneTwister;
        
        public function DungeonGenerator(iWidth:int, iHeight:int) {
            
            this._Dungeon = new Dungeon(iWidth, iHeight);
            
            this._rnd = MersenneTwister.getInstance();
            
        }
        
        public function createMaze (iDirChange:int = 100):Dungeon {
            
            var aCellStack:Array = new Array();
            var aCellNeighbors:Array;
            
            var iTotalCells:int = this._Dungeon.iWidth * this._Dungeon.iHeight;
            var iCellCount:int = 1;
            var iRndCell:int;
            var iRndDir:int;
            
            var pCurrentCell:Point = new Point(this._rnd.Range(0, this._Dungeon.iWidth -1), this._rnd.Range(0, this._Dungeon.iHeight -1));
            var pPopCell:Point;
            
            while (iCellCount < iTotalCells) {
                
                // get neighbor cells ...
                aCellNeighbors = this._Dungeon.getSurroundingCells(pCurrentCell);
                
                // set the cell
                if (aCellNeighbors.length != 0) {
                    
                    iRndCell = this._rnd.Range(0, (aCellNeighbors.length - 1));
                    iRndDir = Dir.getDirFromPoint(pCurrentCell, aCellNeighbors[iRndCell]);
                    
                    // remove walls
                    this._Dungeon.cell(pCurrentCell).setWall (iRndDir, 1);
                    this._Dungeon.cell(aCellNeighbors[iRndCell]).setWall(Dir.getOppositeDir(iRndDir), 1);
                    
                    // store for later use ...
                    aCellStack.push(new Point(pCurrentCell.x, pCurrentCell.y));
                    pCurrentCell = new Point(aCellNeighbors[iRndCell].x, aCellNeighbors[iRndCell].y);
                    
                    iCellCount++;
                } else {
                    pPopCell = aCellStack.pop();
                    pCurrentCell = new Point(pPopCell.x, pPopCell.y);
                }
                
            } // while
            
            
            return this._Dungeon;
            
        }
        
    }
    
}


The code of the dungeon generator ... for now only with the maze creation in it.
Note that the variable iDirChange is currently not used, but I'll go over it in the 2nd part of this article.

I think that is enough for today, you can see the result (and from the upcoming articles, too) Random Dynamic Level Creation Test page (or here).

See you next time when I add some direction modifications and take care of dead ends ...

nGFX


Comments (7) -

  • Iain

    6/24/2009 5:05:08 PM |

    That's cool as hell!

  • tonypa

    6/25/2009 7:41:34 AM |

    Is it going to be like rogue?

  • tonypa

    6/25/2009 7:46:35 AM |

    I think saving 4 walls in each cell is overkill. Suppose you have cell with wall on right side, it means the cell right from it would always have wall on left side. Unless you are doing some sort of one-way walls, you only need to save 2 walls in each cell and get other 2 walls from neighbouring cells.

  • nGFX

    6/25/2009 7:50:23 AM |

    Hi tony,

    "Is it going to be like rogue?"
    not quite and very :)
    I think RPG elements and random levels are what makes it rogue like, the game that most inspired me for these two elements was "sword of fargoal" (http://www.fargoal.com/). I guess the sci-fi part will add a bit of diversification and introduce some more gameplay elements (to be revealed later ;) )

    nGFX

  • nGFX

    6/25/2009 8:02:15 AM |

    "I think saving 4 walls in each cell is overkill."
    Yep, that's pretty much correct for the creation process, but I think I have some valid reasons to do so:
    1. it makes it easier to check which side of the cell can be used
    2. it simplifies the detection of dead ends (ie. a cell with 3 walls), which would otherwise invold checking the 4 neighboring cells
    3. direction detection (same as the two above)
    4. (the most valid one for me) they will be needed when I plot the ingame visuals, each wall cannot only be 0 (for wall) and (1 for no wall), but I can use it to assign different "textures" to each by using other numbers than 1.

    That's right now not very well done, but for the next article I'm refactoring (or refining) some of the methods to reflect that.

    nGFX

  • tonypa

    6/25/2009 8:39:42 AM |

    Well, suppose you want to add or remove a wall by opening or closing doors. You need to modify 2 cells then or you would end up in situation where one cell thinks there is a wall and other thinks the wall is missing (again, would be great to make one way doors). Basically I prefer simpler storing system where one piece of data is all you need, maybe some sort of wall class where each wall between 2 cells exist once and you can access it from both cells to check it or change it.

    But I also dont know how its going to evolve in next chapters so you can safely ignore my moanings :)

  • nGFX

    6/25/2009 10:25:12 AM |

    :)
    Nah, these are valid thoughts.

    I must admit that even cells have their drawbacks, basically I'd say it'll be even easier to use a tilebased approach.

    My idea is that you don't need to open a door in two cells, because a wall only exists from the "inside" of the cell, so in thoery you coul have very eays secret doors by having a door in one cell and a wall in the other, though while painting the levels (or assembling the 3d data later on) I do have to make "2" doors of course.

    On the long run, I still need to find ways to translate complete sets of "cells" (ie for a room) into  the biggest part I can cover with 3d assets - so I don't have to use one piece of wall per cell wall and instead use a bigger one ...

    Oh well, I think I start refining code and implementing the next step now ...

    nGFX

Comments are closed