Spatial Indexing for Fun and Performance


When trying to optimize your sprite engine and reduce the time needed to draw a frame, optimizing texture size and texture batching are all well and good but they won’t do much good if you’re simply trying to draw too many sprites at once. In order to maximize performance, it’s important to be able to quickly determine which sets of game objects actually need to be updated or drawn on any given frame. With a large, heavily-populated game world, only submitting to the GPU objects that will actually be on the screen can reap enormous performance gains.

One of the most common methods to determine which objects occupy a particular area of the game world is to implement a spatial index. There are many different algorithms that can be used to implement a spatial index, but in this post I’ll cover one of the simplest: a Grid index.

To demonstrate the benefits of a spatial index, I setup a demo that renders a large number of sprites of which only a small number are actually on the screen. Starting with the demo from my sprite scaling post, I modified it to create over 16,000 sprites and randomly position them in an area larger than the screen. Running the demo on an Xbox 360, you can see roughly 500 sprites rendered on screen but taking a dismal 27.5 ms per frame to draw.

We’ve dropped straight from 60 fps territory and we’re barely hanging on to 30 fps. This just from submitting the sprites to the GPU. We aren’t even trying to update or animate them. This is the kind of code that gets programmers fired (or promoted to management! Just kidding, of course).

So, now we try implementing a spatial index to improve this situation. Before getting to the Grid implementation, I start with an even simpler implementation to illustrate the usage of the spatial index: a straight list of all registered sprites.

The basic idea of the single-list spatial index is for all the sprites in the game world to be registered upon creation. Then, on every update, the spatial index creates a list of sprites on screen by iterating through its internal sprite list and producing a list containing only sprites whose bounding rectangles intersect with the screen’s rectangle. The game then uses the list created by the spatial index when performing sprite draw calls.

Even as brute-force an implementation as the single sprite list produces a dramatic performance improvement:

Wow, 5.8 ms per frame. That’s an almost 5x improvement. Obviously, the main reason for the performance improvement is that we are now only submitting 458 sprites to the GPU instead of the original 16,384. Even with the spatial index iterating over those same 16,384 sprites every frame, the performance increase is huge.

But, we can do even better. In the screenshot I display the amount of time the spatial index takes to calculate the visible set displayed in parentheses. While 5.8 ms is better than 27.5 ms, you can see we’re spending the majority of the 5.8 ms in the spatial index (4.5 ms). This is where the Grid implementation comes in.

The Grid implementation of the spatial index works by dividing the game world into a grid of cells. Each of the cells contains its own list of the game objects contained within that cell. When creating the list of visible sprites, the spatial index checks each cell against the screen rectangle and only includes sprites from the cells that intersects with the screen rectangle. By splitting the sprites into cells and checking the cells first for intersections, we can preemptively reject large numbers of sprites with a single check.

With a cell size of 64×64 we get the following results:

A frame draw time of 1.4 ms with only about 0.4 ms spent in the spatial index. Now that’s what I’m talking about.

You may notice that the layering of the sprites is different from the second screenshot to the third. This is because the Grid spatial index ends up changing the order of the sprites in the list used when issuing sprite batch draw calls. To solve this problem, you will need a sorting solution to control sprite depth. Setting SpriteModeSort.BackToFront in SpriteBatch.Begin() and defining a 0.0 – 1.0 depth for each sprite is probably the easiest method to implement and should be suitably performant. Thankfully, we now have more than enough performance to spare for it.

You can see my spatial index implementation below:

#define USE_GRID_INDEX

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace TimingTest
{
#if USE_GRID_INDEX
    class GridInfo
    {
        public Rectangle GridRect;
        public List<TileSprite> GridItems;

        public GridInfo(int x, int y, int width, int height)
        {
            GridRect = new Rectangle(x, y, width, height);
            GridItems = new List<TileSprite>();
        }
    }
#endif
    public class SpatialIndex
    {
#if USE_GRID_INDEX
        const int GRID_CELL_WIDTH = 256;
        const int GRID_CELL_HEIGHT = 256;

        List<GridInfo> gridInfos;
#else
        List<TileSprite> itemList;      //The one-list dumb implementation
#endif
        public SpatialIndex()
        {
#if USE_GRID_INDEX
            gridInfos = new List<GridInfo>();
#else
            itemList = new List<TileSprite>();
#endif
        }

        public void RegisterItem(TileSprite item)
        {
#if USE_GRID_INDEX
            GridInfo targetGridInfo = null;

            int gridInfoCount = gridInfos.Count;
            for (int i = 0; i < gridInfoCount; ++i)
            {
                if (gridInfos[i].GridRect.Contains((int)item.Position.X, (int)item.Position.Y))
                {
                    targetGridInfo = gridInfos[i];
                    break;
                }
            }

            if (targetGridInfo == null)
            {
                int gridStartX = ((int)item.Position.X / GRID_CELL_WIDTH) * GRID_CELL_WIDTH;
                int gridStartY = ((int)item.Position.Y / GRID_CELL_HEIGHT) * GRID_CELL_HEIGHT;

                targetGridInfo = new GridInfo(gridStartX, gridStartY, GRID_CELL_WIDTH, GRID_CELL_HEIGHT);
                gridInfos.Add(targetGridInfo);
            }
            System.Diagnostics.Debug.Assert(targetGridInfo != null);
            targetGridInfo.GridItems.Add(item);
#else
            itemList.Add(item);
#endif
        }

        public void GetItemsInRect(ref List<TileSprite> items, Rectangle rect)
        {
            items.Clear();

#if USE_GRID_INDEX
            int gridInfoCount = gridInfos.Count;
            for (int i = 0; i < gridInfoCount; ++i)
            {
                if (rect.Intersects(gridInfos[i].GridRect))
                {
                    int itemCount = gridInfos[i].GridItems.Count;
                    for (int j = 0; j < itemCount; ++j)
                    {
                        if (rect.Intersects(gridInfos[i].GridItems[j].BoundingRect))
                        {
                            items.Add(gridInfos[i].GridItems[j]);
                        }
                    }
                }
            }
#else
            int itemCount = itemList.Count;
            for (int i = 0; i < itemCount; ++i)
            {
                if (rect.Intersects(itemList[i].BoundingRect))
                {
                    items.Add(itemList[i]);
                }
            }
#endif
        }
    }
}
Share this Article:
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Print