Hello!
I got BMX a few days ago and I'm really enjoying it. I've realized the usefulness of Types and Methods, so I'm trying to learn those a little better.
Many of my ideas incorporate large play areas and lots of enemies, so I need something like a QuadTree for collision detection. I figured I'd start with something else though, an array containing linked lists of objects inside each grid 'cell'. Objects may change grid cells as they move, removing themself from the old one and adding themself to the new.
To check for collisions I only look at the nearby cells. I would have to check 3*3 cells normally, but I check if the object is close to any of the edges, and that way I only have to check 1, 2 or 4 cells.
Well, it's almost working! However, the program mysteriously slows down gradually. I think it manages to kill some of my tray icons too, so I'm not sure how safe it is to run! I don't get any nasty errors though.
I've narrowed down the problem to line 140. It's the part where I know which grid cell is nearby, and I begin checking what objects are in its linked list. I do this with a regular For EachIn loop. If I comment it away I don't get any problems.
I've tried making it a Type Function and just a normal Program Function, but I still get the slowdown. I'm pretty clueless to what the problem is. I'm thinking that maybe some objects are kept in memory somehow. Maybe the lists get corrupted as objects flicker between the grid cells. Maybe I need to run some GarbageCollector? I'm using BlitzMax 1.09.
--
Edit: Intalled 1.14 and the Garbage Collector made the problem go away. I'll be reading this WikiPedia link in a minute:
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
Scroll down for screens (An array out of bound problem still remains if the grid size/num constants are changed.)
Edit: Actually, scroll down a bit for a better version of this program, without the array bounds error. Faster too.
Last Edit? Actually, by now I got a much better version. Open dir:
http://web.telia.com/~u48508900/spacegame/
I got BMX a few days ago and I'm really enjoying it. I've realized the usefulness of Types and Methods, so I'm trying to learn those a little better.
Many of my ideas incorporate large play areas and lots of enemies, so I need something like a QuadTree for collision detection. I figured I'd start with something else though, an array containing linked lists of objects inside each grid 'cell'. Objects may change grid cells as they move, removing themself from the old one and adding themself to the new.
To check for collisions I only look at the nearby cells. I would have to check 3*3 cells normally, but I check if the object is close to any of the edges, and that way I only have to check 1, 2 or 4 cells.
Well, it's almost working! However, the program mysteriously slows down gradually. I think it manages to kill some of my tray icons too, so I'm not sure how safe it is to run! I don't get any nasty errors though.
I've narrowed down the problem to line 140. It's the part where I know which grid cell is nearby, and I begin checking what objects are in its linked list. I do this with a regular For EachIn loop. If I comment it away I don't get any problems.
I've tried making it a Type Function and just a normal Program Function, but I still get the slowdown. I'm pretty clueless to what the problem is. I'm thinking that maybe some objects are kept in memory somehow. Maybe the lists get corrupted as objects flicker between the grid cells. Maybe I need to run some GarbageCollector? I'm using BlitzMax 1.09.
--
Edit: Intalled 1.14 and the Garbage Collector made the problem go away. I'll be reading this WikiPedia link in a minute:
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
Scroll down for screens (An array out of bound problem still remains if the grid size/num constants are changed.)
Edit: Actually, scroll down a bit for a better version of this program, without the array bounds error. Faster too.
Last Edit? Actually, by now I got a much better version. Open dir:
http://web.telia.com/~u48508900/spacegame/
Graphics 640,480,0 SeedRnd(MilliSecs()) Const XGRIDSIZE=64, YGRIDSIZE=48 'Size of grid cells Const XGRIDPLAYAREA=8, YGRIDPLAYAREA=8 'Size of grid array/map Const XPLAYAREA=XGRIDSIZE*XGRIDPLAYAREA, YPLAYAREA=YGRIDSIZE*YGRIDPLAYAREA 'PlayArea size in pix is calculated Global Pyths:Int ' For Dbug / benchmarking. Global GridList:TList[XGRIDPLAYAREA,YGRIDPLAYAREA] 'Set us up the grid, each grid position has a pointer list For y=0 To XGRIDPLAYAREA-1 For x=0 To YGRIDPLAYAREA-1 GridList[x,y] = New TList Next Next Global AllList:TList = New TList ' This is a linked list containing all the objects, used for updating all. Type Zig Global IDCount:Int ' Just for fun, first time I use type globals! Field XPos:Float Field YPos:Float Field Value:Int Field XGridCurr:Byte ' Current grid cell it's in Field YGridCurr:Byte Field XGridOld:Byte ' Old grid cell it was in, so we can check if it has moved Field YGridOld:Byte Field XEdge:Byte ' How close to edges 0-2 (-1 to +1 in a way) Field YEdge:Byte ' Dun wanna check 3*3 grids so it's useful to know edge proximity. Method New() 'Constructor XPos=Rnd(XPLAYAREA) ' Place in playarea YPos=Rnd(YPLAYAREA) IDCount=IDCount+1 Value=IDCount AllList.AddLast Self ' Add to AllList XGridCurr=XPos / XGRIDSIZE 'What grid cell coord? YGridCurr=YPos / YGRIDSIZE If XGridCurr<0 XGridCurr=0 ' Bounds for grid array. Just wanna make sure cuz array errors are nasty. If YGridCurr<0 YGridCurr=0 If XGridCurr>XGRIDPLAYAREA-1 XGridCurr=XGRIDPLAYAREA-1 If YGridCurr>YGRIDPLAYAREA-1 YGridCurr=YGRIDPLAYAREA-1 XGridOld=XGridCurr 'It's new so there's no old coords YGridOld=YGridCurr GridList(XGridCurr,YGridCurr).AddLast Self ' Add to GridList End Method Method Report() ' Draw SetColor 255,191,63 DrawRect XPos-1,YPos-1,3,3 End Method Method Move() XPos=XPos+Rnd(1)-0.5 YPos=YPos+Rnd(1)-0.5 If XPos<0 XPos=0 ' Bounds for pixel play area If YPos<0 YPos=0 If XPos=>XPLAYAREA-1 XPos=XPLAYAREA-1 If YPos=>YPLAYAREA-1 YPos=YPLAYAREA-1 XGridOld=XGridCurr ' Store old grid coordinates so we can check for movement with them later YGridOld=YGridCurr XGridCurr=XPos / XGRIDSIZE ' Find out what grid cell it's in. YGridCurr=YPos / YGRIDSIZE If XGridCurr<0 XGridCurr=0 ' Bounds for grid array. Just wanna make sure cuz array errors are nasty. If YGridCurr<0 YGridCurr=0 If XGridCurr>XGRIDPLAYAREA-1 XGridCurr=XGRIDPLAYAREA-1 If YGridCurr>YGRIDPLAYAREA-1 YGridCurr=YGRIDPLAYAREA-1 If XGridOld<>XGridCurr Or YGridOld<>YGridCurr ' Has it grid-moved? GridList(XGridCurr,YGridCurr).AddLast Self ' Add to new GridList GridList(XGridOld,YGridOld).Remove Self ' Remove from old GridList EndIf Local XRel:Int=XPos-(XGRIDSIZE*XGridCurr) ' Here we need to figure out what edge it's close to. Local YRel:Int=YPos-(YGRIDSIZE*YGridCurr) XRel=XRel/(XGRIDSIZE/3.0) YRel=YRel/(YGRIDSIZE/3.0) ' Better use 3.0 here, otherwise it might yeild a 3? XEdge=Xrel ' Can't store signed (-1) so we store 0-2 YEdge=Yrel End Method Method ProximityCheck() ' We only wanna check the grid cells it's close to, and its own grid cell of course. ' Since no sentinels are used, we must also do a boundry check. ' I have a feeling this 'If' construction could be simplified, couldn't make a 'For' loop work tho. Local Xok=False, Yok=False ' First check bounds If XGridCurr+(XEdge-1)=>0 And XGridCurr+(XEdge-1)<XGRIDPLAYAREA Xok=True If YGridCurr+(YEdge-1)=>0 And YGridCurr+(YEdge-1)<YGRIDPLAYAREA Yok=True CollisionCheck(0,0,True) ' no need to test Edge polarity in the same grid If XEdge<>1 If Xok=True ' Bounds CollisionCheck((XEdge-1),0,False) EndIf EndIf If YEdge<>1 If Yok=True ' Bounds CollisionCheck(0,(YEdge-1),False) EndIf If XEdge<>1 If Xok=True And Yok=True CollisionCheck((XEdge-1),(YEdge-1),False) EndIf EndIf EndIf End Method ' !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ' !PROBLEM IN THIS METHOD CAUSES GRADUAL SLOWDOWN! ' !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ' This method checks the distance to all objects in a selected grid cell Method CollisionCheck(x:Int,y:Int,PolarityCheck) Local Dist:Float, XDiff:Float, YDiff:Float, PolDiff:Byte 'If x<0 x=0 ' Bounds check in here instead? 'If y<0 y=0 'If x=>XGRIDPLAYAREA x=XGRIDPLAYAREA-1 'If y=>YGRIDPLAYAREA y=YGRIDPLAYAREA-1 For BugTemp:Zig = EachIn GridList(x+XGridCurr,y+YGridCurr) ' <<< It is this line causing problems! Isn't deleted after use? If BugTemp<>Self 'Just Temp<Self to save 'handshake' time? Might work. ' Test Edge 'polarities', must be opposite, unless in the same grid. If PolarityCheck=False 'We're not in the same grid, I hope! Never know with the bounds checks resetting stuff. ' not sure if I shouldn't just make the grid cells smaller. 'PolDiff = Abs((XEdge-1)-(x+BugTemp.XEdge-1)) + Abs((YEdge-1)-(y+BugTemp.YEdge-1)) 'If PolDiff =< 1 PolarityCheck=True PolarityCheck=True EndIf If PolarityCheck=True Pyths=Pyths+1 ' Count pythagoras just for benchmarking purposes. XDiff=Abs(XPos - BugTemp.XPos) YDiff=Abs(YPos - BugTemp.YPos) Dist=Sqr(XDiff^2 + YDiff^2) SetColor 60,95,110 ' Potential DrawLine XPos,YPos,BugTemp.XPos,BugTemp.YPos If Dist<16 SetColor 70,170,255 DrawLine XPos,YPos,BugTemp.XPos,BugTemp.YPos EndIf Else SetColor 50,55,65 ' Wrong Edge polarity! DrawLine XPos,YPos,BugTemp.XPos,BugTemp.YPos EndIf EndIf Next End Method End Type For i=1 To 100 Temp:Zig = New Zig Next SetClsColor 0,0,0 TimerStart = MilliSecs() TimerDiff = MilliSecs() While Not KeyHit(KEY_ESCAPE) Cls For y=0 To YGRIDPLAYAREA-1 ' Draw the grid For x=0 To XGRIDPLAYAREA-1 SetColor 50,50,50 DrawRect x*XGRIDSIZE, y*YGRIDSIZE,XGRIDSIZE,YGRIDSIZE SetColor 0,0,0 DrawRect x*XGRIDSIZE+1, y*YGRIDSIZE+1,XGRIDSIZE-2,YGRIDSIZE-2 ' Draw center for edge polarity clarity. SetColor 50,50,50 DrawRect x*XGRIDSIZE+(XGRIDSIZE/3.0), y*YGRIDSIZE+(YGRIDSIZE/3.0),XGRIDSIZE/3.0,YGRIDSIZE/3.0 Next Next TimerStart=MilliSecs() For Temp:Zig = EachIn AllList Temp.Move() ' Move Zig, ha ha. Next Pyths=0 For Temp:Zig = EachIn AllList Temp.ProximityCheck() ' Do the proximity test. Temp.Report() Next SetColor 70,120,220 DrawText "Pyths:" + Pyths,8,32 TimerDiff = MilliSecs()-TimerStart DrawText "ms:" + TimerDiff, 8,16 ' This timer slows down as a result of... ??? If KeyDown(KEY_SPACE) ' Debug! Hold down SpaceBar to count all objects. Count Matches atm. a=0 For Temp:Zig = EachIn AllList ' Count entire list a=a+1 Next DrawText "AllList Count:" + a,10,20 a=0 For y=0 To YGRIDPLAYAREA-1 ' Count grid cell by grid cell For x=0 To XGRIDPLAYAREA-1 For Temp:Zig = EachIn GridList(x,y) a=a+1 Next Next Next DrawText "GridList Count:" + a,10,30 EndIf Flip Wend