Dungeon Building Algorithm

A dungeon building algorithm, based on this page
http://roguebasin.roguelikedevelopment.org/index.php?title=Dungeon-Building_Algorithm

zlaper

forked:2
favorite:7
lines:324
license : GPLv3 License
modified : 2011-09-03 21:28:37

Embed: Tweet

package
{
    import flash.display.*;
    import flash.events.*;
    import flash.geom.Rectangle;
    import flash.utils.clearInterval;
    import flash.utils.setInterval;

[SWF( frameRate="30", width="400", height="400" )]
    public class DungeonGeneration extends Sprite
    {
        // Size
        private static const COLS:int = 80;
        private static const ROWS:int = 80;
        // Types
        private static const DIRT:int = 0;
        private static const FLOOR:int = 1;
        private static const WALL:int = 2;
        private static const DOOR:int = 3;
        // Consts
        private const FEATURES:int = 50;
        private const NEW_FEATURE_TRIES:int = 200;

private const MIN_CORRIDOR:int = 10;
        private const MAX_CORRIDOR:int = 20;

private const MIN_ROOM:int = 6;
        private const MAX_ROOM:int = 14;

// Dungeon container
        private var grid:Vector.<Vector.<int>>;
        private var random:PM_PRNG;
        private var roomInterv:uint;
        private var currFeature:int;

private var screen:BitmapData;
        private var drawTile:Rectangle = new Rectangle( 0, 0, 10, 10 );

public function DungeonGeneration()
        {
            this.addEventListener( Event.ADDED_TO_STAGE, init );
        }

private function init( event:Event ):void
        {
            this.removeEventListener( Event.REMOVED_FROM_STAGE, init );

grid = new Vector.<Vector.<int>>();
            for ( var i:int = 0; i < COLS; i++ )
            {
                grid[ i ] = new Vector.<int>();
                for ( var j:int = 0; j < ROWS; j++ )
                    grid[ i ][ j ] = DIRT;
            }

random = new PM_PRNG( 12345 );

screen = new BitmapData( 400, 400, false, 0x000000 );
            addChild( new Bitmap( screen ));

createFirstRoom();

stage.addEventListener( Event.ENTER_FRAME, update );
        }

private function update( event:Event ):void
        {
            screen.lock();
            screen.fillRect( screen.rect, 0x000000 );
            // Draw tiles            
            for ( var i:int = 0; i < COLS; i++ )
            {
                for ( var j:int = 0; j < ROWS; j++ )
                {
                    drawTile.x = i * 5;
                    drawTile.y = j * 5;
                    switch ( grid[ i ][ j ])
                    {
                        case DIRT:
                            screen.fillRect( drawTile, 0x000000 );
                            break;
                        case FLOOR:
                            screen.fillRect( drawTile, 0x2B2121 );
                            break;
                        case WALL:
                            screen.fillRect( drawTile, 0x3D3C37 );
                            break;
                        case DOOR:
                            screen.fillRect( drawTile, 0x733F12 );
                            break;
                    }
                }
            }
            screen.unlock();
        }

private function createFirstRoom():void
        {
            var fw:int = random.nextIntRange( 6, 12 );
            var fh:int = random.nextIntRange( 6, 12 );

createRoom(( COLS * .5 ) - ( fw * .5 ), ( ROWS * .5 ) - ( fh * .5 ), fw, fh );

currFeature = FEATURES;
            roomInterv = setInterval( createFeature, 200 );
        }

private function createFeature():void
        {
            trace( currFeature );
            if ( currFeature-- == 0 )
            {
                clearInterval( roomInterv );
                return;
            }

var i:int, j:int;
            var giveUp:int = 0;
            var tx:int = -1;
            var ty:int = -1;
            var tt:int, tb:int, tl:int, tr:int;
            var dir:int = -1;
            do
            {
                i = random.nextIntRange( 2, COLS - 2 );
                j = random.nextIntRange( 2, ROWS - 2 );

trace( i, j );
                if ( grid[ i ][ j ] == WALL )
                {
                    tt = grid[ i ][ j - 1 ];
                    tb = grid[ i ][ j + 1 ];
                    tl = grid[ i - 1 ][ j ];
                    tr = grid[ i + 1 ][ j ];
                    if ( tt == DIRT && ( tl == WALL && tr == WALL ))
                    {
                        tx = i;
                        ty = j - 1;
                        dir = 0;
                    }
                    else if ( tb == DIRT && ( tl == WALL && tr == WALL ))
                    {
                        tx = i;
                        ty = j + 1;
                        dir = 1;
                    }
                    else if ( tl == DIRT && ( tt == WALL && tb == WALL ))
                    {
                        tx = i - 1;
                        ty = j;
                        dir = 2;
                    }
                    else if ( tr == DIRT && ( tt == WALL && tb == WALL ))
                    {
                        tx = i + 1;
                        ty = j;
                        dir = 3;
                    }

}
            } while ( dir == -1 && giveUp++ < NEW_FEATURE_TRIES )

if ( dir != -1 )
            {
                do
                {
                    var w:int, h:int;
                    var sx:int, sy:int;
                    var feature:Number = Math.random();
                    // Two features for now
                    if ( feature < .3 )
                    {
                        // Corridor
                        {
                            if ( dir == 0 || dir == 1 )
                            {
                                sx = tx - 1;
                                w = 3;
                                h = random.nextIntRange( MIN_CORRIDOR, MAX_CORRIDOR );
                                if ( dir == 0 )
                                {
                                    // Up
                                    sy = ty - h;
                                    if ( sy < 1 )
                                        continue;
                                }
                                else
                                {
                                    // Down
                                    sy = ty + 1;
                                    if ( ty + h > ROWS - 1 )
                                        continue;
                                }
                            }
                            else
                            {
                                sy = ty - 1;
                                w = random.nextIntRange( MIN_CORRIDOR, MAX_CORRIDOR );
                                h = 3;
                                if ( dir == 2 )
                                {
                                    // Left
                                    sx = tx - w;
                                    if ( sx < 1 )
                                        continue;
                                }
                                else
                                {
                                    // Right
                                    sx = tx + 1;
                                    if ( tx + w > ROWS - 1 )
                                        continue;
                                }
                            }
                        }
                    }
                    else
                    {
                        // Room
                        {
                            if ( dir == 0 || dir == 1 )
                            {
                                w = random.nextIntRange( MIN_ROOM, MAX_ROOM );
                                h = random.nextIntRange( MIN_ROOM, MAX_ROOM );

sx = tx - int( w * .5 );
                                if ( sx < 1 || ( sx + w ) > COLS - 1 )
                                    continue;

if ( dir == 0 )
                                {
                                    // Up
                                    sy = ty - h;
                                    if ( sy < 1 )
                                        continue;
                                }
                                else
                                {
                                    // Down
                                    sy = ty + 1;
                                    if ( ty + h > ROWS - 1 )
                                        continue;
                                }
                            }
                            else
                            {
                                w = random.nextIntRange( MIN_ROOM, MAX_ROOM );
                                h = random.nextIntRange( MIN_ROOM, MAX_ROOM );

sy = ty - int( h * .5 );
                                if ( sy < 1 || ( sy + h ) > ROWS - 1 )
                                    return;

if ( dir == 2 )
                                {
                                    // Left
                                    sx = tx - w;
                                    if ( sx < 1 )
                                        continue;
                                }
                                else
                                {
                                    // Right
                                    sx = tx + 1;
                                    if ( tx + w > ROWS - 1 )
                                        continue;
                                }
                            }
                        }
                    }

// Check Bounds
                    if ( sx < 1 )
                        sx = 2;
                    if ( sx + w > COLS - 2 )
                        w = sx - COLS - 2;
                    if ( sy < 1 )
                        sy = 1;
                    if ( sy + h > ROWS - 2 )
                        h = sy - ROWS - 2;
                    
                    // Attempt to create
                    if ( createRoom( sx, sy, w, h ))
                    {
                        grid[ tx ][ ty ] = DOOR;
                        switch(dir)
                        {
                            case 0:
                                grid[tx][ty+1] = FLOOR;
                                break;
                            case 1:
                                grid[tx][ty-1] = FLOOR;
                                break;
                            case 2:
                                grid[tx+1][ty] = FLOOR;
                                break;
                            case 3:
                                grid[tx-1][ty] = FLOOR;
                                break;
                        }
                        break;
                    }
                } while ( giveUp++ < NEW_FEATURE_TRIES )
            }

}

private function createRoom( s:int, e:int, w:int, h:int ):Boolean
        {
            w += s;
            h += e;
            if ( checkArea( s, e, w, h ) && (s != w && e != h))
            {
                for ( var i:int = s; i <= w; i++ )
                {
                    for ( var j:int = e; j <= h; j++ )
                    {
                        if ( i == s || i == w || j == e || j == h )
                            grid[ i ][ j ] = WALL;
                        else
                            grid[ i ][ j ] = FLOOR;
                    }
                }
                return true;
            }

return false;
        }

private function checkArea( s:int, e:int, w:int, h:int ):Boolean
        {
            for ( var i:int = s; i <= w; i++ )
            {
                for ( var j:int = e; j <= h; j++ )
                {
                    if ( grid[ i ][ j ] != DIRT )
                        return false;
                }
            }
            return true;
        }
    }
}

/**
 * Implementation of the Park Miller (1988) "minimal standard" linear
 * congruential pseudo-random number generator.
 *
 * For a full explanation visit: http://www.firstpr.com.au/dsp/rand31/
 *
 * The generator uses a modulus constant (m) of 2^31 - 1 which is a
 * Mersenne Prime number and a full-period-multiplier of 16807.
 * Output is a 31 bit unsigned integer. The range of values output is
 * 1 to 2,147,483,646 (2^31-1) and the seed must be in this range too.
 *
 * David G. Carta's optimisation which needs only 32 bit integer math,
 * and no division is actually *slower* in flash (both AS2 & AS3) so
 * it's better to use the double-precision floating point version.
 *
 * @author Michael Baczynski, www.polygonal.de
 */
class PM_PRNG
{
    /**
     * set seed with a 31 bit unsigned integer
     * between 1 and 0X7FFFFFFE inclusive. don't use 0!
     */
    public var seed:uint;

public function PM_PRNG( _seed:uint = 1 )
    {
        seed = _seed;
    }

/**
     * provides the next pseudorandom number
     * as an unsigned integer (31 bits)
     */
    public function nextInt():uint
    {
        return gen();
    }

/**
     * provides the next pseudorandom number
     * as a float between nearly 0 and nearly 1.0.
     */
    public function nextDouble():Number
    {
        return ( gen() / 2147483647 );
    }

/**
     * provides the next pseudorandom number
     * as an unsigned integer (31 bits) betweeen
     * a given range.
     */
    public function nextIntRange( min:Number, max:Number ):uint
    {
        min -= .4999;
        max += .4999;
        return Math.round( min + (( max - min ) * nextDouble()));
    }

/**
     * provides the next pseudorandom number
     * as a float between a given range.
     */
    public function nextDoubleRange( min:Number, max:Number ):Number
    {
        return min + (( max - min ) * nextDouble());
    }

/**
     * generator:
     * new-value = (old-value * 16807) mod (2^31 - 1)
     */
    private function gen():uint
    {
        //integer version 1, for max int 2^46 - 1 or larger.
        return seed = ( seed * 16807 ) % 2147483647;
    }
}

Code Fullscreen

Preview Fullscreen