[BMAX] Square to square collision seem to fail....

[Pixel_Outlaw]

I'm posting this here because this has become a language specific questions.

My square packing program was coming along nicely until the squares started to not check for collisions.

I've tried to comment on my code.

Basically it makes a random sized "room" then tries to fit the room into the "dungeon" array. The problem is that rooms do not seem to detect each other which leads to overlapping. The problem seems to lie on my add room function for the dungeons.

Well maybe someone here can help me.

Code: [Select]


' packs rooms inside an array
Strict
SeedRnd(MilliSecs())
' a dungeon holds an array and rooms that overlay spaces in the array
Type dungeon
Field array:Byte[,] , rooms:TList = New TList, rooms_maxed:Byte = False, room_count:Int = 0

Method add_room(min_width:Int, min_height:Int, max_width:Int, max_height:Int)
Local array_width:Int = array.dimensions()[0]
Local array_height:Int = array.dimensions()[1]
' first ensure that the room is not larger than the array
If max_width > array_width
max_width = array_width
End If

If max_height > array_height
max_height = array_height
End If

' ensure that the min values are larger than 0
If min_width < 2 min_width = 2
If min_height < 2 min_height = 2
' now set the size of this room
Local width:Int = Rand(min_width, max_width)
Local height:Int = Rand(min_height, max_height)
' if rooms_maxed = false, start at a random spot and find an open space
' if this is not possible reduce the width or the length by 1 unit and try again
' if either width or height = 1 quit and call the dungeon fully populated (rooms_maxed=true)
Local search_width:Int = array_width - width
Local search_height:Int = array_height - height
' now start a while loop that will search the whole array for an empty spot
Local search_x:Int = Rand(0, search_width)
Local search_y:Int = Rand(0, search_height)
' max iterations to look through for box
Local max_checks:Int = search_width * search_height
' places checked in while loop
Local checked:Int = 0
Local finished:Int = 0
While Not finished
'check to see if our room hit no other rooms, if not keep going
' add a room because it will fit (0 rooms)
If room_count > 0
Local r:room = New room
r.x = search_x
r.y = search_y
r.x2 = search_x + width - 1
r.y2 = search_y + height - 1
' check through the rooms for collisions
For Local b:room = EachIn(rooms)
If rooms_collide(b, r) = False
carve_room(r)
ListAddFirst(rooms, r)
room_count:+1
finished = True
End If
Exit
Next
EndIf

If room_count = 0
Local r:room = New room
r.x = search_x
r.y = search_y
r.x2 = search_x + width - 1
r.y2 = search_y + height - 1
' set the area inside the room to 0
carve_room(r)
ListAddFirst(rooms, r)
room_count:+1
finished = True
Exit
EndIf

' add to the index
search_x:+1
If search_x > search_width
search_x = 0
search_y:+1
End If
If search_y > search_height
search_y = 0
End If
checked:+1
If checked = max_checks
finished = True
End If
Wend
End Method

Method carve_room(r:room)
' take a room and carve out the space needed set squares to 0's
For Local x = r.x To r.x2
For Local y = r.y To r.y2
array[x, y] = 0
Next
Next
End Method

Method ready_array(length:Int, height:Int)
' sets all indexes to 1 and readys the array for writing
Local a:Byte[length, height]
array = a
For Local x:Int = 0 To length - 1
For Local y:Int = 0 To height - 1
array[x, y] = 1
Next
Next
End Method
End Type

Type room
Field x:Int, y:Int, x2:Int, y2:Int
End Type

Function rooms_collide:Byte(room1:room, room2:room)
If room1.y2 < room2.y
Return 0
EndIf
If room1.y > room2.y2
Return 0
EndIf
If room1.x2 < room2.x
Return 0
EndIf
If room1.x > room2.x2
Return 0
EndIf

Return 1
End Function

'test here
Local d:dungeon = New dungeon
d.ready_array(50, 50)
For Local i = 0 To 14
d.add_room(5, 5, 5, 5)  ' keep the rooms consistant to find the problem
Next

' test draw dungeon please
Graphics(640, 480)
For Local i = 0 To d.array.dimensions()[0] - 1
For Local j = 0 To d.array.dimensions()[1] - 1
If d.array[i, j]
SetColor 128, 128, 128
DrawRect(i * 8, j * 8, 7, 7)
Else
SetColor 200, 200, 200
DrawRect(i * 8, j * 8, 7, 7)
End If
Next
Next
Flip
WaitKey()



[hellfire]

Code: [Select]

For Local b:room = EachIn(rooms)
    If rooms_collide(b, r) = False
carve_room(r)
ListAddFirst(rooms, r)
room_count:+1
finished = True
    End If

I guess you just want to add the new room if it doesn't collide with *any* of the other rooms...

[Hotshot]

you making ROUGE game (I dont know if I have spell it right but I used play that game lots on ATARI 65XE...it got crap graphics but Good gameplay    )

[Pixel_Outlaw]

Ahhh thanks. I kept going over the code and just was having a hard time. I had not Divined the Code for over a week. Stuck camping at the base of a mountain in a boating lake. Perhaps I've grown a bit rusty.


Yes I'm making an engine for roguelike games. It should prove to work pretty slick when done.

[zawran]

I did not read through your code, but based on your image did this, which seems to work for placing rooms in the maze without overlap, so perhaps there is something to be gained from it.

Code: [Select]

SuperStrict

Graphics 1024,768

Local mazesize:Int = 50
Local maze:Int[mazesize,mazesize]
Local rooms:Int = 20
Local roomsize:Int = 5
Local spacefound:Int = 0
Local x:Int,y:Int,rx:Int,ry:Int

SeedRnd(MilliSecs())

For Local i:Int = 0 Until rooms

Repeat
spacefound = 0
rx = Rnd(mazesize-roomsize-1) ' create random x start from left side until mazesize minus the roomsize minus the border
ry = Rnd(mazesize-roomsize-1) ' same thing for the y start
For x = 0 Until roomsize+2
For y = 0 Until roomsize+2
If maze[rx+x,ry+y] = 1 Then spacefound :+ 1 ' check to see if any squares in the maze is taken already by a room
Next
Next
Until spacefound = 0 ' until no squares taken found

For x = 0 Until roomsize
For y = 0 Until roomsize
maze[rx+x+1,ry+y+1] = 1 ' fill in the new room
Next
Next

Next

Cls

For x = 0 To 49
For y = 0 To 49
If maze[x,y] = 0 Then
SetColor(128,128,128)
DrawRect(x*8,y*8,7,7)
Else
SetColor(192,192,192)
DrawRect(x*8,y*8,7,7)
End If
Next
Next

Flip
WaitKey
End


[Pixel_Outlaw]

Just ran your code seemed to run quickly. Mine looks really bloated now!  Very Impressive zawran! Have a karmoid.

I guess I will post what I have working.

Code: [Select]


' packs rooms inside an array
Strict
SeedRnd(MilliSecs())
' a dungeon holds an array and rooms that overlay spaces in the array
Type dungeon
Field array:Byte[,] , rooms:TList = New TList, rooms_maxed:Byte = False, room_count:Int = 0

Method add_room(min_width:Int, min_height:Int, max_width:Int, max_height:Int)
Local array_width:Int = array.dimensions()[0]
Local array_height:Int = array.dimensions()[1]
' first ensure that the room is not larger than the array
If max_width > array_width
max_width = array_width
End If

If max_height > array_height
max_height = array_height
End If

' ensure that the min values are larger than 0
If min_width < 2 min_width = 2
If min_height < 2 min_height = 2
' now set the size of this room
Local width:Int = Rand(min_width, max_width)
Local height:Int = Rand(min_height, max_height)
' if rooms_maxed = false, start at a random spot and find an open space
' if this is not possible reduce the width or the length by 1 unit and try again
' if either width or height = 1 quit and call the dungeon fully populated (rooms_maxed=true)
Local search_width:Int = array_width - width
Local search_height:Int = array_height - height
' now start a while loop that will search the whole array for an empty spot
Local search_x:Int = Rand(0, search_width)
Local search_y:Int = Rand(0, search_height)
' max iterations to look through for box
Local max_checks:Int = search_width * search_height
' places checked in while loop
Local checked:Int = 0
Local finished:Int = 0
While Not finished
'check to see if our room hit no other rooms, if not keep going
' add a room because it will fit (0 rooms)
If room_count > 0
Local r:room = New room
r.x = search_x
r.y = search_y
r.x2 = search_x + width - 1
r.y2 = search_y + height - 1
' check through the rooms for collisions
Local collisions:Int = 0
For Local b:room = EachIn(rooms)
If rooms_collide(b, r) = True
collisions:+1
End If
Next
If collisions = 0
carve_room(r)
ListAddFirst(rooms, r)
room_count:+1
finished = True
End If
EndIf

If room_count = 0
Local r:room = New room
r.x = search_x
r.y = search_y
r.x2 = search_x + width - 1
r.y2 = search_y + height - 1
' set the area inside the room to 0
carve_room(r)
ListAddFirst(rooms, r)
room_count:+1
finished = True
Exit
EndIf

' add to the index
search_x:+1
If search_x > search_width
search_x = 0
search_y:+1
End If
If search_y > search_height
search_y = 0
End If
checked:+1
If checked = max_checks
finished = True
End If
Wend
End Method

Method carve_room(r:room)
' take a room and carve out the space needed set squares to 0's
For Local x = r.x To r.x2
For Local y = r.y To r.y2
array[x, y] = 0
Next
Next
End Method

Method ready_array(length:Int, height:Int)
' sets all indexes to 1 and readys the array for writing
Local a:Byte[length, height]
array = a
For Local x:Int = 0 To length - 1
For Local y:Int = 0 To height - 1
array[x, y] = 1
Next
Next
End Method
End Type

Type room
Field x:Int, y:Int, x2:Int, y2:Int
End Type

Function rooms_collide:Byte(room1:room, room2:room)
If room1.y2 + 1 < room2.y
Return 0
EndIf
If room1.y - 1 > room2.y2
Return 0
EndIf
If room1.x2 + 1 < room2.x
Return 0
EndIf
If room1.x - 1 > room2.x2
Return 0
EndIf

Return 1
End Function

'test here
Local d:dungeon = New dungeon
d.ready_array(25, 25)
For Local i = 0 To 20
d.add_room(4, 4, 7, 7)    ' keep the rooms consistant to find the problem
Next

' test draw dungeon please
Graphics(640, 480)
For Local i = 0 To d.array.dimensions()[0] - 1
For Local j = 0 To d.array.dimensions()[1] - 1
If d.array[i, j]
SetColor 128, 128, 128
DrawRect(i * 8, j * 8, 7, 7)
Else
SetColor 200, 200, 200
DrawRect(i * 8, j * 8, 7, 7)
End If
Next
Next
Flip
WaitKey()



[zawran]

Here it is again, this time as a type with functions and methods. I have added a maxAttempts variable to prevent it from hitting an eternal loop in the room creation method and its a bit more flexible allowing for varied width/height of dungeon and rooms. Its in no way complete, but its been fun playing around with anyways.

Code: [Select]

SuperStrict

Graphics 640,480

SeedRnd(MilliSecs())

Local dunMaze:dungeonMaze = dungeonMaze.createMaze(25,25,0)
For Local i:Int = 0 To 19
dunMaze.createMazeRoom(Rnd(3,6),Rnd(3,6),1,50)
Next

While Not KeyHit(KEY_ESCAPE)
Cls
dunMaze.drawMaze()
Flip
If KeyHit(KEY_SPACE) Then
dunMaze.resetMaze(Rnd(20,40),Rnd(20,40),0)
For Local ii:Int = 0 To Rnd(15,35)
dunMaze.createMazeRoom(Rnd(3,6),Rnd(3,6),1,50)
Next
End If
Wend
End

Type dungeonMaze
Global dungeonMazeList:TList = CreateList()

Field maze:Int[,] ' the maze array that holds the content of the maze
Field mazeLink:TLink ' keep a direct link to the object in the list
Field mazeWidth:Int
Field mazeHeight:Int

Function createMaze:dungeonMaze(width:Int,height:Int,value:Int=0)
Local dm:dungeonMaze = New dungeonMaze
Local tmpMaze:Int[width,height]
dm.maze = tmpMaze
dm.mazeWidth = width
dm.mazeHeight = height
dm.mazeLink = ListAddLast(dungeonMazeList,dm)
' clear maze before returning
For Local x:Int = 0 Until width
For Local y:Int = 0 Until height
dm.maze[x,y] = value
Next
Next
Return dm
End Function

Method resetMaze(width:Int,height:Int,value:Int=0)
Local tmpMaze:Int[width,height]
maze = tmpMaze
mazeWidth = width
mazeHeight = height
For Local x:Int = 0 Until width
For Local y:Int = 0 Until height
maze[x,y] = value
Next
Next
End Method

Method removeMaze()
RemoveLink( mazeLink )
End Method

Method createMazeRoom(roomSizeX:Int,roomSizeY:Int,roomValue:Int,maxAttempts:Int = 10)
Local x:Int,y:Int,rx:Int,ry:Int,spacefound:Int,cnt:Int = 0
Repeat
spacefound = 0
rx = Rnd(mazeWidth-roomSizeX-1) ' create random x start from left side until width minus the roomsize minus the border
ry = Rnd(mazeHeight-roomSizeY-1) ' same thing for the y start and height
For x = 0 Until roomSizeX+2
For y = 0 Until roomSizeY+2
If maze[rx+x,ry+y] = 1 Then spacefound :+ 1 ' check to see if any squares in the maze is taken already by a room
Next
Next
cnt :+ 1
If cnt > maxAttempts Then Return
Until spacefound = 0 ' until no squares taken found
For x = 0 Until roomSizeX
For y = 0 Until roomSizeY
maze[rx+x+1,ry+y+1] = 1 ' fill in the new room
Next
Next
End Method

Method drawMaze()
For Local x:Int = 0 Until mazeWidth
For Local y:Int = 0 Until mazeHeight
If maze[x,y] = 0 Then
SetColor(128,128,128)
DrawRect(x*8,y*8,7,7)
Else
SetColor(192,192,192)
DrawRect(x*8,y*8,7,7)
End If
Next
Next
End Method
End Type


[Pixel_Outlaw]

That's cool!

Do you want me to credit you when I release this? I'm not going to just copy and paste your code but I feel that you should be credited when the engine is done.

[zawran]

No need to credit I am just having a bit of fun with it. It can be used for anything you find useful.