Random Dynamic Levels - Part 2

This is part 2 of my collection of articles that'll deal with the theory (and the actual creation) of random dynamic levels for a (space)game. In part one we created a damn pretty maze and in part two we're going to modify it a good deal.

If you take a look at part one's output you'll notice that the code generates a pretty random maze. And there we got out first drawback: it's pretty darn random, way to random to assemble a man made structure and not quite what we would expect a spacestation / space ship to look like.

So the first modification I'm going to add will be a method that can reduce the randomness of the maze.

Part 2 - part 1 - making something not that random

My idea is to qualify the randomness by a percentage value, so a random factor of 0 will give you long straight passages that only change direction if the need to (random at that), while using a value of 100 the method will never (as far as it possible) return the same direction twice.

Of course that tiny little addition causes a lot of fuzz and requieres to rewrite a part of the core maze generator function. In part 1 I used a method to get all surrounding cells of a given point, but in order to use the direction modifier we need to use directions instead.

          //... skipped

          while (iCellCount < iTotalCells) {
                
                // get neighbor cells ...
                aCellDirections = myDungeon.getPossibleDirections(pCurrentCell);
                
                // set the cell
                if (aCellDirections.length != 0) {
                    
                    /* old way no direction modification used
                    iRndCell = rnd.Range(0, (aCellNeighbors.length - 1));
                    iRndDir = Dir.getDirFromPoint(pCurrentCell, aCellNeighbors[iRndCell]);
                    */
                    iRndDir = this.getFactoredRandomDir(iLastDir, aCellDirections, iDirChange);
                    pNextCell = myDungeon.getNextPos(pCurrentCell, iRndDir);
                    iLastDir = iRndDir;
                    
                    // remove walls
                    myDungeon.cell(pCurrentCell).setWall (iRndDir, WallType.OPEN);
                    // old way: myDungeon.cell(aCellNeighbors[iRndCell]).setWall(Dir.getOppositeDir(iRndDir), WallType.OPEN);
                    myDungeon.cell(pNextCell).setWall(Dir.getOppositeDir(iRndDir), WallType.OPEN);
                    
                    // store for later use ...
                    aCellStack.push(new Point(pCurrentCell.x, pCurrentCell.y));
                    // old way: pCurrentCell = new Point(aCellNeighbors[iRndCell].x, aCellNeighbors[iRndCell].y);
                    pCurrentCell = new Point(pNextCell.x, pNextCell.y);
                    
                    iCellCount++;
                } else {
                    pPopCell = aCellStack.pop();
                    pCurrentCell = new Point(pPopCell.x, pPopCell.y);
                }
                
            } // while

Some new variables in there: iLastDir (so we can keep track of the last direction used), pNextCell (a point that stores the next cell, basically just a temp. variable), iRndCell has been removed and aCellNeighbours has been renamed to aCellDirections ...

There are two new methdods: getPossibleDirections and getFactoredRandomDir. The first one returns an array that just contains directions that can be used (ie. cells that have not been visited yet), directions are simply stored as 0=North, 1=East and so one (I've encapsulated them into a Dir class to make it easier to read). The second method is a neat example how to make things overly complicated ...

        private function getFactoredRandomDir (iLastDir:int, aListDir:Array, iFactor:int = 50):int {
            
            var rnd:MersenneTwister = MersenneTwister.getInstance();
            var bChangeDir:Boolean = (rnd.Range(0, 99) < iFactor);
            
            var iReturn:int = iLastDir;
            
            // the last used dir is not in the list of possible new directions, so we need to pick a random one ...
            if (aListDir.toString().lastIndexOf(iLastDir.toString()) == -1) {
                iReturn = aListDir[rnd.Range(0, (aListDir.length -1))];
            } else {
                
                // we must change direction AND have at least 2 choices
                if (aListDir.length > 1) {
                    
                    if (bChangeDir) {
                        while (iReturn == iLastDir) {
                            iReturn = aListDir[rnd.Range(0, (aListDir.length -1))];
                        }
                    }
                    
                } else {
                    // just pick what's left ...
                    iReturn = aListDir[0];
                }
                
            }
            
            return iReturn;
            
            
        }

AS3 arrays (in CS3) don't have the nice method I know from c#: contains which would have been oh so easy to use here. I toyed for a fraction of a second with the idea to use a loop to check if a given value would be in an array, but then decided to go ... quick and dirty and use toString and lastIndexOf instead.

The code above is quite easy, so I only do a quick run through it...
- decide if we need to apply a direction change
- if we need to, check if the last dir is in the list of possible dirs, if not just pic a random new (this applies to both states: need to change and keep direction)
- otherwise just pick a random dir until it's not equal the last dir used

That's it.

Running the test app with different values seems to produce the desired results:
0% produces the most possible straight halls,
50% produces somewhat random halls
100% produces a maze with no straight hall at all.

Part 2 - part 2 - still way to much filled space ...

Looking at the maze reveals that there are no free spaces in it, of course we could just paint rooms over it, but I doubt it'll look like what I have in mind.
Randomly removing cells from the map is no option (even if we do check if we would just block a passage), but what about removing cells that just end the passage (ie: dead ends).
Looking at the maze again, it seems that we have (depending on the randomness of direction changes) a lot of them, so our next task would be to find those dead ends and remove them. The first "problem" that comes to me is that each time we remove dead ends, we'd create new ones. In order to clean up the map we only run the "removDeadEnds" methods a couple of times and we're done - right?

Not quite.

If we choose some unlucky values, it might happen that we kill the whole maze and that's something we don't want at all.

I decided to use a percentage of TotalCells that I want to be removed, so if we use 50%, the method should remove half of all available cells.

        public function removeDeadEnds (myDungeon:Dungeon, iRemoveDeadEnd:int = 20):Dungeon {
            
            var rnd:MersenneTwister = MersenneTwister.getInstance();
            
            var i:int;
            var j:uint;
            var iDir:int;
            var iRndCell:int;
            
            var iDeadEndsToRemove:int = Math.ceil((myDungeon.iWidth * myDungeon.iHeight) * iRemoveDeadEnd / 100);
            var iDeadEndCount:int = 0;
            
            var bExit:Boolean = false;
            
            var aTmp:Array;
            
            // the worst case may only return one dead end per run, so
            // to be sure we run it as many times as we may max need
            for (i = 0; i < iDeadEndsToRemove; i++) {
                
                aTmp = myDungeon.getDeadEnds();
                
                if (aTmp.length > 0 && !bExit) {

                    while (aTmp.length > 0) {
                    
                        // this is to make sure that the cells are somewhat even
                        // distributed if we do not use the whole lot
                        iRndCell = rnd.Range(0, (aTmp.length - 1));
                        iDir = myDungeon.cell(aTmp[iRndCell]).getDeadEndDir();
                        
                        myDungeon.cell(myDungeon.getNextPos(aTmp[iRndCell], iDir)).setWall(Dir.getOppositeDir(iDir), WallType.WALL);
                        myDungeon.cell(aTmp[iRndCell]).setWalls();
                        
                        aTmp.splice(iRndCell, 1);
                        
                        if (++iDeadEndCount >= iDeadEndsToRemove) {
                            bExit = true;
                            break;
                        }
                        
                    }
                } else {
                    break;
                }
                
            }
            
            return myDungeon;
            
        }

The comments should explain quite well what's going on in there. Only thing to mention is that I pic random dead ends if there are more available dead ends than cells to remove.

Compile and test ... and viola well done for today. :)

(I must admid it took longer to type all that than to code, so I had a bit of spare time left and coded something alse ;) )

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 if the server is down).

nGFX