Collision Detection with Tiled maps
I've had a few questions about how to perform collision detection on maps loaded with the Tiled map loader for SFML, so I'm going to attempt to explain how I personally manage collision detection with the usual caveat that there are most likely much better ways to do it (some of which I've already discovered and will have utilities available for them in the next update). I should also point out that this post is only about detection, and not handling the collisions. Not all collisions are about solid objects; you may also want to add triggers for events, or terrain changes to a map such as slowing down a player walking through quicksand. The functions provided by the map loader are more suited to some cases than others.
The first thing of note is that the method I use is not based on per-tile collisions. Traditionally tile maps contain IDs for each tile which allow you to pick a tile type simply by querying the position in the world and looking up the corresponding tile. The reason I don't use this method is due in part to the fact that there is no discreet tile data stored once the map is loaded and the layers are drawn using a vertex array for each tile set (see here). It is completely possible to store such data, and I may add the functionality in the future should I decide I need it. The main reason, however, is down to the fact that Tiled offers us an alternate approach with the use of map objects.
Within the Tiled editor you can add a new Object Layer, upon which you can draw simple primitives, fairly complex polygons or even stamp tiles from a tile set. This offers (in my opinion) more flexibility as collision areas are not limited to either the size nor the shape of a single tile. Object layers are also light and fast so it's no problem to create a single layer to contain all your solid objects, another for triggers, another for terrain changes and so on... Each object also has customisable options which are added via its properties tab, allowing you to name it and add custom data pairs. For example you may wish to add the name of a target entity to a trigger object, and the name of an action to take when the collision is triggered. All of these properties as well as a few utilities are exposed by the map loader via the MapObject class.
The most common functions of the MapObject I use for collision detection are Contains(point) and Intersects(MapObject). Both return a boolean when queried with a single point in map space coordinates (such as a point attached to a sprite or player) or another MapObject. If you're wondering about attaching collision points to a sprite, I based my method on this article. Rather than using pixel coordinates, however, I create a std::array of sf::vector2f which represent points in local sprite coordinates. For example a top down racing game may have 4 points on a vehicle, one at each corner:
sf::vector2f(-20.f, -30.f);
sf::vector2f(20.f, -30.f);
sf::vector2f(20.f, 30.f);
sf::vector2f(-20.f, 30.f);
This assumes a sprite sized 40 x 60. By adding a point to the sprite's position you then get the world coordinate for the 'collision point'. This can then be submitted to MapObject::Contains().
There are two basic methods for retrieving a list of MapObjects for testing. The simplest is to use the loader's GetLayer() function. Each layer contains a vector of all its child objects, through which you can iterate and query. In pseudo code this looks like:
std::vector<MapLayer>& layers = map.GetLayers();
for(auto& layer : layers)
{
if(layer.type == tmx::ObjectGroup)
{
for(auto& obj : layer.objects)
{
if(layer.name == "collision")
{
for(auto& point : player.collisionPoints)
{
if(obj.contains(player.position + point))
{
//handle collision
break; //don't test more points than you need
}
}
}
else if(layer.name == "trigger")
{
//send trigger command to queue
}
}
}
}
So for every layer in the map we check to see if it is an ObjectGroup by querying its type. Then we test which kind of collision layer it is by checking its name. Names can be set in the layer properties of Tiled. If we find a layer we want to test, iterate over each object it contains, and test to see if any of the player's collision points are contained within the object.
While this works it can be uneconomic testing every single object on a map for collision. To take the top down racer example again we know that the vehicle is never going to collide with anything outside the viewable area, so we can ignore all off screen objects which is an immediate optimisation. To take this further we can use a spacial partitioning method to calculate which objects are close enough to a specific point or area (such as the area occupied by the player) and then test only those objects. The map loader offers a special class for doing this which implements the Quad Tree method of spacial partitioning. I wrote about its usage a few posts back, so I'll not reiterate here - just give you this link.
While having employed the latter method in most of my projects there are more advanced methods of collision testing, particularly when you need to handle physics. MapObjects are actually made up of a series of points which are used internally by the Contains() method and these points can be used in other ways. One example is to use these points to store a series of segments which make up the shape of that object. Coupled with the trajectory vector of a moving object we can calculate which segment of the shape was intersected and from which direction - which, in turn, allows calculation of a normal vector about which the trajectory can be reflected. This is something I am currently working on, based on this article at Wild Bunny (a site which, by the way, you should read in its entirety - particularly this as you're evidently here to read about collision detection).
You can also, of course, farm out physics handling to a library such as box2D, a few simple functions will allow you to convert the list of points which make up the MapObject into a series of polygons which box2D will treat as a solid objects for you. I won't cover the details here as it is out of the article's scope, however.
Of course not all collisions have to be about solid objects. I mentioned earlier a trigger based system. If I assume you've read the SFML Development book (and why wouldn't you?) then your engine will likely contain a node graph system as well as a command stack for addressing entities within the graph. Using MapObjects it is relatively simple to, upon collision, create a new command based on the MapObjects properties, place it on the stack, and have it affect the target entity. Perhaps you would want to open a door when standing in a specific spot, or have the player only able to 'use' something when they are close enough (ie within the trigger area).
On their own the included MapObject functions are also useful for times when a player needs to be dealt damage, perhaps because they are standing in lava, or falling onto spikes.
Hopefully this will give you some idea about how the rudimentary collision detection is done within the map loader. I've tried to leave the classes as extensible as possible to aid adding custom functionality or just improve what already exists. If anyone has any other techniques they would like to offer or suggest, please feel free to post them in the comments.
The first thing of note is that the method I use is not based on per-tile collisions. Traditionally tile maps contain IDs for each tile which allow you to pick a tile type simply by querying the position in the world and looking up the corresponding tile. The reason I don't use this method is due in part to the fact that there is no discreet tile data stored once the map is loaded and the layers are drawn using a vertex array for each tile set (see here). It is completely possible to store such data, and I may add the functionality in the future should I decide I need it. The main reason, however, is down to the fact that Tiled offers us an alternate approach with the use of map objects.
Within the Tiled editor you can add a new Object Layer, upon which you can draw simple primitives, fairly complex polygons or even stamp tiles from a tile set. This offers (in my opinion) more flexibility as collision areas are not limited to either the size nor the shape of a single tile. Object layers are also light and fast so it's no problem to create a single layer to contain all your solid objects, another for triggers, another for terrain changes and so on... Each object also has customisable options which are added via its properties tab, allowing you to name it and add custom data pairs. For example you may wish to add the name of a target entity to a trigger object, and the name of an action to take when the collision is triggered. All of these properties as well as a few utilities are exposed by the map loader via the MapObject class.
 |
| Tile object editor. Note object layers on the right |
The most common functions of the MapObject I use for collision detection are Contains(point) and Intersects(MapObject). Both return a boolean when queried with a single point in map space coordinates (such as a point attached to a sprite or player) or another MapObject. If you're wondering about attaching collision points to a sprite, I based my method on this article. Rather than using pixel coordinates, however, I create a std::array of sf::vector2f which represent points in local sprite coordinates. For example a top down racing game may have 4 points on a vehicle, one at each corner:
sf::vector2f(-20.f, -30.f);
sf::vector2f(20.f, -30.f);
sf::vector2f(20.f, 30.f);
sf::vector2f(-20.f, 30.f);
This assumes a sprite sized 40 x 60. By adding a point to the sprite's position you then get the world coordinate for the 'collision point'. This can then be submitted to MapObject::Contains().
 |
| Tile map rendered in game with debug info on |
There are two basic methods for retrieving a list of MapObjects for testing. The simplest is to use the loader's GetLayer() function. Each layer contains a vector of all its child objects, through which you can iterate and query. In pseudo code this looks like:
std::vector<MapLayer>& layers = map.GetLayers();
for(auto& layer : layers)
{
if(layer.type == tmx::ObjectGroup)
{
for(auto& obj : layer.objects)
{
if(layer.name == "collision")
{
for(auto& point : player.collisionPoints)
{
if(obj.contains(player.position + point))
{
//handle collision
break; //don't test more points than you need
}
}
}
else if(layer.name == "trigger")
{
//send trigger command to queue
}
}
}
}
So for every layer in the map we check to see if it is an ObjectGroup by querying its type. Then we test which kind of collision layer it is by checking its name. Names can be set in the layer properties of Tiled. If we find a layer we want to test, iterate over each object it contains, and test to see if any of the player's collision points are contained within the object.
While this works it can be uneconomic testing every single object on a map for collision. To take the top down racer example again we know that the vehicle is never going to collide with anything outside the viewable area, so we can ignore all off screen objects which is an immediate optimisation. To take this further we can use a spacial partitioning method to calculate which objects are close enough to a specific point or area (such as the area occupied by the player) and then test only those objects. The map loader offers a special class for doing this which implements the Quad Tree method of spacial partitioning. I wrote about its usage a few posts back, so I'll not reiterate here - just give you this link.
While having employed the latter method in most of my projects there are more advanced methods of collision testing, particularly when you need to handle physics. MapObjects are actually made up of a series of points which are used internally by the Contains() method and these points can be used in other ways. One example is to use these points to store a series of segments which make up the shape of that object. Coupled with the trajectory vector of a moving object we can calculate which segment of the shape was intersected and from which direction - which, in turn, allows calculation of a normal vector about which the trajectory can be reflected. This is something I am currently working on, based on this article at Wild Bunny (a site which, by the way, you should read in its entirety - particularly this as you're evidently here to read about collision detection).
You can also, of course, farm out physics handling to a library such as box2D, a few simple functions will allow you to convert the list of points which make up the MapObject into a series of polygons which box2D will treat as a solid objects for you. I won't cover the details here as it is out of the article's scope, however.
Of course not all collisions have to be about solid objects. I mentioned earlier a trigger based system. If I assume you've read the SFML Development book (and why wouldn't you?) then your engine will likely contain a node graph system as well as a command stack for addressing entities within the graph. Using MapObjects it is relatively simple to, upon collision, create a new command based on the MapObjects properties, place it on the stack, and have it affect the target entity. Perhaps you would want to open a door when standing in a specific spot, or have the player only able to 'use' something when they are close enough (ie within the trigger area).
On their own the included MapObject functions are also useful for times when a player needs to be dealt damage, perhaps because they are standing in lava, or falling onto spikes.
Hopefully this will give you some idea about how the rudimentary collision detection is done within the map loader. I've tried to leave the classes as extensible as possible to aid adding custom functionality or just improve what already exists. If anyone has any other techniques they would like to offer or suggest, please feel free to post them in the comments.
Comments
Post a Comment