Array Tlist and leaks

BlitzMax Forums/BlitzMax Beginners Area/Array Tlist and leaks

Arne(Posted 2005) [#1]
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/





Mark Tiffany(Posted 2005) [#2]
Before version 1.12, you had to include FlushMem in your main loop somewhere to free up discarded memory. I can't spy a FlushMem above, and would give the symptoms you describe.

But if you upgrade to the latest version (now 1.14), you no longer need to worry about FlushMem, it's all automated for you, and it should reolve your problem! The code above certainly seems to run fine for me.


Arne(Posted 2005) [#3]
Thnks for the help! It works now! Mister 'Garbage Collector', whatever he does, did the trick. I hope he does his job well though, the objects are all over the place doing stuff.


(Image removed, serverspace troubles)

Still get some array out of bound errors crashing the program when I toy around with the grid resolution and object amount. Need to look into that. Comments on the code greatly appreciated! I bet a lot of people have done similar things for collision detection.


FlameDuck(Posted 2005) [#4]
Mister 'Garbage Collector', whatever he does
He collects garbage. Obviously. :o>


Arne(Posted 2005) [#5]
Haha, well let's hope he's more professional than me!

Edit: this problem was solved and I went for another solution.

I got a minor question. I'm using rather large grid cells now, think the size of a Zelda screen. So I figured that I'd give each object in a cell an X,Y polarity that indicates how close it is to an edge (-1,0,+1 for X and Y). This way I won't have to check the 8 surrounding screens (cells), but only the one the object is on, and possibly one above or to the sides, or if the polarity is in a corner, I check 4 screens in total. You can see the center 0,0 polarity of each screen here, drawn as a grey solid square.

(Image removed, serverspace troubles)

Now I got greedy, and thought why not use the polarity of the object I'm checking against aswell? If the 'Hero' has a top edge polarity, I only need to check 'Pythagoras' against objects in the screen above with a bottom edge polarity.

I basically have 3 sets of X,Y variables that I can use to produce a True or False to check for Pythagoras. Looks like this. Green is the allowed 'enemy' polarities (either 1 or 2 steps away), Blue is the relative screen coordinate (cell), and black would be the player standing in a corner.

(Image removed, serverspace troubles)

I have failed to produce a good formula for this, and the problem should be simple.


Now here's the question: Is the polarity thing completely retarded? Should I just grab the bull by its horns and skip polarity, and just check all 8 surrounding cells instead, but make them smaller to limit the amount of objects likely to be inside? This will consume more memory of course, and objects will change cells more often. How much does a TList cost in terms of memory?

I want to make something like 1000 objects and maybe have a playfield the size of 20*20 screens, or larger. Enemy population will be along the lines of Zelda.


Arne(Posted 2005) [#6]
Never mind, it was much more efficient to waste memory on the TList array. It made the code much cleaner too!

Right now I'm doing 1000 objects, 2000 proximity checks are done in maybe 11ms, and the movement (changing grids and so) is 3ms maybe. Not sure how good that performance is.
I'm using a 2.5ghz P4.

(Image removed, serverspace troubles)

Without lines this time. Each object checks maybe around 0-5 others, and unfortunately the objects check each other twice (A to B and B to A). The play area is actually 8k something pixels high and wide, so I scaled it down for plotting. Each GridCell is 128px. The TList array is 64*64 PLUS Sentinels, so it's 66*66. I was scared It'd hog a ton of mem but It's just using 270kb it seems.




Edit: Pic with lines just for clarity, seems they grab a few ms.
(Image removed, serverspace troubles)


LarsG(Posted 2005) [#7]
I have no clue what you're doing, Arne.. but it looks kinda cool though.. :)


Mark Tiffany(Posted 2005) [#8]
You might want to use the codebox tag, rather than the code tag. It does look cool though, whatever it is!


Tom(Posted 2005) [#9]
Hi,

Thoughts for optimising:

Try a fast square root calculation:
http://supp.iar.com/FilesPublic/SUPPORT/000419/AN-G-002.pdf

How about a square root lookup table? (memory hog!)

In your move loop try to use multiplication rather than division. Have a Const in your type:

Const sz:Float = 1.0 / GRIDSIZE

And replace:

XGridCurr=XPos / GRIDSIZE
YGridCurr=YPos / GRIDSIZE

With..

XGridCurr=XPos * sz
YGridCurr=YPos * sz

Same thing for the division in your draw loop:
this could be pre-calculated > (480.0/PIX_PLAYAREA)

Your demo averages 5ms, with some of the things I said there I got it down to a 'flickery 4!' :P


Arne(Posted 2005) [#10]
Wow, thanks!

SQRT table would be a hog indeed! I'll take a look at that pdf soon, gotta run an errand first. I suppose it covers using a dist^2 = (x^2+y^2) solution.

So multiplication is faster? XGridCurr is kinda sensitive, because it's used in the array, but I have a little padding (16px) added before the sentinels so I should be safe from strange float rounding errors I guess.

The draw stuff is all temporary, I just wanted to see what was going on.

Thanks a lot for taking time to comment!

For those who wonder what this is, I'm going to use it for stuff where I have a large persistant and active world. An example could be Asteroids, but with a much larger play area and asteroids that can all collide with each other.
I Made some quick GFX. No explosions or ufo yet. I figure I can just use rotate on the stuff, and use SetColor and LIGHTBLEND for the 2 shield layers (rotating cw and ccw to look varied and cool).

(Image removed, serverspace troubles)


fredborg(Posted 2005) [#11]
You don't need square root or power at all, both are really heavy calculations for the cpu. Do it like this instead:

' Place at top of code
Const DISTCOL# = 50*50

' The collision check method
	Method CollisionCheck(x:Int,y:Int) ' x,y are in the range 1- 0 +1
		Local Dist:Float, Diff:Float
		
		For Local BugTemp:Zig = EachIn GridList[x+XGridCurr,y+YGridCurr] 
			If BugTemp<>Self 'Just Temp<Self to save 'handshake' time? Might work.
			
				Pyths=Pyths+1 ' Count pythagoras just for benchmarking purposes.
				Diff = (XPos - BugTemp.XPos)
				Dist = Diff*Diff 	

				Color=1
				If Dist<DISTCOL
					Diff = (YPos - BugTemp.YPos)					
					Dist :+ Diff*Diff
					If Dist<DISTCOL
						Color=2
					EndIf
				EndIf
				
			EndIf
		Next
		
		'Delete BugTemp '? This is the garbage leak?

	End Method
There is actually a point in splitting up the distance calculation in several sub pieces, as in larger data sets it allows you to quickly filter out irrelevant entries, without wasting a lot of calculations on them. But it might not make any difference in your code...


Arne(Posted 2005) [#12]
Aah, yes, I was vaguely aware of using the ^2 solution, but didn't really know how to implement it. I'll definately use that bit of code! Thanks!

I threw in a Pythagoras because it's the first thing I could think of. I actually don't know what type of distance check to use yet. For an asteroids game, definately some Pythagoras cuz stuff is round.

Otherwise cubes could be useful in some games. I think dist= abs(x1-x2) + abs(y1-y2) is rhombic.

Maybe it would it be possible to do a distance lookup table that has lower resolution (greater distance) further away/up in the array?

I'm really tired now, been up all night and now it's getting dark again. I'll see tomorrow if I can work some on making a simple Asteroids game to demonstrate the idea with the program.