Last time round I had got to the point of raycasting a silhouette on a spritesheet, with a largely clean solution that only had a few areas of potential messiness. I think the last useful thing I can do in terms of "learning Go while cleaning up an old project" rather than "watch me write software" is to add palette support and get to the flat-shaded MVP discussed in Part 2, maybe followed by a coda of cleaning up any mess I've made along the way.

Palettes

OpenTTD is derived (via Transport Tycoon Deluxe) from Transport Tycoon, a 1994 game that was originally in 256-colour SVGA. Since MagicaVoxel files also use an 8-bit palette we need to have some palette support even to output the 32-bit sprites of our MVP, and it makes sense to use the Transport Tycoon one.

The Transport Tycoon palette is not just a list of colours as some of them have semantic meaning within the game, either for '90s-style palette cycling animation or for recolouring with the player's chosen company livery.

Transrender originally did all of its lighting and shading within this paletted domain. It therefore tracks a lot of information about how to lighten and darken colours without changing to an inappropriate hue, and combine them when downscaling a larger image to a smaller one. TTDPalette.cs is one of the oldest and messiest parts of Transrender, combining responsibilities from all over the place including raw data storage, anti-aliasing, palette behaviour and even concurrency semantics.

I'd like GoRender to load all of its data from a JSON file, which has the advantage of allowing users to tune palette behaviour (and even use different palettes) without needing code access. The data structure will have two main types of data:

  • The individual palette colours.
  • The ranges which identify where ramps of colours begin and end, and which special behaviour those have.

More importantly I'll need to learn how to read JSON in Go, which is going to be useful in contexts far beyond GoRender.

Loading a palette

A lesson from Transrender is that we need to do a lot of things with colours in addition to merely palette retrieval - prepare masks, lighten or darken them, and convert to or from 32bpp modes. I'm going to create a package called colour, of which the palette functions can be a small part.

First let's create some structures in palette.go to store the data I know will be needed:

package colour

type PaletteEntry struct {
	R,G,B byte
}

type PaletteRange struct {
	start, end byte
}

type Palette struct {
	Entries []PaletteEntry
	Ranges []PaletteRange
}

(Message from the future: spot the obvious and accidental mistake which will cause this to fail.)

At this point I have a good idea what my JSON will look like - something like this:

{
  "entries": [
    [0,0,0],
    [255,255,255]
  ],
  "ranges": [
    { 
      "start": 0, 
      "end": 1 
    }
  ]
}

This seems like a reasonable compromise between readability and not having an enormous file where every entry is an {"r": 0, "g": 0, "b": 0} entry.

With this in mind, I can now write my first test:

const exampleJson = "{\"entries\": [[0,0,0],[255,255,255]], \"ranges\": [{\"start\": 0, \"end\": 1}]}"

func TestGetPaletteFromJson(t *testing.T) {
	palette := GetPaletteFromJson(strings.NewReader(exampleJson))

	expectedRanges := []PaletteRange{{0, 1}}
	expectedEntries := []PaletteEntry{{0, 0, 0}, {255, 255, 255}}

	if len(palette.Ranges) != len(expectedRanges) {
		t.Fatalf("ranges length %d is too short, expected %d", len(palette.Ranges), len(expectedRanges))
	}

	if len(palette.Entries) != len(expectedEntries) {
		t.Fatalf("entries length %d is too short, expected %d", len(palette.Entries), len(expectedEntries))
	}
	
	for i, r := range expectedRanges {
		if palette.Ranges[i] != r {
			t.Errorf("palette range %d not loaded correctly: was %v, expected %v", i, palette.Ranges[i], r)
		}
	}

	for i, e := range expectedEntries {
		if palette.Entries[i] != e {
			t.Errorf("palette entry %d not loaded correctly: was %v, expected %v", i, palette.Entries[i], e)
		}
	}
}

Now it's time to start investigating how to parse some JSON. This is in the standard library (https://golang.org/pkg/encoding/json/). I think what I want to do is to unmarshal the data. My first naive attempt looks like this:

func GetPaletteFromJson(handle io.Reader) (p Palette) {
	data, err := ioutil.ReadAll(handle)

	if err != nil {
		return Palette{}
	}

	json.Unmarshal(data, &p)
	return
}

New concepts here:

  • Declaring the return value in the function specification, so we don't need to initialise it in the function body.
  • Passing a pointer to json.Unmarshal using the & operator.

Unfortunately this isn't there yet. I have two test failures:

--- FAIL: TestGetPaletteFromJson (0.00s)
    palette_test.go:26: palette range 0 not loaded correctly: was {0 0}, expected {0 1}
    palette_test.go:32: palette entry 1 not loaded correctly: was {0 0 0}, expected {255 255 255}

This gets more interesting if I add some error handling to my unmarshalling call:

if err := json.Unmarshal(data, &p); err != nil {
	fmt.Print(err.Error())
	return Palette{}
}

Now my output looks like this:

json: cannot unmarshal array into Go struct field Palette.Entries of type colour.PaletteEntry--- FAIL: TestGetPaletteFromJson (0.00s)
    palette_test.go:17: ranges length 0 is too short, expected 1

This is a rather brain-jarring realisation for someone used to other languages. When I called json.Unmarshal with some data that didn't quite match the structure I was working with, I got both an error and a best-effort attempt to do something with the data anyway. This is very different philosophically from what I'm used to, and I think I might be reaching that moment where I start to understand Go's error handling a bit more.

Regardless, we still have an error and I need to work out how to treat that array as a tuple. This is where I need to start getting into interfaces, an important Go concept by the looks of things. I bumped into the edges of this earlier trying to use image/draw on an object which didn't have a Set() method, but now I need to understand what's going on a bit better.

Before I do anything, PaletteEntry is going to require its own custom unmarshalling code in order to address the challenge of converting an array to a tuple. Let's (not really) implement that now:

func (p *PaletteEntry) UnmarshalJSON(buf []byte) error {
	fmt.Printf("unmarshal function called!\n")
	return fmt.Errorf("not implemented")
}

My failed test output now looks like this, which is what I'd hoped for:

unmarshal function called!
not implemented--- FAIL: TestGetPaletteFromJson (0.00s)
    palette_test.go:17: ranges length 0 is too short, expected 1

So now we've implemented that part of the unmarshalling interface explicitly, we can use another interface to map the array values into our struct:

func (p *PaletteEntry) UnmarshalJSON(data []byte) error {
	i := []interface{}{&p.R, &p.G, &p.B}

	if err := json.Unmarshal(data, &i); err != nil {
		return err
	}

	return nil
}

This part of my test now works and I no longer get an error unmarshalling the JSON data, but I'm still left with a failure on my palette ranges:

palette range 0 not loaded correctly: was {0 0}, expected {0 1}

This turns out to be a stupid newbie mistake and I'd have soon found it had I tried to use PaletteRange outside of the colour package - those lowercase fields aren't exported! Renaming them to Start and End means the JSON unmarshaller can now find and populate them, and my test passes.

This is an early warning I have some potentially brittle code here if I ever start renaming fields, so I'll finish up my implementation by explicitly specifying the names of the fields in JSON rather than letting Go's unmarshaller find them by convention:

package colour

import (
	"encoding/json"
	"fmt"
	"io"
	"io/ioutil"
)

type PaletteEntry struct {
	R, G, B byte
}

type PaletteRange struct {
	Start byte `json:"start"`
	End   byte `json:"end"`
}

type Palette struct {
	Entries []PaletteEntry `json:"entries"`
	Ranges  []PaletteRange `json:"ranges"`
}

func (p *PaletteEntry) UnmarshalJSON(data []byte) error {
	i := []interface{}{&p.R, &p.G, &p.B}

	if err := json.Unmarshal(data, &i); err != nil {
		return err
	}

	return nil
}

func GetPaletteFromJson(handle io.Reader) (p Palette) {
	data, err := ioutil.ReadAll(handle)

	if err != nil {
		return Palette{}
	}

	if err := json.Unmarshal(data, &p); err != nil {
		fmt.Print(err.Error())
		return Palette{}
	}

	return
}

Outputting a flat-shaded sprite

I'm now very close to being able to get R,G,B values for my sprite. I just need a method which extracts Go's 16-bit values from the 8 bit per channel palette data.

Test:

func TestPalette_GetRGB(t *testing.T) {
	palette := GetPaletteFromJson(strings.NewReader(exampleJson))

	expected := [][]uint32{{0,0,0},{65535,65535,65535},{65535,32639,0},{0,0,0}}

	for i, e := range expected {
		if r,g,b := palette.GetRGB(byte(i)); r != e[0] || g != e[1] || b != e[2] {
			t.Errorf("entry at %d not returned correctly: was [%d %d %d], expected %v", i,r,g,b,e)
		}
	}
}

Implementation:

func (p Palette) GetRGB(index byte) (r,g,b uint32) {
	if int(index) < len(p.Entries) {
		entry := p.Entries[index]
		rgba := color.RGBA{R: entry.R, B: entry.B, G: entry.G}
		r,g,b,_ = rgba.RGBA()
		return
	}

	return 0,0,0
}

I've added another entry to the JSON data so we can make sure r,g,b are interpreted in the right order, and then used Go's own standard library to translate between colour formats.

This also handles the case where a palette is smaller than the range of colours in the voxel file, by returning black in that instance.

The next step is to return the voxel colour index in RenderInfo, so I'll update that in raycaster.go:

type RenderInfo struct {
	Collision bool
	Index byte
}

And then set it during the raycasting loop:

if object[lx][ly][lz] != 0 {
    result[x][y].Collision = true 
    result[x][y].Index = object[lx][ly][lz]
}

What's nice is my raycaster doesn't need to care about palettes and colours - sprite is the package with the responsibility for turning raycaster data into images. To make that happen, I'll rewrite GetRaycastSprite to use the palette data:

func GetRaycastSprite(object voxelobject.RawVoxelObject, pal colour.Palette, bounds image.Rectangle, angle int) image.Image {
	info := raycaster.GetRaycastOutput(object, angle, bounds.Max.X, bounds.Max.Y)
	img := image.NewRGBA(bounds)

	for x := bounds.Min.X; x < bounds.Max.X; x++ {
		for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
			if info[x][y].Collision {
				r,g,b := pal.GetRGB(info[x][y].Index)
				img.Set(x, y, color.RGBA64{R: uint16(r), G: uint16(g), B: uint16(b), A: 65535})
			}
		}
	}

	return img
}

The nice thing with my GetRGB() function checking index ranges is I can pass an empty palette and I should get my existing behaviour of outputting a black silhouette, although in this case the background will be transparent rather than white. And our survey says...

Excellent!

I now create the JSON file with the correct Transport Tycoon palette. After that, I can add yet more brittle, unpleasant and badly-structured code to my main package to load it:

paletteFile, err := os.Open("files/ttd_palette.json")

if err != nil {
	s := fmt.Sprintf("could not open palette file: %s", err)
	panic(s)
}

palette := colour.GetPaletteFromJson(paletteFile)

if err := paletteFile.Close(); err != nil {
	s := fmt.Sprintf("error closing palette file: %s", err)
	panic(s)
}

Let's take a look at the output now:

Ouch. More bugs. I'm not sure yet whether this is happening in my untested raycaster code or if some of my tests have bad assumptions, but it's difficult to tell exactly what's going on at that small resolution. Luckily, bumping up the scale is a one-line change:

sheets := spritesheet.GetSpritesheets(object, palette, 4.0, 8)

And a one-line bugfix in spritesheet.go for a scenario that wasn't in my tests (this should tell you something about the importance of tests - all of the resolved bugs so far have been related to test cases we didn't explore! What I should be doing here is writing new tests for each of these bugs, so I know I don't encounter the problem again):

compositor.Composite(spr, img, image.Point{X: int(float64(i * spriteSpacing) * scale)}, rect)

With these fixed, our output starts to reveal what's gone wrong:

This is all rather unexpected. Despite starting with the same plane and render direction as my C# version, the object is upside-down compared to where it should be, and possibly facing the wrong way.

The values I took from Transrender for the render direction and viewport plane look sensible. My first assumption is something screwy is happening with my vector mathematics. I look to see if I've made an error with BiLerpWithinPlane returning an upside-down result, and it looks like this might be the case.

But even "correcting" this, the voxel object itself is upside-down. There's a reason for this which I would have discovered a lot faster had I written tests for the ray casting itself... while I check to see if there's a collision, I don't actually stop raycasting at that point. So the output is the last voxel the raycaster collided with, not the first.

Adding a simple break to the raycaster solves all of these problems and I don't need any hacks around the edges to get correct output from incorrect assumptions.

I now have something much closer to what I expected (I've set the scale to 2.0 as this is what the image I suggested for the MVP used):

But we're still not quite there - here's the image we're trying to match:

What we're seeing here is some special behaviour of the Transport Tycoon palette. There are two ranges which correspond to "company" colours: [80-87] and [199-205]. I'm going to add a couple of new properties to PaletteRange:

type PaletteRange struct {
	Start byte `json:"start"`
	End   byte `json:"end"`
	IsPrimaryCompanyColour bool `json:"is_primary_company_colour,omitempty"`
	IsSecondaryCompanyColour bool `json:"is_secondary_company_colour,omitempty"`
}

And then put that data in my JSON file:

  "ranges": [
    {
      "start": 80,
      "end": 87,
      "is_secondary_company_colour": true
    },
    {
      "start": 199,
      "end": 205,
      "is_primary_company_colour": true
    }
  ]

To see if this works, I'm going to update GetRGB with this very slow approach to seeing if I should return the monochrome equivalent of the colour:

func (p Palette) GetRGB(index byte) (r, g, b uint32) {
	if int(index) < len(p.Entries) {
		entry := p.Entries[index]
		rgba := color.RGBA{R: entry.R, B: entry.B, G: entry.G}
		r, g, b, _ = rgba.RGBA()

		for _, rng := range p.Ranges {
			if index >= rng.Start && index <= rng.End {
				if rng.IsPrimaryCompanyColour || rng.IsSecondaryCompanyColour {
					y := (19595*uint32(entry.R) + 38470*uint32(entry.G) + 7471*uint32(entry.B) + 1<<15) >> 8
					return y,y,y
				}
			}
		}

		return
	}

	return 0, 0, 0
}

A couple of test updates to make sure this behaviour is being used, and we can run the command line tool again:

Success! This is what we wanted from the MVP, and it's already rather more flexible in certain respects than the C# version, which can't trivially do all of this with a one-line change:

However we do have some areas which need revisiting, particularly that rather slow range lookup. In Part 5 I'll be taking some of the things I've learnt creating new code and using them to tidy up a few of the expedient but messy things I wrote creating the MVP renderer.