Gamedev Like it's 1977: CHIP-8

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Gamedev Like it's 1977: CHIP-8

Scaevolus: Apr 16, 2007

HottiePippen posted:

I think I'm misusing while loops, but I can't figure out what I'm doing wrong. Wondering if someone can spot it. I can do the following:

AFAIKT they should be the same, but they are behaving differently. Any idea what I'm doing wrong?

while loops don't work like C.

code:

loop
BLAH
while CONDITION
BAR
again

could be translated to

code:

while(1) {
  BLAH
  if (!CONDITION) break;
  BAR
}

# ¿ May 18, 2014 02:35

Adbot: ADBOT LOVES YOU

# ¿ May 10, 2024 10:04

Scaevolus: Apr 16, 2007

The previous version had min/max/mean/stddev statistics of 92/11261/777/757, so the extra rotation is a significant improvement.

The conjecture is that it's "random enough" for a Chip8 game, despite significant biases.

I tested it, but reversing a byte before doing the rotation has negligible impact on the distribution -- if you have a run of one bits in a byte, you'll still have that run after you reverse it.

Doing two extra rotation attempts improves the statistics to 588/1346/777/77.

Scaevolus fucked around with this message at 06:53 on Jun 27, 2014

# ¿ Jun 27, 2014 06:51

Scaevolus: Apr 16, 2007

I ported Mr Worm to SuperChip8.

# ¿ Aug 10, 2014 09:00

Scaevolus: Apr 16, 2007

Good catch! Updated with that fix.

The hardest part of writing this was the Queue implementation. Initially I was trying to do some insane dynamically growing circular queue structure and couldn't work out the kinks of increasing its size, then I realized I could just have a large fixed-size (256 byte) queue and rely on wrapping behavior.

Debugging Octo programs is pretty miserable. Simple debug printing with basic interpolation would help a lot. A command like:

:log "got $v0 out of queue. [$queuehead, $queuetail]"

Would log a message to an output buffer on the side of the screen as you play the game.

Maybe with a few conversion commands

code:

interpolation: $name[:conversion specifier]
conversion specifiers:
x -- print in hex
b -- print in binary
s -- print as signed decimal
d -- (default) print as unsigned decimal
\d+ -- for memory locations, print multiple bytes

so you could write things like :log "random bit permutation $perm:b" or :log "stack: size:$stacksize $stack:8x"

edit: did a bit more refactoring and cleanup

Scaevolus fucked around with this message at 00:24 on Aug 11, 2014

# ¿ Aug 11, 2014 00:00

Scaevolus: Apr 16, 2007

Internet Janitor asked me to do a petit-postmortem for Mr Worm.

My initial plan was to port one of the many TI-83 or TI-89 games to Chip8. Sighnoceros' shooter suggested Phoenix.

I did some experiments with smooth movement using xor-masked sprites. The trick to moving a sprite smoothly is to xor the sprite in the source and destination positions together. This is pretty easy to do in Paint.net -- make two layers, set the blend mode to 'XOR', draw the sprite in different colors on both of them, and move the layers around.

Here's the Phoenix ship on top, with the xor-mask for vertical movement below it:

The movement was pretty smooth, but porting the whole game was less exciting. Searching for another game that could use the smooth movement, I remembered Mr Worm:

https://www.youtube.com/watch?v=ONzSyj1HeFk

Snake, with 12 possible directions (the "o"s in the diagram, "x" is the center)

code:

 ooo
o   o
o x o
o   o
 ooo

Milestone 1: get the sprites and basic drawing/movement code done. This snake just wanders randomly until it hits itself.

Endless version

Milestone 2: get the tail working. The following logic is very wrong, so the game turns into a short lightcycle game with a bad AI where you always lose. The plan is a circular queue of past snake directions, so to erase the tail there's a 'second snake' that just duplicates the draw calls that the head made so many steps ago. In this version, the circular queue is of variable size, and there's a significant amount of complexity managing the concepts of queuelen/queuecap/queuehead/queuetail.

This took a while to debug:

Better:

Working

Milestone 3: a snake that grows when it eats things.

This is where things got hairy. The circular queue code worked, but it was written to only use 'queuecap' bytes -- the current maximum length of the tail.

The queue might be like this (where 6 is the last head position, and 0 is the tail that's following):

code:

4 5 6 0 1 2 3

Growing it, the queue needs to become something like:

code:

4 5 6 _ 0 1 2 3
(or)
0 1 2 3 4 5 6 _

This is annoying-- offsets needs to be juggled and memory copied, and Chip8 makes it harder. After banging my head against the wall for a few hours, I realized that the entire problem was irrelevant: there's no reason to constrain the queue to a minimal size in RAM. Once I realized this, I made the circular queue have a maximum size of 256 bytes. This eliminated the wraparound checks for queuehead/queuetail (since they'll overflow and wrap around naturally), and made growing the queue trivial.

Milestone 4: title, score.

Compared to the nightmare of attempting to get a dynamic queue working with no debugger, implementing the last few features to polish off the game was easy.

Scaevolus fucked around with this message at 06:41 on Aug 16, 2014

# ¿ Aug 16, 2014 06:34

Scaevolus: Apr 16, 2007

I got my Octo disassembler working on the 157 Chip8 binaries I found.

Here's BLINKY, a Pacman clone with very strange controls (A,S,3,E).

# ¿ Aug 17, 2014 22:40

Adbot: ADBOT LOVES YOU

# ¿ May 10, 2024 10:04

Scaevolus: Apr 16, 2007

The RLE method can work with better coding.

Taking the example high-complexity image, here's what the run-lengths are:
[5, 2, 64, 10, 47, 3, 6, 2, 3, 1, 2, 2, 31, 1, 8, 1, 7, 4, 4, 2, 2, 1, 3, 1, 29, 1, 1, 1, 7, 1, 11, 4, 2, 2, 1, 1, 3, 1, 28, 1, 1, 1, 6, 2, 15, 4, 2, 1, 3, 1, 27, 1, 1, 1, 6, 1, 1, 1, 2, 1, 4, 8, 5, 1, 3, 1, 27, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 10, 1, 15, 23, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 5, 1, 2, 2, 1, 13, 1, 24, 1, 2, 1, 3, 1, 2, 1, 1, 1, 2, 5, 1, 1, 3, 14, 25, 1, 2, 1, 3, 2, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 2, 11, 1, 3, 15, 1, 9, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 1, 2, 3, 7, 1, 1, 3, 15, 1, 9, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 7, 1, 1, 1, 1, 1, 15, 1, 8, 1, 4, 1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 13, 5, 6, 1, 4, 1, 1, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 14, 3, 7, 2, 3, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 15, 1, 8, 1, 5, 1, 2, 3, 1, 1, 2, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 15, 1, 7, 1, 6, 1, 3, 1, 2, 2, 5, 1, 1, 1, 3, 1, 1, 1, 1, 3, 2, 6, 14, 1, 7, 1, 4, 1, 1, 1, 4, 1, 1, 1, 6, 1, 1, 1, 3, 9, 6, 1, 13, 1, 7, 9, 3, 2, 7, 1, 1, 1, 3, 1, 4, 1, 3, 2, 5, 1, 12, 1, 11, 1, 2, 1, 5, 1, 7, 1, 1, 1, 3, 1, 3, 1, 1, 4, 1, 2, 4, 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, 3, 1, 2, 1, 3, 1, 3, 1, 1, 1, 3, 4, 9, 1, 4, 1, 10, 1, 7, 5, 1, 1, 5, 1, 1, 1, 6, 1, 1, 1, 3, 1, 7, 5, 1, 1, 4, 1, 9, 1, 2, 5, 4, 9, 8, 1, 1, 1, 4, 1, 12, 11, 2, 5, 9, 1, 4, 1, 2, 1, 7, 1, 2, 1, 4, 1, 17, 1, 1, 1, 3, 10, 6, 1, 4, 1, 2, 6, 1, 1, 3, 1, 4, 1, 18, 5, 6, 2, 2, 12, 5, 1, 2, 1, 4, 1, 4, 1, 17, 1, 2, 1, 8, 1, 1, 1, 12, 3, 3, 1, 2, 1, 3, 1, 6, 1, 15, 13, 3, 1, 14, 2, 1, 1, 3, 1, 2, 8, 14, 1, 2, 1, 9, 3, 1, 1, 16, 3, 2, 1, 23, 1, 2, 1, 10, 1, 2, 1, 15, 2, 3, 1, 2, 13, 9, 12, 2, 1, 2, 1, 15, 1, 21, 2, 19, 6, 16, 1, 5]

The number for each is total: 587 (1: 317, 2: 82, 3: 50, 4: 25, 5: 17, 6: 14, 7: 13, 9: 10, 15: 10, 8: 7, 10: 5, 12: 5, 13: 5, 14: 5, 11: 4, 16: 2, 17: 2, 23: 2, 27: 2, 18: 1, 19: 1, 21: 1, 24: 1, 25: 1, 28: 1, 29: 1, 31: 1, 47: 1, 64: 1)

Elias gamma coding encodes positive integers into a stream of bits, like so:

code:

Number          Encoding    Implied probability
1 = 2^0 + 0     1           1/2
2 = 2^1 + 0     010         1/8
3 = 2^1 + 1     011         1/8
4 = 2^2 + 0     00100       1/32
5 = 2^2 + 1     00101       1/32
6 = 2^2 + 2     00110       1/32
7 = 2^2 + 3     00111       1/32
8 = 2^3 + 0     0001000     1/128
9 = 2^3 + 1     0001001     1/128
10 = 2^3 + 2    0001010     1/128
11 = 2^3 + 3    0001011     1/128
12 = 2^3 + 4    0001100     1/128
13 = 2^3 + 5    0001101     1/128
14 = 2^3 + 6    0001110     1/128
15 = 2^3 + 7    0001111     1/128
16 = 2^4 + 0    000010000   1/512
17 = 2^4 + 1    000010001   1/512

Note how the probability closely matches the input distribution. After encoding, the image takes up 198B: 00101 010 0000001000000 0001010 00000101111 011 00110 010 011 1...

Interestingly, it does worse with vertical runs, since the probability distribution doesn't match as well. A different choice of universal code might fix this. (1: 288, 2: 111, 3: 46, 4: 28, 5: 18, 7: 11, 6: 10, 8: 10, 10: 8, 11: 8, 13: 7, 21: 7, 9: 6, 24: 5, 12: 4, 15: 3, 16: 2, 19: 2, 20: 2, 22: 2, 28: 2, 14: 1, 17: 1, 18: 1, 23: 1, 26: 1)

tl;dr:

code:

raw: 256

RLE + Elias-gamma coding:
simple-horiz: 121
simple-vert: 129
complex-horiz: 198
complex-vert: 208

Scaevolus fucked around with this message at 19:33 on Oct 5, 2014

# ¿ Oct 5, 2014 19:31

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Gamedev Like it's 1977: CHIP-8