Alright. My dungeon generator has some problems...

[sladjkf]

So, I'm working on a random dungeon generator based on this one here.

http://www.roguebasin.com/index.php?tit ... _Algorithm

My code is essentially working, but it seems to have some problems...



As you can see, it generates unreachable areas and also generates strange blobs of area, as well as these straight looking bar thingies that I circled.

Below is all my code-sorry if it's a lot. Any help is greatly appreciated.

Code: Select all

function draw_room(x,xtwo,y,ytwo,map,rows,columns,deposit_table)
	local record = {}
	for i=x ,xtwo - 1 do --loop to draw the next room
		for i_two=y,ytwo - 1 do
			table.insert(record,{i,i_two}) --x,y
			if map[i_two][i] == 2 then
				print(i_two,i)
				goto if_errror
			end
			if i_two > rows or i > columns then
				goto if_errror
			end
			map[i_two][i] = 2
		end
	end
	goto quickend
	::if_errror::
	deposit_table=record
	error("Those spaces were already empty")
	::quickend::
end

function love.load()
	deposit_table={}
	math.randomseed(os.time())
	math.random(); math.random(); math.random() 
	--load tilesheet
	tileset=love.graphics.newImage("countryside.png")
	love.window.setMode( 1366, 768, {resizable=true} )
	--tileset's quads
	tileset_quadinfo={
	{32,32},
	{0,0}
	}
	tileset_quads = create_quads(tileset_quadinfo,32,32,64,64)
	--set variables
	map = {}
	columns = 43
	rows = 20
	min_room_width = 4
	min_room_height = 4
	max_room_height = 7
	max_room_width = 7
	--generate a filled map
	for i=0,rows do
		table.insert(map,{})	
	end
	for key,value in ipairs(map) do
		for i=0,columns do
			table.insert(value,1) --solid tile value. Add in quads?
		end
	end
	--draw initial room
	local startingroom_x=math.floor(columns/2)
	local startingroom_y=math.floor(rows/2)
	map[startingroom_y][startingroom_x] = 2 --empty out a tile
	local startingroom_xtwo=math.random(min_room_width,max_room_width) + startingroom_x
	local startingroom_ytwo=math.random(min_room_width,max_room_height) + startingroom_y -- these are the second points. used for determining length.
	
	for i=startingroom_x ,startingroom_xtwo -1 do --loop to draw the initial room
		for i_two=startingroom_y,startingroom_ytwo -1 do
			map[i_two][i] = 2
		end
	end
	
	room_border_tiles = {}
	--determine the borders
	for i=startingroom_x, startingroom_xtwo - 1 do --NOTE: coordinates are deposited in here as [y,x] for better use with the map array
		table.insert(room_border_tiles,{startingroom_y-1,i,"top"}) 
	end
	for i=startingroom_x, startingroom_xtwo -1 do
		table.insert(room_border_tiles,{startingroom_ytwo,i,"bottom"})
	end
	for i=startingroom_y, startingroom_ytwo -1 do
		table.insert(room_border_tiles,{i,startingroom_x -1,"left"})
	end
	for i=startingroom_y, startingroom_ytwo -1 do
		table.insert(room_border_tiles,{i,startingroom_xtwo,"right"})
	end
	local number_of_tries=0 --stop the loop when this equals 'bout 10
	while number_of_tries <= 30 do
		local selected_tile=math.random(#room_border_tiles) --changes for testing. Remember to change back.
		--local choice = math.random(1,2) --determine what kind of structure to build next
		--this code is for the top. Add in relevant loops and ifs as neccessary
		if room_border_tiles[selected_tile][3] == "top" then
			nextroom_xtwo = math.random(min_room_width,max_room_width)
			nextroom_ytwo = math.random(min_room_height,max_room_height)
			nextroom_x = room_border_tiles[selected_tile][2] - math.floor(nextroom_xtwo/2)
			nextroom_y = room_border_tiles[selected_tile][1] - nextroom_ytwo
			nextroom_xtwo = nextroom_xtwo + nextroom_x
			nextroom_ytwo = nextroom_ytwo + nextroom_y
		elseif room_border_tiles[selected_tile][3] == "bottom" then
			nextroom_xtwo = math.random(min_room_width,max_room_width)
			nextroom_ytwo = math.random(min_room_height,max_room_height) 
			nextroom_x = room_border_tiles[selected_tile][2] - math.floor(nextroom_xtwo/2)
			nextroom_y = room_border_tiles[selected_tile][1] + 1
			nextroom_xtwo = nextroom_xtwo + nextroom_x
			nextroom_ytwo = nextroom_ytwo + nextroom_y
		elseif room_border_tiles[selected_tile][3] == "left" then
			nextroom_xtwo = math.random(min_room_width,max_room_width)
			nextroom_ytwo = math.random(min_room_height,max_room_height) 
			nextroom_x = room_border_tiles[selected_tile][2] - nextroom_xtwo
			nextroom_y = room_border_tiles[selected_tile][1] - math.floor(nextroom_ytwo/2)
			nextroom_xtwo = nextroom_xtwo + nextroom_x
			nextroom_ytwo = nextroom_ytwo + nextroom_y
		elseif room_border_tiles[selected_tile][3] == "right" then
			nextroom_xtwo = math.random(min_room_width,max_room_width)
			nextroom_ytwo = math.random(min_room_height,max_room_height) 
			nextroom_x = room_border_tiles[selected_tile][2] + 1
			nextroom_y = room_border_tiles[selected_tile][1] - math.floor(nextroom_ytwo/2)
			nextroom_xtwo = nextroom_xtwo + nextroom_x
			nextroom_ytwo = nextroom_ytwo + nextroom_y
		end

		if not pcall(draw_room,nextroom_x,nextroom_xtwo,nextroom_y,nextroom_ytwo,map,rows,columns,deposit_table) then
			number_of_tries = number_of_tries + 1
			goto continue
		end
		for i=nextroom_x, nextroom_xtwo - 1 do --NOTE: coordinates are deposited in here as [y,x] for better use with the map array
			table.insert(room_border_tiles,{nextroom_y-1,i,"top"}) 
		end
		for i=nextroom_x, nextroom_xtwo -1 do
			table.insert(room_border_tiles,{nextroom_ytwo,i,"bottom"})
		end
		for i=nextroom_y, nextroom_ytwo -1 do
			table.insert(room_border_tiles,{i,nextroom_x -1,"left"})
		end
		for i=nextroom_y, nextroom_ytwo -1 do
			table.insert(room_border_tiles,{i,nextroom_xtwo,"right"})
		end
		map[room_border_tiles[selected_tile][1]][room_border_tiles[selected_tile][2]]=2
		table.remove(room_border_tiles,selected_tile)
		::continue::
	end
end

function love.update(dt)
end

function love.draw()
	draw_map(map,32,32,tileset_quads,tileset)
	for key,value in ipairs(room_border_tiles) do
		--print(value[2],value[1])
		love.graphics.rectangle("line",value[2]*32-32,value[1]*32-32,32,32)
	end
	for key,value in ipairs(deposit_table) do
		love.graphics.setColor(0,255,0,255)
		love.graphics.rectangle("line",value[1]*32-32,value[2]*32-32,32,32)
	end
end

function draw_map(map,TileW,TileH,Quads,Tileset)
 for rowIndex,row in ipairs(map) do --note: ipairs is slightly less efficient than loop above
  for columnIndex,tile in ipairs(row) do
   local x,y = (columnIndex-1)*TileW, (rowIndex-1)*TileH
   love.graphics.draw(Tileset, Quads[tile], x, y)
  end
 end
end

function create_quads(QuadInfo,tileW,tileH,TilesetW, TilesetH)
  Quads = {}
  for i,info in ipairs(QuadInfo) do
  Quads[i] = love.graphics.newQuad(info[1], info[2], tileW, tileH, TilesetW, TilesetH) --create quads
 end
 return Quads
end

[s-ol]

You should probably outline your algorhitmn so we can tell where your implementation fails.

I'd like to help but I didn't ever do any PCG :/

[Robin]

A .love would be more useful.

[sladjkf]

Sorry 'bout that, here's a .love.

How my algorithm works:
Essentially, if you looked through the link I posted initially, it's something like this.

In this algorithm a "feature" is taken to mean any kind of map component e.g. large room, small room, corridor, circular arena, vault etc.
Fill the whole map with solid earth
Dig out a single room in the centre of the map
Pick a wall of any room
Decide upon a new feature to build
See if there is room to add the new feature through the chosen wall
If yes, continue. If no, go back to step 3
Add the feature through the chosen wall
Go back to step 3, until the dungeon is complete
Add the up and down staircases at random points in map
Finally, sprinkle some monsters and items liberally over dungeon

I think where my implementation is failing is around the "See if there is room to add the new feature through the chosen wall" bit. It does that just fine, but it seems to leaving behind some things? I also tried adding code to prevent rooms from overlapping, so it might be there also. I'm not quite sure, so that's why I made a post here.