301 Days

A year of gamedev experiments.

Day 2 - Stripes and Chunks

| Comments

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


Stripes

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:

DS Map.cs
1
2
3
4
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:

1
2
3
4
5
6
7
8
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Make a list of the cells sorted by coordinates:
List<Vector3> cellsKeys = new List<Vector3>(cells.Keys);
cellsKeys.Sort(
    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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
cell_transforms = new Dictionary<Vector3, Transform>();
foreach (Vector3 v in cellsKeys) {
    num_cells++;
    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,
                                       position,
                                       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? 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.

1
2
3
4
5
6
7
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);
}

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”:

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


Chunks

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 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) {
    currXSize++;
    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;
    }
    currXSize--;
}
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);

Looking good. We can uncomment that scale reduction and switch to an orthographic camera to get a good view of the chunks: A bit better than the stripes, though there are a few places where it’s still clearly not optimal.

Day 2b code

Comments