PDA

View Full Version : Random dungeon generation with cellular automata


DrakilorP2P
07-26-2008, 10:30 PM
This one should be pretty straightforward. Each cell have a finite amount of states. Every generation, all cells are simultaneously changed according to a set of rules which are dependant on the cell's "neighbourhood."

An example of a cellular automaton is Conway's Game of Life, which you may be familiar with.
Its rules as per copy pasta:
1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
4. Any dead cell with exactly three live neighbours comes to life.

//true: alive cell
//false: dead cell

function onCreated()
{
this.grid = newGrid();
this.grid = randomizeGrid(this.grid, 0.45);

// Create a glider for use with conway's game of life
/*this.grid = newGrid();
this.grid[1][1] = true;
this.grid[2][2] = true;
this.grid[0][3] = true;
this.grid[1][3] = true;
this.grid[2][3] = true;*/

scheduleEvent(0.1, "loopLimitIsEvil", false);
scheduleEvent(0.2, "loopLimitIsEvil", false);
scheduleEvent(0.3, "loopLimitIsEvil", false);
scheduleEvent(0.4, "loopLimitIsEvil", false);
scheduleEvent(0.5, "loopLimitIsEvil", false);
scheduleEvent(0.6, "loopLimitIsEvil", true);
}

function onLoopLimitIsEvil(save)
{
if (save) writeToFile(this.grid, "temp/conway.txt");
else this.grid = iterateCellularAutomaton(this.grid, "cave");

}

function newGrid()
{
temp.grid = new[64][64];

return temp.grid;
}

function iterateCellularAutomaton(grid, functionName)
{
temp.newGrid = newGrid();

for (temp.x=0; temp.x<64; temp.x++) {
for (temp.y=0; temp.y<64; temp.y++) {
temp.newGrid[temp.x][temp.y] = makevar(functionName)(grid, temp.x, temp.y);
}
}

return temp.newGrid;
}

function randomizeGrid(grid, ratio)
{
temp.RNG = new MRandomR250();

for (temp.x=0; temp.x<64; temp.x++) {
for (temp.y=0; temp.y<64; temp.y++) {
grid[temp.x][temp.y] = temp.RNG.randFloat() < ratio;
}
}

return grid;
}

function writeToFile(grid, filePath)
{
temp.string = "GLEVNW01\n";

for (temp.y=0; temp.y<64; temp.y++) {
temp.string @= "BOARD 0 " @ temp.y @ " 64 0 ";
for (temp.x=0; temp.x<64; temp.x++) {
if (grid[temp.x][temp.y] == true) temp.string @= "Ag";
else temp.string @= "YG";
}

temp.string @= "\n";
}

temp.string.saveString(filePath, 0);
}

function countNumberOfNeighbours(grid, x, y)
{
//We're assuming that anything outside the level boundaries are walls. No torus for us.
temp.numNeighbours = 0;
if (grid[x-1][y-1] == true || x-1 < 0 || y-1 < 0) temp.numNeighbours ++;
if (grid[x-1][y] == true || x-1 < 0) temp.numNeighbours ++;
if (grid[x-1][y+1] == true || x-1 < 0 || y+1 > 63) temp.numNeighbours ++;
if (grid[x][y-1] == true || y-1 < 0) temp.numNeighbours ++;
if (grid[x][y+1] == true || y+1 > 63) temp.numNeighbours ++;
if (grid[x+1][y-1] == true || x+1 > 63 || y-1 < 0) temp.numNeighbours ++;
if (grid[x+1][y] == true || x+1 > 63) temp.numNeighbours ++;
if (grid[x+1][y+1] == true || x+1 > 63 || y+1 > 63) temp.numNeighbours ++;

return temp.numNeighbours;
}

function cave(grid, x, y)
{
temp.numNeighbours = countNumberOfNeighbours(grid, x, y);

if (grid[x][y] == true && temp.numNeighbours >= 4) return true;
if (grid[x][y] == false && temp.numNeighbours >= 5) return true;
return false;
}

//Conway's game of life.
function conwayLife(grid, x, y)
{
temp.numNeighbours = countNumberOfNeighbours(grid, x, y);

if (grid[x][y] == true && temp.numNeighbours in {2, 3}) return true;
if (grid[x][y] == false && temp.numNeighbours == 3) return true;
return false;
}



The results, to say the least, are repulsive. Unless you're coding GraalHack, you'll need to do some work yourself to get any useful levels.

Obviously though, there are all sorts of other exciting things you can do with this, such as making grass grow.

function makeGrassGrow(grid, x, y)
{
temp.numNeighbours = countNumberOfNeighbours(grid, x, y);

temp.RNG = new MRandomR250();
if (temp.numNeighbours > 0) {
if (temp.RNG.randInt(1, 10) == 1) return true;
}
if (temp.numNeighbours > 1) {
if (temp.RNG.randInt(1, 5) == 1) return false;
}
if (grid[x][y] == true) return true;
return false;
}

napo_p2p
07-26-2008, 10:54 PM
Nifty! I like.

Mark Sir Link
07-27-2008, 12:55 AM
gosper glider please