dla dungeon generator algorithm

[ispot]

hello, hobby-newb here. i already managed to build some pong/tetris/basic platformers with love, so far so good

sorry if this is not the right place to ask this but i'm pulling my hair out, struggling to implement this dungeon generation algorithm. i tried to adapt the code and while there are no errors calling this function results in 100% cpu or crashes. should this be threated? i'm kinda clueless..

Code: Select all

--http://roguebasin.roguelikedevelopment.org/index.php?title=Diffusion-limited_aggregation

local x,y,cx,cy = 0 
local map = {}

function createmap()
size =24
blocksize = 32

--init map
for i=0, size do --height
	map[i] = {}
	for j=0, size do -- width
		map[i][j] = 1
	end
end

-- dla map
local builderSpawned=0
local builderMoveDirection=0
local allocatedBlocks=0 --variable used to track the percentage of the map filled
local rootX= size/2
local rootY= size/2 --this is where the growth starts from. Currently center of map
local stepped=0 --this is how long corridors can be
local orthogonalAllowed=1 --Orthogonal movement allowed? If ~=, it carves a wider cooridor on diagonal

-- The Diffusion Limited Aggregation Loop 
while allocatedBlocks < (size*size)/8 do
	if builderSpawned ~= 1 then
    --Spawn at random position
	cx = 2+math.floor(math.random()*size-2)
	cy = 2+math.floor(math.random()*size-2)
		--See if builder is ontop of root
		if math.abs(rootX - cx)<= 0 and math.abs(rootY-cy)<=0 then
			--builder was spawned too close to root, clear that floor and respawn
			if map[cx][cy] ~= 1 then
			 map[cx][cy]=1
			 allocatedBlocks = allocatedBlocks+1
			end
	    else 
			builderSpawned = 1
			builderMoveDirection = math.floor(math.random()*8)
			stepped=0
		end --end if
	else  --builder already spawned and knows it's direction, move builder
		if builderMoveDirection==0 and cy>0 then  
		cy = cy-1 
		stepped = stepped +1  --north
		elseif builderMoveDirection==1 and cx<size then 
		cx = cx+1 
		stepped = stepped +1 --east
		elseif builderMoveDirection==2 and cy<size then 
		cy = cy+1 
		stepped = stepped +1   --south
	    elseif builderMoveDirection==3 and cx>0  then 
	    cx = cx+1 
	    stepped = stepped +1 --west
		elseif builderMoveDirection==4 and cx<size and cy>0 then 
		cy=cy-1 cx=cx+1 
		stepped=stepped+1  --northeast
	    elseif builderMoveDirection==5 and cx<size and cy<size then 
	    cy = cy+1 cx=cx+1 
	    stepped=stepped+1 -- southeast
	    elseif builderMoveDirection==6 and cx>0 and cy<size then 
	    cy=cy+1 cx=cx-1 
	    stepped=stepped+1 -- northwest
	    elseif builderMoveDirection==7 and cx>0 and cy>0 then 
	    cy=cy-1 cx=cx-1 
	    stepped=stepped+1 -- southwest
		end
		-- ensure that the builder is touching an existing spot 
		if cx<size and cy<size and cx>1 and cy>1 and stepped<=5 then
			if map[cx+1][cy]==1 then
			    if map[cx][cy] ~= 1 then 
			    	map[cx][cy]=1
			    	allocatedBlocks=allocatedBlocks+1 --east
			    end
			elseif map[cx-1][cy]==1 then
				if map[cx][cy] ~= 1 then
				   	map[cx][cy]=1
				   	allocatedBlocks=allocatedBlocks+1 --west
				end
		    elseif map[cx][cy+1]==1 then
			    if map[cx][cy] ~= 1 then 
					map[cx][cy]=1
					allocatedBlocks=allocatedBlocks+1 --south
			    end
		    elseif map[cx][cy-1]==1 then
			    if map[cx][cy] ~= 1 then
					map[cx][cy]=1
					allocatedBlocks=allocatedBlocks+1 --north
			    end
		    elseif map[cx+1][cy-1]==1 then
				if map[cx][cy] ~= 1 then 
					map[cx][cy]=1 
				    allocatedBlocks=allocatedBlocks+1
					if  orthogonalAllowed == 1 then
					    map[cx+1][cy]=1
					    allocatedBlocks=allocatedBlocks+1
					end
			    end
			elseif map[cx+1][cy+1]==1 then
				if map[cx][cy] ~= 1 then
					map[cx][cy]=1
					allocatedBlocks=allocatedBlocks+1
					if orthogonalAllowed == 1 then 
						map[cx+1][cy]=1
					    allocatedBlocks=allocatedBlocks+1
					end
				end
			elseif map[cx-1][cy+1]==1 then 
				if map[cx][cy] ~= 1 then 
					map[cx][cy]=1
					allocatedBlocks=allocatedBlocks+1 
					if orthogonalAllowed == 1 then
						map[cx-1][cy]=1 
						allocatedBlocks=allocatedBlocks+1
					end
				end
			elseif map[cx-1][cy-1]==1 then
				if map[cx][cy] ~= 1 then
					map[cx][cy]=1
					allocatedBlocks=allocatedBlocks+1
				    if orthogonalAllowed == 1 then 
					    map[cx-1][cy]=1
					    allocatedBlocks=allocatedBlocks+1
					end
				end
			end
		else  builderSpawned=0 
		end
	end --end if
end --end while 

return map

end

[pgimeno]

There are several bugs in the original code, that you have ported.

Code: Select all

cx = 2+Math.floor(Math.random()*size-2)

That's pretty much the same as Math.floor(Math.random()*size) because it's subtracting and adding 2 without affecting the floor. Perhaps the intention was to multiply with (size-2) to leave a margin, and the author forgot the parentheses.

Anyway, JS doesn't have integer Math.random(), but Lua does, so it's better to use it:

Code: Select all

cx = math.random(0, size-1)

Similarly, for direction you can use:

Code: Select all

builderMoveDirection = math.random(0, 7)

Another bug is that for direction 3, it should subtract 1 from cx, not add. There are other bugs related to boundary conditions.

But back to your problem, I think it is that you're initializing map with all 1's, not all 0's.

Also, watch out for the globals you're defining. I don't think size or blocksize need to be global.

[ispot]

awesome pgimeno, thanks so much for your help! i got it working now.
i should have found out about int random() and initializing the map to 1's was a leftover from testing my draw func
my actual implementation is slightly different, i'm using this this together with classic lib because i want to spawn several instances of maps for different dungeon levels in the future (i'm not comfortable with metatables yet). i forgot to declare size and blocksize locally in my function example posted here as i'm actually using them as instance variables with self.