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?
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