xnaFan's Blog

Whew... that title is a tongue-twister , but it is nonetheless as precise as I can describe this way of keeping track of what to render.

If your game-world is tilebased, you can pretty much rely on finding out what tiles the corners of your screen is in, and then render all the tiles in the columns and rows between and including those four tiles.

BUT ... if your objects have random positions and sizes, it may be hard to figure out what to draw (because it is within your screen's borders) and what not to draw (because it is in a part of the world that is currently not visible on the player's screen).

This tutorial will give you an understanding of how you can optimize what your graphics adapter spends its time rendering, but only for your stationary objects. The reason this algorithm can not be used for moving objects is that the calculations for the optimization are performed at startup, and then that data is used every time you redraw the screen.

If you want to optimize rendering of moving objects, then you can look into the quadtree algorithm (javascript visualization). Here's a C# implementation.

The algorithm

1. Split your entire world into a number of rectangles (a number of rows and columns)
2. For each rectangle in your world
1. create a list to hold the objects which are even partly visible in that rectangle
3. For each stationary items in your world
1. find all the rectangles that the item is even partly in
2. add the item to those rectangles' lists

Algorithm visualization

Here you can see the result of

1. splitting the world into 2 rows and 2 columns
2. adding all the items to lists for each rectangle resulting in four lists with 4, 5, 6 and 4 items in (of which 3 items are in more than one list)

This means that if our screen is entirely in the bottom right quarter of our world, we only have to render 4 items out of 15 - giving us a 73% decrease in items rendered!

Let's see this in action

The code

Here is the code which initializes a Dictionary which enables me to find a List<Sprite> quickly by looking it up in the Dictionary with a given Rectangle,

//the dictionary which holds the list of sprites that overlap a given rectangle
Dictionary<Rectangle, List<Sprite>> _rectangleListDictionary 
    = new Dictionary<Rectangle, List<Sprite>>();

Here's the code which generates the rectangles

void SplitMapIntoSegments(Vector2 worldSize, int columns, int rows)
{
    Rectangle[,] rectangles = new Rectangle[columns, rows];
    int screenSegmentWidth = (int)(worldSize.X / columns);
    int screenSegmentHeight = (int)(worldSize.Y / rows);

    for (int x = 0; x < columns; x++)
    {
        for (int y = 0; y < rows; y++)
        {
            rectangles[x, y] = new Rectangle(x * screenSegmentWidth, y * screenSegmentHeight, screenSegmentWidth, screenSegmentHeight);
        }
    }
    _rectangles = rectangles;
}

And the code for adding all items in the gameworld to the rectangles they are partly in

//loops through all rectangles that the map is currently split into
//finds all sprites that overlap a given rectangle and adds them to a list
//adds the list to the RectangleDictionary with the rectangle as key, for fast lookups later
void AddSpritesToListsInRectangleDictionary()
{
    _rectangleListDictionary.Clear();

    for (int x = 0; x <= _rectangles.GetUpperBound(0); x++)
    {
        for (int y = 0; y <= _rectangles.GetUpperBound(1); y++)
        {
            List<Sprite> spriteListForThisRectangle = new List<Sprite>();
            Rectangle currentRectToCheckSpritesFor = _rectangles[x, y];

            foreach (var sprite in _sprites)
            {
                if (currentRectToCheckSpritesFor.Intersects(sprite.Bounds))
                {
                    spriteListForThisRectangle.Add(sprite);
                }
            }

            _rectangleListDictionary.Add(currentRectToCheckSpritesFor, spriteListForThisRectangle);
        }
    }
}

Source code

Here is the sample project (vs2010 and XNA 4.0).

This entry was posted on Wednesday, March 27th, 2013 at 22:20 and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.