# The HAM problem

While I was tinkering with my code to render Amiga HAM images, one challenge was finding good images. So I considered generating them myself, but this is not as easy as it sounds. Building an image with a colour palette requires Colour quantisation, but HAM is a little bit trickier.

When selecting your palette for a classical colour palette image, like for an instance a GIF image, you want to have one representative for each colour cluster. In a HAM image you have two choices for each pixel: select a close colour in the palette, or derive the colour from the previous pixel.

Another way to describe the problem is that of a robot that needs to follow a path in 3 dimensional space, the robot is only allowed to either move along one of the axis (Manhattan norm) or to teleport to one of P arbitrary points. The goal is to select the teleport points and to plan a path of the robot: either move along one axis or teleport, so that its path is a close as possible to the points in the original path (the image to encode).

The position along each axis is discrete, for each there are P possibilities. There are also P teleportation points (palette entries) each with P3 possible values. So the total number of palettes is 𝐂 (P3, P). For each point in the path, there are 4 × P choices (1 teleport and 3 moves). So the number of possibles paths of length N is (4 × P)N. Clearly the total solution space is pretty big: 𝐂 (P3, P) × (4 × P)N. For a classical HAM file, N = 320 × 400 and R = 24, which is around 3.17 × 10231235 possibilities, so an exhaustive search is not a reasonable approach.

If the problem would only be that of finding a path, without the colour-table jumps, some linear programming would do the trick, but here, the selection of the path and the selection of the colour table are deeply connected…

This site uses Akismet to reduce spam. Learn how your comment data is processed.