Procedural Level Generation (Lua)

[funnygamemaker]

So If im trying to create a procedural map generation like paranautical activity, or the binding of Isaac, but what I cant seem to understand is, if I create csg's with a for loop, or if I just create them with Entity:Instance, how would I check for collision with other csg's that are already made? So that when the csg's generate they dont back track and overlap.

[Rick]

So that when the csg's generate they dont back track and overlap.

 

I think you would use a 3D array (widthxheightxdepth) to store what "tile" is filled or not. Now this is all a very basic implementation of all of this. If you plan on allowing creation and destruction of these things like in a minecraft clone than this would be the best way to do any of this. Those things get more complicated on how to handle it.

[funnygamemaker]

Im using a 2D array for starters.

grid = {}
for i=0, 8,2 do
 grid[i] = {}

for j = 0, 8,2 do

 grid[i][j] = 0

end

I was thinking if I use the array, were "grid[j]= 0" should I have it based on a 0 or 1 based system or true and false, so that if its true or 1 its filled, and if its false or 0 its empty. But How would I do a Check to see if a certain grid is filled or empty. I made it 2d because Y value is just 0, that only values that will change would be x and z.

[Rick]

I mean you can make it any value and check you want. A common idea is that a 0 means empty and a 1 means something is already there so you can't put another there. And by having it only 2D you can't build upward/downward which I would guess you would like to do at some point.

[funnygamemaker]

I'm still having trouble with the fact of, how can I place the array to certain cords in the map; because what I'm trying to do is to stop the generation from backtracking and from creating another block(room) over one that is already made. I have a pretty crappy diagram , but all the purple squares are just for other possibilities of rooms, and if you see it generates the first room(green) then the second room, but you look at the arrows, the generation still can allow it to regenerate a block backwards and over the current previous rooms, which I don't want it to do, here's the chart

http://imgur.com/Uc35PsU

 

 

Here's and example video on what I'm trying to do

 

Im sorry that I dont have the script atm, I will edit this later today when I get home.

[nick.ace]

That's the point of the 2D array. Like Rick said, every time you place a piece down you put a 1 (or a non-zero number) in the corresponding grid cell. Everytime you think you might place down a piece, you check to see if a number !=0 is in that corresponding grid cell.

 

For example, if your grid looks like this and you are at the underlined position, you check randomly up, down, right, or left. Let's say you get left. Since if this case you can't go left because a 1 is there, you either pick up, down, or right (or you could optionally terminate):

 

0 0 0 0

0 0 0 0

1 1 0 0

0 0 0 0

 

You are not placing the array on coordinates of the map. The array IS the map.

[shadmar]

Here is an great article + code:

http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

[funnygamemaker]

I've been trying for a bit but still getting errors,

you check randomly up, down, right, or left. Let's say you get left

how would I do a check N,E,S,W. here is some of my attempts, neither one works, but I'm trying, I know I'm missing some variable information but I've been re-writing everything in differnt ways like 10 times already.

 

curgridy = 5 -- starting position
curgridx = 5 -- starting position
for i = 0, 6, 1 do

if direcction == 1 then
if grid[curgridx+1][curgridy] == 0 then
pos = pos + Vec3(2,0,0)
room:Instance()
room:SetPosition(pos)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(pos.x,pos.y,pos.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
grid[curgridx+1][curgridy] = 1
curgridx = curgridx + 1
end
end
if direcction == 2 then
if grid[curgridx][curgridy+1] == 0 then
pos = pos + Vec3(0,0,2)
room:Instance()
room:SetPosition(pos)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(pos.x,pos.y,pos.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
grid[curgridx][curgridy+1] = 1
curgridy = curgridy + 1
end
end
end
end

attempt 2.

if window:KeyHit(Key.Z) then
room:Instance()
room:SetPosition(pos)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(pos.x,pos.y,pos.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
pos = roompos
math.randomseed(Time:Millisecs())
directionOfRoom =math.random(1,3)
if directionOfRoom == 1 then
if gridz == 0 then
pos = pos + Vec3(0,0,2)
else
directionOfRoom = math.random(2,3)
end
gridz = gridz + gridz
elseif directionOfRoom == 2 then
if gridx == 0 then
pos = pos + Vec3(2,0,0)
else
directionOfRoom = math.random(2,3)
end
gridx = gridx + gridx

elseif directionOfRoom == 3 then
pos = pos + Vec3(-2,0,0)
end

end

---------------------another failed attempt

function Script:Start()
math.randomseed(Time:Millisecs())



grid= {}

for x=0, 5,1 do
grid[x] = {}

for y = 0, 5,1 do

grid[x][y] = 0
end
end


room = Model:Box(2,1,2)
room:SetPosition(0,0,0)
room:SetColor(255/255,20/255,20/255)
local roomcol = Shape:Box(0,0,0,0,0,0,2,1,2)
room:SetShape(roomcol)
roomcol:Release()

window = Window:GetCurrent()
math.randomseed(Time:Millisecs())
numberofrooms = math.random(1,4)
selectedroom = math.random(1,4)

posx = Vec3(0,0,0)
posy = Vec3(0,0,0)
grid[5][5] = 1
maxnumberofroom = math.random(5,10)

--getroomside = {grid[x+1][z], grid[x-1][z], grid[x][z+1], grid[x][z+1]}


grid[5][5] = 1

numDir = 4
curgridx = 5
curgridy = 5
math.randomseed(Time:Millisecs())
direcction = math.random(1,4)

end


function Script:UpdateWorld()
math.randomseed(Time:Millisecs())
local red = math.random(0,255)
local blue = math.random(0,255)
local green = math.random(0,255)




for i=0, 7, 1 do



if grid[curgridx][curgridy] == 1 then
if direcction == 1 then
posx = posx + Vec3(2,0,0)
room:Instance()
room:SetPosition(posx)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(posx.x,posx.y,posx.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
curgridx = curgridx + 1

else
if direcction == 2 then
posy = posy + Vec3(0,0,2)
room:Instance()
room:SetPosition(posy)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(posy.x,posy.y,posy.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
curgridy = curgridy +1
if direcction == 3 then
posx = posx + Vec3(-2,0,0)
room:Instance()
room:SetPosition(posx)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(posx.x,posx.y,posx.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
curgridx = curgridx - 1
else
if direcction == 4 then
posy = posy + Vec3(0,0,-2)
room:Instance()
room:SetPosition(posx)
room:SetColor(red/255,blue/255,green/255)
roompos = room:GetPosition()
roomcolision = Shape:Box(posy.x,posy.y,posy.z,0,0,0,2,1,2)
room:SetShape(roomcolision)
curgridy = curgridy- 1
end
end
end
end
end
math.randomseed(Time:Millisecs())
direcction = math.random(1,4)
end


end

[nick.ace]

What is the "direcction" variable (it doesn't get assigned anything)?

 

Here is the direction you generally want to take to create levels like this to ensure that everything is interconnected:

 

//starting at (0,0)
grid={}
gridsize_x=10
gridsize_y=10

start_x=5
start_y=5

//initialize
for x=0,gridsize_x do
for y=0,gridsize_y do
grid[x][y]=1
end
end
grid[start_x][start_y]=0

for z=0,10 do //you can use the keypress instead if you want, this is just to show multiple iterations

//initialize
randnum=Math:Floor(Math:Random(0,3.9))
if randnum==0 then
if start_x>0 and grid[start_x-1][start_y]<1 then start_x=start_x-1 end
elseif randnum==1 then
if start_x<gridsize_x-1 and grid[start_x+1][start_y]<1 then start_x=start_x+1 end
elseif randnum==2 then
if start_y>0 and grid[start_x][start_y-1]<1 then start_y=start_y-1 end
elseif randnum==3 then
if start_y<gridsize_y-1 and grid[start_x][start_y+1]<1 then start_y=start_y+1 end
end
grid[start_x][start_y]=0

end

//fill in with models, boxes, etc.
for x=0,gridsize_x do
for y=0,gridsize_y do
if grid[x][y]==1 then
//Place box or wall or whatever here
end
end
end

 

I didn't test this code, but you should be able to just plug it in (and of course replace the box comment at the end)

 

Right now it is basically one long path that DOESN'T cross over itself. You also won't have walls duplicate in the same spot because you are doing a boolean subtraction operation effectively (carving). You'll probably find it easier to carve out a map that to just build one from scratch, and this algorithm will help you with that. If you decide later to use modular pieces instead of blocks, then you just reverse the condition of the last nested for-loops.

 

Some ways to improve this:

• Add recursion so that the path can break off into multiple paths (medium)
  
• Go with the totally random approach to start and create a minimum spanning tree (hard)
  
• Add better ending conditions instead of expecting z to terminate after 10 iterations (easy)
  
• Allow for overlapping paths to add more variety (easy)
  
• Add affinity towards certain directions: basically make some directions more common than others based on location or other factors (easy)