Optimising Collision Testing

So having the ability to load and display maps via my Tiled Map Loader is all well and good, but I need to interact with the loaded map, and I need to do it efficiently. I decided the best place to start was to take advantage of Tiled's object format, which I did by creating different layers in my map to represent different interactions. The most common of these is collision detection between the player and the map geometry, and is key to the feel of the game play, be it with solid objects, variations in terrain or transitions to other maps. The problem with this is that on a large map there can be literally hundreds of objects, all of which potentially need to be tested for collisions. Collision detection operations are usually quite expensive on the CPU, particularly when it comes to physics interactions, so reducing the number of tests to a minimal is a really important. I found the simplest reduction was to ignore everything not visible on screen, which was a good start when I had a single sprite / player to test against the rest of the map, but with multiple sprites or NPCs which exist off screen and must still update their map interactions this approach is less suitable. For instance there may be 200 objects on a map, 50 of which are on screen at any one time. Testing these against a single player is a good increase in efficiency, even if only 10 of those objects are close enough to potentially collide. Much of this gain is lost, however, when introducing more players. Four players on the screen will send the test count right back up to 200 again (each of the 50 objects gets tested 4 times, once against each player) which is not optimal. The answer was to employ a more suitable space partitioning system, and in this case I chose to use a quad tree. This works by recursively dividing a 2D space into smaller partitions, grouping any map objects into 'quads'. Using the position of the player sprite it's now much easier to decide which map objects I want to test for collision by looking at only those contained within quads which contain or intersect the area occupied by the player sprite. Google provides many useful and interesting articles, and I found this one in particular describes a method simple yet effective enough to solve my problem. By creating a single class which creates a tree 'node' it recursively partitions itself and adds child nodes as necessary to group map objects much more efficiently than merely culling every object not on screen. Further to that a tree of these nodes need only be created once per frame, and can be queried multiple times by different sprites. Using the four player scenario as an example again the tree could be queried 4 times, once for each player, and return only the nearest objects to that player. As this is usually between 0 and 10 (depending on the map) the total number of objects to test for collision per frame is reduced from 200 to anywhere between 0 and 40 - a vast improvement. Here is a video of it in action, the green boxes representing partitions created by the tree, and red boxes representing the partitions which actually return anything for testing (the jerkiness is an unfortunate side effect of the capture software).

I've made this a feature of my map loader class which I've updated and made available here (and is still available via the original link in my last post). Using the quad tree is optional too, if you decide it is unnecessary for your project then just don't call any of its functions (there are still some scenarios where the overhead of creating a tree each frame is more than the overhead of testing every object - although which those are is a judgement call). If you do wish to use it then there are only 2 important functions. First you must update the tree's root node, which I usually do by passing the viewable area (although you can of course pass in any area, including space which is currently off-screen).

ml.UpdateQuadTree(sf::FloatRect(0.f, 0.f, 800.f, 600.f));

If you use an sf::View to move around your map then you'll want to call the update function every frame passing in the new visible area. In my tests I've passed a 1080p view to it at 60fps and had no performance problems. It is important to note that this must be called at least once before attempting to query the tree's data, else it will throw an exception.

Once the tree is updated it is ready to be queried, and can be done so multiple times. The query function returns a vector of pointers to MapObjects, which can then be used for any collision testing. To query the tree use:

std::vector<MapObjects*> objects = ml.QueryQuadTree(testArea);

The parameter testArea is a sf::FloatRect representing the area of potential collision, usually the bounding box of a player sprite. Instead of testArea you could use sf::Sprite::getGlobalBounds() for example. You can then perform collision testing on each of the MapObjects pointed to by the returned vector. For a more detailed and practical example look at the demos and source included in the map loader archive.