MazeGenerator

From Unify Community Wiki
(Difference between revisions)
Jump to: navigation, search
(Removing all content from page)
m (Reverted edits by Joseph05408 (Talk); changed back to last version by Technicat)
Line 1: Line 1:
 +
== Overview ==
  
 +
This Javascript maze generator is used in the FuguMaze player/widget. It's based on a recursive subdivision algorithm described in the Wikipedia article on maze generation.
 +
 +
== Implementation ==
 +
 +
Each cell of the maze is a cube with a tile on each side (a textured plane). '''InstantiateFloor''' and '''InstantiateWalls''' instantiates the tiles - this is the time-consuming part, hence the use of coroutines and a progress indicator (I attach the script to a GameObject with a GUIText that acts as the progress display)
 +
 +
'''MakeMaze''' runs the maze generation algorithm, deactivating all the walls and then recursively subdividing the by activating walls and knocking holes in corridors to connect regions.
 +
 +
The Start function runs the wall/floor instantiation functions and then optionally activates another game object to start the game. In the case of FuguMaze, that start object is a first person controller with a script that places itself in the maze.
 +
 +
The maze generation can be made generic by changing the '''Room''' class to, say, use booleans for the walls. Then you can run MakeMaze and build a physical realization from the resulting maze structure.
 +
 +
 +
<javascript>
 +
/* Copyright (c) 2007-2008 Technicat, LLC */
 +
 +
// a square plane used for walls, floor, and ceiling
 +
var tile:Transform;
 +
var tileSize:int = 10;
 +
 +
// next state
 +
var next:GameObject;
 +
 +
// maze dimensions
 +
var height:int = 1;
 +
var width:int = 1;
 +
 +
private var maze;
 +
private var tileCounter = 0;
 +
 +
private var facingDown:Quaternion = Quaternion.Euler(180,0,0);
 +
 +
class Room {
 +
var east:Transform;
 +
var west:Transform;
 +
var north:Transform;
 +
var south:Transform;
 +
}
 +
 +
function Start() {
 +
maze = new Array(width*height);
 +
yield StartCoroutine("InstantiateFloor");
 +
yield StartCoroutine("InstantiateWalls");
 +
guiText.enabled = false;
 +
if (next != null) {
 +
next.active = true;
 +
}
 +
}
 +
 +
function InstantiateWalls() {
 +
var mid = tileSize/2;
 +
var pos = new Vector3(0,mid,0);
 +
for (var x:int =0; x< width; ++x) {
 +
var xpos:int = x*tileSize;
 +
for (var y:int =0; y< height; ++y) {
 +
var ypos:int = y*tileSize;
 +
var room = new Room();
 +
pos.x = xpos;
 +
pos.z = ypos-mid;
 +
room.south = InstantiateTile(pos,Quaternion.identity);
 +
room.south.Rotate(90,0,0);
 +
pos.x = xpos-mid;
 +
pos.z = ypos;
 +
room.west = InstantiateTile(pos,Quaternion.identity);
 +
room.west.Rotate(0,0,270);
 +
room.west.Rotate(0,90,0);
 +
pos.x = xpos;
 +
pos.z = ypos+mid;
 +
room.north = InstantiateTile(pos,Quaternion.identity);
 +
room.north.Rotate(270,0,0);
 +
room.north.Rotate(0,180,0);
 +
pos.x = xpos+mid;
 +
pos.z = ypos;
 +
room.east =InstantiateTile(pos,Quaternion.identity);
 +
room.east.Rotate(0,0,90);
 +
room.east.Rotate(0,270,0);
 +
maze[MazeIndex(x,y)]=room;
 +
ShowProgress();
 +
yield;
 +
}
 +
}
 +
}
 +
 +
// floor and ceiling
 +
function InstantiateFloor() {
 +
var floorpos:Vector3 = Vector3.zero;
 +
for (var x:int=0; x< width; ++x) {
 +
floorpos.x = x*tileSize;
 +
for (var y:int=0; y< height; ++y) {
 +
floorpos.z = y*tileSize;
 +
floorpos.y = 0;
 +
InstantiateTile(floorpos,Quaternion.identity);
 +
floorpos.y = tileSize;
 +
InstantiateTile(floorpos,facingDown);
 +
ShowProgress();
 +
yield;
 +
}
 +
}
 +
}
 +
 +
function ShowProgress() {
 +
var progress:float = tileCounter/(height*width*6.0);
 +
guiText.text = progress.ToString("maze generated: #0%");
 +
}
 +
 +
function InstantiateTile(pos:Vector3,rot:Quaternion):Transform {
 +
++tileCounter;
 +
return Instantiate(tile,pos,rot);
 +
}
 +
 +
function MakeMaze() {
 +
ClearMaze();
 +
SetOuterWalls();
 +
SubDivideMaze(0,width-1,0,height-1);
 +
}
 +
 +
function ClearMaze() {
 +
for (var x:int=0; x< width; ++x) {
 +
for (var y:int=0; y< height; ++y) {
 +
maze[MazeIndex(x,y)].west.active = false;
 +
maze[MazeIndex(x,y)].east.active = false;
 +
maze[MazeIndex(x,y)].north.active = false;
 +
maze[MazeIndex(x,y)].south.active = false;
 +
}
 +
}
 +
}
 +
 +
function SubDivideMaze(left,right,bottom,top) {
 +
if (left!=right && bottom != top) {
 +
var x:int = Random.Range(left,right);
 +
var leftdoor:int = Random.Range(left,x+1);
 +
var rightdoor:int = Random.Range(x+1,right+1);
 +
var y:int = Random.Range(bottom,top);
 +
var bottomdoor:int = Random.Range(bottom,y+1);
 +
var topdoor:int = Random.Range(y+1,top+1);
 +
AddNorthWall(left,right,y);
 +
AddEastWall(bottom,top,x);
 +
var doors = Random.value;
 +
if (doors < 0.25) {
 +
SetNorthWall(MazeIndex(leftdoor,y),false);
 +
SetNorthWall(MazeIndex(rightdoor,y),false);
 +
SetEastWall(MazeIndex(x,bottomdoor),false);
 +
} else {
 +
if (doors < 0.5) {
 +
SetNorthWall(MazeIndex(leftdoor,y),false);
 +
SetNorthWall(MazeIndex(rightdoor,y),false);
 +
SetEastWall(MazeIndex(x,topdoor),false);
 +
} else {
 +
if (doors < 0.75) {
 +
SetNorthWall(MazeIndex(rightdoor,y),false);
 +
SetEastWall(MazeIndex(x,bottomdoor),false);
 +
SetEastWall(MazeIndex(x,topdoor),false);
 +
} else {
 +
SetNorthWall(MazeIndex(leftdoor,y),false);
 +
SetEastWall(MazeIndex(x,bottomdoor),false);
 +
SetEastWall(MazeIndex(x,topdoor),false);
 +
}
 +
}
 +
}
 +
SubDivideMaze(left,x,y+1,top);
 +
SubDivideMaze(x+1,right,y+1,top);
 +
SubDivideMaze(left,x,bottom,y);
 +
SubDivideMaze(x+1,right,bottom,y);
 +
}
 +
}
 +
 +
function SetOuterWalls() {
 +
AddNorthWall(0,width-1,height-1);
 +
AddSouthWall(0,width-1,0);
 +
AddEastWall(0,height-1,width-1);
 +
AddWestWall(0,height-1,0);
 +
SetNorthWall(MazeIndex(width-1,height-1),false);
 +
}
 +
 +
function MazeIndex(x:int,y:int):int {
 +
return y*width+x;
 +
}
 +
 +
 +
function SetNorthWall(room,value) {
 +
maze[room].north.active = value;
 +
var neighbor:int = RoomNorth(room);
 +
if (neighbor !=-1) {
 +
maze[neighbor].south.active = value;
 +
}
 +
}
 +
 +
function SetSouthWall(room,value) {
 +
maze[room].south.active = value;
 +
var neighbor:int = RoomSouth(room);
 +
if (neighbor !=-1) {
 +
maze[neighbor].north.active = value;
 +
}
 +
}
 +
 +
function SetEastWall(room,value) {
 +
maze[room].east.active = value;
 +
var neighbor:int = RoomEast(room);
 +
if (neighbor !=-1) {
 +
maze[neighbor].west.active = value;
 +
}
 +
}
 +
 +
function SetWestWall(room,value) {
 +
maze[room].west.active = value;
 +
var neighbor:int = RoomWest(room);
 +
if (neighbor !=-1) {
 +
maze[neighbor].east.active = value;
 +
}
 +
}
 +
 +
function AddNorthWall(left:int,right:int,y:int) {
 +
for (var hwall:int = left; hwall<=right; ++hwall) {
 +
SetNorthWall(MazeIndex(hwall,y),true);
 +
}
 +
}
 +
 +
function AddEastWall(bottom:int,top:int,x:int) {
 +
for (var vwall:int = bottom; vwall<=top; ++vwall) {
 +
SetEastWall(MazeIndex(x,vwall),true);
 +
}
 +
}
 +
 +
function AddSouthWall(left:int,right:int,y:int) {
 +
for (var hwall:int = left; hwall<=right; ++hwall) {
 +
SetSouthWall(MazeIndex(hwall,y),true);
 +
}
 +
}
 +
 +
function AddWestWall(bottom:int,top:int,x:int) {
 +
for (var vwall:int = bottom; vwall<=top; ++vwall) {
 +
SetWestWall(MazeIndex(x,vwall),true);
 +
}
 +
}
 +
 +
function RoomEast(index:int) {
 +
var y:int = index/width;
 +
var x:int = index-y*width;
 +
if (x==width-1) {
 +
return -1;
 +
} else {
 +
return MazeIndex(x+1,y);
 +
}
 +
}
 +
 +
function RoomWest(index:int) {
 +
var y:int = index/width;
 +
var x:int = index-y*width;
 +
if (x==0) {
 +
return -1;
 +
} else {
 +
return MazeIndex(x-1,y);
 +
}
 +
}
 +
 +
function RoomNorth(index:int) {
 +
var y:int = index/width;
 +
var x:int = index-y*width;
 +
if (y==height-1) {
 +
return -1;
 +
} else {
 +
return MazeIndex(x,y+1);
 +
}
 +
}
 +
 +
function RoomSouth(index:int) {
 +
var y:int = index/width;
 +
var x:int = index-y*width;
 +
if (y==0) {
 +
return -1;
 +
} else {
 +
return MazeIndex(x,y-1);
 +
}
 +
}
 +
 +
function GetRoom(x:int,y:int) {
 +
return maze[MazeIndex(x,y)];
 +
}
 +
 +
 +
</javascript>

Revision as of 19:03, 19 October 2009

Overview

This Javascript maze generator is used in the FuguMaze player/widget. It's based on a recursive subdivision algorithm described in the Wikipedia article on maze generation.

Implementation

Each cell of the maze is a cube with a tile on each side (a textured plane). InstantiateFloor and InstantiateWalls instantiates the tiles - this is the time-consuming part, hence the use of coroutines and a progress indicator (I attach the script to a GameObject with a GUIText that acts as the progress display)

MakeMaze runs the maze generation algorithm, deactivating all the walls and then recursively subdividing the by activating walls and knocking holes in corridors to connect regions.

The Start function runs the wall/floor instantiation functions and then optionally activates another game object to start the game. In the case of FuguMaze, that start object is a first person controller with a script that places itself in the maze.

The maze generation can be made generic by changing the Room class to, say, use booleans for the walls. Then you can run MakeMaze and build a physical realization from the resulting maze structure.


<javascript> /* Copyright (c) 2007-2008 Technicat, LLC */

// a square plane used for walls, floor, and ceiling var tile:Transform; var tileSize:int = 10;

// next state var next:GameObject;

// maze dimensions var height:int = 1; var width:int = 1;

private var maze; private var tileCounter = 0;

private var facingDown:Quaternion = Quaternion.Euler(180,0,0);

class Room { var east:Transform; var west:Transform; var north:Transform; var south:Transform; }

function Start() { maze = new Array(width*height); yield StartCoroutine("InstantiateFloor"); yield StartCoroutine("InstantiateWalls"); guiText.enabled = false; if (next != null) { next.active = true; } }

function InstantiateWalls() { var mid = tileSize/2; var pos = new Vector3(0,mid,0); for (var x:int =0; x< width; ++x) { var xpos:int = x*tileSize; for (var y:int =0; y< height; ++y) { var ypos:int = y*tileSize; var room = new Room(); pos.x = xpos; pos.z = ypos-mid; room.south = InstantiateTile(pos,Quaternion.identity); room.south.Rotate(90,0,0); pos.x = xpos-mid; pos.z = ypos; room.west = InstantiateTile(pos,Quaternion.identity); room.west.Rotate(0,0,270); room.west.Rotate(0,90,0); pos.x = xpos; pos.z = ypos+mid; room.north = InstantiateTile(pos,Quaternion.identity); room.north.Rotate(270,0,0); room.north.Rotate(0,180,0); pos.x = xpos+mid; pos.z = ypos; room.east =InstantiateTile(pos,Quaternion.identity); room.east.Rotate(0,0,90); room.east.Rotate(0,270,0); maze[MazeIndex(x,y)]=room; ShowProgress(); yield; } } }

// floor and ceiling function InstantiateFloor() { var floorpos:Vector3 = Vector3.zero; for (var x:int=0; x< width; ++x) { floorpos.x = x*tileSize; for (var y:int=0; y< height; ++y) { floorpos.z = y*tileSize; floorpos.y = 0; InstantiateTile(floorpos,Quaternion.identity); floorpos.y = tileSize; InstantiateTile(floorpos,facingDown); ShowProgress(); yield; } } }

function ShowProgress() { var progress:float = tileCounter/(height*width*6.0); guiText.text = progress.ToString("maze generated: #0%"); }

function InstantiateTile(pos:Vector3,rot:Quaternion):Transform { ++tileCounter; return Instantiate(tile,pos,rot); }

function MakeMaze() { ClearMaze(); SetOuterWalls(); SubDivideMaze(0,width-1,0,height-1); }

function ClearMaze() { for (var x:int=0; x< width; ++x) { for (var y:int=0; y< height; ++y) { maze[MazeIndex(x,y)].west.active = false; maze[MazeIndex(x,y)].east.active = false; maze[MazeIndex(x,y)].north.active = false; maze[MazeIndex(x,y)].south.active = false; } } }

function SubDivideMaze(left,right,bottom,top) { if (left!=right && bottom != top) { var x:int = Random.Range(left,right); var leftdoor:int = Random.Range(left,x+1); var rightdoor:int = Random.Range(x+1,right+1); var y:int = Random.Range(bottom,top); var bottomdoor:int = Random.Range(bottom,y+1); var topdoor:int = Random.Range(y+1,top+1); AddNorthWall(left,right,y); AddEastWall(bottom,top,x); var doors = Random.value; if (doors < 0.25) { SetNorthWall(MazeIndex(leftdoor,y),false); SetNorthWall(MazeIndex(rightdoor,y),false); SetEastWall(MazeIndex(x,bottomdoor),false); } else { if (doors < 0.5) { SetNorthWall(MazeIndex(leftdoor,y),false); SetNorthWall(MazeIndex(rightdoor,y),false); SetEastWall(MazeIndex(x,topdoor),false); } else { if (doors < 0.75) { SetNorthWall(MazeIndex(rightdoor,y),false); SetEastWall(MazeIndex(x,bottomdoor),false); SetEastWall(MazeIndex(x,topdoor),false); } else { SetNorthWall(MazeIndex(leftdoor,y),false); SetEastWall(MazeIndex(x,bottomdoor),false); SetEastWall(MazeIndex(x,topdoor),false); } } } SubDivideMaze(left,x,y+1,top); SubDivideMaze(x+1,right,y+1,top); SubDivideMaze(left,x,bottom,y); SubDivideMaze(x+1,right,bottom,y); } }

function SetOuterWalls() { AddNorthWall(0,width-1,height-1); AddSouthWall(0,width-1,0); AddEastWall(0,height-1,width-1); AddWestWall(0,height-1,0); SetNorthWall(MazeIndex(width-1,height-1),false); }

function MazeIndex(x:int,y:int):int { return y*width+x; }


function SetNorthWall(room,value) { maze[room].north.active = value; var neighbor:int = RoomNorth(room); if (neighbor !=-1) { maze[neighbor].south.active = value; } }

function SetSouthWall(room,value) { maze[room].south.active = value; var neighbor:int = RoomSouth(room); if (neighbor !=-1) { maze[neighbor].north.active = value; } }

function SetEastWall(room,value) { maze[room].east.active = value; var neighbor:int = RoomEast(room); if (neighbor !=-1) { maze[neighbor].west.active = value; } }

function SetWestWall(room,value) { maze[room].west.active = value; var neighbor:int = RoomWest(room); if (neighbor !=-1) { maze[neighbor].east.active = value; } }

function AddNorthWall(left:int,right:int,y:int) { for (var hwall:int = left; hwall<=right; ++hwall) { SetNorthWall(MazeIndex(hwall,y),true); } }

function AddEastWall(bottom:int,top:int,x:int) { for (var vwall:int = bottom; vwall<=top; ++vwall) { SetEastWall(MazeIndex(x,vwall),true); } }

function AddSouthWall(left:int,right:int,y:int) { for (var hwall:int = left; hwall<=right; ++hwall) { SetSouthWall(MazeIndex(hwall,y),true); } }

function AddWestWall(bottom:int,top:int,x:int) { for (var vwall:int = bottom; vwall<=top; ++vwall) { SetWestWall(MazeIndex(x,vwall),true); } }

function RoomEast(index:int) { var y:int = index/width; var x:int = index-y*width; if (x==width-1) { return -1; } else { return MazeIndex(x+1,y); } }

function RoomWest(index:int) { var y:int = index/width; var x:int = index-y*width; if (x==0) { return -1; } else { return MazeIndex(x-1,y); } }

function RoomNorth(index:int) { var y:int = index/width; var x:int = index-y*width; if (y==height-1) { return -1; } else { return MazeIndex(x,y+1); } }

function RoomSouth(index:int) { var y:int = index/width; var x:int = index-y*width; if (y==0) { return -1; } else { return MazeIndex(x,y-1); } }

function GetRoom(x:int,y:int) { return maze[MazeIndex(x,y)]; }


</javascript>

Personal tools
Namespaces

Variants
Actions
Navigation
Extras
Toolbox