Quickest way to test collisions

[idrougge]

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.

Actually, Blitz has a ShapesHit and a RectsHit command to do that in few lines of code, this thread is just about possible optimisations by writing your own collision detection routine.

[Retro1234]

Amos you have Bob collision commands that work quick and tell you what Bob hit what Bob can you do this in Blitz?

Though I don't think this was ever really used in commercial games they tended to go for Boxing.

[Shatterhand]

Originally Posted by Retro1234

Amos you have Bob collision commands that work quick and tell you what Bob hit what Bob can you do this in Blitz?

Though I don't think this was ever really used in commercial games they tended to go for Boxing.

If you use ShapesHit, yes. Not very fast, as I bet not very fast on Amos too and that's why they go for "Boxing"...

[Retro1234]

iirc it's seamless with Bobs in Amos but doesn't work so well with Sprites and scrolling thats why I never used it.

[Shatterhand]

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.

The DisplayAdjust entry on Blitz Basic manual is the most unuseful thing I ever read on a Manual. It's 2 paragraphs which give you ZERO insight on how the command works and what you're supposed to do with it.

Blitz manual is really a mess

[E-Penguin]

Blitz is pretty low-level, I'd be surprised if the language overheads were significant compared to the execution time of 1000+ arithmetic operations and conditional branches.

[NorthWay]

My take on how to do it (designed for assembler):
Take smallest object you want to check against, pick highest value of width or height, round up to next power of 2 (call this A).
Divide screen width by A, round up to next power of 2 (call this B).
Divide screen height by A, round up to next power of 2 (call this C).
Make a grid as a B*C array of single linked pointers.

For every object find which place in the grid the upper left corner belongs to and link in a pointer to the object. (Simple AND and shift operations.)
In the end check player against all objects in all the grid squares it can overlap.

[Master484]

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.

This should surely improve speed, if it's done in the right way.

However, I just realized that in the example code that I gave, I may have done it in the wrong way.

So here again...

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

...Because the inner IF statements only happen if the "IF" before it was true, then this means that in this case doing this trick can actually make things slower.

This is because I think that in many collision checks it only does one IF check and nothing more, which means that here for example bx = bulletx(g) in many cases gives speed boost for only the first "bx check", which is actually a "slow boost", because in this trick you always need at least 2 speed boosts in order to gain speed.

So in this example, I would probably remove all those variable changes, except the ex = enemy(f) at the top; only for that I am 100% sure it adds a lot of speed, but the others may actually slow things down.

---

Also, if possible, you should design the main object control loop in a way that only in the beginning you do this variable change trick, and then you put the variables back only after the whole main loop has finished.

So if your loop looks like this:

MOVEMENT
AI LOGIC (if any)
TEST COLLISION
BLIT
repeat until all objects done

Then the modified loop might look something like this:

enemyx = enemyx(f)
enemyy = enemyy(f)
MOVEMENT
AI LOGIC (if any)
TEST COLLISION
BLIT
enemyx(f) = enemyx
enemyy(f) = enemyx
repeat until all objects done

This way the only time when the variable change happens is at the beginning of absolutely everything, so that you don't need to do this stuff at every sub routine. The variable changes themselves take some time, so it's best to minimize the amount of times when this happens.

And also it helps if you name the "fast variables" with names that are similar to the Array/Newtype variables that you are changing, so ObjectX(n) simply becomes ObjectX = ObjectX(n). For Newtypes at least the name can be exactly the same, I assume that the same is true for normal arrays.

---

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.

Yes, dual playfield speeds up some things, but also it consumes lot of DMA time in comparison to standard 16 color mode, or so I have read. But on the other hand, in 16 color mode you'll be repairing the background all the time, and consume DMA slots that way. So in the end I'm not sure what would be better for shmups, good games were made for both dual PF and standard modes.

[ 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.

Well, if 900 checks consumes one frame, then in two frames you could do 1800 checks + some more because it's in ASM. Player bullets are multiplied sprites I think, and the enemies dont shoot that much. And there are occasional slowdowns when the screen gets crowded, so in those cases it actually uses 3 frames to count and draw all that stuff.

[E-Penguin]

Originally Posted by NorthWay

For every object find which place in the grid the upper left corner belongs to and link in a pointer to the object. (Simple AND and shift operations.)
In the end check player against all objects in all the grid squares it can overlap.

This is a variation on the tile approach - assign every object to a tile and check collisions against the surrounding tiles when doing a move?

Imagine a 20x16 byte array, each cell representing a 16 pixel tile. Write into that byte the shape number (or sprite number) representing the object, 0=empty. As an object moves, check if the destination cell is occupied, and if so, by whom. Destination cell = (x >> 4, y >> 4).

It limits movement/collisions to the cell size though. Small cells take up more memory.

[Master484]

Here is one more idea:

Add four more variables for the bullets: bulletLeftSide, bulletRightSide, bulletUpSide, bulletDownSide.

Use these variables to store the X and Y locations of the bullets hitbox walls. Update these variables every time when a bullet moves.

So 8 bullets move, and after every move you update 4 variables, so it's 8*4 = 32 operations.

And after this is done, then this routine:

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

Can be written in this way:

if enemyx(f) > bulletLeftSide(g)
  if enemyx(f) < bulletRightSide(g)
    if enemyy(f) > bulletDownSide(g)
      if enemyy(f) < bulletUpSide(g)
         collide()
      endif
    endif
  endif
endif

So we can remove those four + and - operations from the checks.

And because we had 30 enemies checked against 8 bullets, then we save 30*8*4 = 960 operations.

And even in the case where just one IF was checked (the case of the fastest non-collision) , we save 240 operations.

This should give a massive speed boost.


---

The DisplayAdjust entry on Blitz Basic manual is the most unuseful thing I ever read on a Manual. It's 2 paragraphs which give you ZERO insight on how the command works and what you're supposed to do with it.

True, and it's a shame because this command is super important if you're using the Display Library.

Here is what I know of this evil command.

I think that the default Blitz DisplayAdjust is just this:

DisplayAdjust CoplistNumber,0,0,0,0,0

This gives a normal 320 pixel wide screen, which is also the same if you dont use this command at all.

But here is a DisplayAdjust to get a 288 pixel wide screen:

DisplayAdjust CoplistNumber,-2,8,0,16,-16

That works for my AGA shmup demo at least, and it gives some 10% to 15% boost to bob drawing speed in comparison to a full 320 pixels screen.

Notice that those values I have found out through random shotgunning and guessing how this command works.

Also notice that if any of the larger AGA display fetch modes are activated, then that has an big effect on this command. But on A500 you don't have worry about this.

For the Slice library things are much more simple, because you just give the screen width in the Slice command (just make sure it's a value that can be divided with 16) . This is why I actually often use the Slice library when doing stuff for the A500.

[Shatterhand]

But here is a DisplayAdjust to get a 288 pixel wide screen:

DisplayAdjust CoplistNumber,-2,8,0,16,-16

That works for my AGA shmup demo at least, and it gives some 10% to 15% boost to bob drawing speed in comparison to a full 320 pixels screen.

Notice that those values I have found out through random shotgunning and guessing how this command works.

Also notice that if any of the larger AGA display fetch modes are activated, then that has an big effect on this command. But on A500 you don't have worry about this.

Later I'll test this on my ECS machine to see if I get similar results.

When you suggest to have a smaller display... if instead of having a less wide display, I just avoid using all screen vertically (Say, instead of using the 320x256 resolution, I go for just 320x200), will this help me get that DMA time too? Or it makes no difference?

[E-Penguin]

No expert but I think the width is important for DMA as the screen is drawn per line. A thinner display means less time fetching for the next line. Whereas a PAL display contains 256 lines whether you draw to them or not.

[Shatterhand]

Originally Posted by E-Penguin

No expert but I think the width is important for DMA as the screen is drawn per line. A thinner display means less time fetching for the next line. Whereas a PAL display contains 256 lines whether you draw to them or not.

That's what I thought too, but better asks for people who know their shit better than me

[alpine9000]

Don’t forget that your code is still running across all vertical lines (including the v-blank), so especially if your code is running out of chip ram then not having useless blank data copied to the screen will give you more time for CPU regardless of if it’s vertical or horizontal.

The visual DMA debugger is great for this kind of thing, especially when combined with marking important timing events with a background palette change.

[Master484]

When you suggest to have a smaller display... if instead of having a less wide display, I just avoid using all screen vertically (Say, instead of using the 320x256 resolution, I go for just 320x200), will this help me get that DMA time too? Or it makes no difference?

I have tested reducing the screen size both vertically and horizontally, and both methods give more speed. I'm not sure which way is better, but I could do some tests later.

Blitz manual also recommends that you reduce the screen size if you want more speed, here is a quote from the manual:

" Decrease the size of the display. During a frame, the display slows down the processor and blitter. A smaller display increases the amount of time given to the processor and blitter. "

This is the reason why almost all commercial games run on reduced screen sizes. A full 320*256 looks cool, and if you can get that to run at 50 FPS then great. But if you want more speed, then a little bit of size can be sacrificed.

Examples of games that have a 288 pixels wide screen: Elfmania, Risky Woods, Midnight Resistance, Battle Squadron, X-out, Agony, Amnios, and many more...X-out actually uses a visual trick that tries to hide this by making the score panel wider than the actual game area.

Some other examples would be Z-out and Turrican 2 that have 304 pixel screens, and Hybris and Mega Typhoon that have just 256 wide screens.

[Shatterhand]

Vertical shmups actually benefit from less horizontal space. On hybrid it makes a lot of sense to have a smaller screen. Considering most of that game uses just sprites, probably the coder chose a smaller display more for a gameplay than a speed benefit.

[Daedalus]

If you're using lots of colours, you also need to reduce the display width in order to use all the sprites. I can't remember exactly where the cut-off is, but sprite channel 7 will disappear on a full-width display when you reach a certain number of bitplanes.

[Shatterhand]

Originally Posted by Daedalus

If you're using lots of colours, you also need to reduce the display width in order to use all the sprites. I can't remember exactly where the cut-off is, but sprite channel 7 will disappear on a full-width display when you reach a certain number of bitplanes.

On a 3x3 dual playfield you lose channel 7

[Cobe]

Originally Posted by Shatterhand

On a 3x3 dual playfield you lose channel 7

Yup, same happened to me. But I was surprised that on ECS sprite was displayed correctly while on OCS it was a bit trashed.

[Shatterhand]

Originally Posted by Cobe

Yup, same happened to me. But I was surprised that on ECS sprite was displayed correctly while on OCS it was a bit trashed.

Yes, same to me, that's why my game "Roadtrip" shows some small graphics glitches when running on OCS (At least on Winuae, I have no OCS machine to test, just an A600 )