Sorted Sprite Collision Detection.

All 680x0 related coding posts in this section please.

Moderators: simonsunnyboy, Mug UK, Zorro 2, Moderator Team

User avatar
Atari Super Hero
Atari Super Hero
Posts: 508
Joined: Wed Nov 24, 2004 8:13 pm
Location: Halesowen, West Midlands, England

Sorted Sprite Collision Detection.

Postby bod/STAX » Tue Oct 02, 2012 10:32 am

I am currently optimising the collision detection code for the players bullet sprites with the game map.

The best way I can see is to sort the bullet sprites as suggeted in another thread.

This is the way the routine works at the moment:

1. Scan through the bullet structures to see which contain an on screen bullet.
2. Store used bullets structures X coord, Y coord and strucuture address in a table.
3. Sort the table into decending order (for example in the Y dimension bullets furthest to the top of the screen first, bottom of the screen last).
4. Scan through current tiles on screen coords and check with the sorted table, if an onscreen bullet has hit a tile read the structures address and set bullet status
accordingly. Read the next bullet from the table and check with the same tile if no collision move onto next tile.

Dong things this way means I only need to scan though the tiles onscreen once to check all onscreen bullets.

The problem I have is that only some bullets seem to be being detected.

Would I need to sort the bullets in the X dimension, sort the table and do a collision detect and then sort the bullets in the Y dimension, sort the table and do a second collision detect?

I know my sort routine works OK as it's from an old vectorball routine I wrote that sorted the balls into the Z dimension correctly.

I should also point out that the tiles are checked in the normal manner, left to right, top to bottom.
So let it be written, So let it be done. I'm sent here by the chosen one.

Atari User
Atari User
Posts: 33
Joined: Tue May 18, 2010 2:04 pm

Re: Sorted Sprite Collision Detection.

Postby seedy1812 » Mon Oct 08, 2012 7:56 am

Sorting the bullets depending up their y , x position will be slower than just unsorted.

If you are doing a vertical scroller an alternative is to create a 1 bit per tile collision map . ( is the tiles are 16 pixels wide on a 320 screen this is 20 bits -> or 1 long word ) and you only need data for what you see on screen. Of course this only gets updated when a new strip is added to the screen. This should speed things up as to detect you will only need to sub a map offset check its on the colission map and do a couple shifts to find out if a collision takes place. From this coordiante you can the get the tile involved.

User avatar
Fuji Shaped Bastard
Fuji Shaped Bastard
Posts: 3472
Joined: Sat Jun 30, 2012 9:33 am

Re: Sorted Sprite Collision Detection.

Postby dml » Wed Dec 12, 2012 2:41 pm

One method I had used in the past was to maintain a sorted list on both axes for a large world (or sorting by the world's major axis for a narrow one), using the object's lower/right edge for the sort.

This is simple and provides two means to keep stuff sorted cheaply for collision and near-interaction checking (especially the latter which can't really be done with collision masks):

- As the objects move themselves, a common part of the AI service could maintain the sort order for each object by updating that object's links. This is needed for objects that must interact with no 'loss' since the sort order is always correct. The cost profile is linear.

- For objects which can interact but loss isn't critical, an incremental pass can be performed each frame which sorts a only a few links at a time. The cost profile is super linear - efficiency rises with object count - but the loss rate also rises and tends to be proportional to the speed of an object. It also requires 2 separate list groups per object so it really needs to pay for itself to be worthwhile.

This approach is really only useful for a 1st pass rejection in big worlds with stuff going on outside the visible window and where the objects can be arbitrarily big - since the rejection cost per item is low. If all your collisions happen within or near the displayable window in the world and the objects are small, just using collision masks is usually cheaper.

There are many variations on the 'sorted list' including cell grids (objects migrate from cell to cell, and check neighbour cells for interactions - or occupy several cells at once and only check those) and quad or binary trees, which scale very well for different sized objects but are more complex to maintain.

Social Media


Return to “680x0”

Who is online

Users browsing this forum: No registered users and 3 guests