Collision Detection

[johnno56]

A quick question(s) in reference to 2D collision detection. Does BBCSDL have any "built-in" collision commands or would I have to do it "old school" and use something like an AABB routine?

J

[DDRM]

Hi Johnno,

I don't think there's any in-built collision detection in BBC BASIC, though the supported Box 2D library does support it, I think. Not sure if there's any built into SDL, which you could call as a SYS command - that's certainly a possibility given the emphasis on gaming support in SDL.

Depending on what level of sophistication you need, collision detection isn't too hard in 2D: just check for overlap of the bounding boxes is a good start - is that what you mean by AABB (axis-aligned bounding box)?

David Williams might be a good one to comment: David, does your GLIB or variants offer collision detection?

Best wishes,

D

[David Williams]

Most of my games use GfxLib2 to draw sprites and stuff, and the collision detection method I almost always use is based on setting bits in the otherwise unused alpha channel of the background that the sprites are drawn on. This allows easy, very fast (often practically free), pixel-perfect collision detection. But it's not without its limitations! (I can expand on this point if requested to do so.) In any case, I would advise the OP to soldier on with BBCSDL because of its cross-platform nature and SDL2 is more capable than GfxLib2. There's also the minor 'issue' that GfxLib2 isn't really officially available any more, although if anyone really wants a copy of it then I can provide a link. I'd stick with SDL2, though.


David.
--

[DDRM]

Intriguing! I'd be interested to read an outline of your approach!



D

[johnno56]

So... In a nutshell... Nothing built-in... I am used to using AABB (Rect/Rect, Circle/Circle, Circle/Rect)... "Old school" is a little more work but that doesn't bother me. I suppose I ought to familiarize myself with the basic (no pun intended) graphics commands... It's been a 'long' time since I have coded anything BBC...

Thank you for replying and offering suggestions. Much appreciated.

J

[David Williams]

Intriguing! I'd be interested to read an outline of your approach!

Okay, very briefly because I don't want to derail J's thread which is about 2D collision detection with BBCSDL.

I don't think alpha channel-based collision detection is amenable to how SDL2 does things, but as I'm an extremely infrequent user of BBCSDL and with almost no knowledge of SDL2 itself, I'm not in a position to say anything about it. Johnno should consider contacting Richard directly.

With BB4W and the now elusive GfxLib2, you can plot a sprite (an alien or a ball or whatever) using something like:

Code: Select all

SYS GFXLIB_PlotSetAlphaBit%, gfx{}, alien_spr_addr, alien_spr_width, alien_spr_height, xpos, ypos, 5

and it will draw the sprite in the usual way, except that it also sets bit 5 in the 'spare' alpha byte of any overwritten background pixels (there are 4 bytes per pixel - red, green, blue and alpha). Usually, the alpha channel of a bitmap (or sprite) is used for alpha blending or anti-aliasing masks and whatnot, but here we've repurposed it for collision detection!

The are 8 alpha bits available (labelled 0 to 7). Here I've chosen bit 5 for no special reason other than example purposes.

So, having plotted our alien sprite, how do we actually detect it later? Well, there are several ways (but I don't have time to go into all of them - sorry!), with GfxLib2 you can do this:

Suppose you want to see if your, say, ball sprite is colliding with an alien sprite, you could use GFXLIB_PlotTestAlphaBit:

Code: Select all

SYS GFXLIB_PlotTestAlphaBit%, gfx{}, ball_spr_addr, ball_spr_width, ball_sprite_height, xpos, ypos, 5 TO R%

If the returned value R% turns out to be non-zero, then we've got a collision. That function plots the ball sprite, but also at the same time tests for any (overwritten) background alpha values which have bit 5 set in them. If it finds just one such pixel, it returns the value 2^5 (=32) in R% (otherwise zero). If you have lots of aliens on the screen, it doesn't tell you *which* particular alien your ball sprite has collided with, so you then have to do a search of some sort. But the initial collision detection is very fast. It's the subsequent search that takes time.

There's a method (not always applicable) which does away with having to search altogether. When you plot an alien sprite, you can store its array index directly into the alpha byte of any background pixels it overwrites. So discovering which alien your ball has collided with is just a matter of detecting a non-zero alpha value (which indicates a collision), and that alpha value is actually the array index of your alien -- well, not quite: the actually value that gets stored is index+1 if your alien array is zero-based (which it usually will be, I guess).

Anyway, I've made two example programs demonstrating (1) GFXLIB_PlotSetAlphaBit and (2) GFXLIB_PlotSetAlphaValue. You won't be able to run the BBC BASIC source code because the required version of GfxLib2 isn't available, but you can run the *compiled* programs in the exe folder (although Windows security watcher will doubtlessly try to persuade you not to!). When you run the (compiled) programs, you move the ball sprite around with the mouse, and when you click the left mouse button, if the ball is colliding with an alien sprite, that sprite will simply disappear.

GfxLib2 has a whole handful of alpha-channel-based collision detection-related functions. I used many/most of them for practically every game I made with BB4W.

Here's the temporary link:

http://www.proggies.uk/files/temp/gfxli ... ection.zip


David.
--

[johnno56]

David,

Not derailed... lol Grateful for the information. To be honest, I had to read through it a few times, before I could grasp the concepts as I am not as clever as most of you guys... lol But I am glad that there is at least one of us that has a handle of gfxlib...

Many thanks for the effort you have applied in responding. Much appreciated.

J

[DDRM]

Cute. Thanks, David.

[David Williams]

Cute. Thanks, David.

I should have mentioned in my incredibly rushed 'outline' that using this sort of alpha channel-based collision detection is just another version of colour-based collision detection. Back on the Acorn Archimedes, the most common screen mode for games was Mode 13 (320x256, 1 byte per pixel for 256 colours). One collision detection idea that I used (borrowed from someone else) was that all sprites comprised of odd-numbered colours were baddies! So all you had to do to detect a baddy was read a pixel (byte) from the screen, test its bit 0, and if set then you've got a baddy right there. Pretty fast, at the potential cost of vastly reducing the number of colours available for other things. And there's several variations on this method.

I remember the author of Nevryon (1991) -- one of the 'big' early Archimedes games -- telling me that he used the overlapping rectangles method for collision detection, so if it was good enough for him...

By the way, colour/alpha-based collision detection might not always be as fast as I earlier suggested. I suppose it depends on game specifics.


David.
--