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