Quickest way to test collisions

[Daedalus]

Originally Posted by Shatterhand

Never figured this out either and it seems there's no way to do it without resorting to ASM (!!!)

My sprite 0 is always just a blank sprite and a draw it on the channel I want the sprite to dissapear.

Yep, that's a good solution... Another is to give it an X or Y coordinate that's beyond the limits of the screen - unlike blitting, sprites can be positioned beyond the limits of the visible area without trashing memory.

[E-Penguin]

I just found this...
http://eab.abime.net/showthread.php?...=remove+sprite

So, a quick way to disable a sprite is just to poke a 0 to the appropriate register then? I'll give that a go this evening.

http://amiga-dev.wikidot.com/hardware:sprxctl

Poke.w $dff142 0

, presumably

[Daedalus]

Yeah, that's more like the "official" way of doing it. I don't bother with that method personally, but it should work, bearing in mind the bit about also poking 0 to the SPRxDAT register as well.

[Shatterhand]

Originally Posted by E-Penguin

How can you tell its taking longer than a frame? I assumed because the red bar was relatively constant (not flickering between frames) it was all done before each vwait.

It was flickering on my setup.

I can test it on my real a600 if you want it. I made some tests yesterday on my a600. 16x16 3 bitplanes bouncing balls + simple joystick reading routines + test collision with 6 bullets ..14 bouncing balls is the max I get in a frame. The 15th one will make the code miss the frame

[E-Penguin]

I was doing some research last night, and the general opinion seems to be that it is, fundamentally, an O(n²) problem which scales exponentially with the number of object-pairs. The solutions were to do a broad-search phase to narrow down the options and then a narrow-search phase to perform the collision detection on likely candidates.

The broad-search phases were variations on the "sort by axis and sweep" proposal I'd made before.

If your game is a horizontal scroller, sorting on the x-axis makes sense as things are generally aligned along that plane. Likewise for vertical scrollers and the y-axis.

The "sweep" that seems to be most popular it to consider the beginning- and end-position along the chosen axis, in a sort of state machine.

This depends on using an axis-aligned bounding-box (AABB), which practically we're doing anyway. This requires 2 (x,y) pairs for upper-left and bottom-right to define the box. Looking at it from the single-axis perspective (let's assume x), you have x_begin and x_end.

If your list is ordered x-wise, then as you sweep from first to last, you should increase a counter at every x_begin, and decrement it at every x_end. If the counter goes above 1 then there is an overlap, and the current shape should be added to a list of potential collisions, for detailed checking in the narrow-search phase.

If you've got travel equally in both axes there are clever tree algorithms to break the screen down into zones according to sum of the subnodes, but that seems a bit complicated for a first effort, and as most Amiga games are focused on scrolling in one plane, might be overkill.

I'll give it a go this evening.

p.s. when you ran my test code did you have the blitz runtime debugger disabled? That makes a big difference.

[Shatterhand]

p.s. when you ran my test code did you have the blitz runtime debugger disabled? That makes a big difference.

Good question... I don't remember

[Shatterhand]

Originally Posted by Dan

well, then each bullet shall have grid position coordinates px,py

The enemy ship has, as well, px,py Grid - coordinates.


So when you save the coordinates for each bullet, you check if bullets px/py coordinate are near ship px,py , something like pseudo code:

if abs(bulletPX(x)-EShip_px(x))<=2 and Abs(BulletPY(y)-EShip_Py(x))<=2 then 
check for colision
endif

you should see what works better <=2 or <=1 , depending on the grid size.

You know what? This gave me an idea... I am between classes, was about to take a 20 minutes nap (I'm very tired now), and the idea just came to me.

I could use this approach for the X and Y coordinates instead of using grids.

Using my own own previous code as a base

for f =0 to num_enemies
   for g = 0 to num_bullets
       if abs(enemyx(f) - bulletx(g)) <= 16
            if abs(enemyy(f) - bulletx(y)) <= 16
                  collide()
            endif
        endif
    next
next

I don't know how fast is the ABS function, but I am pretty sure doing a subtraction is pretty quickly. If distance on X and Y are less than the hitbox size, then it's a hit.

This will work with 16x16 hitboxes (which is the size I am working), but you could have the size of hitboxes on a separate field.

Not only this would halve the checks, also the first check would return true on a smaller number of iterations.

Damn I'll only have time to check this on the weekend, I'd like to test it and see how much time I'd gain with this.

[Master484]

One thing that you could try is to use normal variables instead of variables that are inside of lists, arrays or NEWTYPE lists.

Variables that look like "enemy()\x" are super slow. And I think the same goes for the array variables in this code piece you posted:

for f =0 to num_enemies
   for g = 0 to num_bullets
       if enemyx(f) > bulletx(g) - 8
          if enemyx(f) < bulletx(g) + 8
              if enemyy(f) > bullety(g) - 8
                 if enemyy(f) < bullety(g) + 8
                          collide()
                 endif
              endif
          endif
        endif
    next
next

So to make this faster, you might try a version that looks something like this:

for f =0 to num_enemies
   for g = 0 to num_bullets

       ex = enemyx(f) ; makes normal variables
       bx = bulletx(g)

       if ex > bx - 8
          if ex < bx + 8

              ey = enemyy(f)  ; makes normal variables
              by = bullety(g)

              if ey > by - 8
                 if ey < by + 8
                          collide()
                 endif
              endif
          endif
        endif
    next
next

So you just first place the "list variables" into normal word variables, and then do all the checks with the normal variables.

And you should do the same thing for all parts of the code that make operations with variables that are inside lists/arrays/NewTypes and so on.

Every time when Blitz sees something like "enemyX (item number)", it first goes through a process where it searches for that variable inside that array/list/NEWTYPE list or whatever. And this is very slow.

---

Also here is a small shooter demo that I made last year:
http://eab.abime.net/showthread.php?t=85844

The ADF called "AGADualPlayfieldShmup" has a "bullet hell" style demo, although it's A1200 only...I can't remember much of it, but I think the collision detection was quite fast and it has blitz source code in the disk.

[Shatterhand]

Originally Posted by Master484

One thing that you could try is to use normal variables instead of variables that are inside of lists, arrays or NEWTYPE lists.

Variables that look like "enemy()\x" are super slow. And I think the same goes for the array variables in this code piece you posted:

for f =0 to num_enemies
   for g = 0 to num_bullets
       if enemyx(f) > bulletx(g) - 8
          if enemyx(f) < bulletx(g) + 8
              if enemyy(f) > bullety(g) - 8
                 if enemyy(f) < bullety(g) + 8
                          collide()
                 endif
              endif
          endif
        endif
    next
next

So to make this faster, you might try a version that looks something like this:

for f =0 to num_enemies
   for g = 0 to num_bullets

       ex = enemyx(f) ; makes normal variables
       bx = bulletx(g)

       if ex > bx - 8
          if ex < bx + 8

              ey = enemyy(f)  ; makes normal variables
              by = bullety(g)

              if ey > by - 8
                 if ey < by + 8
                          collide()
                 endif
              endif
          endif
        endif
    next
next

So you just first place the "list variables" into normal word variables, and then do all the checks with the normal variables.

And you should do the same thing for all parts of the code that make operations with variables that are inside lists/arrays/NewTypes and so on.

Every time when Blitz sees something like "enemyX (item number)", it first goes through a process where it searches for that variable inside that array/list/NEWTYPE list or whatever. And this is very slow.

---

Also here is a small shooter demo that I made last year:
http://eab.abime.net/showthread.php?t=85844

The ADF called "AGADualPlayfieldShmup" has a "bullet hell" style demo, although it's A1200 only...I can't remember much of it, but I think the collision detection was quite fast and it has blitz source code in the disk.

I am under the impression I already made this test and made no difference at all.

But if I actually did it, I'll try it again later and see if I get better performance. Your argument sounds very valid

[E-Penguin]

Flat arrays should be faster than lists of NEWTYPEs because there's less dereferencing to do. However it's not the major source of slowdown - that's the nested loops.

[Master484]

I am under the impression I already made this test and made no difference at all.

It might have been that you tested it in a case where the variable was used only once, in which case there is no speed difference.

So if you have:

ObjectX (obj number) + 5

And change it to:

x = ObjectX (obj number)
x + 5

Then you won't notice any difference.

But when you have two or more operations made with the same array variable like :

ObjectX (obj number) + 5
ObjectX (obj number) + 7

Then it will surely be faster with this trick:

x = ObjectX (obj number)
x + 5
x + 7

---

One other thing that came into my mind is the order in which X and Y hits should be checked. Usually that case which is more rare should be always checked first.

So if this is a vertically scrolling shooter where bullets travel from down to up and up to down, then the Y axis might be more rare, but I'm not 100% sure...

I'm just thinking that bullets might stay a long time in the correct X zone, but the hit doesn't happen for many frames because the bullet is still too low or too high in the screen and so the Y axis hit takes a long time come true.

So if the X zone is checked only after Y hit is true, meaning that the horizontal check only happens when the bullet and the target are at the same height, then I think it might be faster.

So it might be a good idea to swap the order in which X and Y are checked, and see if it has any effect.

[Shatterhand]

While the code I wrote here checks X axis first, the one I am using on my A600 actually checks Y axis first , for this exact reason

[Master484]

While the code I wrote here checks X axis first, the one I am using on my A600 actually checks Y axis first , for this exact reason

Ok.

I don't know how fast is the ABS function

I tested the speed of ABS in my speed tester program.

1000 ABS commands took 7 frames with VPOS around 50.

So unfortunately ABS seems quite slow. But the idea of counting the distance difference with a single substraction was good, I think this would work well in a shmup where you can put the Handle of all objects to the middle of the hitbox.

Also I tested the speed of "if then" comparisons.

1000 "If X < Y then A=1" comparisons took 2 frames with VPOS around 70.

1000 "If Test1(item number) < Test2 (item number) then A=1" took 2 frames with VPOS around 250.

Results are from a A500 setup with 8 MB of Fast RAM.

---

So indeed doing around 800-900 IF THENs is enough to take the entire frame.

So in the scenario of 8 bullets * 30 enemies * 4 IFs some tricks are needed.

Firstly, you should check that your code follows the logic of "Blit-Code-Blit", so that both the CPU and Blitter can run at the same time as much as possible.

If you draw all your objects one after another, so for example if you have 30 consequtive Blit commands with no other code between the blits, then lots of CPU time is wasted.

When Blitz sees any kind of drawing command (Blit, QBlit, Block, Scroll etc), it won't start executing that command until the last drawing command has finished. This is of course because the Blitter can draw only one thing at a time. So the CPU simply stops and waits for the Blitter to finish the current task, and only after this wait it executes the next graphics command and gives the Blitter orders to draw more stuff.

So if your code looks like this:

Blit enemy 1
Blit enemy 2
Blit enemy 3
Check collisions for enemy 1
Check collisions for enemy 2
Check collisions for enemy 3

Then lots of time is wasted: during the Blits the CPU is doing nothing other than waiting for the blitter, and during the collision checks the Blitter is doing nothing.

So a better way to handle this is this:

Blit enemy 1
Check collisions for enemy 1
Blit enemy 2
Check collisions for enemy 2
Blit enemy 3
Check collisions for enemy 3

Or in a game loop it would maybe look like this:

Repeat
Blit object (n)
Check collisions for object (n)
Move object (n)
Until AllObjectsDone=1

The Amiga is almost like a multi-processor computer thanks to it's special chips; the chips allow it to do many things at the same time. But to take advantage of this design you need to program your game so that it allows this multitasking to happen.

---
---

And another speed trick that has already been suggested, is that you check collisions only every second frame. So split 100 bullets in two groups and check 50 this frame and the other 50 next frame.

Although as mentioned if the bullets move too fast then collisions might be skipped. But for slower bullets this will work fine. Usually player bullets are fast, but enemy bullets are often slower. So for enemy bullets you might use this trick; and if a player vs enemy bullet collision is occasionally missed it doesn't matter so much...players only complain if their lasers miss the enemies, not when enemy lasers miss them.

[E-Penguin]

Good call on the multitasking. That's an aspect of Amiga programming that needs extra thought!

[Master484]

Good call on the multitasking. That's an aspect of Amiga programming that needs extra thought!

Indeed, I would even say that this is the most important thing when planning your general code flow.

I myself didn't realize this until I made some tests after reading some of the discussions in the assembler forum about blitter waits, and then I felt stupid when I realized that Blitz automatically waits for the Blitter to finish before executing any graphics command.

Because this is how the Amiga works: in assembler you must always wait for the Blitter to finish before giving it new stuff to draw...and Blitz Basic handles this waiting automatically for us, but what the manual doesn't tell is that the CPU then sits idle between the Blits, unless you give it something to do.

I believe that other languages like AMOS handle their graphics commands in this fashion too, so this is a good trick to try out.

---

Also screen size can affect performance quite a lot. If you are running a dual playfield on 320*256 full screen, then this eats up a lot of DMA time, because the screen is 6 bitplanes deep. This is why many dual playfield games, and games on general, run on reduced screen sizes.

So if your screen is 320 pixels wide, try reducing it to 288 or something. This way at every scanline there will be "empty space" on both sides of the display where no Display DMA is active, and this gives a good speed boost to both drawing and CPU operations.

On the Slice library reducing the screen width will automatically give you the speed boost. But on the Display library the width change is done with the DisplayAdjust command, and in it you have to set both the screen start and stop AND the correct data fetch start and stop in order to get the speed boost. If you change only the display width but not the data fetch, then it wont have any effect.

---

Also I would like to correct this code suggestion that I posted earlier:

for f =0 to num_enemies
   for g = 0 to num_bullets

       ex = enemyx(f) ; makes normal variables
       bx = bulletx(g)

       if ex > bx - 8
          if ex < bx + 8

              ey = enemyy(f)  ; makes normal variables
              by = bullety(g)

              if ey > by - 8
                 if ey < by + 8
                          collide()
                 endif
              endif
          endif
        endif
    next
next

This is the better way to do it:

for f =0 to num_enemies

  ex = enemyx(f)

   for g = 0 to num_bullets

       bx = bulletx(g)

       if ex > bx - 8
          if ex < bx + 8

              ey = enemyy(f)  ; makes normal variables
              by = bullety(g)

              if ey > by - 8
                 if ey < by + 8
                          collide()
                 endif
              endif

          endif
        endif

    next
next

In the old version the ex = enemyx(f) was done in every bullet check, even though it only needed to be done when the switch to the next enemy happened. Not sure if ey = enemyy(f) should also be moved where the ex = enemyx(f) now is, or should it be left where it is...testing would be needed to see which way is faster.

[Shatterhand]

I usually have my enemies on a list and I run a loop that works like

MOVEMENT
AI LOGIC (if any)
TEST COLLISION
BLIT
repeat

so in a certain way I am blitting between CPU operations.
The other thing I'm doing now is putting all my "list variables" on normal variables at the start of each iteration (well, at least the ones I am going to use more than once), so I only manipulate the normal variables. At the end of the iteration, I put the values back to the list variable. Didn't test how much speed I gained with it though... I am just trusting you (and to be frankly, this makes easier to work with subroutines )

Now for the display size, that's something I didn't know. Most of the time I use Dual Playfield so I don't have to redraw backgrounds graphics when moving stuff around, and this is supposed to be faster.

[Retro1234]

I'm interested to know what your solution is but surely if your moving All your Bobs at once in some loop you can also add a few lines to check if theres a collision?

...I keep forgetting you have 32 bullets and lots of enemies...Dammm

I'm really intrigued to know your solution.

There must be a common trick to this.

This is why a lack of Blitz examples is annoying.

[Shatterhand]

[ Show youtube player ]

around 31:30

You have up to 20 player bullets on screen + up to 15 enemies on screen (probably more)

20 * 15 * 4 = 1200 checks. And this is just the heli playing, you could have a 2nd player shooting even more bullets.

HOW THE HELL did those guys do it back at the time? I know Ron Pieket is a magic coder, but certainly there's some trick... even if I know Swiv isn't running at 50 fps.

-

Right now what I'm doing is running the enemy/collision logic at 25 fps and have the player shooting less bullets. Actually running the logic at 25 fps helped with other issues too.

[volvo_0ne]

Then they say AMOS is poor....

You can do bob/bob collision detects in 3 lines (4 if you want to know which bob/s)

Why is Blitz more complicated?

Afterall apart fro being system (screen) compliant, it does the same thing.

[Shatterhand]

Originally Posted by volvo_0ne

Then they say AMOS is poor....

You can do bob/bob collision detects in 3 lines (4 if you want to know which bob/s)

Why is Blitz more complicated?

Afterall apart fro being system (screen) compliant, it does the same thing.

You can do it with 30 objects against other 8 objects in a single frame?

Several examples here were done with just 4 lines too, even less with that. The thing is not how hard its to do it, the thing is when you need to check a lot of objects against a lot of objects. Although I posted this on the blitz forum (because that's what I am using), this is a very common problem when coding 2D games.

Can you do 960 IFs checks on Amos in a single frame? If so, then Blitz indeed has something very wrong with it.