Palette and Tile Generation


This was never about making a game

Please note, this isn't really about Genesis programming all that much. It's about some tools I'm working on to make Genesis programming easier. If you just want to see some beautiful assembly code then please check out the other articles in this series.

I've been thinking about writing a sequel to Retail Clerk '89 lately. I have a ballpark story in mind and some new lead characters. I'm doing this even though it's possible no one ever played Retail Clerk '89. I've done zero to promote it outside of posting it here. This limits the potential audience to people who randomly stumble across this page. I know I could change that but it's not important to me.

I'm largely making the "no one played it" assumption based on not receiving any hate mail. I expected at least one person to complain that this free demo that I charged them nothing for caused them deep emotional trauma. I'm very disappointed in you internet.

So why would I make a sequel to a game nobody played? It's simple, my point isn't making a game anyone wants to play. A game demo is just a consequence of my real goals:

1) Learn to program at least one 90s console in assembly.

2) Build a general game engine like thing to play casual adventure games.

3) Build tooling to generate stuff for this game engine like thing.

I attempted parts 2 & 3 around 15 years ago and failed. It's OK, your first attempt at anything should fail. That first time I came up with some grand over-engineered engine design. I then tried to fit a game demo around it. It went badly and I lost interest in the project. The second time I started with a game idea and built things as I needed them, it went a bit better. I accomplished goal #1 and like 50% of goal #2. Now it's time to work on #3...

The first thing I want to build is a way to generate palette and tile data from PNG images. Bitmap and GIF are fine too, anything that's lossless and supports a fixed color palette. One of the most monotonous things about building Retail Clerk '89 was creating tiles and the patterns to draw them on the screen. I'd prefer to point to an image and have some code figure all that out for me.

Let's try this out by converting this scene from Ys II to the Genesis:

Dialog from Ys II

Oh, spoiler alert maybe. I guess you can't really tell what's going on in this scene from a >30 year-old game anyway.

This is from the TurboGrafx-16 CD version which means it has more colors than what the Genesis can support. Sort of, I'll get to it soon. This is good because "match to nearest color in palette" is a feature I want to build.

The full image only has 41 colors:

Dialog from Ys II - colormap

The Genesis can do 41 colors but is limited to 15 per palette (accounting for transparency). That makes decomposing this into layers a little tricky. Let's do the easy ones first.

Here's the frame which we'll draw in scroll B low:

Frame

Then we have the floor and walls which will also go in scroll B low:

Floor and walls

The image overlay will go in scroll A high:

Overlay

So we have 3 layers and 3 palettes. Everything's fine so far. Now let's look at the sprites:

Sprites

I'm not an expert on the technical aspects of the TurboGrafx-16, maybe in the future, but I vaguely understand that each sprite can have a unique palette. This is why in a game like Ys the villagers all have colorful outfits. So we're going to have to merge a couple similar colors unfortunately. This doesn't bode well for a Ys I&II port to the Sega CD either.

Yeah, OK, so this leaves us with the following 4 palettes to create:

Palette 0

Palette 1

Palette 2

Palette 3

Reminder: entry 0 of palette 0 is the background color, entry 0 of the other palettes is the transparency color.

Code

A quick recap of what we need to build:

1) Something to extract a 16 color Genesis palette from an image, preferably one that is only 16 colors to begin with

2) Something to convert an image into a set of the unique 8x8 tiles used to create it

3) Something to map each color in these tiles to the nearest color in a 16 color Genesis palette

4) Something to produce a pattern that maps the 8x8 tiles to the order they appear in the original image

Let's start with the code to extract Genesis palettes from an image. This code takes a map of image file paths -> destination ASM files:

public abstract class ExtractPalette{

 private final static String newLine=System.lineSeparator();

public static void extract(String basePath,Map sourceDestinationMap,String includeFilePath){

 FileWriter paletteWriter=null;

 FileWriter includeWriter=null;

 try{

  includeFilePath=basePath+includeFilePath;

  includeWriter=new FileWriter(includeFilePath);

  for(Map.Entry<String,String> entry:sourceDestinationMap.entrySet()){

  String sourceFilePath=basePath+entry.getKey();

  String outputFilePath=basePath+entry.getValue();

  paletteWriter=new FileWriter(outputFilePath);

  File sourceFile=new File(sourceFilePath);

  BufferedImage image=ImageIO.read(sourceFile);

  int width=image.getWidth();

  int height=image.getHeight();

  ArrayList<String> colors=new ArrayList<String>();

  for(int row=0;row<height;row++){

   for(int col=0;col<width;col++){

   int color=image.getRGB(col,row); 

   String hexString=Integer.toHexString(color);

   String genesisRGBStr=ColorUtils.rgbStringToGenesisRgbString(hexString);

   int index=colors.indexOf(genesisRGBStr);

   if(index<0){

    colors.add(genesisRGBStr);

    if(colors.size()>16){

    throw(new Exception("More than 16 colors found in: "+entry.getKey()));

    }else{

    StringBuffer line=new StringBuffer();

    line.append("\tdc.w\t%");

    line.append(genesisRGBStr);

    line.append(" ; ~");

    line.append(hexString);

    line.append(newLine);

    paletteWriter.write(line.toString());

    }

   }

   }

  }

  int size=colors.size();

  if(size<16){

   for(int i=size;i<16;i++){

   paletteWriter.write("\tdc.w\t%0000000000000000");

   paletteWriter.write(newLine);

   }

  }

  paletteWriter.flush();

  paletteWriter.close();

  //update the include file

  String includePathRel=PathResolver.getRelativePath(includeFilePath,outputFilePath);

  if(includePathRel.startsWith("..")){

   includePathRel=includePathRel.substring(3);

  }

  StringBuffer includeString=new StringBuffer();

  String label="Palette"+includePathRel.substring(includePathRel.lastIndexOf(File.separator)+1,includePathRel.lastIndexOf('.'));

  includeString.append(label);

  includeString.append(":");

  includeString.append(newLine);

  includeString.append("\tinclude '");

  includeString.append(includePathRel);

  includeString.append("'");

  includeString.append(newLine);

  includeString.append(newLine);

  includeWriter.write(includeString.toString());

     }

  includeWriter.flush();

  includeWriter.close();

 }catch(Exception x){

  x.printStackTrace();  

 }finally{

  try{if(paletteWriter!=null){paletteWriter.flush(); paletteWriter.close();}}catch(Exception x){ }

  try{if(includeWriter!=null){includeWriter.flush(); includeWriter.close();}}catch(Exception x){ }

 } 

 }

}

I guess this code would be handy too:

public static String rgbStringToGenesisRgbString(String rgb){

  StringBuilder grgb=new StringBuilder();

  //ffrrggbb

  //01234567

  grgb.append("0000");

  //BBB

  grgb.append(hexStringToGenesisRgb(rgb.substring(6,8)));

  grgb.append("0");

  //GGG

  grgb.append(hexStringToGenesisRgb(rgb.substring(4,6)));

  grgb.append("0");

  //RRR

  grgb.append(hexStringToGenesisRgb(rgb.substring(2,4)));

  grgb.append("0");

  return(grgb.toString());

}

[...]

public static String hexStringToGenesisRgb(String hexString){

  int i=Integer.parseInt(hexString,16);

  i=i/32;

  String b=Integer.toBinaryString(i);

  if(b.length()>3){b=b.substring(0,3);return(b);}

  if(b.length()==2){b="0"+b;return(b);}

  if(b.length()==1){b="00"+b;return(b);}

  if(b.length()==0){return("000");}

  return(b);

}

That gives us a palette file that looks like:

 dc.w %0000111000001110 ; ~ffff00ff

 dc.w %0000000000000000 ; ~ff000000

 dc.w %0000100000000000 ; ~ff000094

 dc.w %0000111000000000 ; ~ff0000ff

 dc.w %0000000000000110 ; ~ff6b0000

 dc.w %0000000000001000 ; ~ff940000

 dc.w %0000001000100010 ; ~ff212421

 dc.w %0000111000100000 ; ~ff0024ff

 dc.w %0000000000001100 ; ~ffd60000

 dc.w %0000110001000000 ; ~ff0049d6

 dc.w %0000111001100000 ; ~ff006dff

 dc.w %0000111010000000 ; ~ff0092ff

 dc.w %0000111010100000 ; ~ff00b2ff

 dc.w %0000010010001100 ; ~ffd6924a

 dc.w %0000011010101110 ; ~ffffb26b

 dc.w %0000111011100100 ; ~ff4afbff

And an include file we need to compile this thing later:

Palettepalette0:

 include 'palettes/palette0.X68'

Palettepalette1:

 include 'palettes/palette1.X68'

Palettepalette2:

 include 'palettes/palette2.X68'

Palettepalette3:

 include 'palettes/palette3.X68'

This next part is going to be a little tough to understand because I won't explain it well. We are going to generate the tiles and also the patterns. By "pattern" I mean - "what order to draw the tiles relative to the first tile in the set". Think of it sort of like this - you have a set of tiles numbered 0 to X. The pattern tells you what order to draw the tiles to recreate the original image. Each tile is an 8x8 array of numbers between 0-15 where 0-15 corresponds to a color in the palette.

I know, not a good explanation. Here's the code to do it all:

public class TilesetParameters implements Serializable{

 private static final long serialVersionUID=666L;

 public TilesetDefinition[] tilesets;

 public String tileIncludeFilePath;

 public String patternIncludeFilePath;

}

[...]

public class TilesetDefinition implements Serializable{

 private static final long serialVersionUID=666L;

 public String name;

 public String palettePath;

 public String sourceFilePath;

 public String destinationFilePath;

 public String allowDuplicateTiles;

 public String patternFilePath;

}

[...]

public class BuildTiles{

 private final static String newLine=System.lineSeparator();

 public static void build(String basePath,TilesetParameters tiles){

  FileWriter tileIncludeWriter=null;

  FileWriter tileWriter=null;

  FileWriter patternWriter=null;

  FileWriter patternIncludeWriter=null;

  try{

   //setup include writers

   String tileIncludeFilePath=basePath+tiles.tileIncludeFilePath;

   tileIncludeWriter=new FileWriter(tileIncludeFilePath);

   String patternIncludeFilePath=basePath+tiles.patternIncludeFilePath;

   patternIncludeWriter=new FileWriter(patternIncludeFilePath);

   //loop through all tilesets

   for(int i=0;i<tiles.tilesets.length;i++){

    boolean allowDuplicateTiles=false;

    if((tiles.tilesets[i].allowDuplicateTiles!=null)&&(tiles.tilesets[i].allowDuplicateTiles.equalsIgnoreCase("TRUE"))){

     allowDuplicateTiles=true;

    }

    boolean createPattern=false;

    if((tiles.tilesets[i].patternFilePath!=null)&&(!tiles.tilesets[i].patternFilePath.isBlank())){

     createPattern=true;

    }

    //read colors from the palette

    ArrayList<String> colors=new ArrayList();

    BufferedReader reader=null;

    reader=new BufferedReader(new FileReader(basePath+tiles.tilesets[i].palettePath));

    String currentLine;

    while((currentLine=reader.readLine())!=null){

     colors.add(ColorUtils.genesisRgbStringToHexString(currentLine));

    }

    reader.close();

    //setup the tilewriter

    String tileOutputPath=basePath+tiles.tilesets[i].destinationFilePath;

    tileWriter=new FileWriter(tileOutputPath);

    //setup the patternwriter

    String patternOutputPath=null;

    if(createPattern){

     patternOutputPath=basePath+tiles.tilesets[i].patternFilePath;

     patternWriter=new FileWriter(patternOutputPath);

    }

    //read the source file

    String sourceFilePath=basePath+tiles.tilesets[i].sourceFilePath;

    File sourceFile=new File(sourceFilePath);

    BufferedImage image=ImageIO.read(sourceFile);

    //get & test image width

    int width=image.getWidth();

    if(width%8!=0){throw(new Exception("Image width must be a multiple of 8"));}

    //get & test image height

    int height=image.getHeight();

    if(height%8!=0){throw(new Exception("Image width must be a multiple of 8"));}

    if(createPattern){

     int rowCount=height/8;

     patternWriter.write("\tdc.w\t$"+Integer.toHexString(rowCount-1).toUpperCase()+"\t; "+rowCount+" rows");

     patternWriter.write(newLine);

     int colCount=width/8;

     patternWriter.write("\tdc.w\t$"+Integer.toHexString(colCount-1).toUpperCase()+"\t; "+colCount+" columns");

     patternWriter.write(newLine);

    }

    ArrayList<Tile8x8> uniqueTiles=new ArrayList();

    //loop through all the pixels and filter out duplicate tiles

    int row=0;

    while(row<height){

     int col=0;

     while(col<width){

      Tile8x8 tile8x8=new Tile8x8();

      //loop through each pixel of the next 8x8 cell

      for(int x=col;x<(col+8);x++){

       for(int y=row;y<(row+8);y++){

        int color=image.getRGB(x,y);

        String hexString=Integer.toHexString(color);

        int index=ColorUtils.findNearestColor(colors,hexString);

        //yes, these are getting transposed on purpose

        tile8x8.pixels[y-row][x-col]=index;

       }

      }

      int tileIndex=-1;

      boolean addTile=allowDuplicateTiles;

      if(!addTile){

       tileIndex=uniqueTiles.indexOf(tile8x8);

       addTile=tileIndex<0;

      }

      if(addTile){

       uniqueTiles.add(tile8x8);

       tileIndex=uniqueTiles.size()-1;

       String indexStr="\t; "+Integer.toHexString(tileIndex).toUpperCase();

       tileWriter.write(indexStr);

       tileWriter.write(newLine);

       tileWriter.write(tile8x8.toAsmLines());

       tileWriter.write(newLine);

      }

      if(createPattern){

       patternWriter.write("\tdc.w\t"+Integer.toHexString(tileIndex).toUpperCase());

       patternWriter.write(newLine);

      }

      col+=8;

     }

     row+=8;

    }

    //update the include files

    String includePathRel=PathResolver.getRelativePath(tileIncludeFilePath,tileOutputPath);

    if(includePathRel.startsWith("..")){

     includePathRel=includePathRel.substring(3);

    }

    StringBuffer includeString=new StringBuffer();

    includeString.append(tiles.tilesets[i].name);

    includeString.append("TilesStart:");

    includeString.append(newLine);

    includeString.append("\tinclude '");

    includeString.append(includePathRel);

    includeString.append("'");

    includeString.append(newLine);

    includeString.append(tiles.tilesets[i].name);

    includeString.append("TilesEnd:");

    includeString.append(newLine);

    includeString.append(newLine);

    tileIncludeWriter.write(includeString.toString());

    //close the tile writer

    tileWriter.flush();

    tileWriter.close();

    if(createPattern){

     includePathRel=PathResolver.getRelativePath(patternIncludeFilePath,patternOutputPath);

     if(includePathRel.startsWith("..")){

      includePathRel=includePathRel.substring(3);

     }

     includeString=new StringBuffer();

     includeString.append("Pattern");

     includeString.append(tiles.tilesets[i].name);

     includeString.append(":");

     includeString.append(newLine);

     includeString.append("\tinclude '");

     includeString.append(includePathRel);

     includeString.append("'");

     includeString.append(newLine);

     includeString.append(newLine);

     patternIncludeWriter.write(includeString.toString());

     //close the pattern writer

     patternWriter.flush();

     patternWriter.close();

    }

   }

  }catch(Exception x){

   x.printStackTrace();

  }finally{

   try{if(tileIncludeWriter!=null){tileIncludeWriter.flush();tileIncludeWriter.close();}}catch(Exception x){ }

   try{if(patternIncludeWriter!=null){patternIncludeWriter.flush();patternIncludeWriter.close();}}catch(Exception x){ }

   try{if(tileWriter!=null){tileWriter.flush();tileWriter.close();}}catch(Exception x){ }

   try{if(patternWriter!=null){patternWriter.flush();patternWriter.close();}}catch(Exception x){ }

  }

 }

}

Here's some other code I should have included earlier:

 public static String genesisRgbStringToHexString(String genRgb){

  Color c=genesisRgbStringToColor(genRgb);

  return(Integer.toHexString(c.getRGB()));

 }

 public static Color genesisRgbStringToColor(String genRgb){

  int start=genRgb.indexOf("%0000")+5;

  String bStr=genRgb.substring(start,start+3);

  String gStr=genRgb.substring(start+4,start+7);

  String rStr=genRgb.substring(start+8,start+11);

  int b=Integer.parseInt(bStr,2)<<5;

  int g=Integer.parseInt(gStr,2)<<5;

  int r=Integer.parseInt(rStr,2)<<5;

  return(new Color(r,g,b));

 }

[...]

 public final static String getRelativePath(String absolutePath1,String absolutePath2){

  // verify input parameters

  if(absolutePath1==null){

   if(absolutePath2==null){

    return(null);

   }

   return(absolutePath2);

  } else if(absolutePath2==null){

   return(absolutePath1);

  }

  StringBuffer relativePath=new StringBuffer();

  StringTokenizer tokenizer1=new StringTokenizer(absolutePath1,File.separator);

  StringTokenizer tokenizer2=new StringTokenizer(absolutePath2,File.separator);

  // are there tokens?

  if(tokenizer1.hasMoreTokens()&&tokenizer2.hasMoreTokens()){

   // are the first tokens (drive letters) equal?

   String token1=tokenizer1.nextToken();

   String token2=tokenizer2.nextToken();

   if(token1.equals(token2)){

    int parentCount=0;

    boolean pathBroken=false;

    while(tokenizer1.hasMoreTokens()&&tokenizer2.hasMoreTokens()){

     token1=tokenizer1.nextToken();

     token2=tokenizer2.nextToken();

     if(!token1.equals(token2)||pathBroken){

      pathBroken=true;

      relativePath.append(File.separator);

      relativePath.append(token2);

      parentCount++;

     }

    }

    // one or both are now out of tokens

    if(tokenizer1.hasMoreTokens()){

     parentCount+=tokenizer1.countTokens();

    } else if(tokenizer2.hasMoreTokens()){

     while(tokenizer2.hasMoreTokens()){

      relativePath.append(File.separator);

      relativePath.append(tokenizer2.nextToken());

     }

    }

    // now append parent paths or self path

    if(parentCount>0){

     for(int index=0;index

      relativePath.insert(0,PARENT_PATH);

      relativePath.insert(0,File.separator);

     }

     relativePath.insert(0,PARENT_PATH);

    } else{

     relativePath.insert(0,SELF_PATH);

    }

    // add a path separator to the end of this

    if(absolutePath2.endsWith(File.separator)){

     relativePath.append(File.separator);

    }

   } else{ // need to return the absolute path

    return(absolutePath2);

   }

  }

  return(relativePath.toString());

 }

This is probably the most import piece of code in this whole thing - at least it has saved me the most time in converting images to tiles:

 public static int findNearestColor(ArrayList colorList,String color){

  int index=colorList.indexOf(color);

  if(index>-1){return(index);}

  int nearestColorIndex=0; //default to zero

  double nearestColorDistance=Math.sqrt((255^2)*3)+1D;

  for(int i=0;i<colorList.size();i++){

   double distance=colorDistance(colorList.get(i),color);

   if(distance==0D){return(i);} //this probably can't happen

   if(distance<nearestColorDistance){

    nearestColorIndex=i;

    nearestColorDistance=distance;

   }

  }

  return(nearestColorIndex);

 }

That gives us some tiles that look like:

; 0

dc.l $04444444

dc.l $40000000

dc.l $45214412

dc.l $42144644

dc.l $42214664

dc.l $45144611

dc.l $45146166

dc.l $45144644

; 1

dc.l $44444444

dc.l $00000000

dc.l $22222222

dc.l $55555554

dc.l $15414411

dc.l $64141122

dc.l $66412255

dc.l $46625555

[...]

And some patterns that look like this:

dc.w $4 ; 5 rows

dc.w $1 ; 2 columns

dc.w $0

dc.w $1

dc.w $2

dc.w $3

dc.w $4

dc.w $5

dc.w $6

dc.w $7

dc.w $8

dc.w $9

And after everything is glued together we get this:

Finished product

Now we have a rough idea of what Ys Book I&II would look like on the Sega Genesis. The colors look muted compared to the TurboGrafx-16 CD version. This is a 1:1 conversion and perhaps it could be made to look better if the image was optimized for the Genesis' palettes.

Let's look at the original vs Genesis palettes to see how some very small differences lead to this - the TurboGrafx-16 palette is the top row of these:

Palette 0 comparison

Palette 1 comparison

Palette 2 comparison

Palette 3 comparison

What's Next?

There are a couple possible things I'll tackle next:

1) Use these tools to freshen-up the appearance of the mall in Retail Clerk '89 for a sequel game.

2) Use these to build a Myst-like game in a completely different setting.

3) Grow bored of working with the Genesis and do something else.

All three of these are equally likely options.

Download

Here's the demo ROM with a couple extra scenes and a little music. It's a tad bloated because it's importing a lot of code used to build Retail Clerk '89 but only needs about 10% of it. This should run on any Genesis emulator and real hardware. It's not very exciting though.

Here's the unfinished and likely buggy Java code. The final Java build tools will be on my GitHub page eventually, likely but not definitely under a repository called RetailClerk90 when it exists.




Related