Friday, December 31, 2010

DotNetFish - Optimizing the Tiling Routines

I made an optimization to the tiling routine and pushed the changes up to Github. Let me take a minute to explain what change I made. Orginally, I was writing each tile to the large bitmap, and then going through the bitmap pixel by pixel, and determining if the pixel needed to be set to white or black. Now I am doing the following.
  1. Create two new bitmaps, all black and all white
  2. instead of writing the tile directly to the bitmap, manipulate the 256x256 tile
  3. check the edges of the bitmap for water
  4. if the bitmap edge has both water and land, then you have to scan each pixel and change it from black to white. 
  5. otherwise you can just use the all black or all white bitmaps.
This has a few advantages. Instead of having to check  65k pixels per tile for tiles that only have all water or all land, you only have to check 1024. Now then, This takes me pretty far along the path of optimization. Its still a bit slow though. In order to improve the speed I will need to drop into using, pointers, and bitmapdata. I suggest you take a look at this article Bob Powell's website Understanding Locking Bits and The BitmapData Class He has a very good faq regarding GDI+ and I have used it every time I have ever had to manipulate graphics in GDI+. Its a bit complicated, but basically, we are going to manipulate an array of pixel values instead of the pixels themselves, which cuts out a bunch of the overhead. Here is the relevant code to get the bitmap data
BitmapData bmpData = bitmap.LockBits(
    new Rectangle(0, 0, bitmap.Width, bitmap.Height),
    ImageLockMode.ReadWrite,
    PixelFormat.Format32bppArgb);
            
//This is a pointere that referenece the location of the first pixel of data 
System.IntPtr Scan0 = bmpData.Scan0;

//calculate the number of bytes
int bytes = bmpData.Stride * bitmap.Height;

//An array of bytes. Just remember that each pixel format has a different number of bytes.
//In our case, the number of bytes is 4 per pixel or RGBA. 
byte[] rgbValues = new byte[bytes];

//Safely copying the data to a managed array
System.Runtime.InteropServices.Marshal.Copy(Scan0,
                rgbValues, 0, bytes);
The above code gets the bitmap data. After that we would loop through the edges looking for the different tile types. The important line here is the position, that makes sure we grab the right values for each pixel
//Loop though all of the pixels on the Y edge
for (int y = 0; y < bitmap.Height; y+=255)
{
    for (int x = 0; x < bitmap.Width; x+=5)
    {
        int position = (y * bmpData.Stride) + (x * 4);

        retval = IsWater(rgbValues[position], rgbValues[position + 1], rgbValues[position + 2]);

        if (retval == true)
            hasWater = true;
        else 
            hasLand = true; 

        if (hasLand && hasWater)
            break;
    }
        if (hasLand && hasWater)
            break;
}
We do the same thing for the x edges if we havent already detected both water and land.. Lastly, here is how we set the color values.
private void PaintTile(int height, int width, ref byte[] rgbValues, int stride)
{
    for (int x = 0; x < width; x++)
    {
        for (int y = 0; y < height; y++)
        {
            int position = (y * stride) + (x * 4);

            if (rgbValues[position] == 204 && rgbValues[position + 1] == 179 && rgbValues[position + 2] == 153)
                rgbValues[position] = rgbValues[position + 1] = rgbValues[position + 2] = 255;
            else
                rgbValues[position] = rgbValues[position + 1] = rgbValues[position + 2] = 0;
        }
    }
} 
I used a reference type here instead of a value. Its a better choice here since as soon as this method is called the data gets saved back into the bitmap using the following code
//Save the manipulated data back to the bitmap.
System.Runtime.InteropServices.Marshal.Copy(rgbValues, 0, Scan0, bytes);
bitmap.UnlockBits(bmpData);
Make sure you always call UnlockBits when you are done! Go grab commit 3a8f1b95c1a6fd1bd1e8053 if you want to see what the project looks like up to this point.

No comments:

Post a Comment