Author Topic: FlxCaveGenerator  (Read 9191 times)

eddietree

  • Member
  • **
  • Posts: 64
  • Karma: +0/-0
  • Bees nuts
    • View Profile
    • Illogictree
FlxCaveGenerator
« on: Sat, Oct 16, 2010 »


Working on my game, Between the Devil and the Deep Blue Sea, I implemented a really neat algorithm that generates caves quite elegantly. The description of the algorithm is described here. Just wanted to share the code with the community.


The class FlxCaveGenerator can be used to generate a cave similar the image shown above. The caves are random each time you call the function.

Class implementation:
Code: [Select]
package
{
/**
* This class uses the cellular automata algorithm
* to generate very sexy caves.
* (Coded by Eddie Lee, October 16, 2010)
*/
public class FlxCaveGenerator
{
private var _numTilesCols:uint = 10;
private var _numTilesRows:uint = 10;

/**
* How many times do you want to "smooth" the cave.
* The higher number the smoother.
*/
public static var numSmoothingIterations:uint = 6;

/**
* During initial state, how percent of matrix are walls?
* The closer the value is to 1.0, more wall-e the area is
*/
public static var initWallRatio:Number = 0.5;


/**
*
* @param nCols Number of columns in the cave tilemap
* @param nRows Number of rows in the cave tilemap
*/
public function FlxCaveGenerator( nCols:uint, nRows:uint )
{
_numTilesCols = nCols;
_numTilesRows = nRows;
}

/**
* @param mat A matrix of data
*
* @return A string that is usuable for FlxTileMap.loadMap(...)
*/
static public function convertMatrixToStr( mat:Array ):String
{
var mapString:String = "";

for ( var y:uint = 0; y < mat.length; ++y )
{
for ( var x:uint = 0; x < mat[y].length; ++x )
{
mapString += mat[y][x].toString() + ",";
}

mapString += "\n";
}

return mapString;
}

/**
*
* @param rows Number of rows for the matrix
* @param cols Number of cols for the matrix
*
* @return Spits out a matrix that is cols x rows, zero initiated
*/
private function genInitMatrix( rows:uint, cols:uint ):Array
{
// Build array of 1s
var mat:Array = new Array();
for ( var y:uint = 0; y < rows; ++y )
{
mat.push( new Array );
for ( var x:uint = 0; x < cols; ++x ) mat[y].push(0);
}

return mat;
}

/**
*
* @param mat Matrix of data (0=empty, 1 = wall)
* @param xPos Column we are examining
* @param yPos Row we are exampining
* @param dist Radius of how far to check for neighbors
*
* @return Number of walls around the target, including itself
*/
private function countNumWallsNeighbors( mat:Array, xPos:int, yPos:int, dist:uint = 1 ):int
{
var count:int = 0;

for ( var y:int = -dist; y <= dist; ++y )
{
for ( var x:int = -dist; x <= dist; ++x )
{
// Boundary
if ( xPos + x < 0 || xPos + x > _numTilesCols - 1
|| yPos + y < 0 || yPos + y > _numTilesRows - 1 ) continue;

// Neighbor is non-wall
if ( mat[yPos + y][xPos + x] != 0 ) ++count;
}
}

return count;
}

/**
* Use the 4-5 rule to smooth cells
*/
private function runCelluarAutomata( inMat:Array, outMat:Array ):void
{
const numRows:uint = inMat.length;
const numCols:uint = inMat[0].length;

for ( var y:uint = 0; y < numRows; ++y )
{
for ( var x:uint = 0; x < numCols; ++x )
{
var numWalls:int = countNumWallsNeighbors( inMat, x, y, 1 );

if ( numWalls >= 5 ) outMat[y][x] = 1;
else outMat[y][x] = 0;
}
}
}

/**
*
* @return Returns a matrix of a cave!
*/
public function generateCaveLevel():Array
{
// Initialize random array
var mat:Array = genInitMatrix( _numTilesRows, _numTilesCols );
for ( var y:uint = 0; y < _numTilesRows; ++y )
{
for ( var x:uint = 0; x < _numTilesCols; ++x )
mat[y][x]=( Math.random() < initWallRatio ? 1:0 );
}

// Secondary buffer
var mat2:Array = genInitMatrix( _numTilesRows, _numTilesCols );

// Run automata
for ( var i:int = 0; i < numSmoothingIterations; ++i )
{
runCelluarAutomata( mat, mat2 );

// Swap
var temp:Array = mat;
mat = mat2;
mat2 = temp;
}

return mat;
}
}
}



Example code of how to use this class:
Code: [Select]
// Create cave of size 200x100 tiles
var cave:FlxCaveGenerator = new FlxCaveGenerator(200, 100);

// Generate the level and returns a matrix
// 0 = empty, 1 = wall tile
var caveMatrix:Array = cave.generateCaveLevel();

// Converts the matrix into a string that is readable by FlxTileMap
var dataStr:String = FlxCaveGenerator.convertMatrixToStr( caveMatrix );

// Loads tilemap of tilesize 16x16
var tileMap:FlxTilemap = new FlxTilemap();
tileMap.loadMap( dataStr, ImgTileSheet, 16, 16 );


Source Code (.as)
« Last Edit: Sat, Oct 16, 2010 by eddietree »
Dev Blog: illogictree | Twitter: @eddietree

initials

  • Contributor
  • ****
  • Posts: 378
  • Karma: +0/-0
  • Initials
    • View Profile
    • Initials Blog. Code and other things.
Re: FlxCaveGenerator
« Reply #1 on: Sat, Oct 16, 2010 »
Thank you so much.
I'm going to have a go at implementing this right now and see how it goes.

Thanks again.
Initials: Super Lemonade Factory, Super Lemonade Factory Part Two, Above The Clouds, Revvolvver, Four Chambers of the Human Heart

initials

  • Contributor
  • ****
  • Posts: 378
  • Karma: +0/-0
  • Initials
    • View Profile
    • Initials Blog. Code and other things.
Re: FlxCaveGenerator
« Reply #2 on: Sat, Oct 16, 2010 »
Code: [Select]
// Create cave of size 200x100 tiles
var cave:FlxCaveGenerator = new FlxCaveGenerator(200, 100);

// Generate the level and returns a matrix
// 0 = empty, 1 = wall tile
var caveMatrix:Array = cave.generateCaveLevel();

// Converts the matrix into a string that is readable by FlxTileMap
var dataStr:String = FlxCaveGenerator.convertMatrixToStr( caveMatrix );

// Loads tilemap of tilesize 16x16
var tileMap:FlxTilemap = new FlxTilemap();
tileMap.loadMap( dataStr, FlxTilemap.ImgAuto, 16, 16 );
add(tileMap);

If you want to use this with Flixels auto tiles, here's the code.
Don't forget to add it to the Playstate (last line of code).

Thanks again, works great.


Initials: Super Lemonade Factory, Super Lemonade Factory Part Two, Above The Clouds, Revvolvver, Four Chambers of the Human Heart

eddietree

  • Member
  • **
  • Posts: 64
  • Karma: +0/-0
  • Bees nuts
    • View Profile
    • Illogictree
Re: FlxCaveGenerator
« Reply #3 on: Sat, Oct 16, 2010 »
I'd love to see any results you got from my code. :)

Screenshots?
Dev Blog: illogictree | Twitter: @eddietree

darthlupi

  • Active Member
  • ***
  • Posts: 241
  • Karma: +0/-0
  • All Smiles
    • View Profile
    • LupiGames.com
Re: FlxCaveGenerator
« Reply #4 on: Wed, Oct 20, 2010 »
Thank you so much!   Can all parts of the cave be accessed? I wonder, because I was thinking of making a little exploration game with random map generation!  ooo ahhh

Thanks for being so generous!
To take care of that not so fresh feeling: #flixel on irc.freenode.net.

Use your favorite IRC client or  http://webchat.freenode.net/

Vexhel

  • Member
  • **
  • Posts: 30
  • Karma: +0/-0
  • Huh?
    • View Profile
Re: FlxCaveGenerator
« Reply #5 on: Wed, Oct 20, 2010 »
Very nice! I was looking for something like this for a long-term plan of mine.

EricPett7

  • New Member
  • *
  • Posts: 2
  • Karma: +0/-0
    • View Profile
    • Credit Card Processing, llc
Re: FlxCaveGenerator
« Reply #6 on: Thu, May 5, 2011 »
Awesome man! I wonder if it will be difficult to customize the script to create them with certain shapes (letter maybe?) =)

eddietree

  • Member
  • **
  • Posts: 64
  • Karma: +0/-0
  • Bees nuts
    • View Profile
    • Illogictree
Re: FlxCaveGenerator
« Reply #7 on: Thu, May 5, 2011 »
Yes, since cellular automata is a semi-random process in which organic structures are generated, forcing it to take specific shapes would be quite hard. Sorry
Dev Blog: illogictree | Twitter: @eddietree

IQpierce

  • Gamewright
  • Member
  • **
  • Posts: 39
  • Karma: +2/-0
    • View Profile
    • Deep Plaid Games
Re: FlxCaveGenerator
« Reply #8 on: Fri, May 6, 2011 »
Cool stuff. I'm always surprised by how few references to cellular automata techniques when I read articles about procedural level generation; I've used it on some past projects to terrific effect.

I once did a 2D map generator for a top-down game, where I wanted to randomly have certain cities, forests, and rivers on the map. I ended up coming up with some neat cellular automata techniques to "tease out" the shapes and configurations I wanted for these different terrain elements. For instance, any filled tiles that were completely off on their own would become a City; large blobs of filled tiles would become a Forest; and I would do some iterative massaging to encourage long linear strings of filled tiles to appear, and make those be Rivers.

It was an interesting process of both looking for naturally-emerging configurations that were close to what I wanted, and then doing a few cycles of processing to encourage those shapes to take even more of the shape I needed them to. All this seems very well-suited to Flixel and its tile-based nature.
I'm just one guy trying to make some interesting decisions!

Chelnok

  • Contributor
  • ****
  • Posts: 257
  • Karma: +0/-0
    • View Profile
Re: FlxCaveGenerator
« Reply #9 on: Tue, May 24, 2011 »
I'd love to see any results you got from my code. :)

Screenshots?

Very handy for getting start when designing big levels! Especially when using autotiling..

Couple screenshots:

----------------------------------------


I havnt used to use autotiling, but it seems to work preatty nice.
Actually your cavegenerator made me to try autotiling first time. Thanks for that also :)

Great tutorial about autotiling: http://www.saltgames.com/?p=184

lechuckgl

  • Active Member
  • ***
  • Posts: 118
  • Karma: +0/-0
    • View Profile
Re: FlxCaveGenerator
« Reply #10 on: Tue, Jun 21, 2011 »
Thanks, this class - and the tutorial - are absolutely great ! However, I still couldn't find a way to get rid of isolated chunks. Could you throw me a bone here ? I am really clueless (well, I actually have some ideas, but they seem impractical and/or inefficient).

Cheers

GrimPanda

  • Member
  • **
  • Posts: 46
  • Karma: +1/-0
    • View Profile
    • Grim Panda Games
Re: FlxCaveGenerator
« Reply #11 on: Fri, Jul 8, 2011 »
Amazing!  Thanks for sharing. 
"Mortis Ailuropoda"

initials

  • Contributor
  • ****
  • Posts: 378
  • Karma: +0/-0
  • Initials
    • View Profile
    • Initials Blog. Code and other things.
Re: FlxCaveGenerator
« Reply #12 on: Wed, Oct 12, 2011 »
I just implemented this into the Ogmo Level Editor.

I'll upload it to git shortly, but if you are super keen, email me.

http://vimeo.com/30484721
« Last Edit: Fri, Oct 14, 2011 by initials »
Initials: Super Lemonade Factory, Super Lemonade Factory Part Two, Above The Clouds, Revvolvver, Four Chambers of the Human Heart

arcade27

  • Member
  • **
  • Posts: 40
  • Karma: +0/-0
    • View Profile
Re: FlxCaveGenerator
« Reply #13 on: Fri, Oct 14, 2011 »
Defenitly going to implement this into a small game im working on.
LEss of a cave i need but the base line code will defentily get me closer to what i need then i currently have acheabed with my several fail attempts !

Kimikaze-N00B

  • King
  • Member
  • **
  • Posts: 20
  • Karma: +0/-0
  • -The leader of everything-
    • View Profile
Re: FlxCaveGenerator
« Reply #14 on: Wed, Oct 19, 2011 »
I could really use this for my new space game :o