Array Tlist and leaks

The forum is locked. These are the original blitzbasic.com forums, kept so they can still be read. No new topics, replies or edits can be made here. To join in, head over to the Blitz3D+ forums.

Arne

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/

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