Collision Detection when using drawPixels()

[dannyroy_77]

Hi guys,
Thanx a lot for the previous posts, has been really helful and never knew a Discusssion board would be of sooo much use.

I got the method of extracting pixel data by getPixels() of DirectGraphics and then separating the sprites and then drawing them using drawPixels().

Now how will u do collision detection, will it be by the standard rectangle collision, using the x, y, w,h and checking intersection or is there any other better way to do it ?

[bartekn]

It depends whether your sprites are transparent or not. In the first case it's very easy as you only need to compare coordinates of two sprites in order to check if they intersects. In case of transparent sprites it's more difficult. Firstly you have to calculate the intersection rectangle of these two sprites, and then for each pixel in the rectangle check in both sprites if it's non transparent, if so the sprites collide with each other. Of course you can optimize the sprites' rectangles so there is no transparanet borders.

[albech]

Trick of my old Amiga days here:

For near pixel perfect collision, use a seperate 1-bit collision mask,
that is scaled down to 25% of the original.

This works for most - even fancy - and saves you a lot of pixel tests and you get great results.

Anyone buying me some beers now?

[dannyroy_77]

how do u use a collision mask , pls could u show some code
complementing it.
like suppose i have two sprites
1 sprites - width = 20, height = 30
2 sprited - width = 40, height = 50

Now suppose they intersect, how do i still make out if the non transparent pixels are touching ?
Plz show it with some sample code, wud be extremely helful.
Thanx , wud buy u beer sumday

[bartekn]

Collision masks are good if you don't need precise results, otherwise you will have to shift bits, which could be very slow. I can give you an example: both sprites are the same, 10x5 (o - transparent, x - any other color):

oxxxxxoooo
oxxxxxoooo
ooxxxooooo
ooxoxooooo
oooooooooo

If you were to use collision masks you would have to create a byte array 2x1 (10 bits fit on 2 bytes, and 5 bits fit on 1 byte) each bit set to 0 if there is a transparent pixel, 1 otherwise.
When checking collision you have to AND bot collision masks and check whether the result is 0 (no collision) or not (a collision detected). Of course it requires calculating offsets in both masks. However this is inaccurate without bits shifting because 1 byte represents 8 pixels, therefore in order to tests properly one would have to shift.

On the other hand collision masks require additional handling/memory etc. so I don't suggest using that. Nowadays phone processors' are much faster than Amiga's was, so if you have a well designed sprites (the example given is not so good because the last line is fully transparent) pixel testing is very good.

That's my point of view. Choose wisely what's better for you ;-)

[dannyroy_77]

Most of the things u just said went over my head lol
please could u provide me some links to get my graphix cconcepts right.
Thanx

[albech]

@bartekn,

Collision masks *are* in fact pixel tests, and one can greatly benefit from them:
- very small mem footprint
- precise
- quicker, much quicker than pixel tests (8 pixels in one go, 32 pixels in one go if you use scaled masks)
- scalable
- selectable (you can adjust your mask so that some areas of sprites are not subject to collision).

>>Collision masks are good if you don't need precise results

Eh, what? Collision masks are good *if you need* precise results.

>>If you were to use collision masks you would have to byte
>>array 2x1 (10 bits fit on 2 bytes, and 5 bits fit on 1

Ah, 5 bits fit on 1...how about 8 + 2 bits ???

>>When checking collision you have to AND bot collision masks
>>and check whether the result is 0 (no collision) or not (a
>>collision detected).

Correct.

>>Of course it requires calculating offsets in both masks.

No, just source offsets...

>>However this is inaccurate without bits shifting because 1 byte
>>represents 8 pixels, therefore in order to tests properly one
>>would have to shift.

No, you don't have to shift anything....

>>On the other hand collision masks require additional
>>handling/memory etc. so I don't suggest using that.

Yes, indeed - 10 bytes for your example (10x5)...or 5 bytes scaled...

>>Nowadays phone processors' are much faster than Amiga's was

You're joking now, aren't you?

>>...so if you have a well designed sprites...

well designed sprites should have a width that is a multiple of four...

[dannyroy_77]

albech couud u show some code, i understood, very little, but not sure wot i understood is right.
see suppose i have two images in short pixel format

x = val1,val2,val3
val2,val3,vla4
val3,val2,val1
val1,val0,val2

x = image of 3*4 pixels

y = val5,val0,val1,val2
val3,val1,vla4,val3
val2,val0,val1,val5
val2,val1,val2,val6

y = image of 4 * 4 pixels

val* = values of pixels in short,

now how do i check collision using collision masks ?
can u explain in terms of x and y

[bartekn]

@Albech,

>Collision masks *are* in fact pixel tests, and one can greatly >benefit from them:
>- very small mem footprint
Please tell me if there is a possibility to shrink a bit mask to the size smaller 8 times than the original sprite, then I can agree with you on "small memory footprint". Of course without any bit compression and other stuff like that ;-).

>- precise
if you don't use scaled masks! If you DO then you need both scaled and not scaled in order to be precise, but then you need additional memory

>- quicker, much quicker than pixel tests (8 pixels in one go, 32 >pixels in one go if you use scaled masks)
I agree with that.

>- scalable
>- selectable (you can adjust your mask so that some areas of >sprites are not subject to collision).
Correct.

>>Eh, what? Collision masks are good *if you need* precise results.
Of course when not talking about scaled masks.

>>Ah, 5 bits fit on 1...how about 8 + 2 bits ???
I don't understand...

>>No, just source offsets...
Sure, as a matter of fact just only in one mask.

>>No, you don't have to shift anything....
I definitely don't agree with you on that. Well, if sprites move by multiplicity of 8, then you are right ;-) I don't think if it's applicable to J2ME games (because of the small size of screen), e.g. in my game I use 12x12 tiles, the same for most of the sprites, there are sprites that move by 1,2,3,4 and 6 pixels per tick!

Please tell me then how to check if two sprites (12x12) collides with each other, if one is located at (0,0) and the other at (11,11) (they share only one pixel at (11,11)), without using bit shifting.

>>>>Nowadays phone processors' are much faster than Amiga's was
>>You're joking now, aren't you?
No I'm not. E.g. Nokia 7650 uses 104 MHz ARM processor (RISC architecture), comparing to old Amigas with 7Mhz 16 bit...

>>well designed sprites should have a width that is a multiple of >>four...
why four, not eight?

Bartek

[albech]

>>Please tell me if there is a possibility to shrink a bit mask to
>>the size smaller 8 times...

well for 25% compression, just use every fourth pixel and scanline of the sprite for the mask...

>- precise
>>if you don't use scaled masks!

What super-fancy objects are you trying to collide???
With 1:4 scaling for masks, you can do almost every 2D game (platformer, shooter, ...). Back in 86 I wrote several games that used that technique to collide with enemies, shots, rockets, even very irregular backgrounds, it works, believe me.

>>Ah, 5 bits fit on 1...how about 8 + 2 bits ???
>>I don't understand...

To avoid shifting around, use every bit of a byte, the leftovers (2 in this case) live in the upper nibble of byte #2.

>>No, you don't have to shift anything....
>>definitely don't agree with you on that.
>>well, if sprites move by multiplicity of 8, then you are right ;-)

I am even right when sprites move by one pixel...

>>Please tell me then how to check if two sprites (12x12) collides >>with each other, if one is located at (0,0) and the other at
>>(11,11) (they share only one pixel at (11,11)), without using >>bit shifting.

First, after doing the simple box/box intersection test, you have the intersection of both - use this to get your offsets for the source and create one additional mask byte for the destination.
Then do (only one calculation, in this very optimal case your mask/mask test and you are done.
Where's the shift?

>>No I'm not. E.g. Nokia 7650 uses 104 MHz ARM processor
>>(RISC architecture), comparing to old Amigas with 7Mhz 16 bit...

Yes, I know that...
But MHz is not an indication of performance - why is Series 60 so fu**ing slow ??? - your game must run at 600 frames then (based on your assumption) mine on the Amiga were all on 60fps (50 for PAL).

>>why four, not eight?

one long (for 8 bit images), or 2 longs for 16 bit images - alignment...

[bartekn]

Well, Albech, so if you are talking about compression please do not use "precise" word, otherwise other guys can get confused ;-). That was my point of view.

If you have small sprites (I consider 12x12 to be small) then EVERY pixel matters, there MUST not be compression at all! Otherwise you can even loose all sprite, if it's very small (only a few pixels of 144 are non transparent).

Regarding Amiga, I know some people from the age of Atari ST, Amiga etc., who still believe their machines are the best, the fastest, blabla... It's an endless discussion, I'm not going into that... The only thing that should be addressed here: Amiga was designed to be very fast in graphics, it has a lot of hardware accelerated features e.g. sprite collision detection and other.

Jsut comparing a speed of two CPU's isn't enough (look at AMD and Intel comparision tests on Tom's Hardware pages), I agree.

However the upcoming MIDP 2.0 standard (it's even available on one of the Nokia's phone) has Sprite class with collision detection methods that can be implemented in the hardware (at least it's Sun suggestion).

It's really interesting discussion ;-)

[dannyroy_77]

Cud some one answer my question ?

albech couud u show some code, i understood, very little, but not sure wot i understood is right.
see suppose i have two images in short pixel format

x = val1,val2,val3
val2,val3,vla4
val3,val2,val1
val1,val0,val2

x = image of 3*4 pixels

y = val5,val0,val1,val2
val3,val1,vla4,val3
val2,val0,val1,val5
val2,val1,val2,val6

y = image of 4 * 4 pixels

val* = values of pixels in short,

now how do i check collision using collision masks ?
can u explain in terms of x and y

[bartekn]

OK, dannyroy, I'll try to explain it to you...

I assume you use TYPE_USHORT_4444_ARGB format.

You must construct two bit masks for 'x' and 'y' sprites. Then for each valN of x you must check whether it's transparanet or not (boolean transparent = (valN & 0xf000) != 0. The first mask would be 3bitsx4, but as we can operate only on bytes therefore it would be 1x4 byte array. The same applies to the second sprite.

When about to check if x collides with y you have to perform two steps:
1) in the first step check if the sprites' rectangles intersect
2) then calculate offset in in the first mask (depending on the intersected rectangle) and then compare bit masks using AND operator (in that case you might shift 1-7 bits before ANDing, because of 1 byte alignment).

If you used compressed bit masks, as Albech suggested, you would have only 4 bits (1bit (every fourth pixel) x 4 ) carrying information about the transparency for each sprite...

Sorry, but I have not time to write an appropriate Java code.

[dannyroy_77]

Ok i got a bit of it, has any of you guys made or use level editors such as Tile Studio etc for j2me and do u think its a good idea writing a editor ? and if so does anyone want to work on an open source project for level editor for j2me ?

[bartekn]

I plan to write an editor, for now I use a very rough solution - I have a plain text file that looks sth like that:

##############################
#E.*#a..+.+.+++.+..+..+++...G#
#*.a#Hc.+++.++..+..+..+.+...b#
#*.+#Fa.+.+.+++.++.++.+++.!!!#
###A####.....*....#A####===###
#+++.%+=...%*.*%..#b#++++++++#
#!+++%+#=####.##=##B#+.**%%%%#
#**..%+#.*..#C#*+*#c#+.*.%***#
#b.%%@%B..%%&%%..c#+C+.*%$..X#
##############################

and then match characters to tile indexes ;-)

P.S.
Does anyone know how to use a Courier font when posting???