Investigating genesis of horizontal div15 routine

[DEBRO]

We all know the VCS was designed to have two sprites, two missiles, a ball, and playfield graphics. This was ideal for producing games like Tank (i.e. Combat) and Pong.

The horizontal movement registers support this as well. Given you reset the player's horizontal position with a strobe to RESPx. Then during the vertical blanking period you can adjust the player's position by setting the HMPx register for fine motion between -7 and 8.

As the engineers looked to do more games it became apparent that they needed to account for more sprites on the screen.

In the Stella at 20 volume 2 episode, Larry Kaplan speaks of a breakthrough they had with changing the sprite graphics as you went down the screen. They mention this was first done with Air-Sea Battle. In Air-Sea Battle the screen was split into horizontal bands and they would repurpose the sprite as they entered different bands. This worked but you would also have to reposition these sprites based on their new horizontal positions.

Larry goes on to say that the next breakthrough came from Joe Decuir. Joe wrote a routine that would take the horizontal position of a sprite and calculate the coarse positioning value for the RESPx strobe and the fine motion value for the HMPx register. It has long been believed this routine was shown in Air-Sea Battle as...

CalcXPos
   sta tempXPosition                ; save off the x position
   bpl .determineCoarseValue
   cmp #XMAX                        ; make sure object not out of range
   bcc .determineCoarseValue        ; if not compute coarse value
   lda #0
   sta tempXPosition                ; set to min value
.determineCoarseValue
   lsr                              ; divide position by 16
   lsr
   lsr
   lsr
   tay                              ; save the quotient
   lda tempXPosition                ; get the object's x position
   and #$0F                         ; keep div16 remainder
   sty tempDiv16                    ; save div16 value
   clc
   adc tempXPosition                ; add back division by 16 remainder
   cmp #15
   bcc .skipSubtractions
   sbc #15                          ; subtract 15
   iny                              ; and increment coarse value
.skipSubtractions
   cmp #XMIN                        ; make sure hasn't gone pass min x value
   eor #$0F                         ; get 4-bit 1's complement for fine motion
   bcs .skipFineIncrement
   adc #1                           ; increment fine motion value
   dey                              ; reduce coarse value
.skipFineIncrement
   iny                              ; increment coarse value
   asl                              ; move fine motion value to upper nybble
   asl
   asl
   asl
   sta tempFineMotion               ; save it for later
   tya                              ; move coarse value to accumulator
   ora tempFineMotion               ; accumulator holds fine/coarse value
   rts

This routine works and can be seen in a number of early Atari and Activision titles. Even the homebrew community adopted this positioning routine early on with games produced in the late 90's and early 2000's until Manual Rotschkar made an astounding discovery while reverse engineering Battlezone.

The reverse engineering of Battlezone was the first time the homebrew community experienced the now standard routine of dividing the sprite's horizontal position by 15 for the RESPx strobe and using the remainder to adjust for the fine motion. This routine took less bytes than the positioning found in Air-Sea Battle and it could be used inside the kernel with could save RAM as well. This routine has a fine motion range of -6 to 8. I was working on my port of Climber 5 when this was discovered and quickly changed my code to use this routine for horizontal positioning. I have long been curious about the genesis and evolution of this routine since its discovery.

Another discovery came while I was working on Climber 5. During this time I started reverse engineering Garry Kitchen's Donkey Kong. This was to get an understanding of how he handled Mario's movement on the ladders. While reverse engineering Donkey Kong, I found Garry used a similar positioning routine found in Battlezone.

Garry has been interviewed before. He stated he learned to develop for the VCS by reverse engineering games using his Apple ][. Since Donkey Kong wasn't his first VCS game, I thought I'd take a look at his first published VCS game. Doing a reverse engineering of Space Jockey I saw the same horizontal positioning routine used in Donkey Kong. This would mean this routine had to have been introduced by Atari somewhere or Garry modified the routine found in Air-Sea Battle.

Doing a little more investigation, we know Atari had nine launch titles with the VCS. Here they are in alphabetical order...

• Air-Sea Battle

This one reuses sprites in horizontal bands. This has been long believed the first appearance of positioning sprites on the fly. It uses a horizontal positioning routine used by Atari and early Activision titles.

• Basic Math

This game doesn't use player sprites. All graphics are done using playfield graphics so no horizontal positioning is needed.

• Blackjack

The sprites are positioned once in preparation for the six digit display routine.

• Combat

The sprites have their horizontal position reset (i.e. RESPx) once. Then their position is adjusted during the vertical blanking period by setting their fine motion (i.e. HMPx).

• Indy 500

There is no sprite reuse in this game. The sprites are positioned similarly to Combat.

• Star Ship

This game reuses sprites. It uses the same routine found in Air-Sea Battle to determine the sprite's coarse and fine motion values.

• Street Racer

This is another game by Larry Kaplan that uses a routine similar to the one found in Air-Sea Battle. It's slightly different because it uses the value from the discharge of the paddle to determine the player's horizontal position.

• Surround

This uses a routine similar to the one found in Combat where the sprite's horizontal position is reset once and the position adjusted during the vertical blanking period by setting the fine motion value.

• Video Olympics

Joe Decuir is credited as the designer. This is the first appearance of the divide by 15 positioning for the launch games!

Is Video Olympics the real routine created by Joe Decuir both he and Larry speak of in Stella at 20? Is this the genesis of this divide by 15 routine?

The horizontal positioning used in Video Olympics is similar to the one discovered in Space Jockey with slight differences in the implementation but the outcome being the same. The Video Olympics routine does a 1's complement to the divide by 15 remainder, subtracts seven (the carry bit is clear), the result is then used for the fine motion adjustment giving a full -7 to 8 range.

;
; Horizontal reset starts at cycle 8 (i.e. pixel 24). The object's position is
; subtracted by 47 to push their pixel positioning to start at cycle 23 (i.e.
; pixel 69) with an fine adjustment of -7 to start objects at pixel 62.
;
MoveObjectHorizontally
   sec
   sbc #47
   ldy #2
.divideBy15
   iny
   sbc #15
   bcs .divideBy15
   eor #$FF                         ; get 1's complement of remainder
   sbc #7 - 1                       ; subtract value by 7 (i.e. carry clear)
   JMP_SWITCH_NYBBLES               ; move upper nybbles to lower and vice-versa
   sty WSYNC
.coarseMoveObject
   dey
   bpl .coarseMoveObject
   sta RESP0,x                      ; set object's coarse position
   sta HMP0,x                       ; set object's fine motion value
   rts

Space Jockey and Donkey Kong do a 4-bit 1's complement to the divide by 15 remainder. This is valid because the upper nybbles of the remainder are irrelevant to this routine. It then shifts the value to the upper nybbles for the fine motion adjustment and adds eight to the 4-bit 2's complement again giving a full -7 to 8 range for the fine motion. Example from Space Jockey...

HorizPositionObject
   sta WSYNC                  ; 3   wait for next scanline
   sec                        ; 2
.coarseMoveLoop
   sbc #15                    ; 2   divide position by 15
   bcs .coarseMoveLoop        ; 2³
   eor #15                    ; 2   4-bit 1's complement for fine motion
   asl                        ; 2   shift remainder to upper nybbles
   asl                        ; 2
   asl                        ; 2
   asl                        ; 2
   adc #(8 + 1) << 4          ; 2   increment 2's complement by 8 for full range
   sta RESP0,x                ; 4   set coarse position value
   sta WSYNC
;--------------------------------------
   sta HMP0,x                 ; 4   set fine motion value
   rts                        ; 6

[+nanochess]

Thanks for researching this. Interesting info!

[+Muddyfunster]

I don't pretend to understand half of this (the assembly bits at least), but this is really fascinating, thanks for posting this.

[Lillapojkenpåön]

Averybody that has the chronological knowledge of stuff like this should make similar posts, it's extremely interesting for newcomers so we can catch up.

The only other one I can think of is this http://atariage.com/forums/topic/210361-who-discovered-the-cycle-73-cycle-74-hmove/

If there's more I would like to know about them.