speed with CollideImage

I noticed that the framerate of BlitzMax can drop dramatically with CollideImage. Take e.g. the following code I found on this forum.

Graphics 640,480,32

Global tList:TList = New TList

Type img
	Field image:timage
	Field x:Float,y:Float
	Field sx:Float,sy:Float
	Field r:Float,sr:Float
	
	Function Create:img(f:String)
		i:img = New img
		i.image = LoadImage(f)
		i.x		= Rnd(20,620)
		i.y		= Rnd(20,460)
		i.sx	= Rnd(-3,3)
		i.sy	= Rnd(-3,3)
		i.r		= Rnd(0,360)
		i.sr	= Rnd(-5,5)
		tList.Addlast i
		Return i
	End Function
	
	Method Update()
		x :+ sx
		y :+ sy
		r :+ sr
		If x>620 And sx>0
			sx = -sx
		ElseIf x<20 And sx<0
			sx = -sx			
		EndIf
		If y>460 And sy>0
			sy = -sy
		ElseIf y<20 And sy<0
			sy = -sy
		EndIf
		
		SetBlend ALPHABLEND
		SetScale 0.3,0.3
		SetRotation r
		SetColor 255,255,255
		
		' Draw this image in collision layer 1
		CollideImage(image,x,y,0,0,1)
		' Test all other images with collision layer 1
		For Local i:img = EachIn tList
			If i<>Self
				' This tests i.image for collision with layer 1
				If CollideImage(i.image,i.x,i.y,0,1,0)
					' We have a collision so let's make it red!
					SetColor 255,0,0
				EndIf
			EndIf
		Next
		' Clear all collision layers
		ResetCollisions()
		DrawImage image,x,y
	End Method
	
End Type

For j = 0 To 9
	i:img = img.create("bmax120.png")
Next

Repeat
	
	Cls
	
	For i:img = EachIn tList
		i.Update()
	Next
	
	Flip
	FlushMem
	
Until KeyHit(KEY_ESCAPE)

With nine images everything runs fine, but increasing the number of images to 50 the app becomes very slow. Is something wrong with this code?

Thanks.

Not sure if there's anything wrong but you could try doing a simple circle or box collision check first before doing a CollideImage check. I'm sure CollideImage is somewhat costly since it's pixel perfect.

I think the 50 image test is doing about 30 times the 'work' as the 10 image test. I get 1ms and 25ms which seems about right.

50 images = 50! ( 50 * 49 * 48 * ... * 2 * 1 ) tests if they are on the same layer, perhaps this is a reason?
Seperating into different layers speeds the stuff up

50! seems like an awfully huge number of operations to have to wait for: 3.04140932 × 10^64

Doesn't sound right...

Its not 50! this would be insane. Its like 50! but with addition instead of multiplication.

(1+N)(N/2)
(1+50)(50/2)
60*25
1550 checks

Still alot, but much more reasonable XD. A box or circle check would speed this up immensly. Keep in mind when comparing distances you dont have to have square roots anywhere. So, you take the sum of the squares of the components in the vector representing the difference in position. Then, compare to the sum of the radii squared. In bmax, it is faster to multiply the radii by itself (same for the other squares). Oriented Bounding Boxes could work, but without accessing the internals of bmax (for the matrices) it would probably be slower than a circle test.

Every image has to check 50 other images. So it's 50+50+50+...=50*50=2500 instead of 9*9=81. So I guess tonyg is correct with about 30 times the 'work', however I remember that BlitzPlus didn't have this trouble with 50 images. I don't have my PC here so I can't check.

[EDIT} Bot Builder I posted together with you. I'll take your advice and try this first (after having some sleep).

An optimised system will check 50+49+48+47+... an unoptimized system will check 50+50+50+... you only need to check a specific pair once.

To optimize I would try the following main loop-

While PLAYING
ResetCollisions
Update each object - move and write new position to collide mask
Collide each object - use collision read to change object states

Render each object
Wend

the killer in the above code could be all the ResetCollisions calls and the above design should help.

Running the code in debug mode will be much more noticable for performance also, processor intense bmx code is far more effected than graphics intense testing.

We could do with a CollideOval command also of course.