Determing FPS within another FPS .. How?

[DSMan195276]

I know I could set up individual frame counters for every object and skip, say, every 9th frame to achieve 85%. However, the original Pac-Man arcade machine had 16K of ROM and 2K of RAM and I can't imagine this was the procedure used with such limited space.

You got me too interested in this That said, 2K RAM is really a fair amount, I suspected they just used a counter, but it's actually much more interesting. Like you mentioned, I managed to find a dissassembled and commented copy of the Ms. Pac-Man code, you can see it here. It sounds like this and Pac-Man work basically the same, and this appears to be the important point. Thankfully I happen to be a bit familiar with z80 assembly:

Code: (Select All)

182f  2a484d    ld      hl,(#4d48)    ; load HL with speed for pacman in normal state (low bytes)
1832  29        add     hl,hl        ; double
1833  22484d    ld      (#4d48),hl    ; store result
1836  2a464d    ld      hl,(#4d46)    ; load HL with speed for pacman in normal state (high bytes)
1839  ed6a      adc     hl,hl        ; double with carry
183b  22464d    ld      (#4d46),hl    ; store result.  is it time for pacman to move?
183e  d0        ret     nc        ; no, return.  pacman will be idle this time.

183f  21484d    ld      hl,#4d48    ; yes, load HL with speed for pacman in normal state (low byte)
1842  34        inc     (hl)        ; increase by one

That code is a bit hard to read, but really all it's doing is shifting the combined 32-bit value in 4d46-4d49 one bit to the left, and if the last bit shifted out (the one shifting out the high part) was a 1 then Pac-Man moves. We also add one to the counter when that happens, basically turning the code into a rotation (so when we shift out a 1 bit, we tack a 1 onto the beginning).

Else-where in the code, that 4d46-4d49 value is preloaded with various bit patterns, and the pattern controls how often a bit is shifted out and thus how fast pac-man moves. Based on some other comments in that code, I think these are the 4 bit patterns for original Pac-Man:

Code: (Select All)

55555555 (16 ones, 80%)
6AD56AD5 (18 ones, 90%)
6D6D6D6D (20 ones, 100%)
6AD56AD5 (18 ones, 90%)

The bit patterns themselves do repeat but the ones and zeros are not always at the same interval, so consequently Pac-Man does not move perfectly smoothly. It does however explain the percentages, as it's all based on the number of one bits that will get shifted out. More ones getting shifted-out will make Pac-Man faster, and the fastest is 20 ones which makes the percentages work out.

The one thing I'm not sure on is how often that actually gets called, but it sounds like it's just once a frame. That leads to some odd speeds per second if you actually calculate it, since there's 60 frames a second but the bit pattern repeats every 32 frames. The 80% speed is 30 moves per second, the 100% speed is roughly 37.5.

[TerryRitchie]

For 85%, what if you do:
IF (2*frames) MOD 18 THEN ...

Would that work?

Whoa, as Pete said, +1

That produces some really weird results I need to investigate further. (2 * Frames) MOD 20, 18, and 9 all come out to 54FPS ?!?

Going in order from MOD 1 to MOD 20 you get:

0, 0, 40, 30, 48, 40, 52, 45, 54, 48, 55, 50, 56, 52, 56, 53, 57, 54, 57, 54

[TerryRitchie]

I know I could set up individual frame counters for every object and skip, say, every 9th frame to achieve 85%. However, the original Pac-Man arcade machine had 16K of ROM and 2K of RAM and I can't imagine this was the procedure used with such limited space.

You got me too interested in this That said, 2K RAM is really a fair amount, I suspected they just used a counter, but it's actually much more interesting. Like you mentioned, I managed to find a dissassembled and commented copy of the Ms. Pac-Man code, you can see it here. It sounds like this and Pac-Man work basically the same, and this appears to be the important point. Thankfully I happen to be a bit familiar with z80 assembly:

Code: (Select All)

182f  2a484d    ld      hl,(#4d48)    ; load HL with speed for pacman in normal state (low bytes)
1832  29        add     hl,hl        ; double
1833  22484d    ld      (#4d48),hl    ; store result
1836  2a464d    ld      hl,(#4d46)    ; load HL with speed for pacman in normal state (high bytes)
1839  ed6a      adc     hl,hl        ; double with carry
183b  22464d    ld      (#4d46),hl    ; store result.  is it time for pacman to move?
183e  d0        ret     nc        ; no, return.  pacman will be idle this time.

183f  21484d    ld      hl,#4d48    ; yes, load HL with speed for pacman in normal state (low byte)
1842  34        inc     (hl)        ; increase by one

That code is a bit hard to read, but really all it's doing is shifting the combined 32-bit value in 4d46-4d49 one bit to the left, and if the last bit shifted out (the one shifting out the high part) was a 1 then Pac-Man moves. We also add one to the counter when that happens, basically turning the code into a rotation (so when we shift out a 1 bit, we tack a 1 onto the beginning).

Else-where in the code, that 4d46-4d49 value is preloaded with various bit patterns, and the pattern controls how often a bit is shifted out and thus how fast pac-man moves. Based on some other comments in that code, I think these are the 4 bit patterns for original Pac-Man:

Code: (Select All)

55555555 (16 ones, 80%)
6AD56AD5 (18 ones, 90%)
6D6D6D6D (20 ones, 100%)
6AD56AD5 (18 ones, 90%)

The bit patterns themselves do repeat but the ones and zeros are not always at the same interval, so consequently Pac-Man does not move perfectly smoothly. It does however explain the percentages, as it's all based on the number of one bits that will get shifted out. More ones getting shifted-out will make Pac-Man faster, and the fastest is 20 ones which makes the percentages work out.

The one thing I'm not sure on is how often that actually gets called, but it sounds like it's just once a frame. That leads to some odd speeds per second if you actually calculate it, since there's 60 frames a second but the bit pattern repeats every 32 frames. The 80% speed is 30 moves per second, the 100% speed is roughly 37.5.

Well that's genius. Sort of like a punched paper tape roll. Move if no hole, don't move if a hole is seen. So they did use individual counters, just in a very unconventional but RAM conservative way. No need to involve the stack to get and maintain separate variables/values.

For some reason that number 37.5 rings a bell with me. I'm thinking it had something to do with the refresh rate of the old raster CGA monitors used in those arcade machines back then. According to the Pac-man Dossier the refresh rate of the game was 60.61Hz though. I've been assuming that meant the game ran at 60FPS. Perhaps that's the wrong assumption? Those coders back then would have had to sync their graphics with the video hardware ensuring to draw when the scan line was at the top left corner. Video cards do this automagically now or languages have built in commands to deal with this (_DISPLAY).

[TerryRitchie]

Ok, I just found an updated Pacman Dossier on the net. It states that: 100% speed = 75.75757625 pixels/sec

https://pacman.holenet.info/

Appendix A: Table A-1

Very close to 37.5 * 2

This in my mind is almost certainly due to having to program directly to the video hardware.

I'm probably not going to be able to achieve perfect pattern matching as I had hoped.

[Pete]

Maybe you should start with Ms. PacMan, first. She stops frequently to ask for directions.

Pete

[TerryRitchie]

Maybe you should start with Ms. PacMan, first. She stops frequently to ask for directions.

Pete

[Pete]

As always, glads to be of immenze technikel assisteeance to the solvation of compleecated izzues.

- Sam

[TerryRitchie]

I believe DSMan has solved the riddle of how the programmers did it. I started writing patterns down to see if I could store the frame counters into integers and lo and behold this pattern emerged:

Code: (Select All)

123456789012345678901234567890123456789012345678901234567890
------------------------------------------------------------
1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1   -24FPS(40%)  10010100101001010010 = 608850  = 94A52
1 1 1  1 1 1  1 1 1 1 1 1  1 1 1  1 1 1 1 1 1  1 1 1  1 1 1   -27FPS(45%)  10101001010100101010 = 693546  = A952A
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1   -30FPS(50%)  10101010101010101010 = 699050  = AAAAA
1 1 11 1 1 1 11 1 1 1 1 11 1 1 1 11 1 1 1 1 11 1 1 1 11 1 1   -33FPS(55%)  10101101010101101010 = 709994  = AD56A
11 1 1 11 11 1 1 11 11 1 1 11 11 1 1 11 11 1 1 11 11 1 1 11   -36FPS(60%)  11010101101101010110 = 875350  = D5B56
11 11 11 1 11 11 11 11 11 11 1 11 11 11 11 11 11 1 11 11 11   -39FPS(65%)  11011011010110110110 = 898486  = DB5B6
11 111 11 11 111 11 11 111 11 11 111 11 11 111 11 11 111 11   -42FPS(70%)  11011101101101110110 = 908150  = DDB76
111 111 111 111 111 111 111 111 111 111 111 111 111 111 111   -45FPS(75%)  11101110111011101110 = 978670  = EEEEE
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111   -48FPS(80%)  11110111101111011110 = 1014750 = F7BDE
111111 11111 111111 111111 11111 111111 111111 11111 111111   -51FPS(85%)  11111101111101111110 = 1040254 = FDF7E
111111111 111111111 111111111 111111111 111111111 111111111   -54FPS(90%)  11111111101111111110 = 1047550 = FFBFE
1111111111111111111 1111111111111111111 1111111111111111111   -57FPS(95%)  11111111111111111110 = 1048574 = FFFFE
111111111111111111111111111111111111111111111111111111111111  -60FPS(100%) 11111111111111111111 = 1048575 = FFFFF

The patterns repeat three times over a 60 frame span meaning I can store the patterns in 20bit integers. Not sure how the Pac-Man coders got them into even smaller 16bit integers?


Now its a simple task of counting frames and ANDing the counter to the desired frame rate value. Easy peasy.

Thanks DSMan for your work and help with this.

[TerryRitchie]

I believe DSMan has solved the riddle of how the programmers did it. I started writing patterns down to see if I could store the frame counters into integers and lo and behold this pattern emerged:

Code: (Select All)

123456789012345678901234567890123456789012345678901234567890
------------------------------------------------------------
1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1   -24FPS(40%)  10010100101001010010 = 608850  = 94A52
1 1 1  1 1 1  1 1 1 1 1 1  1 1 1  1 1 1 1 1 1  1 1 1  1 1 1   -27FPS(45%)  10101001010100101010 = 693546  = A952A
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1   -30FPS(50%)  10101010101010101010 = 699050  = AAAAA
1 1 11 1 1 1 11 1 1 1 1 11 1 1 1 11 1 1 1 1 11 1 1 1 11 1 1   -33FPS(55%)  10101101010101101010 = 709994  = AD56A
11 1 1 11 11 1 1 11 11 1 1 11 11 1 1 11 11 1 1 11 11 1 1 11   -36FPS(60%)  11010101101101010110 = 875350  = D5B56
11 11 11 1 11 11 11 11 11 11 1 11 11 11 11 11 11 1 11 11 11   -39FPS(65%)  11011011010110110110 = 898486  = DB5B6
11 111 11 11 111 11 11 111 11 11 111 11 11 111 11 11 111 11   -42FPS(70%)  11011101101101110110 = 908150  = DDB76
111 111 111 111 111 111 111 111 111 111 111 111 111 111 111   -45FPS(75%)  11101110111011101110 = 978670  = EEEEE
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111   -48FPS(80%)  11110111101111011110 = 1014750 = F7BDE
111111 11111 111111 111111 11111 111111 111111 11111 111111   -51FPS(85%)  11111101111101111110 = 1040254 = FDF7E
111111111 111111111 111111111 111111111 111111111 111111111   -54FPS(90%)  11111111101111111110 = 1047550 = FFBFE
1111111111111111111 1111111111111111111 1111111111111111111   -57FPS(95%)  11111111111111111110 = 1048574 = FFFFE
111111111111111111111111111111111111111111111111111111111111  -60FPS(100%) 11111111111111111111 = 1048575 = FFFFF

The patterns repeat three times over a 60 frame span meaning I can store the patterns in 20bit integers. Not sure how the Pac-Man coders got them into even smaller 16bit integers?


Now its a simple task of counting frames and ANDing the counter to the desired frame rate value. Easy peasy.

Thanks DSMan for your work and help with this.

This works fantastically! This is what I'm going to use from now on when assigning lower frame rates. This method gives me 5% of accuracy from 60FPS downward without using modulus division. Just simple ANDing is all that's needed. Much cleaner and faster.

[Pete]

You're quoting your own post? Seriously Terry, I'm super happy you came up with the solution you were looking for, but I'm also very concerned that in the process you may have gone completely schizophrenic. If so, bad news, because that would make you over qualified to be a Senator Elect from the state of Pennsylvania.

Pete

- Can't wait to see the Pacman clone.