Collision detection in HIRES

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
User avatar
Twilighte
Game master
Posts: 819
Joined: Sat Jan 07, 2006 12:07 am
Location: Luton, UK
Contact:

Collision detection in HIRES

Post by Twilighte »

I have started to write OTYPE again, an old Shoot'em'up idea with fancy smooth scrolling graphics and stuff.
You can find it here..

http://forum.defence-force.org/viewtopic.php?t=345

However i have hit a hurdle i have faced many times before. Collision detection!
Their are a few ways this can be done, just not sure the best one.
Method1
Create a Collision Map. Each and every object is placed in this map whose dimensions are reduced in resolution (from HIRES) to something like 40x34 (6x6 pixel blocks) then detect collision purely through reading areas in this map.
Pros: Easy detection of objects
Cons: Reduced accuracy, slows down game as every object plotted on screen must also be plotted in collision map.
Method2
Detect position and size of every object in relationship to other objects.
Pros: Faster and can be more accurate
Cons: Difficult to work with irregular or curve shaped objects
Method3
Use Method 2 then move down to pixel level to detect potential collision either by directly reading from screen or by redrawing each object relative to one another in a buffer.
Pros: Pixel accurate collision detection
Cons: Slow especially in stage 2 phase where gameplay would slow down as objects move very close to one another.
Method4
As objects are displayed, their position and sizes are recorded/modified in a table. When collision detection is required, the list is scanned.
Pros: This is similar to Method 2 but centralises searching of collisions to a single set of tables.
Cons: Difficult to work with irregular or curve shaped objects

Any better ideas :?:
User avatar
waskol
Flight Lieutenant
Posts: 414
Joined: Wed Jun 13, 2007 8:20 pm
Location: FRANCE, Paris

Post by waskol »

If I were you I would not bother myself with collision detection at the pixel level : too slow for our Orics.

I would prefer a faster, even it is less accurate, method : consider every object enclosed in a simple geometric shape or even in 2 or 3 if it is fast enough in order to get some more accuracy. The shape(s) can be a rectangular box, or a buble.

From there, and it is the technique often used in nowadays 3D games, is to combine this fast detection, and one of those you mention in your post.

Once 2 bubles collide (fast detection), then you go for a pixel level detection. But is it orth it ?
User avatar
Symoon
Archivist
Posts: 2307
Joined: Sat Jan 14, 2006 12:44 am
Location: Paris, France

Post by Symoon »

Maybe what I'm saying is stupid as I never really thought about such problems but...
Isn't the main ship & its laser (when shooting) the only items that require collision detection ?

Then you'd "just" have to test if any pixel comes next to these items, then there's a collision.
Oh, but the ship would collide with stars then... Mmmh, tough one; actually I don't know :?
User avatar
Twilighte
Game master
Posts: 819
Joined: Sat Jan 07, 2006 12:07 am
Location: Luton, UK
Contact:

Post by Twilighte »

Symoon wrote:Maybe what I'm saying is stupid as I never really thought about such problems but...
No, its actually cool to have someone with little or no prior knowledge to provide fresh insight or ideas into an age old problem.
Symoon wrote:Isn't the main ship & its laser (when shooting) the only items that require collision detection ?
Yes, quite correct, however in order to determine if a collision occurs the other objects like eol baddies and alien waves must all be sized and located.
Dbug has some very strong expertise in this area and i would be surprised he hadn't posted a response yet except his hd died on him recently.

However he was able to advise me that a priority must exist so that the objects that are most likely to collide with other objects are scanned first.
This will provide a much faster engine.
He also suggested two stages where the first detects the coincidence of boundary incursion(or penetration?) and the second moves to pixel level to determine whether the collision actually took place.
User avatar
Twilighte
Game master
Posts: 819
Joined: Sat Jan 07, 2006 12:07 am
Location: Luton, UK
Contact:

Post by Twilighte »

Currently i am working on method 4 without the second stage.
The problem with this game is that every object will also come with colour attribute changes. These all lie to the left of the graphic but not neccesarily exactly 6 pixels to the left.
We don't want to include these in the boundary of the graphic.
So i have devised a scheme where every object has an associated visual offset and size. This is then added to the current sprite position and placed in a list.
The list is actually multiple tables where each one is 32 bytes long.
Each table holds the Left border, right border, top border, bottom border, object type and object id.
Table Entry 0 always holds the Hero Craft and the last 8 entries in the table always hold the Aliens.
Between are held the enemy and hero projectiles and End-Of-Level Bad dudes.
A scan to detect collision between the craft and another object can search from 31 to 1, prioritising (hitting) tests on Craft/Alien collision first.
A scan to detect collision between the Alien and another object can search from 24 to 0, prioritising (hitting) tests on Alien/Projectiles first.
User avatar
Chema
Game master
Posts: 3014
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Greetings.

I have read some docs about collision detection, but I think I lost the urls (can look again if needed).

It is normally not needed to check for a great number of objects in old games (not like todays strategy games with hundreds of sprites around), so any simple method could do. Just check if bounding boxes intersect and then perform a pixel precision check.

If you need to manage many sprites at the same time then this might be too complex. In that cases the best method I found was simple:

1 Each object is defined by its bounding box, which can be calculated easily and is normally fixed during the game (or changes rarely).
2 Divide the screen in areas. Keep track about which areas each object intersects with. Fast intersect rect routines can make this quite rapidly. You only need to alter this list when an object moves, and just for that object.
3 When an object moves you just check for intersection with bounding boxes with objects that are in the same area.
4 Once a collision is detected (again by fast intersect rect routines) just proceed to pixel precision.

I *really* think pixel precision is necessary in arcades. Speccy games did this quite often and it is frustrating being killed by an enemy with is very near but did not collide with you.

Pixel precision is not that hard if you are using masked sprites, as you just check if masks overlap. In this case I think it can be done when drawing objects as all the above needs to be done anyway to repaint anything that is needed.

Else (not masks) you can check if graphics overlap, but objects would need some kind of contour... (?)

In other case, better try to describe objects (as was said some posts ago) by simple polygons. There are algorithms to check for intersections with those too. The graphic might be designed to work well with the polygon :)

If interested I can search for the docs again...

Cheers.
Igotafro
Officer Cadet
Posts: 47
Joined: Tue Feb 05, 2008 3:42 pm

Post by Igotafro »

I *really* think pixel precision is necessary in arcades. Speccy games did this quite often and it is frustrating being killed by an enemy with is very near but did not collide with you.
Yes, that's frustrating, but you can avoid the need for pixel precision by tilting the advantage to the player.

Below is a ship from a shoot 'em up I'm making, the red square is the bounding box I'm using for collisions.

Image

Hm, doesn't want to show my image, use this link then:
http://nevyn.organ.su.se/ship.bmp
User avatar
Twilighte
Game master
Posts: 819
Joined: Sat Jan 07, 2006 12:07 am
Location: Luton, UK
Contact:

Post by Twilighte »

Thanks for that image link Igotafro. Tilting the balance by permitting part of the players ship to collide without collision is indead the way forward.
User avatar
Chema
Game master
Posts: 3014
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Post by Chema »

Igotafro wrote: Yes, that's frustrating, but you can avoid the need for pixel precision by tilting the advantage to the player.
Granted. This is a perfect kludge to make it easier in certain type of games. So if this is the case, then it is the way to go.

In fact in Space:1999 a "cubic" collision region is defined for every object and no pixel-precision is used (it would be a nightmare in 3D!).

However this might not work perfectly in other kind of games (I am thinking on a platform-like game for instance). In those cases some kind of pixel-precision routine should be used... and it shouldn't be difficult once the collision is detected at rectangle level, just check for mask overlap.

If your characters do have a "contour" this is done for free (nearly) as it can be done between your char mask and the currently rendered scene when drawing your moving char...

Anyway, if you are to handle a small ammount of objects (say <10) calling intersect_rect to check between your moving char and the rest can be done quickly, else you will need a method such as the one I described earlier (splitting the scene in regions).

For your records. In Space:1999 (again, sorry for being harassing) the engine (NOISE) has to check for intersections between all the objects and the area that should be redrawn when a character moves to see which objects should be rendered (in double-buffer, of course). And that process is NOT the reason for which it is quite slow... Well OK. I use a trick to check only some objects (those in "nearby tiles"), but still quite a lot in complex rooms.

Cheers.
Post Reply