[roondar]

Originally Posted by Chrille

@roondar:
okay, your example was quick and dirty But your example is more expressive than my writings

You can optimize a lot in your example:
If this is run in a loop, you can put all constants to free data registers and save 8 cycles.

Anoter approach is, you could avoid a lookup tables, if the collision map width is a power of 2, e.g. use a map-width of 64 instead of 40 or 32 instead of 20. And use instead a single shift instruction. Yes, this will also consume a lot of time.

I agree my example can be optimised a bit, but it's not that relevant (nor always easy - you might need those registers you wish to use elsewhere and a power of two grid limits you in other ways even though it is usually faster to shift left by several places than it is to lookup via a table - which itself is faster than requiring a multiply).

The point is that you add on extra overhead for keeping track of the grid and then later reading back from the grid. Even if this is fairly small, it's still extra time you have to make up for in the actual collision testing. For large numbers of objects such an approach makes perfect sense but for smaller numbers I'm still unconvinced.

Remember, my code only shows a single access - it's fairly likely you'll actually need to do four accesses during store (objects that are not tile aligned need up to four tiles in the grid 'set') and again during read. Which either requires additional code to check for how many tiles to set or means taking the 'hit' of always setting four tiles regardless of alignment. Neither is optimal, both take quite a bit of extra time.

All in all, I'm pretty certain that the per object cost is going to be much higher when using a grid. It will be made up for when you check larger numbers of objects, but the question remains how many objects (on average) you'd need for it to make sense.

We are going d'accord that for a single player object it is not beeing worth. On the other side you may have many bullets, that also need a collision detection with background and enemies. And depending on the design enemies could also interact with other objects or background. Then you have to do the calculation to a screen map anyways.

The last version of the grid (as presented) does not seem to be suitable for bullet-to-enemy collisions as is, because it doesn't seem to track what object is where (only that some object is at some position) so you'd have no way of knowing how to handle the bullets. The earlier concept of the linked list does work here, as could a version that notes object numbers somehow - but both of those are more complicated so require extra objects to be faster.

Don't take me wrong, I do feel a tile based system is a good way to make things faster, but it requires the right circumstances to be viable. Simply put, I'm just not so sure that 12 enemy objects is enough for it to be 'winning' and I'm not in a position to write the code to test it at the current time. So it could be faster, but I'm not feeling it yet.


---

Originally Posted by zero

The tile method massively reduces the number of tests though.

For example, say you fill tiles with an index number for each enemy. Now rather than testing every player bullet against every enemy, you just do read per bullet to see which enemy it hit. The number of writes per enemy scales with enemy size, but so does the blit time which is going to be a far bigger issue than a few memory writes.

I realize this fully and don't dispute it. However, you do need up to four index writes per enemy due to alignment issues and, as I've said before, the actual reading/writing of the grid does cost more and this extra time spent must be 'won back' by having the now more expensive tests being so small in number as to cost fewer cycles than the 'cheaper' test that needs to run more times.

This is the core of my point - I'm not disputing fewer tests are needed, just pointing out that a simple bounding box test is really rather cheap and this, coupled with there only being about 12 objects to check, limits the gains that can be made this way.

But again, given enough objects and optimal code, I certainly agree a grid will outperform a simple bounding box loop.

No need to do read-modify-write either, don't worry about over-writing as enemies rarely overlap and when they do it's not clear which one should be hit anyway. No need to clear the grid, just keep toggling bit 7 in your writes/compares.

I'm not convinced you never need to do any clearing. I'd agree you can mostly avoid it, but the devil is in the details and a life lost due to a non-existent enemy colliding with the player is a pretty big no-no. Perhaps I'm just not seeing how you can guarantee you don't need a clear more than anything else.

Also don't worry too much about accuracy. With a fast moving game the player won't notice. When you look at most shoot-em-ups from the 80s and early 90s the collision detection is less than pixel perfect, certainly for enemies, and the small hit boxes obscure that fact. You can do a more accurate bounding box for the player only if required.

That depends on the situation. I'm pretty certain players would notice bullets skipping through enemies, which is a possible problem given that bullets tend to move fairly quickly. However, for player vs enemies or scenery you are most certainly correct.