Faster ImagesCollide for larger objects please!

Im writing a program where I need to do lots of collision checks per frame between a 32x32 pixel character and the background bitmap (1024x768 16bit depth).
However this is Really slow in Blitz Max. I wrote a test program and my program would only do about 28 of these collisions (debug build off) before dropping frames (at 60fps like all good arcade games).
However using the same program, but with collisions between a 32x32 square and another 32x32 square I could do about 3000 of these before dropping frames.

I thought I might be able to get around this by using GrabImage to grab the 32x32 piece of the background under the main character square - but this turns out to be really slow too.

I really think that the ImagesCollide function could be speeded up when doing a collision between a very large bitmap and a small bitmap, because surely it only needs to check a very small square of the larger image - the rest is irrevelent.

Would it also be possible to do a fast version of GrabImage?, because I could imagine situations where it would be time saving to grab parts of the background, and do collision checks on them.

I would be very happy with a faster ImagesCollide function though. Maybe someone could check if it is also slow on their computer - just in case it is my gfx card? Thank you :) Rico

Heres my code (Does anyone know why the timer doesn't work - I was trying to time the function. I'm still learning)

-change the ncol number to alter the number of collisions

-------------------------------------------------

Graphics 1024,768,16
DrawRect 0,0,32,32
image:TImage=CreateImage(32,32)
image2:TImage=CreateImage(32,32)
GrabImage(image,0,0,0)
GrabImage(image2,0,0,0)

back2= CreateImage(32,32)
back:TImage=LoadImage("RMedia\backdropB.png")
SetBlend SOLIDBLEND

timer=CreateTimer(1000)

Cls
x=0;y=200;xv=1;ncol=28
Repeat

DrawImage back,0,0
DrawText tm+" "+tm2,0,0
x=x+xv
If x>992 Then x=992;xv=-xv
If x<0 Then x=0;xv=-xv
tm=TimerTicks(timer)

For t=1 To ncol
   test=ImagesCollide(image,x,y,0,back,0,0,0)
Next

tm2=TimerTicks(timer)-tm

DrawImage image,x,y,0
Flip 1
Until KeyDown(KEY_ESCAPE)

Moderator Note: When posting code, please use the [code ] or [codebox ] tags. See the following FAQ article for more information: What are the forum codes?

How quick is it when you use CollideImage?
I suggest you check through Assari's excellent [a http://www.2dgamecreators.com/tutorials/gameprogramming/collision/T1%20Collision2.html] Learning 2D Game Programming[/a] with Part2 showing how to use Collision layers.
Finally, why are you looping the collision in the same cycle when it will return the same results. I am guessing this is a test but it just seems too false.

I'm not sure how the imagescollide function is coded, however I can think of a few things that should be noted.

1) Without actually knowing, I'm positive that they only check what is needed. It would actually take more of an effort to do it any other way. What would you be comparing the other pixels in the larger image to exactly? This means that when checking a 32x32 image against a 1024x768, only a 32x32 section of the larger image is checked. Since it (probley) already does this, it's faster than grabbing a 32x32 image yourself. (Which will be slow... this could probley be sped up, but not keeping bmax at the opengl level it's at.)
2) When the calculations are done to figure out what part of each image is compared, this automatically guarantees some things. If the two images don't collide at all (based on position, and size, not on actual pixel data), then there aren't any actual pixel vs pixel checks. If only a small area say 5x5 pixels overlap, then only that is checked. What this means is that the function -could- take longer if more of the images overlap. Now, on your tests, you compared times with the function checking a 32x32 image against another 32x32 image, and a 32x32 image against a 1024x768 image. Now, do the two 32x32 images always have the same position? If not, it's not a fair comparison, since I'm willing to bet that in the second case (32x32 vs 1024x768), they always overlap 100%. What this means is that the first test may return with 0 actual pixels checked (won't even have to worry about actual image data), whereas the second test will always check 1024(32*32) pixels.
3) Now, there are still more things that need to be taken into account. The second test (32x32 vs 1024x768) does not need to check 1024 pixels. It could return on the first colliding pixels, which in the best case scenario means 1 actual pixel checked. In the worst case it means all 1024 where checked. Since Max2D creates a collision mask, (I believe) that creates an image detailing what pixels collided, this means that it will check all 1024 pixels, even though the first set may collide. If this is infact the case, then maybe there is a way to disable this functionality? I'm personally not sure as I don't use imagescollide.
4) Speaking of which... why are you using imagescollide? It seems that alot of newbies use this, and want pixel perfect collisions, when infact they are rarely needed, and in most situations undesirable even. Pixel perfect collision can (and will) lead to characters getting stuck or caught on things, and other bad gameplay factors. Pixel perfect collisions are insanely slow. Infact slower now that we use 2d in 3d, I believe. Pixel perfect isn't actually always pixel perfect when we do 2d in 3d as games do now. Etc, etc...

I would look into circle/circle based collision, or atleast see if imagesoverlap (square/square collision) couldn't be used instead. Circle/circle collision is my advice, as it can be extremely fast, and actually tends to lead to the best gameplay imo.

Now, as with everything above, there are exceptions. If your doing a 'point and click' adventure type game, then imagescollide may be the best for you... however even in that case you probley actually only need to check if 1 pixel (the point of the cursor) collides or not, not the whole cursor image.

Hope that isn't too confusing, and hope it helps, if anyone else wants to ellaborate or correct on anthing I said, feel free.

ImagesCollide is very slow and will remain so.
Its meant for very few checks.
It uses CollideImage with a layer (32) as well just that it cleans the layer after each operation! I guess you understand why this is slower than manual layer delete control do you? :)

If you want to do "tile layer" collision and the like, follow aboves advice: Check out assaris tutorial and think about how to use for your benefit.
To give you a simple example (on which you hopefully see why your attempt will never succeed):

You have a platform, your player moves over the screen but the platform is static.

Your approach will enforce a new write to collision layer of the whole platform each logic update. Using a layer you could once write it to that and only check collision of player with it without any further writting of collision data. When the platform moves you update the collision layer and rewrite the platform at the new position.

Use this for your own benefit (by only writting the current surrounding of the player to the collision layer for example if there is nothing else that needs to collide or only around dynamic stuff instead of writting everything) and you will start to realize HOW powerfull the collision system is.

I wrote some extended classes basing on it (Sprite classes) which write themself to specific collision layers and clear the layer if needed. those do it basing on movement etc.
Even did a GUI System basing on it which handles window activation of windows behidn the current one etc by using the indices of the returnes collision object array.

and just to mention that: yours is the noobish approach, not the one using collision layers. For two reasons:
1. You enforce n^2 tests if you want to test all vs all
2. You seem to forget that CollideImage (and ImagesCollide therefor) internally first do a colliderect so if there is no collision of the rect, pixel perfect checks will not even fire.

Trying to do a 1024x768 collision test by the way is a totally idiotic idea, sorry. No one would do that, at least no one with a basic idea of how to layout 2D games efficientely.

the only alternative is a whole own collision system that uses polygons instead of pixels. In that case, I suggest doing research on S.A.T and swept polygon collision


As a general rule: If CollideImage is to slow, your game structure most likely is broken or highly inefficient. So far I have not seen a case where it was a performance problem, so far always the inefficient use of its capabilities caused the slowdowns or very heavy usererrors.

Thank you very much for all the advice - I really appreciate it. I've just visited the tutorial you gave and I am currently reading through it. I wish you could buy a manual or something (I used to love manuals!) which could tell you exactly what each function does - I wasn't entirely sure what collision layers were before.
I do have some further questions though

1. Why does Max create a collison 'mask' showing what pixels have collided exactly - surely it justs needs to know that a collision has occured, not store the details. Is there another function that accesses this then?
2. When using ImagesCollide does Blitx just use a mask (like a 2 colour bitmap - black and white) for each image.

The program I wrote above was just a test to compare speeds because I thought that there shouldn't really that much difference between checking a small image with a small image AND a small image with a large image - given that the number of pixels checked should be the same. It just seems weird that I can only do 28 of the latter type of collision in a frame (60Hz).
I know my approach is somewhat inefficient but I was planning on using the power of modern PCs to save me programming time and make it very easy to add new enemies, obstacles and objects to my program. When I had my character going up a slope for example I could just check the next 2 positions up in a vertical direction using ImagesCollide and if the first one was free I'd move the character there, and if not He'd go to the 2nd one, and if he couldn't go there then the slope was too steep. It meant I could just draw my game background in Paint without much regard to actually defining slopes as slopes etc and I could just destroy bits of the background and my game objects would move happily about :)
Well this is really ineffiecient but I divided each frame up into 20 units and I never had an object moving more than 20 pixels a frame. This meant the most an object could move is 1 pixel before a collision check is done, hence objects never pass through each other or the background. I only actually updated the screen though every 20 units, so the objects weren't being drawn every unit.
I just thought this would not be too strenous for a fast computer, I can do 3000 of the first type of collision( small with small), so i don't think it was wildly optimistic.

I will definitely give collide image a go though. Are the 32 layers related to bitplanes at all, or are they totally different entities?

Thank you very much again for all the help - everyone here is very helpful!

Rico :)

P.S. I do eventually want to do a system using polygons, because I would love to do a 2d physics system for a platform game where you can shoot platforms down which tip and fall and where evvery object can be pushed or picked up - like Phun I suppose.

1) To give you an array of ALL objects you collided with. Not only the first one. Thats important if you use a 1x1 colliderect for example to get "click interaction" and want to know all objects below the mouse.

2) Collision is pure binary data I think (0,1) Either there is something to collide with or there is not :)

Modern computers have more power than old ones right.
But there are a few things that have elementally changed since back then:

1. Screen size is a multiple times what it was back then
2. 2D offered optimations that make a whole lot of a difference. Current hardware have no 2D acceleration at all, BM is pure 2D through 3D. So its better you learn the ins and outs of 3d hardware and opt for that (fillrate, overdraw etc)

=> You will still need to be a capable programmer and have a usefull design if you want to use Max2D for larger scale usage. For higher performance you would need to write your own batched and opted system using DX7 and OpenGL which would do the tasks optimized for your purposes.

And as a last thing: If you can implement some of the optimations and make them optional through flags and put them in the module board, I'm sure it would be considered to put them in.

I have re-written my test program to use CollideImage instead of ImageCollide but it seems to run at the same speed. I am only using one collision layer.
Could someone run my program (using an arbitrary background of the same size (1024x768)) and see what the maximum number of collisions they can do per frame (set ncol to different numbers), before you stop dropping frames. My monitor refreshes at 60Hz, but if yours is different it will at least give me some idea.

On my computer it runs smoothly with ncol=20, but then starts to drop frames around ncol=26.

Use the 'Z','X',';',.' keys to move the white cube around the screen. It is easy to see the difference in the smoothness of the cube's movements if the program is straining.

------------------------------------

'TEST PROGRAM
Graphics 1024,768,16
DrawRect 0,0,32,32

image:TImage=CreateImage(32,32)
image2:TImage=CreateImage(32,32)
GrabImage(image,0,0,0)
GrabImage(image2,0,0,0)


back:TImage=LoadImage("RMedia\backdropB.png")
SetBlend SOLIDBLEND

Cls
ResetCollisions(0)

x=0;y=200
ncol=30 
'ncol is the number of collisions checked for between
'the image and the background each loop


ResetCollisions(1)
CollideImage(back,0,0,0,0,1)

Repeat
	xv=0;yv=0
	lk=KeyDown(KEY_Z);rk=KeyDown(KEY_X)
	jk=KeyDown(KEY_COMMA)
	uk=KeyDown(KEY_SEMICOLON);dk=KeyDown(KEY_PERIOD)


	If lk Then xv=-1
	If rk Then xv=1
	If dk Then yv=1
	If uk Then yv=-1

	x=x+xv;y=y+yv

	DrawImage back,0,0
	DrawText " test  "+test,0,0

	test=0
	' below loop performs a number of collision checks
	' between image and the background
	For t=1 To ncol
		If CollideImage(image,x,y,0,1,0) Then test=1	
	Next


	DrawImage image,x,y,0
	Flip 1
Until KeyDown(KEY_ESCAPE)

I start dropping frames from 60FPS after ncol=200.
I am using a 7600GT rather than the 9800Pro in my sig.

Time for some code clean up. ;) I modified to code to work as follows:

Move the main rect around with the mouse.
Adjust number of collision checks with left/right mouse button.
Displays frames per second, num of collision checks and collision status.

Now you should be able to understand the results better. A bit of advice, stop worrying if your game runs at refresh rate, there's too many pc variables. The better thing to do is code your game using delta timing or some other way to time your logic independant of refresh rate. It takes time sure, but it will save you a bunch of head ache in the future. ;)

Note: This was first time playing with the built in collision checking, wow..the frame rate varies widly depending if you're colliding or not. Very strange, but now I'm tempted to write a quick lunar lander game! :) lol..

'
SuperStrict
'
Global x:Int
Global y:Int
Global ncol:Int = 10
Global frames:Int
Global fps:Int
Global startms:Int=MilliSecs()+1000
Global test:Int
'
Graphics 1024,768,16
Global image:TImage=CreateImage(32,32)
Global image2:TImage=CreateImage(32,32)
Global back:TImage=LoadImage("background.png") ' <<<< change path as needed
DrawRect 0,0,32,32
GrabImage(image,0,0,0)
GrabImage(image2,0,0,0)
'
ResetCollisions(0)
'
HideMouse
ResetCollisions(1)
CollideImage(back,0,0,0,0,1)

Repeat
 '
 If MouseHit(1)
  ncol=ncol-1
  If ncol<1
   ncol=1
  EndIf
 EndIf
 '
 If MouseHit(2)
  ncol=ncol+1
 EndIf
 '
 x=MouseX()
 y=MouseY()
 '
 SetBlend SOLIDBLEND
 DrawImage back,0,0
 DrawImage image,x,y,0
 DrawText "FPS: "+fps,0,0
 DrawText "Num of collide checks: "+ncol,0,30
 DrawText "Collide: "+test,0,60
 '
 test=0
 For Local t:Int=1 To ncol
  If CollideImage(image,x,y,0,1,0) Then test=1 
 Next
 '
 frames=frames+1
 If MilliSecs()>=startms
  startms = MilliSecs()+1000
  fps=frames
  frames=0
 EndIf
 '
 Flip 0
 '
Until KeyDown(KEY_ESCAPE) 
'
ShowMouse
'
'
'

:( I think my post was ignored....

I reiterate a few points. There is -NOT- the same amount of data testing in a 32x32 vs 32x32 images collide and a 32x32 vs 1024x768 test. The main reason for this is that pixels checked are only the ones that actually overlap. With your small images, I'm willing to bet that most of the time they don't overlap at all. With the large vs small image, they always overlap 100% (if the small image is on screen at all). Even with the collision layers stuff, this is true.

Reguardless of which collideimages type command you use, you -will not- get much faster with pixel perfect collision. It's just too many comparisons done on the CPU.

I suggest, once again, that you look into alternate collision methods.

Sorry Scienthsine
I did read your post, its just that I caught up in learning how to use the collision layers as opposed to ImagesCollide.
Anyhow you are right, it does make a BIG difference when the smallers images are overlapping every frame, however I get do about 611 of these (on MGEs program he kindly supplied) before I get a frame drop, where as I can only do about 19 approx before slowdown on the small vs large image test. So there is a big difference.
Of course you are right about looking into alternative methods but it does seem odd it is so slow. Really to do one collision check (in my example) a function needs to check only 32x32 pixels against another 32x32 square. Thats why I wanted a faster ImagesCollide function when doing a small image vs big image check.
Do graphics cards have blitters?, I rember the old Blitz used to tell you if a blitter was available in certain gfx modes. Sorry if you thought I ignored your post - I really appreciate your help and input. Thank you very much!

To tonyG and MGE,

Thank you both for running the program and for writing a better one! (MGE). Yes I noticed that I can a very fast fps when the image is colliding with the background every frame. Maybe after detecting a collision once at a position it doesn't check again? until the image is moved ? I don't know how the collisions work internally.
My computer (well, I'm using someone elses actually)isn't amazingly fast but I am thinking of buying a new one. I will however have to change my approach, I like Dreamora's idea of just checking against the players immediate surroundings. I could chop the background up into 32x32 squares and then only check the 4 squares under the character (but still use CollideImages). I was wondering if there is an easy way to write part of a image to a collision layer, beacuse it would be ace if I could just write the 32x32 section of the background below the player to a collision layer.
The only thing is, is if I have a lot of objects moving around the screen all doing collison checks against the background I might end up effectively drawing the whole background to the collision layer anyway albeit in 32x32 chunks. Anyhow I can see ways this can be speeded up like Dreamora said. So I'll get to work on it
Thanks - Rico

P.S. Just tryed MGE's program using ImagesCollide instead of CollideImage and I get the same fps value. I thought you guys said CollideImage was faster! ;)

You can draw the whole background to background layer but I still would chop it up so it internally does not have to check that many objects.
The other thing is that you normally should seperate your collision writes to at least 2 layers.
One layer where dynamic stuff that shall collide is written to (projectiles, actors etc) and one where the static stuff is like the tilemap etc.
reason is that you can use resetcollision on the dynamic layer on every frame and only reset the static layer when its position changes. Writing the collision is the time consuming part normally, not the reading part so the less often you have to write it the better for the end performance :)

One thing not used in all of these codes here is the fact that you can send an object in when writting the collision data to the layer. if another object then collides with it you will get that object back in the collision array instead of the TImage reference. Very powerfull when you write a little CollisionComponent and makes it very simple to get the "other" object in a collision reaction near instantly.


If you have a "physically" touched game thought using a polygon based physics system (there are a few for BM) might be better, as pixel perfect does not give you surface normals for example so a "bounce" reaction is near impossible if you do not restrict it to simple stuff like circles and quads.

They're the same command under the covers.
Imagescollide will check one image against another by writing the single image to a collision layer and checking.
CollideImage can write multiple images to the collision layer. Because you're testing the same images multiple times you don't get the benefit of Collideimage... I suspect.
If you need to do LOTS of collisions then search for Shifted Grid. I think there is a B3D (maybe a Bmax version) example on these forums.
Alternatively check the code archives for the customised 'shape' collisions (circle. rectangle/ elipse etc) as these will not be as accurate but quicker and, maybe, good enough. You could also try creating collision hotspots on your player and background so you can cut down the number of areas that need to be checked. Personally, I would the tilemap method if your current method doesn't give best results.

Actually.......if you want total pixel accuracy against a background, the performance in this demo isn't that bad to be honest. Especially if you add delta or independant timing logic handling. I've seen games that when they have alot of collision checking going on slow down to 15-20-30 frames per second, but it isn't that bad due to the delta/logic handling.

If you're doing a worms style game its much faster to just sample a few pixesl (test pixels in an area near the player) using pixmap stuff.