56

In honor of today's landing of and sample collection by the OSIRIS-REx spacecraft on the asteroid Bennu:

How did the arcade game Asteroids detect collisions between the screen objects (player's ship, asteroids, enemy saucers, shots) ? Was it a rectangular bounding box? Bounding circle? Intersection of line segments? Other?

asteroids screenshot

Improve this question
5
  • 3
    would be worth getting a peek at the disassembly computerarcheology.com/Arcade/Asteroids/Code.html
    – Jean-François Fabre
    Oct 21, 2020 at 7:44
  • Because the graphics are lines between defined points, and there are a fairly limited number of them, it's probably just iterating through all the lines and checking if the point that is the player's shot is on that line.
    – Alan B
    Oct 21, 2020 at 7:52
  • 6
    you can't do that because you could easily miss a segment by adding too many pixels to the shot at once, and also because it's too expensive for a poor 6502
    – Jean-François Fabre
    Oct 21, 2020 at 7:57
  • You could probably get line intersection checks nearly for free if the game would draw the lines in a conventional frame buffer. But it doesn't.
    – tofro
    Oct 21, 2020 at 8:46
  • 3
    I wish you didn't post that screenshot... now I must question what my level of productivity will be over the next week! ;) Asteroids is perhaps the best video game ever created.
    – End Anti-Semitic Hate
    Oct 21, 2020 at 17:52

1 Answer 1

Reset to default
58

it seems to be a simple bounding box check, as shown here from 6502 code disassembly, collision check between ship and saucer

HitDetShip:
L6A63:  CPX #$01                ;Is object 1 not the player's ship?
L6A65:  BCS HitDetSaucer        ;If not, branch.

L6A67:  ADC #$1C                ;Ship hit box 42+28 = 70 X 70 from center.

HitDetSaucer:
L6A69:  BNE CheckObjHit         ;Is object a saucer? If not, branch.

L6A6B:  ADC #$12                ;Small saucer hit box 42+18 = 60 X 60 from center.
L6A6D:  LDX ScrStatus           ;

L6A70:  DEX                     ;Is the object a small saucer?
L6A71:  BEQ HitDetFinishScr     ;If so, branch.

L6A73:  ADC #$12                ;Large saucer hit box 42+18+18 = 78 X 78 from center.

HitDetFinishScr:
L6A75:  LDX #$01                ;Reload object 1 as a saucer.

CheckObjHit:
L6A77:  CMP ObjXDiff            ;Is object 1 X difference smaller than the hit box?
L6A79:  BCC HitDetNextObj2_     ;If not, no hit detected. Branch to check next object.

L6A7B:  CMP ObjYDiff            ;Is object 1 Y difference smaller than the hit box?
L6A7D:  BCC HitDetNextObj2_     ;If not, no hit detected. Branch to check next object.

HitDetPart3:
L6A7F:  STA ObjHitBox           ;Store hit box value.
L6A81:  LSR                     ;/2.
L6A82:  CLC                     ;Add two hit box values together.
L6A83:  ADC ObjHitBox           ;Hit box value is now 1.5 X value set above, about sqrt(2).
L6A85:  STA ObjHitBox           ;This has the effect of making the hit box more circular.

L6A87:  LDA ObjYDiff            ;Add the two difference values together.
L6A89:  ADC ObjXDiff            ;If it causes a carry, The distance is too great.
L6A8B:  BCS HitDetNextObj2_     ;Branch to move to next object.

L6A8D:  CMP ObjHitBox           ;Is combined difference values grater than the hit box?
L6A8F:  BCS HitDetNextObj2_     ;If so, branch to move to the next object.

I suppose that any other collision check would be too expensive:

  • (square) distance computation needs multiplication. We know that it's not natively supported by 8-bit chips like 6502, and if implemented by software is extremely costly cycle-wise
  • segments collision need a lot more computation, also including multiplication
  • I thought that the game used a shadowed/logical screen that is updated in the background to perform quick lookups (ex: 0 for void, 1 for ship, 2 for saucer, 3 for asteroid), but that wasn't the case (this technique is good but consumes a lot of memory or you have to reduce accuracy, then you have to recompute logical X/Y from real X/Y and use bit/masks, so it's costly if you don't have the memory)
  • game has a vector hardware display, but you can't access to this buffer once drawn or check line intersections with this hardware.

So back to the old bounding box method. The trick is to make bounding boxes smaller than the actual displayed object. Players never complain about collision "bugs" when they get to survive because of them.

Notes: Sorry for my back-and-forth versions. I first thought that the game used bounding boxes (which was right), but relied on a code that used to compute relative positions of saucer/ship, so it was unrelated. Then I thought the game used a logical backbuffer but that would have cost too much in memory to have good accuracy, then back to square one, good old boxes

Improve this answer
7
  • 8
    For distance calculation with 8 bit values can easy be done with lookup tables, even faster than a bound check. I'd see the main point mentioned in the last paragraph. bounding box is simply good enough for the game. Classic KISS.
    – Raffzahn
    Oct 21, 2020 at 9:02
  • 1
    the game has lookup tables for angle / xspeed / yspeed, but not for distance apparently. pre-distance check is interesting when there are a lot of objects to check (which is the case in 3D games or scrollers) but a quick x or y distance check could eliminate far objects without having to compute squares, you're right
    – Jean-François Fabre
    Oct 21, 2020 at 9:14
  • 4
    You can compute distance with various approximations (see e.g. Battlezone's approach, explained near the bottom of this page), but distance fundamentally assumes a collision between circles, and most of the objects in Asteroids are more rounded-squarish. The player's ship is triangular and rotates, which isn't a good match for either shape, but if you move fast enough nobody will notice the approximation.
    – fadden
    Oct 21, 2020 at 14:56
  • 8
    Rob Fullup, the creator of Atari 2600 Missle Command, computed distance by taking the absolute value of delta x and y, and the absolute value of the difference, and then subtracting half of the latter difference from the sum of |dx| and |dy|. This yields skewed octagonal collision regions rather than circular, but that would seem a fine approach for a game like asteroids. BTW, I don't recognize anything in the above code as a collision check.
    – supercat
    Oct 21, 2020 at 16:15
  • @supercat: that's the BZ approach, though it uses 3/8ths rather than 1/2 to be closer to the original math. Might not have made a difference in MC given the coordinate range (256x231 pixels). Should be less expensive to compute that than performing bounding-box comparisons.
    – fadden
    Oct 21, 2020 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .