In the last two articles  we made a maze and then destroyed it by adding a lot of free space. In part 3 of this articles I'm going to add some rooms to the empty space and add some doors ...

Part 3 - part 1 - why seperate things and make rooms?

At a first glance it might not be necessary to seperate data into dungeon, room and cell, but thinking ahead a bit it should make sense ...
My idea is that you can have the dungeon which holds the complete map (with the basic room data rendered into it) and the rooms so you access them easier and most important do some magic with them later. One of the neat things is that you could use a different tiling for rooms making them more detailed or use the additional map data for skinning (when rendering the dungeon into a tile based map).

The main difference between a room and a dungeon is that the room consists of empty cells and has walls along it's boundaries. So the first additional method we'd add to the Room class will be the init method, which simply sets all cells so they form a rectangular room.

public function initCells ():void {
            
    var x:uint;
    var y:uint;
    var cellTmp:Cell;
            
    for (x = 0; x < this.iWidth; x++) {
        for (y = 0; y < this.iHeight; y++) {
                    
            cellTmp = this.cell2(x, y);
            cellTmp.setWalls(WallType.OPEN);
                  
            if (x == 0) cellTmp.setWall(Dir.WEST, WallType.WALL);
            if (x == (this.iWidth - 1)) cellTmp.setWall(Dir.EAST, WallType.WALL);
            if (y == 0) cellTmp.setWall(Dir.NORTH, WallType.WALL);
            if (y == (this.iHeight - 1)) cellTmp.setWall(Dir.SOUTH, WallType.WALL);
        }
    }
}

We could later add methods to create different rooms (ie. two overlapping rectangles, circular rooms), but for now that will do ...

I also added a getter setter for Offset to the room, so we can modify the x and y pos of the bounding rect that we stored in the map class (you'll see later what's that for).

So we now have a room, but how do we get that sucker into the map, or (as just putting it into the map isn't really an issue) where can we place it *best*.

There are a few things that I want to watch when placing the rooms ...
- a room should not overlap any existing room, we rather don't at it
- placing a room at a place where it doesn't touch anything, is something we don't want, too
- rooms overlapping corridors should be avoided
- rooms touching dead ends is something we want (what's nice than finding a room after a long winded corridor?)
- rooms touching any sort of wall is OK, too

Yet again we (as humans) could just look at the map and say "here, there and there" and done, but that stupic piece of plastic cannot... we need to apply some sort of scoring to the whole placement mess.

Here's a bit of pseudo code ...

• start with a VERY high best score, lets say 999999999999 and set current score to 0 ...
  
• Loop over every cell in the dungeon
• at any given position check if the new room overlaps any rooms already in there
  if so, we add 5000 to our current score, otherwise we add nothing
• now loop over every cell in the room and compare it with the current dungeon cell (offsetting the room to the current position)
• if the current room cell touches an empty cell (in the dungeon), add 10
• if we touch a wall, add 3
• if we touch a dead end, add 1
• if the final current score is lower than the best score, sreplace the best score and store the current position as the best possible location
• if the score is higher than the "room overlaps room" score, assume that it only can be placed overlapping a room and drop it, otherwise add it to the dungeon

Here is the scoring code:

private const TOUCH_DEADEND:int = 1;
private const TOUCH_WALL:int = 3;
private const TOUCH_EMPTY:int = 10;
private const OVERLAP_ROOM:int = 5000;
private const OVERLAP_CORRIDOR:int = 100;
        
public function fitMazeRoom (myRoom:Room):Boolean {
    
    var iBestScore:int = 999999999;
    var iScore:int = 0;
    var pBestPos:Point = new Point(0, 0);
    var pOffset:Point = new Point(0, 0);
    
    var cellDungeon:Cell;
    var cellNext:Cell;
    
    var rectTmp:Rectangle = myRoom.rectBound.clone();
    
    var i:uint;
    
    var x:int;
    var y:int;
    
    var xx:int;
    var yy:int;
    
    var iRoomID:uint;
    
    var bAddRoom:Boolean = false;
    
    // loop over map (- roomsize)
    for (y = 0; y < (this.iHeight - myRoom.iHeight + 1); y++) {
        for (x = 0; x < (this.iWidth - myRoom.iWidth + 1); x++) {
            
            // do the scoring ...
            iScore = 0;
            
            // check room/room overlapping
            rectTmp.x = x;
            rectTmp.y = y;
            for (i = 0; i < this._aRoom.length; i++) {
                if ((this._aRoom[i] as Room).rectBound.intersects(rectTmp)) {
                    iScore += OVERLAP_ROOM;
                }
            }
            
            // check room/dungeon overlapping
            for (yy = 0; yy < myRoom.iHeight; yy++) {
                for (xx = 0; xx < myRoom.iWidth; xx++) {
                    pOffset.x = (x + xx);
                    pOffset.y = (y + yy);
                    
                    cellDungeon = this.cell(pOffset);
                    if (cellDungeon.iType == RoomType.CORRIDOR) iScore += OVERLAP_CORRIDOR;
                    
                    if (yy == 0) {
                        iScore += this.getCellScore(this.cell(this.getNextPos(pOffset, Dir.NORTH)), Dir.NORTH);
                    }
                    if (xx == (myRoom.iWidth - 1)) {
                        iScore += this.getCellScore(this.cell(this.getNextPos(pOffset, Dir.EAST)), Dir.EAST);
                    }
                    if (yy == (myRoom.iHeight - 1)) {
                        iScore += this.getCellScore(this.cell(this.getNextPos(pOffset, Dir.SOUTH)), Dir.SOUTH);
                    }
                    if (xx == 0) {
                        iScore += this.getCellScore(this.cell(this.getNextPos(pOffset, Dir.WEST)), Dir.WEST);
                    }
                }
            }
            
            if (iScore < iBestScore) {
                iBestScore = iScore;
                pBestPos = new Point(x, y);
            }
            
        }
    }
    
    // add to dungeon if it doesn't overlap any other rooms
    if (iBestScore < OVERLAP_ROOM) {
        myRoom.pOffset = new Point(pBestPos.x, pBestPos.y);            
        bAddRoom = true;
    }
    
    return bAddRoom;
    
}

private function getCellScore (cellNext:Cell, iDir:int):int {
    
    var iScore:int = 0;
    
    if (cellNext.iType == RoomType.CORRIDOR) {
        if (cellNext.isDeadEnd) {
            iScore += TOUCH_DEADEND;
        } else if (cellNext.hasWall(Dir.getOppositeDir(iDir))) {
            iScore += TOUCH_WALL;
        } else {
            iScore += TOUCH_EMPTY;
        }
    } else {
        if (cellNext.iType == RoomType.ROOM) {
            if (cellNext.hasWall(Dir.getOppositeDir(iDir))) {
                iScore += TOUCH_WALL;
            } else {
                iScore += TOUCH_EMPTY;
            }
        } else {
            iScore += TOUCH_EMPTY;    
        }
    }
    
    return iScore;
    
}

That's ugly and not very fast, but it works.

Some additional info about adding the room to the dungeon: whenever we place a room cell in the dungeon map it's a good idea to check if it overwrites a corridor and if it's a cell on the outer bounds of the room add a new wall to the touching cell (if it's not empty) ...

So far so good, we have rooms in the map, but they cannot yet be reached because we're missing doors ...

Part 3 - part 2 - adding doors and cleaning up

You might ask why I haven't added the doors as soon as I've added the room to the dungeon (and I might just reply that I just didn't mention it), but nope, I didn't add doors - that's the next step.

The reason is quite simple, though. I don't want doors cluttered all over the space and because of that I added another (optional) thing to the room data: hasDoorInDirection ... this way we make sure that there is only one door per wall / room when we add doors ...

Yet again we loop over all rooms and over their outer bounding cells, if we touch another cell, store the current position as possible door location. Then pick a random one per direction and check if it touches another room and if this room might already have a door ...
I guess that's easier to explain with some more code:

private function createDoors (myDungeon:Dungeon, bOneDoorPerRoom:Boolean = true):void {
    
    var rnd:MersenneTwister = MersenneTwister.getInstance();
    
    var i:uint;
    var j:uint;
    
    var x:uint;
    var y:uint;

    var cellTouch:Cell;
    var myRoom:Room;
    
    var aDoor:Array;
    var pDoor:Point;
    var pNext:Point;
    
    for (i = 0; i < myDungeon.aRoom.length; i++) {
        
        myRoom = (myDungeon.aRoom[i] as Room);
        
        aDoor = [[], [], [], []];

        // collect possible door locations ...
        for (y = 0; y < myRoom.iHeight; y++) {
            for (x = 0; x < myRoom.iWidth; x++) {
                
                pDoor = new Point(myRoom.pOffset.x + x, myRoom.pOffset.y + y);
                
                if (y == 0 && pDoor.y > 0) {
                    pNext = myDungeon.getNextPos(pDoor, Dir.NORTH);
                    cellTouch = myDungeon.cell(pNext);
                    if (!cellTouch.isUnused || cellTouch.iType == RoomType.CORRIDOR) {    // the check for a cooridor is needed because they might be just one cell long ...
                        aDoor[Dir.NORTH].push(pDoor);
                        if (cellTouch.isDeadEnd) aDoor[Dir.NORTH].push(pDoor); // double chances for dead ends ...
                    }
                }
                
                if (x == (myRoom.iWidth - 1) && pDoor.x < (myDungeon.iWidth - 1)) {
                    pNext = myDungeon.getNextPos(pDoor, Dir.EAST);
                    cellTouch = myDungeon.cell(pNext);
                    if (!cellTouch.isUnused || cellTouch.iType == RoomType.CORRIDOR) {
                        aDoor[Dir.EAST].push(pDoor);
                        if (cellTouch.isDeadEnd) aDoor[Dir.EAST].push(pDoor); // double chances for dead ends ...
                    }
                }
                
                if (y == (myRoom.iHeight - 1) && pDoor.y < (myDungeon.iHeight - 1)) {
                    pNext = myDungeon.getNextPos(pDoor, Dir.SOUTH);
                    cellTouch = myDungeon.cell(pNext);
                    if (!cellTouch.isUnused || cellTouch.iType == RoomType.CORRIDOR) {
                        aDoor[Dir.SOUTH].push(pDoor);
                        if (cellTouch.isDeadEnd) aDoor[Dir.SOUTH].push(pDoor); // double chances for dead ends ...
                    }
                }
                
                if (x == 0 && pDoor.x > 0) {
                    pNext = myDungeon.getNextPos(pDoor, Dir.WEST);
                    cellTouch = myDungeon.cell(pNext);
                    if (!cellTouch.isUnused || cellTouch.iType == RoomType.CORRIDOR) {
                        aDoor[Dir.WEST].push(pDoor);
                        if (cellTouch.isDeadEnd) aDoor[Dir.WEST].push(pDoor); // double chances for dead ends ...
                    }
                }
            }
        }
        
        // now just pick one door per side ...
        for (j = 0; j < Dir.NUM_BASEDIR; j++) {
            
            if (aDoor[j].length > 0) {
                
                pDoor = aDoor[j][rnd.Range(0, (aDoor[j].length - 1))];
                pNext = myDungeon.getNextPos(pDoor, j);
                
                if (!myRoom.hasDoor(j)) {
                    myRoom.setDoor(j, pDoor);
                    
                    if (bOneDoorPerRoom && myDungeon.cell(pNext).iType == RoomType.ROOM) {
                        myDungeon.getRoom(myDungeon.cell(pNext).iValue).setDoor(Dir.getOppositeDir(j), pNext);
                    }
                    
                    myDungeon.cell(pDoor).setWall(j, WallType.DOOR);
                    myDungeon.cell(pNext).setWall(Dir.getOppositeDir(j), WallType.DOOR);
                }
            }
        }
    }
}

Viola done ... but wait one more thing, cleaning up ...

The last step might not be needed, but imho it makes some nice dungeons: after we've added all the rooms and doors, we remove all remeaning dead ends. This way there will be no corridors just ending somewhere and the map looks nicer.

So we just run the removeDeadEnds method again, this time with 100% ... now:done.

As with the last parts, the link to a working demo of the whole mess is here or here.

nGFX

I just needed to do some eye-candy the other day as a hour break from the current project, so I came up with this ribbon effect

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

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

Hi folks,

most regular readers will have noticed that we've jumped onto the Unity wagon after it finally came out for the windows world and so I think it's time to write down a few of my thoughts ...

What it is:
an easy to use development platform for 3d games (although easy, well, I'll cover that later)

What it is not:
Simply put: easy.
And it is not flash.

So?
The best part of it is, that you can do a decent 3d based game with it quite quickly, that is if you know how to code unity (I might have twittered once or twice that the docs are not one of the strong points) and (what's more important if you or someone in your team) can do low poly 3d.

So?
I really can't stress enough that it is NOT flash, not at all, when you get started with Unity all is nice and straight forward, but once you hit the point where you really would like to do a quick tween for the main menu, or use a fancy drop shadow on your font ... you'll probably start cursing and wish you could use a timeline and some keyframes.

One of the really big letdowns for me was to discover that a quick, easy and nice UI is not going to happen fast in Unity. You can get away with it if you don't need dynamic text to appear, but I need to do a lot of stuff with that, because nearly all of our games are prepared to be played in at least two languages.

How does all that relate to the title?
When I first got in touch with flash (6 I think) AS was really nothing more than a scripting language, coding for the best part was ... shit and most of us messed with onEnterFrames per movielclip. Then AS2 hit the light of the day and with AS3 it came very close to real coding ...
But when I entered the Unity world it seems like the old distributed scripts came back to haunt me. You've got the choice of using a set of different languages: javascript like, c#, boo and some others.

JS on the one hand is easy to use, ridiculously lose typed and commonly used. I really don't like lose typed coding, so for me it was c# ...
Anyway something that commes very close the the old MC based onEnterFrame is Update ... so a script that would move the object 1 "unit" (since we have no pixel) to the left would be:

function Update () {
    transform.position.x++;
}

(or something very close to that, I said I use c#, oh and I'm sure I saw some other methods to do the same)

Save that as a ".js" text file, add that to a cube on stage and viola (there you have the back to script part covered).

I hope you won't be doing that for a complex game, but ... thinking back ... I knew people who did that with flash  ** shudder **.

As I already mentioned, I hate lose typed coding and as I used c# for some years now for coding anyway it was a logical choice (that and the fact that I could continue using Visual Studio).

Oh and did I stress that there is NO timeline?

Everything you want to have animated either needs to be coded (ie for dynamic text) or already be animated in a 3d app ...

Oops, I think I need to get back to work ...

nGFX

ps: just to have something to look at a screenie of the menu (the start of a camera move) of my "test" game to see how I get along with Unity, if everything works well, I might be able to invite for a private beta test on Friday (give me a shout if you want to) ...

Hey my beauties. Sorry I've been ignoring you all, I've just been pretty ill the past week or so ( I was going to say I've been sick, but I used that joke up last post ). It's me not you, honestly.

Just a short post to go with a small experiment. I've done the plasma effect to death in Flash but it's a nice little effect to play with when trying out a new language so I thought I'd see how straight forward it would be to port to Unity.

The answer is... fairly. If nothing else I've discovered that for...in is nasty slow in Unity ( All these new coding caveats to learn, joy ).

Anyway I still feel like crap, so I'm going to cut this short. The effect is hiding behind this link and it's really nothing special, I just wanted to show something after being away for a week or so. If anyone would like the source just ask in the comments.

Squize.

PS. I'm so sorry to everyone I owe an email too, I will catch up, and let's be honest you should know how crap I am by now.

Quite a descriptive title for this post for a change.

So what's wrong with this code:

if (this._iDrawLayer & ChipsGame.VIEW_LAYER_A == ChipsGame.VIEW_LAYER_A) {
// draw contents of layer A ...
}

nothing, really. Nonetheless it's not working in CS3 (yet again, prove me wrong).

Basically it's just the unoptimized check if a certain bit is set or not. Let's do some traces:

trace ("with ():", ((this._iDrawLayer & ChipsGame.VIEW_LAYER_A) == ChipsGame.VIEW_LAYER_A))
trace ("without ():", (this._iDrawLayer & ChipsGame.VIEW_LAYER_A == ChipsGame.VIEW_LAYER_A))
trace ("values :", this._iDrawLayer & ChipsGame.VIEW_LAYER_A , ChipsGame.VIEW_LAYER_A)

The result is this:

with (): true
without (): 1
values: 1 1

Interesting, isn't it?
It seems like the compiler chains the & and the == for some reason that escapes me...

So if you get something undesiered with bitwise operators ... use ( and ) around it.

nGFX

Another quick break down of an effect in 651.

Here's another really old trick we used in 651.

Now 651 is history I thought it may be of interest to go through how some of the parts work.

Let's start with the boring bit for today, the actual structure. To make testing it easier, and to be able to swap and change the order to make sure it felt right, I used a pretty simple yet modular approach,

//------------------------------------------------
// Demo classes
//------------------------------------------------
        private var logo:Logo;
        private var credits:Credits;
        private var twister:Twister;
        private var vectorBalls:VectorBalls;
        private var pimp:Pimp;
        private var showReel:ShowReel;
        private var water:Water;
        private var fin:Fin;
        
        private var sequenceOrder:Array=new Array("logo","twister","vectorBalls","pimp","credits","showReel","water","fin");
        private var sequenceOffset:int;

The sequenceOrder array kinda speaks for itself. The other part of the code is just as straight forward:

//---------------------------------------------------------------------------------------
        public function sequence():void{
            switch (sequenceOrder[sequenceOffset]){
                case "logo":
                    logo=new Logo();
                    break;    
                case "twister":
                    twister=new Twister();
                    break;    
                case "credits":
                    credits=new Credits();
                    break;    
                case "vectorBalls":
                    vectorBalls=new VectorBalls();
                    break;    
                case "pimp":
                    pimp=new Pimp();
                    break;    
                case "showReel":
                    showReel=new ShowReel();
                    break;    
                case "water":
                    water=new Water();
                    break;    
                case "fin":
                    fin=new Fin();
                    break;    
            }
        }

//---------------------------------------------------------------------------------------
        public function finished():void{
            if(++sequenceOffset==sequenceOrder.length){
//Finished            
            } else {
                sequence();
            }
        }

Each segment is totally independent, ie it has it's own init and housekeeping routines, there's no co-dependency at all. To start the demo the sequenceOffset var is set to 0 and then the sequence() method is called.
When a segment has finished, it calls it's houseKeeping() method to dispose of all the bitmaps and removes all the sprites from the stage, and then calls the finished() method ( Hence it being public ).

That's all there is to the underlying structure which runs the demo, it really doesn't get any more straight forward.

Squize.

What do the following things have in comon?

test.swf (5,87 KB)

goAway.swf (8,07 KB)






After my funny little episode with the hacked version of Law of the West I started wondering how to prevent that little pricks that can use an URL changer or decompiler to mess around with my stuff. Above you see what might be a solution. It will not stop someone who really, really wants to see your code from seeing it in the end but it will make it reasonably hard.

So how can you prevent that someone just grabs a decompiler, changes things and publish it back?

Maybe if there is no game inside the swf, at least not directly visible.

This is a screenshot of the library of the goAway.swf. Nice, eh?

Right now goAway is a neat little console app (so you can batch it), that takes an swf, optional a textfile full of vars (so you can check them later from the game itself) and spits out a png.

This can be included in another swf (to be released) and is unpacked after loading - and viola you have your swf again, though it'll be like a loaded swf, so you loose your "root".

There is a lot more security related portential behind this:
- load the png from a server instead of including it.
- use a key to decrypt the png
- create the png on the fly on the server each time with a new key
- store multiple swfs/files in a single png to pack a multi file game into a single distributable swf without a lot of trouble
- and and and

The above swf is just a proof of concept and there is still alot to do on the goAway app in oder to make it useable (maybe a frontend, new features (like dynamic png dimensions, splitting into multiple png files for more security, different ways of reading writing the data into the png (byte order)) not to mention an AS3 class to easily handle the goAway png.

After all I'm quite pleased with the idea, as it makes it quite hard for script kids to mess around with a published flash file with the available tools. Making hacking a game just that little bit harder that is needed to seperate the users from the coders.

And of course SiCo will be used to obfuscate the goAway code ...

Ha!

nGFX

I had an idea last week on how to code a voxel landscape, so a couple of nights after work later, here's my little...

Trip to Mars

( No preloader, but it's only just under 400k )

Just to caveat it, it's not the quickest routine ever and may chug if you've got a slower machine, this is more looks rather than speed.

I'm really pleased with how it turned out. It uses a real image of Mars for it's height map, so it's a lot more rocky than the usual perlin noise generated maps.

That's about it really. I was going to save it up for a demo I have in mind, but I've got no time for it for the foreseeable future, and if I do re-use it as part of a bigger production I've got some ideas to improve it anyway.

Squize.

I needed a bit of a break from all things gamey this evening, so I looked back over my old plasma source.

By stripping the maths down to the bare minimum and using a for...each loop along with other bits and bobs ( Double buffering the screen helped too ) I managed to increase the fps from the 31/32 mark to 42/43.
Pretty sweet.

I thought I could either post it like that, smug in the knowledge that I've speeded up a pretty intensive routine by ( In real terms ) quite a lot, or do something slightly different.

I opted for a bit of a play, and was really surprised ( And pleased ) to see you can attach the same bitmap to multiple sprites and it still updates. From there it was a no brainer what to do with it. In real terms this is plotting less pixels than the plasma effect ( That was 150x150 doubled ), this is a 120x120, but it's a much bigger effect in terms of screen size.

Kaleidoscope

Squize.

So I had a long night yesterday, finishing off some unloved project that I've been delaying for some time now and as some sort of personal reward for being so brave I played a bit with my "play media on the wii" idea...

I had written the service for getting drives, dirs and files a few days ago (don't try this on real a webserver :) ), so I *just* had to do some flash frontend ...

Oh well, I should have known better ....

To give you a basic idea of what I was thinking of, here's a (sized) image:


I thought that fiddling with scrollbars would be a no-go on the Wii, so I came up with the idea of a dragable "canvas".
So you can click on a drive, which opens the folder list for it, clicking on a folder... you get the point.

Now here starts the tricky part ...
Once I had the drive list done, I noticed that it lists floppy disks and CD/DVD drives, too. I either had to give the drive type when getting the list from the service or don't show them (in both cases this means to mess with the service's code - that for quick and easy).
The next thing I noticed that the service currently doesn't care if a directory is hidden or not (and if it is hidden, I might need to know in my flash file).

Well, it doesn't end there (of course not), because I might need to know some more about the files inside a folder (size is obvious) - oh and what is if there are some more files/folders (say you have a folder with 1000 images or mp3s) ...

That clearly killed my idea of a quick solution, I'll have to heavily modify the service (although I had to do that anyway) and there are some quite important things to consider for the swf (I may have to drop the drag idea).

We will see.

nGFX

It's so long ago I've posted something that it's untrue. It may be because there was nothing much to say during that time, that is projects not really game related or so absurdly NDA protected that even to mention the general direction would be ... well expensive.

You surely remember my last (!) post where I have a bit of a rant about the media capabilities of the Wii (still no games on it for me, though). Right now this neat piece of hardware sits beneath the TV left of it's bigger and way more often used brother the xbox 360. All I do with it (you remember: playing Wii Sports after a lot of coding) is using it as TV based web browser.

Webbrowser ... well that brought the idea.

(OK, that and the fact that we had some friends here and wanted to look at some photos from the last party. One of them (a "no gamer") asked if there would be some music to play along and I had to admit that it's not working anymore (due to the glorious photo chanel update))

So inspired be the fact that I got the 360 playing my mp3/fotos/movies from my pc in no time, I started to set up a small test environment webpage on my local IIS to see if I could use the browser to browse my pc's hdd. And of course it works.

So I wrapped the output with some XML and viola I had a flash 7 swf that I could use to browse the directories on my pc. Well done.

The only drawback atm is the fact that there has to be a webserver running ... I guess you can't convince most people to install an IIS on their PC to get some media on the Wii. After a few minutes of thinking it came to me that I could write my own - or better integrate cassini (an open source micro webserver) - to host the services for the Wii ...

Well, let's see where that leads to ...

nGFX

[edit] just found this while hunting for informations about the Wii browser flashplayer ...
http://my.opera.com/[..]flash-7-and-not-8-or-9

But I found a sweet article about making a textured tunnel, and before I knew it this bad boy was up and running...

Tunnel.swf (16.1 KB)

( No displacement maps, just pure pixel plotting. as3, I'm loving you )

I've really got an urge to do a full blown demo. I know I've got far too much on, but it's gnawing away at me.

Squize.

So after Squize was boring us with that grid, I thought it's time to give AS3 a go (finally).

While diving into the "new" AS version I also tried a new editor, I use(d) se|py for AS2, but felt the need to try something new editor wise, too.

I had a look at SharpStyle Neutron, a coding plugin for Visual Studio 2005 (imho one of the best coding environments), but as it's AS2 only (the current beta is able to handle AS3 it seems) so while it's great for AS2 it didn't help me on my current task ...

Another Editor I wanted to give a go was FlashDevelop. I instantly fell in love with the current 3.0.0 beta build. It feels like Visual Studio, it's fast and has some niffty, helpfull features.

So I did what I always do in a new language, I coded a 3d formular plotter, the idea reaches back to the good old c64 days, though, it took a whole night to render a way smaler version.

Anyway this is what I came up with during my first 2 hours of AS3:
plotter.swf (1,31 KB)

It's not that impressive, but it's fast (just used an onEnterFrame to show the plotting).

<olli/>

Well I carried on working on the GWars effect last night, and discovered quite a few things.

The example from yesterday used a raster line plotter, but I tried it with the Flash drawing API ( Which uses Flash's vector plotter ) and it crapped all over it in terms of speed. I was surprised but I guess it's 'cause the dAPI works on a "hardware" level.

Next up was to look at Geometry Wars itself, where I realised that the grid was made up of a load of dots rather than lines. Back to the code, I used the dashTo prototype ( An example of that can be seen here ) and got a nasty drop in speed. No shock there really. Then it dawned on me that the raster line drawer could be kinda handy here, after all it's just a loop and some setPixels, if we're skipping pixels to make a dotted line then it'll reduce the length of the loop.

Sweet, ran a lot quicker.

Next up was a bit of a lucky one. I had a bitmap which I copied the grid to every couple of frames and ran a ColorMatrixFilter on it to fade it down ( By reducing the alpha every frame ), and where I was putting a surround on the screen and positioning things I screwed up the alignment of this bitmap, so I could see the lines slightly offset. It didn't take long to align it so it was offset by half a grid position on the x/y, hey presto, twice as many lines and for no more hit than it was running at anyway.

Time to drop a player sprite in there ( My very first as3 one, I imagine there will be more ). I really liked the control system in neon2, where holding ctrl down stopped the player ship so you could just rotate and shoot, and as3 just gave it to me for free.
When using a MouseEvent.MOUSE_DOWN event listener, the event which is called has an arg passed to it. This arg has all types of interesting goodies in it, one of which is a boolean ctrlKey flag. So adding the keyboard control I wanted took about 3 lines, and from a cpu point of view it's a freebie ( Ok, at the hardware level Flash is scanning the key, but it does anyway on a MOUSE_DOWN event so it's not like I'm polling the keys seperately ).

Want to see it ? Yeah you do.

GWars_v2.swf (37.69 KB)

Squize.

Inspired by this thread at FK games I decided a nice little break from mansion would be in order and started playing with a geometry wars style grid.

It's still not a 100% right, and I think to get much more speed out of it I'm going to have to really rethink it, but it does look pretty cool.

A lot of the actual clever stuff which is beyond me was taken for a example at the always astounding liquid journey site. I also used bytearray.org's raster based line plotter, which I tweaked slightly to try and get a few more ms out of it ( Code for the tweak is here )

public static function quickLine(bmp:BitmapData,x0:int,y0:int,x1:int,y1:int,c:Number):void{
    var i:int;
    var xinc:int;
    var yinc:int;
    var cumul:int;
    var x:int = x0;
    var y:int = y0;
    var dx:int= x1 - x0;
    var dy:int= y1 - y0;
    xinc = ( dx > 0 ) ? 1 : -1;
    yinc = ( dy > 0 ) ? 1 : -1;
    dx = (dx ^ (dx >> 31)) - (dx >> 31);            //Math.abs
    dy = (dy ^ (dy >> 31)) - (dy >> 31);
    bmp.setPixel32(x,y,c);

//Test for a straight vertical line
    if(dx==0){
          for ( i = 1 ; i <= dy ; i++ ){
            y += yinc;
            bmp.setPixel32(x,y,c);
        }
        return;
    }
    if(dy==0){
          for ( i = 1 ; i <= dx ; i++ ){
              x += xinc ;
            bmp.setPixel32(x,y,c);
        }
        return;
    }
   
    if ( dx > dy ){
        cumul = dx >> 1;
          for ( i = 1 ; i <= dx ; i++ ){
            x += xinc;
            cumul += dy;
            if (cumul >= dx){
                  cumul -= dx;
                  y += yinc;
            }
            bmp.setPixel32(x,y,c);
        }
    }else{
        cumul = dy >> 1;
          for ( i = 1 ; i <= dy ; i++ ){
            y += yinc;
            cumul += dx;
            if ( cumul >= dy ){
                  cumul -= dy;
                  x += xinc ;
            }
            bmp.setPixel32(x,y,c);
        }
    }
}

And that's about it really. I'm hoping to play with this some more next time I get chance and hopefully make a homage to a certain popular shoot'em up.

GWars.swf (7 KB)

Squize.

This is it, the last demo effect I'm going to be doing in as3. There are of course more I'd like to do ( Using a plasma as a texture would be a neat one that springs to mind ) but I guess I should be more productive in an actual game kind of way with my free time, rather than pointless eye candy.

Anyway, enjoy yet another cube variation.

DotVectors.swf (32.28 KB)

Squize.

I know I owe a couple of posts about the GOL games, but I've kinda fallen behind.

To get out of trouble, here look at this

Polygons.swf (147 KB)

Phew, that should buy me some time until I can pull my finger out and take some nice grabs.

Squize.

Still trying to get my head around as3, it's a saucy little minx alright.

Anyway, he's yet another old school demo effect, and another one I never managed to get working on the Amiga at the time ( Flash just seems to be an outlet for my past failures as a coder ).

Plasma.swf (5.47 KB)

Guess a bit of texture mapping should be next to keep with this theme.

( For a lot more demo style eye-candy check the experiments cat., and to see them all shoved together and wrapped up with plenty of love, check out 651 )

Squize.

I've had a bit of down time since Friday, so I thought I should finally look into AS3.

I've heard lot's of comments from fellow game devs. That it's a steep learning curve. Being kinda cock sure I thought "It can't be that bad".

Oh silly silly me.

I remember hating AS2 when I crossed over to that late last year, and loving it now, so I know that AS3 is just going to be the same. That nasty month or two of "If I could do this in AS2 it'd have been done 3 hours ago", and that feeling of going from being pretty good at something to absolute lamer. Never nice.

Anyway the fruits of my labour are below. It's just a re-working of my infinite bobs effect I did a little time ago ( In as1. In an hour ). At least I've managed to convert my fps counter ( Although ensuring it stays on top of all the other mcs / sprites / displayObjects / whatever the hell they're called now, is still a bit beyond me ).
No preloader, as that seems to be a can of worms, but it's less than 13k so it's not an issue with this. Also it's not really a clever clever AS3 speed test, the whole point of the original code was to show you can still do funky things in as1 ( It was a slight backlash against what seemed like everyone at that time acting like as3 was the second coming ).

InfiniteBobs.swf (12.18 KB)

Squize.