pmdata's blog

Many Falcon developpers wonder what the blitter can be used for, when the 68030 is as fast for drawing sprites. I answer that the blitter can do this, but in fact, it is a chip that can have other interesting functions, if you know how to use it (which is not the case for many coders). Once upon a time...

Do you remember some arcade games (mainly shoot'em ups) on ST where you would have avoid many adverse shots, but where the program decided elsewhere. Or some other games (fighting ones for example) where you could touch your opponent, even if on the screen you did not see any contact. All these behaviours have one cause: collision test between sprites were not precise enough. Why? Because it needs a bit of CPU time to do, when all ST games rely heavily on it to just display graphics.

Blitter, my friend

So, I order you now to use this poor little blitter to test the collision between any type of sprites, pixel-precisely (yes!!!). The blitter can do all sort of memory operations: copy, logical operations, bit-shifts. With a clever combination of these tasks, we can achieve this goal. For our problem, I was wondering if a simple logical operation could allow me to know if I have a collision or not. Ask yourself: which function give you 1 if both input operands are 1, and 0 in all other cases? Did you find it? No? Well, this is AND operation!!! Knowing this, you just have to make an AND between the two sprites, and the bits set to 1 will tell you where your sprites collide. We just need now to order the blitter to do this operation for us.

How it works

Before starting, look at scheme 1, which lies somewhere around, it shows us what we will have to do. One remark: what are we going to use for our operations? Easy: to test all the pixels of one sprite, we will use the mask of the sprite.

x1,y1,w1,h1 are coordinates and sizes of sprite 1.
x2,y2,w2,h2 are coordinates and sizes of sprite 2.

Bounding boxes

First, our sprites lie in rectangular buffer. We start by checking if the bouding boxes of sprites are intersecting or not. If it's the case, we process the coordinates of the intersection zone, in both sprites. There is intersection if sprite 1 starts in the middle of sprite 2 (or vice-versa), be it horizontally or vertically. The intersection zone lie between the highest value of start point of both sprites (x1 or x2 horizontally), and the lowest of end point of both sprites (x1+w1 or x2+w2 horizontally).

cx=max(x1,x2)
cx2=min(x1+w1,x2+w2)
if (cx2<cx) stop:no collision
cy=max(y1,y2)
cy2=min(y1+h1,y2+h2)
if (cy2<cy) stop:no collision
cw=cx2-cx
ch=cy2-cy

The intersection zone

Now we have the coordinates of it (cx,cy,cw,ch), we now process the position, relative to each sprite.

cx1=cx2=cy1=cy2=0
if (x1<x2) cx1=x2-x1
if (x2<x1) cx2=x1-x2
if (y1<y2) cy1=y2-y1
if (y2<y1) cy2=y1-y2

cx1,cy1,cw,ch is the intersection zone in sprite 1.
cx2,cy2,cw,ch is the intersection zone in sprite 2.

Now we have all parameters we need, we just have to do our logical operations: they are 3 simple operations (see scheme 2):

1. Copy intersection zone from sprite 1 to buffer.
2. AND it with intersection zone from sprite 2.
3. Copy it with OR in a single word, which will be our flag.

The source

Well, which size our temporary buffer need? A 320x200 screen is 64000 pixels, 8000 bytes in 1 plane. This is not so huge. The fact is that the buffer must be the size of your biggest sprite, if you don't know which size to allocate.

The intersection zone can start at any pixel horizontally and vertically, and different for both sprites. So you must bitshift with the blitter. It always shifts to the right, so to align the zone to pixel 0 in buffer, you must shift with 16-n value for horizontal shift.

The last step: how to know if I have bits set to 1 in my buffer? The blitter will tell us: it will copy all words from the buffer with OR, in a single 16bits word (COLFLAG in the source). Upon finish, if COLFLAG is zero, then there is no collision.

Why doing this extra copy? Well, the intersection zone is not necessarily a multiple of 16 pixels, plus there are bit shifts to align in the buffer. The blitter automask unneeded pixels on the right and on the left, so no problem. And don't forget that on STE, a 68000 without cache is not faster than a blitter. This routine works correctly on any machine with a blitter. But on my Falcon, a new problem arose: the data cache... What is the problem?

The routine writes to COLFLAG using the blitter. When the data cache is enabled, there is a problem, because the blitter does its stuff using DMA. The 68030, which resets COLFLAG to zero at start don't know that COLFLAG has been updated by the blitter. So you must disable the data cache before reading the flag to force it to be read from RAM.

Another solution, is to place COLFLAG somewhere where the data cache is not used by the 68030, for example, the I/O address space, reserved for custom chips. But you can not decide a safe 16 bits place on any chip present on the Falcon. Well, the blitter has the solution in it: it has 16 16-bit registers used for some operations, but not ours: the half-tone registers. Now, you just have to tell the blitter to write the COLFLAG in one of this registers, and we will be safe on both CPU and blitter sides.

If you try to test the buffer with the 68030, you must clear it before doing so. But you'll have the same problem with the data cache. So I think my solution (doing everything with the blitter) is not so bad.

The end

Well, if you think the blitter is too bad to display your big sprites in 640x480 and 8 planes, it is better to use it cleverly. The Falcon is a good enough machine, if you know how to use it. It still needs a good game to show off its power.

Sources and explanation (french) (Atari):
blitcol.zip (10 KB)