Hi.
I'm making a random 2d dungeon creator and I need some help improving it. It just creates corridors, rooms and doors for now and it works as it should except the door placement isn't good enough. I've attached a screen shot so you can see what I mean. (to many doors at the end of the corridors)
I found a way to improve the door placement but it's to slow for my liking (it's included in the code).
So if anyone have some suggestions for how I can improve my code I'll be very happy.
I'll also appreciate comments of other areas to improve my code.
Here's the code. I've tried to clean it up an comment it as much as I could.
Rem ***************************************************
Rem Project: Random 2D Dungeon Creator
Rem Created by Ranietz on Monday, January 24, 2011
Rem Version 1.0 February 04, 2011
Rem ***************************************************
`some init stuff
set display mode 1024,768,32
sync on
sync rate 0
randomize timer()
hide mouse
`sets the tilesize
tileSize = 16
`this is the x-size and y-size of the map (must be even numbers) actual map size is +1
mapX = 62
mapY = 46
`this two variables are used a lot in the randomize_map sub routine
mapX2=mapX-1
mapY2=mapY-1
type map_data
imageNr as integer `store the image number for each tile on the map
flood as integer `used for the flood fill routine
endtype
dim map(mapX,mapY) as map_data `this array hold all the map data
`some room variables
maxRooms = 70 `a good indicator for max rooms is: mapX*mapY/40
maxRoomW = 6 `max room width (should be an even number) real max room width is +1
maxRoomH = 6 `max room height (should be an even number) real max room height is +1
`this is used for storing room data
type room_data
roomX as integer
roomY as integer
roomW as integer
roomH as integer
endtype
dim room(maxRooms) as room_data `this array holds all the room data
`use variable names instead of tile numbers
wallTile=1
corridorTile=2
roomTile=3
doorTile=4
`make the wall, floor and door images
gosub make_images
`randomize the map
gosub randomize_map
`*******************************************************************************************************************************************
`MAIN LOOP BEGINS
`*******************************************************************************************************************************************
do
`clear the screen and make a brownish background color
cls rgb(165,136,105)
`randomize the map if spacekey is pressed
if spacekey()=0 then space = 1
if spacekey()=1 and space = 1
space = 0
gosub randomize_map
endif
`draw the map
gosub draw_map
`draw some debug text
`text 0,0,"Map ("+str$(mapX+1)+"x"+str$(mapY+1)+ ") generated in "+str$(mapGenTime)+" ms with "+str$(roomPlaced)+" rooms"
`text 512,0,"Press space to generate a new map"
`text 950,0,"FPS: "+str$(screen fps())
text 300,0,"Room Time:"+str$(roomTime)
text 430,0,"Maze Time:"+str$(mazeTime)
text 560,0,"Door Time:"+str$(doorTime)
text 690,0,"Flood Time:"+str$(floodTime)
text 820,0,"Total Time:"+str$(mapGenTime)
text 0,0,"Map Size:"+str$(mapX+1)+"x"+str$(mapY+1)
text 140,0,"Room Count:"+str$(roomPlaced)
`update the screen
sync
loop
`*******************************************************************************************************************************************
`MAIN LOOP END
`*******************************************************************************************************************************************
`SUB PROGRAMS BEGINS
`*******************************************************************************************************************************************
make_images:
`make wall image (not currently used)
`ink rgb(64,64,64),0
`box 1,1,tileSize-1,tileSize-1
`get image wallTile,0,0,tileSize,tileSize
`make floor image
cls rgb(196,196,196)
ink rgb(255,255,255),0
box 1,1,tileSize-1,tileSize-1
get image corridorTile,0,0,tileSize,tileSize `floor in corridors
get image roomTile,0,0,tileSize,tileSize `floor in rooms
`make door image
cls
ink rgb(139,69,19),0
box 1,1,tileSize-1,tileSize-1
get image doorTile,0,0,tileSize,tileSize
`set ink back to white
ink rgb(255,255,255),0
return
`*******************************************************************************************************************************************
randomize_map:
`this sub routine generates the random dungeon using the following steps
`1 - fill the map with walls
`2 - place some random rooms
`3 - generate mazes around the rooms
`4 - connect dead ends of the mazes to a nearby room (by inserting a door)
`5 - check to see if some rooms are unconnected, then try to connect them to a room or the maze (by inserting a door)
`6 - flood fill the map to see if every area is accessible
`7 - if some part of the area is unaccessible then try to connect it to the accessible area (by inserting a door)
`8 - done!
`this is used to see how long it takes to generate the map
tMap = timer()
repeat
`this is used to see how long it takes to place the rooms to the map
tRooms=timer()
`fill the map with walls
for x = 0 to mapX
for y = 0 to mapY
map(x,y).imageNr=wallTile
next y
next x
`place some random rooms
roomPlaced = 0 `keeps track of how many rooms have been placed on the map
count = 0 `this is used to make sure the following repeat-until loop wont run forever
repeat
inc count
`first get a random (odd number) x,y position of the room with random (odd number) width and height.
tmpRoomW = rnd((maxRoomW-2)/2)*2+2
tmpRoomH = rnd((maxRoomH-2)/2)*2+2
tmpRoomX = rnd((mapX-tmpRoomW-2)/2)*2+1
tmpRoomY = rnd((mapY-tmpRoomH-2)/2)*2+1
`checks if the room collides with any other room
tmp=0
for x = tmpRoomX-1 to tmpRoomX + tmpRoomW +1
for y = tmpRoomY-1 to tmpRoomY + tmpRoomH +1
if map(x,y).imageNr=roomTile then inc tmp
next y
next x
`if the room don't collide with any other room then place it on the map
`write the room data to the room array and inc the roomPlaced variable
if tmp = 0
for x = tmpRoomX to tmpRoomX + tmpRoomW
for y = tmpRoomY to tmpRoomY + tmpRoomH
map(x,y).imageNr=roomTile
next y
next x
room(roomPlaced).roomX = tmpRoomX
room(roomPlaced).roomY = tmpRoomY
room(roomPlaced).roomW = tmpRoomW
room(roomPlaced).roomH = tmpRoomH
inc roomPlaced
endif
until roomPlaced = maxRooms or count > 600 `a good indicator for the count value is: mapX*mapY/5
`this is used to see how long it takes to place the rooms to the map
roomTime=timer()-tRooms
`this is used to see how long it takes to generate the maze
tMaze=timer()
`draw a maze around the rooms
newMap = 1
repeat
`this variable will be increased if the current maze can be continued
continueMaze=0
`if it's not a new map and the current maze is not done then find a new place to continue the current maze
if newMap=0 and mazeNotDone<>0
for x = 1 to mapX2 step 2
for y = 1 to mapY2 step 2
if map(x,y).imageNr=corridorTile
tmp=0 `tmp will be increased if the maze can be continued from the current map coordinate
if x>2
if map(x-2,y).imageNr=wallTile then inc tmp
endif
if x<mapX-2
if map(x+2,y).imageNr=wallTile then inc tmp
endif
if y>2
if map(x,y-2).imageNr=wallTile then inc tmp
endif
if y<mapY-2
if map(x,y+2).imageNr=wallTile then inc tmp
endif
if tmp > 0
tmpX = x
tmpY = y
inc continueMaze
x=mapX2
y=mapY2
endif
endif
next y
next x
endif
`if it's not a new map and the current maze is done then find a start position for a new maze
if newMap=0 and mazeNotDone=0
for x = 1 to mapX2 step 2
for y = 1 to mapY2 step 2
if map(x,y).imageNr=wallTile
map(x,y).imageNr=corridorTile
tmpX = x
tmpY = y
inc continueMaze
x=mapX2
y=mapY2
endif
next y
next x
endif
`if it's a new map then choose a random (odd numbered) start tile.
if newMap=1
repeat
tmpX = abs(((rnd(mapX-1)-(mapX/2))*2)+1)
tmpY = abs(((rnd(mapY-1)-(mapY/2))*2)+1)
until map(tmpX,tmpY).imageNr=wallTile
map(tmpX,tmpY).imageNr = corridorTile
newMap = 0
inc continueMaze
endif
`if the continueMaze variable is bigger than zero then the current maze is not done
`if continueMaze is zero then a new maze must be started
if continueMaze>0
mazeNotDone=1
else
mazeNotDone=0
endif
`set each direction as OK
left = 1
up = 1
right = 1
down = 1
repeat
`choose a random direction
tmp = rnd(99) `this is used to make more or less straight corridors
if tmp > 50
direction = rnd(3)+1
endif
`checks if it's OK to move in the chosen direction
`if yes, then make a (2 tile long) corridor and reset the direction variables
`if no, then set that directions variable to 0
select direction
case 1 `left
if map(tmpX-1,tmpY).imageNr=wallTile and tmpX>1
if map(tmpX-2,tmpY).imageNr=wallTile
map(tmpX-1,tmpY).imageNr=corridorTile
map(tmpX-2,tmpY).imageNr=corridorTile
tmpX = tmpX-2
left = 1
up = 1
right = 0
down = 1
else
left = 0
endif
else
left = 0
endif
endcase
case 2 `up
if map(tmpX,tmpY-1).imageNr=wallTile and tmpY>1
if map(tmpX,tmpY-2).imageNr=wallTile
map(tmpX,tmpY-1).imageNr=corridorTile
map(tmpX,tmpY-2).imageNr=corridorTile
tmpY = tmpY-2
left = 1
up = 1
right = 1
down = 0
else
up = 0
endif
else
up = 0
endif
endcase
case 3 `right
if map(tmpX+1,tmpY).imageNr=wallTile and tmpX < mapX-1
if map(tmpX+2,tmpY).imageNr=wallTile
map(tmpX+1,tmpY).imageNr=corridorTile
map(tmpX+2,tmpY).imageNr=corridorTile
tmpX = tmpX+2
left = 0
up = 1
right = 1
down = 1
else
right = 0
endif
else
right = 0
endif
endcase
case 4 `down
if map(tmpX,tmpY+1).imageNr=wallTile and tmpY < mapY-1
if map(tmpX,tmpY+2).imageNr=wallTile
map(tmpX,tmpY+1).imageNr=corridorTile
map(tmpX,tmpY+2).imageNr=corridorTile
tmpY = tmpY+2
left = 1
up = 0
right = 1
down = 1
else
down = 0
endif
else
down = 0
endif
endcase
endselect
`if all the directions are zero the maze has reached a dead end
until left=0 and up=0 and right=0 and down=0
`check each odd numbered tile. if no tile is "wall", then the maze is done.
oddTileCount=0
for x = 1 to mapX2 step 2
for y = 1 to mapY2 step 2
if map(x,y).imageNr=wallTile then inc oddTileCount
next y
next x
until oddTileCount=0
`this is used to see how long it takes to generate the maze
mazeTime=timer()-tMaze
`this is used to see how long it takes to insert the doors and remove dead ends
tDoor=timer()
`find dead end corridors and try to put a door there. if a door can't be placed then remove the dead end.
`un-rem the 9 places the tmp variable is used for better (but much slower) door placement
maxRemoved=20 `corridors longer than this value will not be completely removed
repeat
dec maxRemoved
deadEndsLeft=0
for x = 1 to mapX2
for y = 1 to mapY2
wallCount=0
`tmp=0
if map(x-1,y).imageNr=wallTile and map(x,y).imageNr=corridorTile then inc wallCount
if map(x+1,y).imageNr=wallTile and map(x,y).imageNr=corridorTile then inc wallCount
if map(x,y-1).imageNr=wallTile and map(x,y).imageNr=corridorTile then inc wallCount
if map(x,y+1).imageNr=wallTile and map(x,y).imageNr=corridorTile then inc wallCount
if wallCount = 4 then map(x,y).imageNr=wallTile
if wallCount = 3
if x>2 `and tmp=0
if map(x-2,y).imageNr=roomTile
map(x-1,y).imageNr=doorTile
dec wallCount
`inc tmp
endif
endif
if x<mapX-2 `and tmp=0
if map(x+2,y).imageNr=roomTile
map(x+1,y).imageNr=doorTile
dec wallCount
`inc tmp
endif
endif
if y>2 `and tmp=0
if map(x,y-2).imageNr=roomTile
map(x,y-1).imageNr=doorTile
dec wallCount
`inc tmp
endif
endif
if y<mapY-2 `and tmp=0
if map(x,y+2).imageNr=roomTile
map(x,y+1).imageNr=doorTile
dec wallCount
`inc tmp
endif
endif
endif
if wallCount = 3
map(x,y).imageNr=wallTile
inc deadEndsLeft
endif
next y
next x
until deadEndsLeft=0 or maxRemoved=0
`checks to see if a room has no doors. if there's no door then try to insert one (door placement should be improved)
for a = 0 to roomPlaced-1
tmpDoor = 0
tmpRoomX = room(a).roomX
tmpRoomY = room(a).roomY
tmpRoomW = room(a).roomW
tmpRoomH = room(a).roomH
`check if the room has a door
for x = tmpRoomX to tmpRoomX + tmpRoomW
for y = tmpRoomY to tmpRoomy + tmpRoomH
if map(x,tmpRoomY-1).imageNr=doorTile then inc tmpDoor
if map(x,tmpRoomY+tmpRoomH+1).imageNr=doorTile then inc tmpDoor
if map(tmpRoomX-1,y).imageNr=doorTile then inc tmpDoor
if map(tmpRoomX+tmpRoomW+1,y).imageNr=doorTile then inc tmpDoor
next y
next x
`if the room has no door then try to insert one
if tmpDoor = 0
tmp=0
for x = tmpRoomX to tmpRoomX + tmpRoomW
for y = tmpRoomY to tmpRoomY + tmpRoomH
if tmpRoomY>2
if map(x,tmpRoomY-2).imageNr<>wallTile and tmp=0
map(x,tmpRoomY-1).imageNr=doorTile
tmp=1
endif
endif
if tmpRoomY<mapY-tmpRoomH-2
if map(x,tmpRoomY+tmpRoomH+2).imageNr<>wallTile and tmp=0
map(x,tmpRoomY+tmpRoomH+1).imageNr=doorTile
tmp=1
endif
endif
if tmpRoomX>2
if map(tmpRoomX-2,y).imageNr<>wallTile and tmp=0
map(tmpRoomX-1,y).imageNr=doorTile
tmp=1
endif
endif
if tmpRoomX<mapX-tmpRoomW-2
if map(tmpRoomX+tmpRoomW+2,y).imageNr<>wallTile and tmp=0
map(tmpRoomX+tmpRoomW+1,y).imageNr=doorTile
tmp=1
endif
endif
next y
next x
endif
next a
`this is used to see how long it takes to insert the doors and remove dead ends
doorTime=timer()-tDoor
`this is used to see how long the flood fill routine takes
tFlood=timer()
`count the floor, room and door tiles (this is used for the flood fill routine)
totalTileCount=0
for x = 1 to mapX2
for y = 1 to mapY2
map(x,y).flood=0
if map(x,y).imageNr<>wallTile then inc totalTileCount
next y
next x
`flood fill routine
`flood the map to see if all floor/room/door tiles are accessible
`find a start tile and set it as flooded
`the floodCount variable keeps track of how many tiles are flooded
floodCount=0
for x = 1 to mapX2
for y = 1 to mapY2
if map(x,y).imageNr<>wallTile `and tmp=0
map(x,y).flood=1
inc floodCount
x=mapX2
y=mapY2
endif
next y
next x
`now we check each flooded tile and see if it has a neighbour tile that can be flooded
`if the neighbour tile can be flooded; flood it and increase the floodCount
`this will be repeated until no more areas can be flooded
gosub flood_fill
`if floodCount<>totalTileCount then it means that parts of the map is un-accessible. now fix it
if floodCount<>totalTileCount
count=0
repeat
inc count
`find the un-accessible tiles
for x = 1 to mapX2
for y = 1 to mapY2
if map(x,y).flood<>1 and map(x,y).imageNr<>wallTile
map(x,y).flood=2
endif
next y
next x
`try to connect the un-accessible part of the map to the accessible part
tmp=0
for x = 1 to mapX2
for y = 1 to mapY2
if map(x,y).flood=2
if x>1 and tmp=0
if map(x-2,y).imageNr<>wallTile
map(x-1,y).imageNr=doorTile
inc totalTileCount
tmp=1
x=mapX2
y=mapY2
endif
endif
if y>2 and tmp=0
if map(x,y-2).imageNr<>wallTile
map(x,y-1).imageNr=doorTile
inc totalTileCount
tmp=1
x=mapX2
y=mapY2
endif
endif
endif
next y
next x
`continue the flood fill to see if everything got connected
gosub flood_fill
until floodCount=totalTileCount or count>250
endif
`this is used to see how long the flood fill routine takes
floodTime=timer()-tFlood
`if floodCount = totalTileCount then the whole map is accessible and the map is complete
`if not then the map generation has failed and we start all over again (should hopefully not happen)
until floodCount=totalTileCount
`this is used to see how long it takes to generate the map
mapGenTime = timer()-tMap
return
`*******************************************************************************************************************************************
flood_fill:
repeat
tmp=0
for x = 1 to mapX2
for y = 1 to mapY2
if map(x,y).flood=1
if map(x-1,y).imageNr<>wallTile and map(x-1,y).flood<>1
map(x-1,y).flood=1
inc floodCount
inc tmp
endif
if map(x+1,y).imageNr<>wallTile and map(x+1,y).flood<>1
map(x+1,y).flood=1
inc floodCount
inc tmp
endif
if map(x,y-1).imageNr<>wallTile and map(x,y-1).flood<>1
map(x,y-1).flood=1
inc floodCount
inc tmp
endif
if map(x,y+1).imageNr<>wallTile and map(x,y+1).flood<>1
map(x,y+1).flood=1
inc floodCount
inc tmp
endif
endif
next y
next x
until tmp=0
return
`*******************************************************************************************************************************************
draw_map:
for x = 0 to mapX
for y = 0 to mapY
`map(x,y).imageNr>0 will draw the wall tiles (slow)
`map(x,y).imageNr>wallTile will not draw the wall tiles (a bit faster)
if map(x,y).imageNr>wallTile then paste image map(x,y).imageNr,x*tileSize,y*tileSize+16
next y
next x
return
