Improving cell loading times by being not stupid

A very important function for every roguelike is the one that retrieves the character/fore color/back color of a tile, which could be saved in a large instance of a Tile-class, or, in the case of SH2RL, in a byte which represents a certain large instance of a Tile-class  ("conversion" is handled with a Byte - Tile dictionary). This function is called several thousand times in the rendering pipeline. In SH2RL's case with a default viewport of 100*80, a whopping 6076 times! (I actually had to reduce the viewport's size, because with 150*80 and 12000 calls the rendering took more than 100ms, which was noticeably "laggy").

While implementing the "GetTileFromCell"-function the first time I just hacked in the first thing that I thought of:

1. Retrieve the unique ID of the cell at the given absolute coordinates (abs_x, abs_y, abs_z)
2. Loop through the three-dimensional array of cells currently loaded and look for an ID match
3. Once the match is found, call the cells "GetTile"-function and return it's value

Now, when I tested the "game" with this function, the following occurred:

Notice that the drawing time was ~62ms if the player was in the upper left corner of the "beige" cell (which is pretty damn long already) but with ~114ms almost 100% higher if the player was in the lower right corner of the "light green" cell, and consequently unacceptably long.
I immediately suspected my GetTileFromCell-function was to blame for this wierd discrepancy in drawing time, because it was basicially the only function called in the rendering process (except for the actual printing function).
This is how the function looked:

private Tile getTileFromCells(int abs_x, int abs_y, int abs_z)
{
    Cell relevantCell;
    int relCellID;


    relCellID = wm.GetCellIDFromCoordinates(abs_x, abs_y, abs_z);


    for (int x = 0; x < 3; x++)
    {
        for (int y = 0; y < 3; y++)
        {
            for (int z = 0; z < 3; z++)
            {
                if (cells[x, y, z].CellID == relCellID)
                {
                    relevantCell = cells[x, y, z];

                    return relevantCell.GetTile(abs_x, abs_y, abs_z);
                }
            }
        }
    }

    return null;
}

As you can see, if the coordinates in question were, say, in the cell at [1,1,1], this function would have to loop though 13 other cells first. Also, the "GetCellIDFromCoordinates" probably took some time as well. Normally, this would not be a problem and the function totally sufficient (if ineffective), but if you call it several thousand times per second, every bit of performance counts.

After some thinking (and facepalming) I came up with this function:

private Tile getTileFromCells(int abs_x, int abs_y, int abs_z)
{
    int x = 0, y = 0, z = 0;
    x = (int)((abs_x - cells[0, 0, 0].X) / WorldMap.CELL_WIDTH);
    y = (int)((abs_y - cells[0, 0, 0].Y) / WorldMap.CELL_HEIGHT);
    z = (int)((abs_z - cells[0, 0, 0].Z) / WorldMap.CELL_DEPTH);

    return cells[x, y, z].GetTile(abs_x, abs_y, abs_z);
                     
}        

The solution was really damn simple (As is often the case when you re-evaluate your code. When you actually write it, it's always the most complicated shit you come up with). All it does is substract the absolute coordinates of the leftmost (X), uppermost (Y), lowest (Z) cell from the requested absolute coordinates (which results in the coordinates relative to the current Map) and then divides the results by the width/height/depth of a cell. This produces the index of the cell holding the tile at the requested coordinates. After implementing this, the performance has doubled (for top left of cell: 60ms -> 30ms) to quadrupled (for bottom right of cell 120ms -> 30ms) and is no longer dependant on the players position.

SUCCESS!

First time I felt the need to do an awkward victory dance, which is not documented here. Probably for the better.