301 Days (redux)

Another metric leap year of gamedev experiments and such

Day 2 - Stripes and Chunks

Jul 27, 2015 - 5 minute read - OldDaysste-reez-muvi

Now let’s actually get down to the business of optimizing the map instantiation.


Beetlejuice suggests stripes

Just pairing up blocks with the same graphic got us down to 8007 instantiations. What if we combine any band of all-the-same-graphic blocks into a single “stripe”?
As we make a block, we’ll just look down the line and stretch to cover any duplicates, then skip instantiating them.

But first we need to know that we’re going through the cells in a useful order. The Dictionary of cells we get is keyed on a string which describes the position:

public void Add(Cell cell)
    this.cells.Add("" + cell.X + "," + cell.Y + "," + cell.Z, cell);

which is fine but we don’t want to have to do a lot of position<->string transformations when looking things up. So let’s make a dictionary based on Vector3 and copy it there:

List<string> cellKeyList = new List<string>(ourMap.cells.Keys);
Dictionary<Vector3, Cell> cells = new Dictionary<Vector3, Cell>();
Dictionary<Vector3, bool> cellNeedsTransform = new Dictionary<Vector3, bool>();
foreach (string k in cellKeyList) {
    Vector3 mapPosition = new Vector3(ourMap.cells[k].X, ourMap.cells[k].Y, ourMap.cells[k].Z);
    cells[mapPosition] = ourMap.cells[k];
    cellNeedsTransform[mapPosition] = true; // Every cell needs a transform by default

We also made a convenient parallel Dictionary to keep track of whether a cell actually needs a Transform. I know Vector3 is overkill here (these are integer cell positions), so we’ll refactor that once we settle on the algorithm. Next we need to make sure we traverse the cell positions in a well-defined order (we’ll use Z.Y.X increasing), which takes a little magic because Vector3 doesn’t have a predefined sort order:

// Make a list of the cells sorted by coordinates:
List<Vector3> cellsKeys = new List<Vector3>(cells.Keys);
    delegate(Vector3 p1, Vector3 p2) {
        int compareV = p1.z.CompareTo(p2.z);
        if (compareV == 0) {
            compareV = p1.y.CompareTo(p2.y);
            if (compareV == 0) {
                compareV = p1.x.CompareTo(p2.x);
        return compareV;

Now we can actually instantiate the blocks/stripes:

cell_transforms = new Dictionary<Vector3, Transform>();
foreach (Vector3 v in cellsKeys) {
    if (cellNeedsTransform[v]) {
        // Instantiate this one
        Vector3 position = new Vector3((-1f) * cells[v].X, (-1f) * cells[v].Y, cells[v].Z);
        Transform tempts = Instantiate(prefab, 
                                       Quaternion.identity) as Transform;
        print("Adding map position " + v + " to cell_transforms!");
        cell_transforms[v] = tempts;
        Renderer rend = tempts.GetComponent<Renderer>();
        rend.enabled = false;
        Material cellMaterial = null;
        for(int i = 0; i < cellMatString.Length; i++) {
            if (cells[v].DisplayGraphic == cellMatString[i]) {
                cellMaterial = cellMat[i];
        if (cellMaterial != null) {
            rend.material = cellMaterial;
            rend.enabled = true;
        } else {
            print("No match for cell display string \"" + cells[v].DisplayGraphic + "\"");
            rend.material = cellMat[0];
            rend.enabled = true;
        // Now check to see if blocks to the right can be skipped
        Vector3 nextCell = v + new Vector3(1f, 0f, 0f);
        while (cells.ContainsKey(nextCell) && cells[nextCell].DisplayGraphic == cells[v].DisplayGraphic) {
            tempts.position += new Vector3(-0.5f, 0f, 0f);
            tempts.localScale += new Vector3(1f, 0f, 0f);
            cellNeedsTransform[nextCell] = false;
            nextCell += new Vector3(1f, 0f, 0f);

Now we have a nice flag for whether the cell actually needs a Transform, so we can skip it if not. After each Transform we do make, we continue down the line as far as it’s the same DisplayGraphic, stretching our Transform and marking them as not needing their own Transforms. Does it work?

now 4914 blocks for 11945 cells now 4914 blocks for 11945 cells

It certainly seems to; we’re down to 4914 blocks and the map still looks right. Well, kind of; the textures are stretched instead of repeated. Let’s see if we can correct that, by bumping up the texture scale when we stretch the block.

while (cells.ContainsKey(nextCell) && cells[nextCell].DisplayGraphic == cells[v].DisplayGraphic) {
    tempts.position += new Vector3(-0.5f, 0f, 0f);
    tempts.localScale += new Vector3(1f, 0f, 0f);
    rend.material.mainTextureScale = new Vector2(tempts.localScale.x, 1f);
    cellNeedsTransform[nextCell] = false;
    nextCell += new Vector3(1f, 0f, 0f);
texture correction in effect texture correction in effect

Much better. Note that the use of the word “scale” here is kind of confusing; I initially assumed I had to decrease, not increase it. In the GUI it’s referred to as “tiling”:

mainTextureScale in GUI mainTextureScale in GUI

Ok, so we’re down to only having to instantiate about 41% of the cells. But we’re only combining in one dimension; will doing two help?

Day 2a code


Chunk gets called in Chunk gets called in

Now we should, after each instantiation, find the maximum x- and y-size to avoid duplication:

// Now check to find the best chunk:
int bestXSize = 1, bestYSize = 1, currXSize = 1, currYSize = 1;
// 	1. Find the maximum X size we could possible be
Vector3 nextCell = v + new Vector3(1f, 0f, 0f);
while (cells.ContainsKey(nextCell) && cellNeedsTransform[nextCell] && cells[nextCell].DisplayGraphic == cells[v].DisplayGraphic) {
    nextCell += new Vector3(1f, 0f, 0f);
//  2. Work down from the maximum possible X, evaluating the max possible Y at each X size
while (currXSize >= 1) {
    bool nextYGood = true;
    while (nextYGood) {
        for (int xOffset = 0; xOffset < currXSize; xOffset++) {
            nextCell = v + new Vector3((float) xOffset, (float) currYSize, 0f);
            if (!(cells.ContainsKey(nextCell) && cellNeedsTransform[nextCell] && cells[nextCell].DisplayGraphic == cells[v].DisplayGraphic)) {
                nextYGood = false;
        if (nextYGood) currYSize++;
    //  3. Keep track of the highest X*Y we've found so far
    if (currXSize * currYSize > bestXSize * bestYSize) {
        bestXSize = currXSize; bestYSize = currYSize;
print("Best size for cell " + v + " is " + bestXSize + "x, " + bestYSize + "y.");
//  4. Mark each cell we're absorbing
for (int yOffset = 0; yOffset < bestYSize; yOffset++) {
    for (int xOffset = 0; xOffset < bestXSize; xOffset++) {
        if (xOffset == 0 && yOffset == 0) continue;
        cellNeedsTransform[v + new Vector3((float) xOffset, (float) yOffset, 0f)]  = false;
//  5. Update the position, scale, and texture scale.
tempts.position += new Vector3(-0.5f * (bestXSize - 1), -0.5f * (bestYSize - 1), 0f);
tempts.localScale += new Vector3((float) (bestXSize - 1), (float) (bestYSize - 1), 0f);
// Uncomment for borders between the blocks:
// tempts.localScale -= new Vector3(0.1f, 0.1f, 0f);
rend.material.mainTextureScale = new Vector2(tempts.localScale.x, tempts.localScale.y);
now 3178 blocks for 11945 cells now 3178 blocks for 11945 cells

Looking good. We can uncomment that scale reduction and switch to an orthographic camera to get a good view of the chunks:

now 3178 visible blocks now 3178 visible blocks

A bit better than the stripes, though there are a few places where it’s still clearly not optimal.

Day 2b code