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

«‹›3 »

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Once upon a time there was an extremely low-cost 8-bit computer called the COSMAC VIP. It was capable of basic video display, came with 2k of ram (expandable to 4k) and was programmed using a hex keypad. Here is a completely realistic and in no way staged presentation of how the VIP was used:

To save memory and ease programming, the VIP came with an interpreter for a very simple bytecode-based programming language called CHIP-8 which included rudimentary collision detection, sprite drawing, numeric display and memory management. In short, the bare minimum you need to write video games!

Chip8 has a 64x32 pixel monochrome display, a little less than 4k of shared program/data space (some of the VIP's low memory is reserved for the interpreter), a 16-level return stack, 16 general-purpose 8-bit registers (The 16th is used as a status flag by some instructions), a 16-button hex keypad (with a really goofy layout) and a "buzzer" which can make some unspecified noise.

Chip8 was lost to obscurity for some time after the death of the COSMAC VIP, but was revived during the 90s through interpreters that ran on HP graphing calculators, and over time interpreters have cropped up for virtually every computing platform. It's a fun and easy way to learn about assembly language, both due to the simplicity of the instruction set and the availability of convenient and interesting IO. Implementing a Chip8 interpreter is also a popular way of learning about emulators.

I've created this thread to gather discussion about Chip8 and serve as a repository for useful information. I think it would be a lot of fun to hold a Chip8-themed game jam- the platform has severe limitations, but they can serve as an excellent seed of creativity. Feel free to discuss Chip8 extensions like the SCHIP, too! If you've written your own Chip8 interpreter, link it and I will add it to the OP.

For my own part, I have recently worked with our own Scaevolus to develop a tiny web-based IDE called Octo that allows you to run Chip8 programs, share them and develop new ones using an assembler I designed. It's surprisingly easy to write complex Chip8 demos right from your browser:

http://johnearnest.github.io/Octo/index.html?gist=4c9fecd91afdb6163964

LINKS AND INFORMATION

Chip8 Information Resources:

http://www.chip8.com the best place to find existing chip8 games.
Mastering Chip-8, a good reference and description of the instruction set.
My own ramblings and examples of programming techniques.
A beginner's guide to using Octo.
An intermediate guide containing a step-by-step tutorial on making a game.

Goon Implementations:

Octo (Internet Janitor)
Chip8.NET (SupSuper)
SDL2 Chip8 Emulator (Floor Is Lava)

Homebrew Games and Programs:

Thom8s Was Alone by Jusion
F8Z by Internet Janitor
Minesweep8r by HottiePippen
Chip2048 by Lime
ChipWar by Internet Janitor
Outlaw by Internet Janitor
Cave Explorer by Internet Janitor
Space Defense by sighnoceros
Mr. Worm (SuperChip) by Scaevolus
Sw8 Copter (SuperChip) by Internet Janitor
RPS by System Logoff
Turnover '77 (SuperChip) by Dr. Stab
Cellular Automata Viewer by SharpenedSpoonv2

Development Tools:

Chasm-Asm, a simple assembler

Internet Janitor fucked around with this message at 05:44 on Aug 26, 2015

# ¿ May 16, 2014 17:49

Adbot: ADBOT LOVES YOU

# ¿ May 10, 2024 10:00

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

It's Friday night. Do you know where your RCA 1802 is?

http://johnearnest.github.io/Octo/index.html?gist=c770a15b0b068aaf762e

I've done a bunch of tinkering with various ways to achieve scrolling effects with sprites, and added my findings to my Chip8 programming techniques guide.

# ¿ May 17, 2014 03:13

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

taqueso: That's a good point. My example makes the (often erroneous) assumption that the actual game code takes a negligible or consistent amount of time to run. I'll rewrite that section.

I'm still figuring a lot of things out, so I hope that my notes there will improve in quality and thoroughness along with my tools. If anyone else notices a mistake or has a better approach than I describe feel free to point it out!

# ¿ May 17, 2014 20:20

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I've done some experimenting with using PWM sprite display to simulate additional colors, and things got a bit out of hand.

epilepsy warning:

I call it "Chipenstein 3D". It's still a little flaky but I think I can fine-tune the raycaster to behave better and add niceties like collision. It doesn't actually use very much memory but it should go without saying that this would be completely unusable at anything close to the speed of real hardware.

edit: http://johnearnest.github.io/Octo/index.html?gist=627c8632c41899595f41

Internet Janitor fucked around with this message at 04:04 on May 18, 2014

# ¿ May 18, 2014 02:29

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

HottiePippen posted:

but this seems broken:

: subroutine
i := memorylocation
i += vA
load v0
vA += 1
;

: routine
vA := 0
while vA != 4 subroutine
;

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

while is actually a keyword for breaking out of a loop�again structure. I'll see about adding an error message to the assembler to warn you about that. Here's an example of a loop using while from the readme:

code:

v0 := 0

# �

loop
    v0 += 1
    while v0 != 5

    # �

again

# ¿ May 18, 2014 02:34

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

As a minor heads-up I've made a number of improvements to Octo that should make it nicer to use:

You can now type tab characters in the editor.
If your program fails to compile, the offending token will be highlighted.
Mismatched control constructs (loop, while and again) should now be identified as errors rather than silently producing weird behavior.
If a program fails to compile, clicking "run" will no longer obscure the error message and then run the last working version.

I hope this makes playing with it less frustrating and error prone.

# ¿ May 21, 2014 03:43

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

taqueso: Sure thing. I've added named numeric constants along with another requested feature, register aliases. To quote the updated manual:

quote:

Numeric constants can be defined with :const followed by a name and then a value, which may be a number, another constant or a (non forward-declared) label. Registers may be given named aliases with :alias followed by a name and then a register. The i register may not be given an alias, but v registers can be given as many aliases as desired. Here are some examples of constants and aliases:
code:
:alias x v0
:alias CARRY_FLAG vF
:const iterations 16
:const sprite-height 9

# ¿ May 21, 2014 15:29

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Lime: Your game is really neat- I'm glad you're enjoying chip8 programming! I'll think about your syntax suggestion, but the approach that taqueso suggests is how programmers normally distinguish between "phrases" of instructions together in Forth, which was the inspiration for some of Octo's syntax.

I've made a few more small improvements to the tools:

The sprite editor can now parse all the number formats Octo uses, so you can paste binary or decimal representations in and modify them. Modified output is still always in hex for the sake of compactness.
The sprite editor has been integrated with Octo itself for more convenient use. The "Sprite Editor" button toggles it.
In case you're getting tired of my amber and brown scheme, colors used to display your game can now be customized, as well as the background colors used for silence or a buzzer. These color choices are reflected in the sprite editor and will be saved when you share your programs. Colors can use any format that works in HTML/CSS.

I've also started doing some tinkering with data structures in Chip8. As some of you may have noticed, memory access is very strange and doing anything more complex than saving and restoring a chunk of the register file or indexing into a simple table can get kinda awkward. It's very important to remember that doing a load or store operation adds N+1 to the i register where N is the register index you're loading or saving "up to". Most of the time this is not particularly helpful behavior, and even less helpful is the fact that you can't subtract from i. I took two stabs at writing a modular stack.

In this first implementation I took a fairly straightforward approach using a static storage array and an index. Since in theory these might be called in a complex program I trash only v0 and vF (and of course i) and avoid touching any other registers. vF is pretty much always a good candidate for temporary storage because it's so easily blown away and would not be used for storing persistent state. Push takes 11 cycles and pop takes 8 (not counting the inevitable overhead of a call and return):

http://johnearnest.github.io/Octo/index.html?gist=69b4c6b775f8046c1106

In my second implementation I decided to try using load and save to shift whole chunks of memory at once. This approach is limited, since we can only support a very small stack that fits in available registers, but if we could afford to trash low registers it is significantly faster- Push is 7 cycles and pop is 5. If we have to preserve register contents it's slower at 11/9 respectively. It also has the benefit of preserving v0, though, so it should be usable in nearly any reasonable context:

http://johnearnest.github.io/Octo/index.html?gist=d751c7096b2cfb935157

Scaevolus managed to come up with a slightly better version of my first program by using some really heinous self-modifying code, but I'll let him talk about that if he wants. Can you guys come up with any better approaches? Perhaps a different puzzle?

# ¿ May 25, 2014 03:49

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Today I decided to do some more tinkering with Chip8 and explore a problem which is at the heart of a number of types of puzzle and strategy games. Given N objects, how do we randomly distribute them over M locations without placing any two at the same location? For example, consider the placement of mines in a game of Minesweeper. There are two common approaches for solving this problem: Guess-and-check or Shuffling.

Consider the locations as an array of booleans initialized to false, which we set to true when we place an object. To Guess-and-check we'll simply choose a random index to place our object, and if that space is occupied, choose another random index. We're done when we've found unoccupied locations for every object.

Java code:

boolean[] locations = new boolean[M];
int objects = N;
while(objects > 0) {
	int index = random(M);
	if (locations[index]) { continue; }
	locations[index] = true;
	objects--;
}

This approach works well if M is significantly larger than N, because we'll always have a wide range of available locations to select. If this is not the case, we may spend quite a bit of time trying and retrying invalid indices. If the random number generator gave us bad choices repeatedly this algorithm might not ever finish!

Another approach is to initialize our destination with the objects we want to place in any positions and then shuffle the items. The most well-known algorithm for a fair in-place shuffle is Fisher�Yates shuffle:

Java code:

boolean[] locations = new boolean[M];
int objects = N;
// distribute the objects:
while(objects --> 0) {
	locations[objects] = true;
}

// perform a shuffle:
for(int i = M-1; i >= 1; i--) {
	int j = random(i);
	boolean t = objects[i];
	objects[i] = objects[j];
	objects[j] = t;
}

Now let's consider how we could do something like this on a Chip8. Since memory operations are a pain, it would be nice to work with bit vectors in registers. The problem now becomes how we can generate a random M-bit number with exactly N bits set. Guess-and-check could work here, but is somewhat undesirable for the reasons I stated earlier. The Fisher-Yates shuffle is also rather difficult to translate since it requires in a large number of bitshifts and the generation of random numbers which are not in a power-of-two range. Since we're working on a game, it may be acceptable to generate bit vectors with distributions which are not completely fair or to consider algorithms which cannot produce every possible bit vector.

The simplest non-fair, non-exhaustive approach is to pre-generate a lookup table with a selection of suitable bit vectors. Here's a table with 32 of the 60 possible 8-bit vectors containing 4 set bits and appropriate code for fetching one into v0:

code:

: bit-vectors
	0xCC 0x39 0x53 0x78 0xF0 0xB1 0x93 0xD8
	0xA9 0x1D 0x55 0xC3 0x3C 0x8D 0xE2 0x63
	0x87 0x56 0xAC 0x27 0x4E 0x36 0x72 0x5C
	0x4D 0x1B 0x0F 0xE4 0xA3 0x5A 0x95 0x2B

: get-vector
	v0 := random 0b11111
	i  := bit-vectors
	i  += v0
	load v0
;

After quite a bit of discussion and experimentation, Scaevolus and I managed to come up with a fairly simple algorithm which can generate any 16-bit permutation with N bits set. Guess-and-check can be modified to complete reliably by choosing a random bit to set, and if it's already set, setting the next 0 bit after it. This works but produces a very biased distribution in which numbers like 0b1111111100000000 are much more likely than 0b010101010101. We can partially compensate for this by picking a second index if our first try has a collision.

For each of the N bits we rotate our bit vector by a random number of bits if the least significant bit is 1. Then we bitwise OR the vector with itself plus one. This has the effect of setting the least significant 0 bit in the bit vector. Then we rotate the vector a second time.

code:

# rotate the output vector
# by a random number of places:
: rotate-random
	v3 := random 0b1111
	loop
		# rotate the 16 bits in v1 and v0
		# using v4 as a temporary:
		v0 <<= v0
		v4 :=  vf
		v1 <<= v1
		v0 |=  vf
		v1 |=  v4

		# repeat random number of times:
		v3 += -1
		if v3 != 0 then
	again
;

# generate a random permutation of
# 16 bits, with N of those bits set:
: permute-bits
	v0 := 0 # output (hi)
	v1 := 0 # output (lo)
	v2 := 8 # loop counter (N)
	        # trash v3, v4
	loop
		# rotate if the LSB of output is set,
		# to avoid creating runs of 1s:
		v3 >>= v1
		if vf != 0 then rotate-random

		# OR output vector with itself + 1
		# to set the least significant 0:
		v3 := v0
		v4 := 1
		v4 += v1
		v3 += vf
		v0 |= v3
		v1 |= v4
	
		# rotate again, to avoid always having
		# 1 as the least significant bit:
		rotate-random

		# repeat N times
		v2 += -1
		if v2 != 0 then
	again
;

Note the trick we use for testing the least significant bit of v1- shift into a temporary register and consult vf. You can use the same approach for testing the most significant bit if you use a left shift instead of a right shift.

Here is a gist containing the tests Scaevolus wrote to evaluate how well-distributed the results of the algorithm are:
https://gist.github.com/rmmh/6a56c0b3dd986605459a

Thoughts? Any other approaches to the problem?

# ¿ Jun 26, 2014 06:33

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Last week I visited some friends and we did a little Chip8 game jam. My game was a (loose) adaptation of the classic Dice Wars:

http://johnearnest.github.io/Octo/index.html?gist=1b254e9ee3e44c10604f

This game takes place on a toroidal field of 16 territories. Each has some number of troops stationed there (1-5). At the beginning of the game, territories are divided between you (white) and an AI opponent (black).

You can order your territories to attack adjacent enemy territories provided you have more than one troop available. When you attack, a number of 8-sided dice will be rolled and summed based on the number of attackers and defenders. If the attackers win, they capture the territory and transfer all but one of their troops over. If the defenders win, they destroy all but one of the attackers and lose one troop, or none if they have only a single troop.

After white has taken a turn, each territory has a 50% chance of producing one new troop. The game ends when black or white has conquered the entire map.

When selecting a territory, ASWD move your cursor, E selects the territory and Q ends your turn. With a territory selected, ASWD choose the direction in which to attack, E confirms the attack and Q cancels. When the game is over press any key to play again.

One of my goals was to write a game which could run playably at a speed that is plausible for real hardware. A strategy game seemed like a natural choice, since I can get away with only redrawing small portions of the display most of the time. ChipWar is fairly elaborate but I'm still using less than half of the available RAM!

Along the way I also added a new set of features to Octo- pseudo-ops for <, >, <= and >=. Ordinarily when doing these sort of comparisons you'd use subtraction and consult the borrow bit:

code:

# is v0 < v1 ?
ve := v1 # ve is a temporary copy so we don't destroy v1
ve =- v0
if vf != 0 then ...

I found it very easy to get these kinds of checks subtly wrong, so for the sake of clarity you can now write the above as:

code:

if v0 < v1 then ...

This emits precisely the same machine code as the above example. Doing these comparisons requires a temporary register aside from vf, so by convention I use ve. It is possible to instruct Octo to use a different temporary register by defining a register alias called compare-temp. A test program demonstrating the new operators can be found here:
https://raw.githubusercontent.com/JohnEarnest/Octo/gh-pages/examples/testcompare.8o

Internet Janitor fucked around with this message at 21:54 on Jul 6, 2014

# ¿ Jul 6, 2014 21:32

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I did a little tinkering with text display. Chip8 has a built-in hex character set, but if we want to display arbitrary text we'll need to supply a font from scratch. 4x5 characters separated by a pixel of padding work pretty well- they allow us to display 5 rows of 12 reasonably legible characters with a few margin pixels left over to play with.

The most straightforward way to store this data would be a linear array of 5-byte chunks, so the alphabet and three punctuation characters will take 145 bytes. We could then convert a character index into an i-address as follows, assuming font is a label with our font data and v0 contains the character index we're interested in:

code:

i  :=  font
i  +=  v0
v0 <<= v0
v0 <<= v0
i  +=  v0

Multiplying by 5 like this is a little clumsy, though. We could eliminate it if we stored our strings as a list of pre-multiplied offsets into the font data. This presents an interesting possibility: if our offsets aren't restricted to simple multiples of 5 we could save some memory by partially overlapping sequential characters in the font. I wrote a simple program which compresses a font in this manner and converts a string into the necessary list of offsets. For the font I drew, applying this technique saved 33 bytes. Observe the raw font in blue, and the overlapped font in red:

And here's a demonstration of using the data in a program:

http://johnearnest.github.io/Octo/index.html?gist=fc20634c9f53d6929c87

This technique of overlapping sprite data can be very useful if you need to squeeze out a few bytes, and in fact the original Chip8 interpreter did this with its hex font data.

Internet Janitor fucked around with this message at 19:12 on Jul 12, 2014

# ¿ Jul 12, 2014 19:06

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Minor note: I corrected an error in the subtraction opcodes of my interpreter. I've updated all the affected example programs. Jusion's "Thom8s Was Alone" was broken by this fix, so I repaired it. The version linked in the OP should work now.

# ¿ Jul 17, 2014 03:24

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I wrote a recreation of the Atari 2600 classic, Outlaw:

Not bad for 512 bytes, hunh? Play it here, or if you'd prefer you can learn about it in tutorial form.

# ¿ Jul 17, 2014 23:06

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

This afternoon I put the finishing touches on a Chip8 adventure game.

http://johnearnest.github.io/Octo/index.html?gist=a1d72c7bbf65520fd20d
Traverse a sprawling 16-screen overworld, solve puzzles, move crates around and, with a little luck, watch an incredible ending sequence! Move with ASWD, and in platformer levels use E to pick up/drop crates and Q to reset the level.

Do you have what it takes to be a Cave Explorer?

If there's interest I could talk about some of the techniques I used to write this game.

# ¿ Jul 22, 2014 23:33

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

OK, then. Sometimes I'm not sure whether I'm just rambling to myself!

The title sequence is made using several full-screen bitmap images. In earlier games I've constructed images by carefully splitting them apart into 8x15 chunks, but this is clumsy and artistically limiting. Instead, I simply wrote a small program to process 1-bit images and convert them into a sequence of hex literals I can paste into Octo. The drawing routine that consumes them looks like this:

code:

: draw-bitmap
	clear
	v0 := 0 # x
	v1 := 0 # y
	v2 := 0 # byte
	v3 := 1 # constant
	loop
		sprite v0 v1 1
		i  += v3
		v2 += 1
		v0 += 8
		if v0 == 64 then v1 += 1
		if v0 == 64 then v0 := 0
		if v1 != 32 then
	again
;

Since I don't have to do any load or store operations in the loop, I can just steadily increment i. Each byte is drawn as an 8x1 sprite, with 8 such sprites per row. I liked the vertical wipe animation this approach produces, but if I wanted to draw as fast as possible I would probably rearrange the data so that I can draw columns as 2 8x15 slices and an 8x2 slice (if necessary), or for maximum uniformity draw columns of 8x8 tiles. It's possible to produce a variety of simple transition effects by drawing portions of the screen in different orders.

Note that bitmaps like this are expensive! A single 32x64 pixel image will take up more than 1/16th your total supply of RAM. Since I only display the title sequence once at the beginning of the game, I reused that memory for scratch buffers in the main game engine. The platformer sequences modify level data in-place, but I need to be able to reset levels if the player makes a mistake. Thus, I start by making a copy of the level data, overwriting part of the title sequence:

code:

: copy-level
	v8 := 0
	loop
		# set i to base of current level
		...
		i += v8
		load v7

		i := level-buffer # overlaid with 'title2'
		i += v8
		save v7

		v8 += 8
		if v8 != 32 then
	again
;

The first time I wrote this routine it was unpleasantly slow, but there was an easy way to speed it up- using load and store to do block copies through the 8 lowest registers. If we're going to put up with the oddities of Chip8 memory operations at least we can find places they actually work to our advantage from time to time! Incidentally if we harness this and the fact that load and store increment i automatically we can write a very tight loop for initializing memory:

code:

: zero-buffer
	i  := buffer
	v8 := 0
	loop
		save v7 # 'stamp' with v0-v7
		v8 += 8
		if v8 != BUFFER_SIZE then # assume the size is a multiple of 8
	again
;

Finally, I used a rather unsavory trick for my text-drawing routine. The string data indexes into the sprite data (for compactness), so I have to juggle i between two locations. i can't be backed up and won't fit in a V-register, so we're stuck. Or are we?

code:

: draw-text
	v1 := 2 # x
	v2 := 1 # y
	v3 := 0 # byte
	# v4 contains length
	loop
		: text-addr i := 0 # self-modify to alter
		i += v3
		load v0
		i := font
		i += v0
		sprite v1 v2 5
		v1 += 5
		if v1 == 62 then v2 += 6
		if v1 == 62 then v1 := 2
		v3 += 1
		if v3 != v4 then
	again
;

Code to call this routine looks like this:

code:

	v0 := 0xA3
	v1 := 0x78
	i  := text-addr
	save v1
	v4 := 19
	draw-text

I stuff the halves of an "i := XXX" instruction into v0 and v1 and clobber those two words of the routine's code before calling it. Remember, folks- the only difference between machine code and a data structure is your frame of mind. Calculating these constant payloads by hand is a bit tedious and I may look into providing Octo with some syntactic sugar.

Most of the rest of the game implementation is fairly mundane. Like with the bitmap images and string/font preparation I discussed earlier I made use of a number of small utility programs to prepare data for consumption by the game engine. Overworld boards were drawn as bitmaps like this (blown up 4x):

And then converted into a sequence of bytes representing columns of 8 4x4 passable or impassable tiles:

code:

: board0
	0x28 0xEB 0x0A 0x7A 0x02 0xEF 0x28 0x2A 
	0x6A 0x4A 0x5A 0x42 0x7A 0x0A 0x6E 0x28

A series of 4 tables keep track of which board is adjacent in each cardinal direction from the current one. Here's what the whole game map might look like if it was mashed together onto a grid sequentially:

Hopefully that provides some interesting food for thought. I'd love to hear any questions or comments.

# ¿ Jul 23, 2014 01:37

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Just in case anyone isn't already familiar, the game is based on my favorite Perry Bible Fellowship strip, of the same name: http://pbfcomics.com/172/

# ¿ Jul 23, 2014 03:47

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I mentioned the use of self-modifying code to perform address indirection in Cave Explorer. This seems to be a fairly common idiom and comes up in a number of Chip8 roms out in the wild.

An unpleasant side-effect of this was the need to hardcode fixed addresses into the machine code I stored in registers. Octo now has a feature which makes this more elegant, and all the docs have been updated to reflect it.

To quote the revised Octo manual:

quote:

Sometimes you may wish to have the 12-bit address represented by a label available in v registers. Octo provides a command called :unpack for this purpose which expands into a pair of register assignment opcodes. It takes a nybble (0-15 numeric literal or constant) followed by a label as arguments. The lower 8 bits of the address will be stored in v1 and the upper 4 bits of the address will be bitwise ORed with the specified nybble shifted left 4 bits and stored in v0. If the label cucumber represented the address 0x582, the following sets of statements would be identical in meaning:
code:
v0 := 0xA5
v1 := 0x82
code:
:unpack 0xA cucumber
This operation makes it possible to write self-modifying code without hardcoding addresses as numeric literals. If you wish to unpack addresses into registers other than v0 and v1 you can define aliases called unpack-hi or unpack-lo, respectively.

In the future I'll see if I can come up with demonstrations of other fun tricks this feature makes more convenient.

# ¿ Jul 24, 2014 05:05

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

More features today. I've extended Octo with the ability to emit and emulate SuperChip instructions. These are a set of extensions to the basic Chip8 instruction set introduced when Chip8 emulators were ported to the HP-48 calculator. They are mainly composed of new graphics instructions, including a high-res (comparatively) 128x64 pixel display mode, the ability to draw 16x16 sprites and the ability to scroll the display horizontally or down (although oddly not up). Good documentation for SuperChip is difficult to come by, so don't be surprised if I'm finding mistakes for the next few weeks.

Another major consideration I've addressed is creating some "quirks-mode" compatibility settings. There are a number of chip8 instruction set guides available online containing errors, particulary in the discussion of how load and store alter i and how the shift instructions work. It's basically intractable now as there are countless emulators and programs which depend on one or the other of these behaviors. Octo uses the most authoritative interpretations to the best of my knowledge (backed up by the original documentation and disassemblies of the original interpreter), but you can now configure Octo to use the alternatives via the "Options" pane. These settings are preserved if you "share" your program, although I do not personally recommend writing new programs which depend on the incorrect behavior. Octo is now capable of successfully running a number of previously troublesome games. If you find a game that doesn't work, please try to track down the source of the problem so that I can make corrections or add more quirks-mode settings as necessary.

# ¿ Jul 26, 2014 03:37

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

A little experiment:

http://johnearnest.github.io/Octo/index.html?gist=0c7895a9a51f68ae1700

I'm not sure I'll have enough memory to do anything interesting with it, though. 16x16 tiles chew through my budget pretty fast.

# ¿ Jul 27, 2014 18:05

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

On the COSMAC VIP programs were loaded into ram by painful hand-entry or from a cassette tape. If you're asking whether a game could dynamically load extra resources at runtime, it would have been possible by using RCA 1802 machinecode, but Chip8 itself has no facilities for this. When a Chip8 interpreter was written for the HP-48 graphing calculator the "superchip" instructions were introduced, and among them were some instructions that let you alter the HP-48's status flags, which served various purposes. There were 64 of these boolean flags, so you could persist 8 Chip8 registers worth of data. Right now Octo emulates those instructions and persists those 64 bits of data between runs but if anyone wanted I suppose I could stash them longer-term in browser cookies.

# ¿ Jul 30, 2014 03:21

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Problem being that virtually no Chip8 interpreters, Octo included, actually emulate the RCA 1802, and none that I am aware of go the additional step of emulating the COSMAC VIP peripherals to any meaningful extent. Even if that was done, the VIP didn't have any sort of random-access persistent memory- the cassette interface required a human to hit play, rewind and record. I wouldn't recommend overloading the behavior of the SuperChip flag variables, especially given that I haven't even managed to find example programs which make use of them.

If you wanted to provide Chip8 with your own set of extended instructions (like SuperChip) to expand addressable RAM somehow or add new IO devices, the following gaps exist in instruction ranges:

0x0NNN is reserved for machine code subroutine jumps. Several instructions exist in this range, but there are small usable gaps. Retaining full legacy compatibility will require careful examination of the original Chip8 disassembly to ensure you're branching into memory that couldn't possibly have stored meaningful code. Superchip uses a few of these for toggling high-res mode.
0x5XYN where N is not 0 is unused. 0 in that position maps to "skip if vX == vY", so this might be a good place for new branch instructions.
0x8XYN where N is 8, 9, A, B, C or D. The other instructions in this family are arithmetic ops.
0x9XYN where N is not 0 is unused. Same deal as 0x5XYN, except when N is 0 it's "skip if vX != vY".
0xEXNN. Most of these are available. 9E and A1 are used for the keypad-test conditional skips.
0xFXNN. Again, most of these are available. Used slots include BCD decoding, the hex character set and interacting with timers. SuperChip uses a swath of these for scrolling instructions.

If it sounds like fun, feel free to fork Octo and add your own instructions.

Personally, I'm more interested in exploring the space of interesting programs that fit inside the existing resource limits. As I mentioned earlier when I discussed compatibility modes my research has found that the Chip8 universe is already distressingly balkanized and littered with mutually incompatible interpretations of behavior. The maintainer of Chip8.com has fashioned his own set of extensions to the Chip8 called MegaChip, but there are scant documents, programs or tools for it, and few signs of life.

Internet Janitor fucked around with this message at 23:53 on Jul 31, 2014

# ¿ Jul 31, 2014 23:48

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

That's really cool, Scaevolus- I particularly like the trick you use with worm-dirtab to load offsets and then have i left at just the right place for the necessary sprite data. Very playable, even at 15 cycles/frame. When I was testing at one point the high score value seemed to display wrong but I can't reproduce it and and I don't see anything obviously wrong in the code.

# ¿ Aug 10, 2014 17:27

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Miserable, eh? That simply will not do.

For starters I've equipped Octo with a register monitor and breakpoints. Pressing the 'i' key will interrupt a running program, 'o' will single-step a paused program and 'i' again will resume execution. You get a register dump like this which uses the compiler's symbol tables to display register aliases, guessed labels and an inferred stack trace:

You can also insert breakpoints in your code with :breakpoint <name> which will automatically pause execution when they are encountered- the name is displayed at the top of the register monitor so you can easily identify which breakpoint you stopped on. Breakpoints do not inject any instructions into the actual program so an exported ROM shouldn't interfere with any other Chip8 interpreter.

I will continue to think about debugging tools and I may add more later such as Scaevolus' suggestion for a debug log or possibly watch points, but hopefully the features I've added already will prove helpful.

# ¿ Aug 12, 2014 20:09

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Scaevolus: The "endless" version of your first milestone is mesmerizing. I wonder if you could use something similar to generate random cave systems or something.

While I was on vacation last week I spent some time tinkering with my own disassembler written in Javascript. Debugging it has not been a particularly fun exercise, but my labors have paid off:

This replaces the previous functionality of the "Load Binary" button. The static analysis I perform uses a technique I'm calling "value smearing". I walk the program graph propagating every value that every register could assume and simulating the postconditions of every instruction until I reach a fixed point. Some postconditions are simulated using a "loose-bound"- for example, when I encounter a vx := key instruction I assume that any key could have been pressed. As you might imagine, this is fairly expensive and only feasible due to the limited memory and small registers of the Chip8. As I say in the disclaimer, it's still slow and flaky, but for many programs it manages to come up with something sensible. Consider it a work in progress and don't be surprised if it screws up.

One interesting thing I've discovered so far is that many programs (such as Brix.ch8) seem to pad their sprite data with an extra 0x00 that is never accessed. I'm not sure what to make of this- perhaps some chip8 implementations drew n+1 rows for a sprite of size n, or maybe some early chip8 assemblers attempted to keep data in 2-word aligned chunks?

# ¿ Aug 20, 2014 06:18

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

In other news, while prowling for new Chip8 roms online I found this.

Using my disassembler I analyzed the program and gradually teased it apart. As it happens, the emulator has some bugs which are masked by complementary bugs in the game. I managed to get it working in Octo by modifying two bytes and along the way I identified a few other possible issues. It was a bit frustrating to reverse-engineer but along the way I made some improvements to my disassembler. Here's the cleaned-up Octo source:

http://johnearnest.github.io/Octo/index.html?gist=35e180cece89ed4d918f

Pressing E "flaps". I shouldn't have to explain anything else.

# ¿ Aug 21, 2014 03:14

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

This morning I put together a CLI frontend for Octo using Node.js:

code:

ij@red$ ./octo
usage: octo [--decompile] [--roundtrip] [--qshift] [--qloadstore] <source> [<destination>]

ij@red$ cat simple.8o
: main
	va := 1
	vb := 2

ij@red$ ./octo simple.8o simple.ch8
ij@red$ hexdump simple.ch8
0000000 6a 01 6b 02                                    
0000004

This should make testing easier and additionally make it more convenient to use Octo in the development of other emulators.

# ¿ Aug 24, 2014 16:43

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I've been thinking about this for a while and I've come to a decision- I've deprecated :proto.

Originally, Octo required an explicit prototype declaration before the use of any unstructured forward reference. The idea behind this was that programs could be read in order and understood without jumping around. In many situations you can adhere to this convention without creating any overhead, but occasionally a forward reference is the most efficient way to program something. By making the "reading order" approach the path of least resistance and making forward references less convenient I thought it would guide users toward a good style.

Having used the language extensively and worked with a number of beginners one-on-one I think this approach is ultimately just confusing and clunky for the vast majority of the people who encounter it. Very few existing languages have restrictions like this. Consider it a failed experiment.

Existing programs which use :proto will still work, but the statement no longer has any effect. You can now freely reference any label from anywhere in the program without making declarations first just like an ordinary assembler. I've updated all the documentation and examples.

# ¿ Aug 25, 2014 18:01

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I have been slowly working to improve the quality of Octo's disassembler and sifting through my corpus of binaries. A number of very old Chip8 programs contain RCA 1802 machine code embedded in them, so to better understand these programs I have added a crude prettyprinter for this instruction encoding. Here's an excerpt from disassembled output of a "clock program" to demonstrate:

code:

...
: sub-0
	v8 := 7
	i := label-9
	sprite v7 v8 7
	v7 += 1
	return

: machine-1
	0xF8 0xFA      # 0x2D8 : LDI  0xFA
	0xAF           # 0x2DA : PLO  F
	0x2F           # 0x2DB : DEC  F
	0x8F           # 0x2DC : GLO  F
	0x3A 0xDB      # 0x2DD : BNZ  0xDB
	0xD4           # 0x2DF : SEP  4

: label-9
	0xFC
	0xFC
	0xFC
...

Better than staring at raw hex bytes, at least! This chunk of code appears to be a timing loop. It loads the value 0xFA into a register loops, decrementing this register until it is zero. The SEP instruction performs a context switch back into the Chip8 program.

Octo is not presently capable of executing a program like this, but the compiler and decompiler can now be used for studying them. If anyone else is interested in reverse-engineering I invite you to poke around with some of the known "hybrid" binaries and see what you can find. The memory and register maps provided in the COSMAC VIP Manual and this primer on RCA 1802 assembly language should be useful.

Internet Janitor fucked around with this message at 19:21 on Aug 27, 2014

# ¿ Aug 27, 2014 19:17

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

http://johnearnest.github.io/Octo/index.html?gist=6e934bfd418bd2efeb16

I guess I'm not feeling very creative today.

# ¿ Sep 2, 2014 21:33

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Time for another effortpost, even if I am just talking to myself.

Sorting is one of the most fundamental classes of bread-and-butter algorithms in Computer Science. Implementing a sorting algorithm on the Chip8 has some interesting challenges. Registers are plentiful, Memory access is cumbersome and recursion is impractical. The Big-O complexity of algorithms tells us how well they should perform for some arbitrary size N, but once we tie ourselves to a specific ISA and an upper limit on practical Ns the story can change. Let's look at a few approaches.

Performance comparisons will be based on a common, arbitrarily chosen shuffled array- in practice different inputs will produce different results but one trial gives us a coarse idea of how algorithms stack up:

code:

:const SIZE   16
:const SIZE-1 15
: data  14 5 15 6 1 3 10 7 0 9 11 4 2 13 8 12

The O(n^2) sorting algorithms are often very compact and don't have much overhead. I went with a selection sort for starters, because the linear scans it involves lend themselves well to Chip8 memory operations:

code:

:alias  here       v1
:alias  rest       v2
:alias  min-index  v3
:alias  min-value  v4
:alias  here-value v5

: selection-sort
	here := 0
	loop
		min-index := here
		i := data
		i += here
		load v0
		min-value  := v0
		here-value := v0

		rest := here
		rest += 1
		i := data
		i += rest
		loop
			load v0
			if v0 >= min-value then jump no-better
				min-index := rest
				min-value := v0
			: no-better

			rest += 1
			if rest != SIZE then
		again

		if min-index == here then jump no-swap
			v0 := here-value
			i := data
			i += min-index
			save v0

			v0 := min-value
			i := data
			i += here
			save v0
		: no-swap

		here += 1
		if here != SIZE-1 then
	again
;

I use a few tricks here. I access the pivot value for each pass up-front and carry it in registers. The loop which finds the minimum value takes advantage of how load increments i, removing the need to re-initialize it and add an offset on each loop iteration. The memory swap at the end of each iteration is fairly bulky, even though I've carefully arranged so that both values will already be in registers.

The algorithm weighs in at 70 bytes and takes roughly 1260 cycles to sort our 16 element array. It'll be hard to write a general-purpose sorting routine that consumes less memory, but we can improve the speed.

The next natural thought is to employ one of the O(n * lg(n)) algorithms. Quicksort seems to be right out because it is naturally implemented recursively and Chip8 doesn't have an argument stack. We could build one, but the overhead doesn't sound good. A better choice is Heapsort:

code:

:const LIMIT   7 # (SIZE/2)+1

:alias left-val  v0
:alias right-val v1
:alias start     v2
:alias root      v3
:alias end       v4
:alias best      v5
:alias left      v6
:alias best-val  v7
:alias root-val  v8

: heap-sort
	start := LIMIT
	end   := SIZE
	loop
		root := start
		sift-down
		start += -1
		if start != -1 then
	again

	start := SIZE-1
	loop
		# swap data[0] with data[start]:
		i := data
		load v0
		vf := v0

		i := data
		i += start
		load v0
		i := data
		save v0

		i := data
		i += start
		v0 := vf
		save v0

		start += -1
		root := 0
		end := start
		sift-down

		if start != 0 then
	again
;

: assign-best
	best     := left
	best-val := left-val
	jump found-best

: sift-down
	i := data
	i += root
	load v0
	root-val := v0

	loop
		left <<= root

		if left > end then return

		i := data
		i += left
		load v1

		best := left
		best += 1
		best-val := right-val

		if left-val > right-val then jump assign-best
		if left == end then jump assign-best
		: found-best

		if root-val >= best-val then return

		i := data
		i += root
		v0 := best-val
		save v0

		i := data
		i += best
		v0 := root-val
		save v0

		root := best
	again

This one was a little tricky to get debugged. Unfortunately, it's worse on both dimensions we're considering. The code takes up 130 bytes and takes 1941 cycles to sort the same 16 element array.

If we scale up the array to 64 elements the insertion sort takes about 17613 cycles while the heapsort is only about 11825. Algorithmic complexities work out as expected, but either approach is impractically slow.

There's a different way to approach this problem. If we have a small, fixed N we could aggressively unroll the steps in a normal sorting algorithm, producing a sequence of code snippets which look something like this:

code:

if v0 <= v1 then jump l-0
	vf := v0
	v0 := v1
	v1 := vf
: l-0

By using a load vf instruction it would be possible to pull the full 16 elements of an array into registers at once, and then this lattice of comparisons and swaps could take care of the rest. That won't quite work, though- comparing the magnitude of two values requires a subtraction, which will destroy the contents of vf as well as one other temporary register. As a result we'd only be able to sort 14 elements in this manner. The next lowest power of two is 8.

What is the best sequence of comparisons and swaps? The obvious approach is to unroll the steps of a Bubble Sort- for size N=8 that would mean 28 swaps. This is a loose bound, though- this site describes optimal sorting networks for N <= 16. Here's one for N=8 that only requires 19 swaps:

This diagram is read left-to-right. Horizontal lines are values in a given position of an array, and vertical lines are a test-and-swap between two values. Vertical lines which are in the same column are swaps that can be carried out simultaneously or in any order and otherwise the test-and-swaps must be carried out left to right. Translating this into Octo code as in the example above, we get a subroutine called sort-8 which is 268 bytes long and takes somewhere around 100 cycles to do its thing. This is fast enough that it could actually be employed in a Chip8 game if called sparingly!

For a fair comparison with the previous two algorithms, we can sort 16 elements by splitting the source array into two halves, using the sorting network on each and then performing a linear merge pass:

code:

: heap1 0 0 0 0 0 0 0 0
: heap2 0 0 0 0 0 0 0 0

:alias val1   v8
:alias val2   v9
:alias dest   va
:alias index1 vb
:alias index2 vc

: fused-sort
	i := data
	load v7
	sort-8
	val1 := v0
	i := heap1
	save v7

	i := data
	load v7
	load v7 # cheaper than adding an offset of 8
	sort-8
	val2 := v0
	i := heap2
	save v7

	index1 := 1
	index2 := 1
	dest   := 0

: merge
	if val1 > val2 then jump merge-2
	append-1
	if index1 != 9 then jump merge
	loop
		append-2
		if dest == 16 then return
	again

: merge-2
	append-2
	if index2 != 9 then jump merge
	loop
		append-1
		if dest == 16 then return
	again

: append-1
	v0 := val1
	i := data
	i += dest
	save v0
	dest += 1

	i := heap1
	i += index1
	load v0
	val1 := v0
	index1 += 1
;

: append-2
	v0 := val2
	i := data
	i += dest
	save v0
	dest += 1

	i := heap2
	i += index2
	load v0
	val2 := v0
	index2 += 1
;

This could be done in-place but I used separate buffers for the sake of conceptual simplicty. The results are impressive: 418 bytes of code and a finished sort in about 479 cycles, completely blowing our previous attempts out of the water at the cost of some precious ram. If this is the best balance we can strike, I hope nobody needs to write a game that requires a routine like this, though- if we use what I believe is a historically accurate clock speed for Chip8 our fastest algorithm takes a little over a second to run.

Anyone think you can make a smaller or more efficient sorting routine? See any optimizations I missed?

# ¿ Sep 10, 2014 02:13

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Today I cleaned up a few rough utility programs I've used for tinkering with Octo and put them on github. Perhaps they will prove useful to others.

Smoothie is a utility for building flicker-free XOR-masked sprite sheets. Given a desired animation sequence it can build a sequence of looping deltas:

You can also use Smoothie as an easy bulk-importer if you disable the xor-masking feature.

TextPack is a utility for creating fonts and encoding strings. I showed a cruder, earlier version of this a while back:

ImagePack is a utility for preparing large images for Octo. You can specify a variety of ways to slice and dice data so that you can inexpensively achieve various wipe and pan effects and speeds:

All of these are commandline Java programs.

# ¿ Sep 16, 2014 21:19

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

http://johnearnest.github.io/Octo/index.html?gist=328ed416559b8cba1d0c

# ¿ Sep 18, 2014 03:55

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

DeathBySpoon, Dijkstracula: Thank you. It means a lot to me to hear this sentiment about my work.

Contrasting Chip8 with the VCS is interesting. Chip8 has severe constraints, but writing programs for it (especially given fairly modern tools) feels pretty high level to me. I don't have to manage memory banks or the relative lengths of branch instructions. Outside benchmarks as in my sorting algorithm showdown I never have to count cycles or really care about the addresses where my code is being assembled and laid out. There's only one "addressing mode". Coding for the VCS seems extremely daunting in comparison- complex addressing modes and memory layouts are key to getting things done quickly and even the simplest program has to concern itself with cycle-counts to "race the beam". I am a bit envious of the color and sound the VCS is capable of, though. (I may yet succumb to the temptation to make a few novel additions to the Chip8 instruction set.)

As for development news the Octo web UI is in the process of getting a bit of a facelift. (If I break anything please bring it to my attention.) While there hasn't been any particular need for it up to this point there is a :org operative in the language now for assembling code and data to fixed addresses which I intend to use for some dumb tricks in the future.

The disassembler is doing a much better job with some problem-child binaries thanks to bugfixes and improved heuristics, but it's still rather slow. One intriguing addition to my menagerie is Pinball, an RCA 1802 hybrid program. It isn't completely disassembled but you can see a number of chunks of machinecode Octo was able to identify and parse. I suspect that the "bad opcodes" immediately following native calls are arguments for the subroutines which are consumed by advancing the Chip8 program counter. In the future I might be able to do some crude static analysis of the machine code to better tease apart the remaining unknown territories of binaries like this.

In the course of my reverse-engineering adventures I have also been bemused to discover that some of the "test programs" for SuperChip features floating around the internet are dead wrong (about things that don't even relate to SuperChip instructions!) If you want to have some fun, see how many mistakes you can find in this Scroll Test program. Octo has flagged unreachable code and data as "unused", but with a bit of head-scratching it's easy to work out what the programmer meant to do. Sometimes when I take things apart I find very clever code but just as often I seem to discover bizarrely inefficient or convoluted code that seems to serve no purpose. The best guess I have is that these weird parts come from ad-hoc patching of binaries after their original assembly, but we may never know for sure.

# ¿ Sep 22, 2014 05:15

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I'm speaking with only second-hand VCS programming experience here, but how much do you think it would help to have an assembler that could check timing constraints for you? Imagine being able to have a block that looks like

code:

scanline {
	// 6502 code goes here
}

The assembler could know how long a scanline is (in cycles), so if you're under it'll introduce the necessary padding and if you exceed that limit you get a compile-time error. Making a feature like this compose with arbitrary subroutine calls and loops might get tricky and require some static analysis or annotations but I imagine it could remove an immense amount of tedium.

In other news, Octo now offers an "examples" menu to make it easier for beginners to see what it's capable of without investing too much effort digging around:

This list is populated from the examples directory in the github repository, so if anyone has a program they want added feel free to submit a pull request.

# ¿ Sep 23, 2014 15:45

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

AtrociousToaster: That looks like a pretty good start! I can say from experience that using Octo to write little testing programs makes tracking down emulation bugs a LOT easier than trying to work them out using existing roms alone. If you install Node.js and check out the Octo repository there's a CLI frontend available for the compiler and decompiler. Keep us updated!

# ¿ Sep 25, 2014 00:41

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Yeah, I wrote that.

I didn't think it would turn into a rant about CS majors versus "creative majors". Oh well. :smith:

# ¿ Sep 25, 2014 15:11

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I did a bunch of refactoring this evening, and now there is a simplified Octo frontend which could be suitable for embedding in an iframe on a blog or something. I thought it'd be nice for those times when a GIF just doesn't capture the full majesty of a program.

code:

<iframe
	src="http://johnearnest.github.io/Octo/embed.html?scale=2&gist=f3685a75817cde6d5c0d"
	width="256"
	height="128"
/>

scale is optional and the gist argument is the same id used when you have Octo "share" a program.

If anybody notices something is broken, please bring it to my attention- I changed a lot of little things today and I never really trust myself in these dynamic languages.

# ¿ Sep 26, 2014 04:18

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

Confirmed!

With the turn of the month just around the corner, get ready for

A month-long Chip8 game jam powered by Octo, with a spiffy website SharpenedSpoon built.

Spread the word: http://octojam.com

# ¿ Sep 29, 2014 22:19

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

If anyone is having trouble coming up with ideas, the COSMAC VIP manual has some suggestions:

Some of these are oddly prophetic visions of the game industry to come.

# ¿ Sep 30, 2014 19:33

Adbot: ADBOT LOVES YOU

# ¿ May 10, 2024 10:00

Internet Janitor: May 17, 2008; "That isn't the appropriate trash receptacle."

I've done a number of effortposts about some crazy scheme that I managed to get working, but today I'd like to briefly discuss an idea that didn't pan out.

Chip8 memory limitations are one of the most serious constraints in building games for the platform. With that in mind, I had an interesting idea for pushing the envelope by trying to adapt a game which is defined by its reliance on abundant static data: Myst. Cloning the entire game in any capacity is strictly out of the question, but how far could we go?

Chip8 has 3584 bytes, or 3.5kb, of memory. A SuperChip 128x64 full-screen bitmap requires 1024 bytes of memory. Assuming we reserve 512 bytes for a game engine- moving a cursor, drawing images- this means we'd be able to have 3 screenfuls of art. That's barely even a start screen! Ok, how about 64x32? That would be 256 bytes of memory per image, or 12 screens. Still not enough for much of an adventure game. If we could manage to compress those images to 50% of their size (or less!), 24 screens starts to sound like enough for a small game.

Our options for compression are limited by the speed and resources of the Chip8. The decompressor must be fairly simple and cannot rely on extensive static data- every byte we spend on its machinery and lookup tables is a byte we have to wring out of our data twofold to come out ahead. Run-Length Encoding seemed like a practical solution, so I whipped up a few compressors to see how well they performed.

Our baseline bitmaps can represent 8 pixels in exactly 1 byte of data. Most of the schemes I considered split data bytes into a pair of nybbles. The most obvious scheme uses the first nybble to store the length of a run of black pixels and the second nybble to store the length of a run of white pixels. This means that, for example, a run of 30 black pixels might be encoded as 0xF0 0xF0. In the best case we can store 30 pixels of data in 1 byte, and in the worst case we might only store a single pixel. A more balanced approach uses the first nybble as a pattern of 4 bits to draw and the second nybble as the number of additional times that pattern is repeated. The best case is representing a whopping 64 pixels of data in one byte and the worst case is representing 4.

This second idea seemed promising enough to code up. I tried searching for repeating strips vertically and horizontally: http://pastebin.com/kZuY4m7D

For a very regular test image, the results looked good:

code:

horiz-pattern:	149 bytes	(-107)
verti-pattern:	91 bytes	(-165)

But for something a bit more evocative of the game I have in mind, not so good:

code:

horiz-pattern:	355 bytes	(+99)
verti-pattern:	264 bytes	(+8)

The performance of compression algorithms is inherently data-dependent, and it may well be possible to achieve compression by imposing restrictions on the art. Maniac Mansion's graphics were famously created through a back-and-forth process of drawing, running the images through a tile-based compression algorithm and tweaking the drawings to get the best results. I might be able to make a point-and-click first-person adventure game, but having done some tinkering I have serious doubts I'd be able to make something like Myst.

Any thoughts? If any of you are up for a challenge, see if you can come up with a compression algorithm which would yield good results for both of my test images while still being feasible to implement on a Chip8.

Internet Janitor fucked around with this message at 02:20 on Oct 4, 2014

# ¿ Oct 4, 2014 02:16

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

«‹›3 »