Vladimir Chavdarov
Tools and Gameplay Programmer
Embedded Files
Terrain Collider Algorithm
Terrain Collider Algorithm
During development, we found out that units push each-other a lot. This is normal in RTS games and is not a problem by itself. However, sometimes they pushed each-other into unwalkable tiles which caused them to "get lost". It also caused them to sometimes clip through static objects like buildings, rocks and walls which was not desired.
The goal of this feature was to combine the Physics System of our engine with the Terrain System to generate dynamic polygon colliders. This should be efficient enough to be called every time the terrain information changes - for example when constructing a new building.
Overview
Overview
The process takes place in a number of steps, all of which will be described below in greater detail and code snippets. The first, and maybe the most important part of the algorithm, is grouping adjacent unwalkable tiles together. Then each of these groups is traversed along its tiles' edges while we keep these edges' points. In the end, we reduce the amount of points so the collider is as simple as possible.
Step 1: Group Obstacle Tiles together
Step 1: Group Obstacle Tiles together
First, we need to determine which tiles on the terrain can be combined in a single collider. We do this to reduce the number of generated colliders as much as possible!
For the sake of readability and functionality, we create a local int vector where 0's represent walkable tiles and 1's represent unwalkable tiles:
// represent the terrain tiles as ints. 0 for walkable, 1 for unwalkable.
std::vector<int> allTiles;
for (const auto& tile : m_data->m_tiles)
{
if (tile.tileFlags & TileFlags::NoGroundTraverse)
allTiles.push_back(1);
else
allTiles.push_back(0);
}
Then, we call the recursive function FindColliderGroupsRecursive (I always put the keyword on recursive functions to save myself the headaches later):
// -----------------------------------------------------
// Step 1: Find the separate groups of unwalkable tiles.
// -----------------------------------------------------
// the groups of unwalkable tiles
std::vector<std::vector<int>> tileGroups;
std::vector<int> directions({1, -1, -1, 1}); // Up, down, left, right
for (int i = 0; i < allTiles.size(); i++)
{
std::vector<int> group;
FindColliderTileGroupRecursive(allTiles, group, i, directions);
if (!group.empty())
{
tileGroups.push_back(group);
}
}
The recursive function is written in such a way that it tries to "latch" onto an unwalkable tile and look for any adjacent unwalkable tiles so it can spread through them. The key part of that process is that the function swaps the value in the allTiles vector that we created initially - that way, it will never go through the same tile twice.
void lvle::TerrainSystem::FindColliderTileGroupRecursive(std::vector<int>& allTiles, std::vector<int>& tileGroup, const int tileIndexToInspect, const std::vector<int>& directions)
{
if (allTiles[tileIndexToInspect] == 1)
{
tileGroup.push_back(tileIndexToInspect);
// make current tile irrelevant to the searching algorithm.
allTiles[tileIndexToInspect] = 0;
// check if adjacent tiles are also unwalkable
for (int i = 0; i < directions.size(); i++)
{
glm::ivec2 tileCoords = IndexToCoords(tileIndexToInspect, m_data->m_width);
if (i < 2)
// up, down
tileCoords.y += directions[i];
else
// left, right
tileCoords.x += directions[i];
if (IsTileInTerrain(tileCoords))
{
int newIndexToInspect = CoordsToIndex(tileCoords, m_data->m_width);
FindColliderTileGroupRecursive(allTiles, tileGroup, newIndexToInspect, directions);
}
}
}
}
This function runs until all tiles are marked with 0 in the allTiles vector. After it is done, we have a vector of vectors of tile indices (or a vector of collider groups - std::vector<std::vector<int>> tileGroups)
Step 2 and 2.5: Find the outer edges of the outer tiles
Step 2 and 2.5: Find the outer edges of the outer tiles
Let's take a look at the image on the left. After executing step 1, we end up with a vector of the indices of all coloured cells. However, for a collider, we only need the outline, hence we only care about the outer cells, which are marked in red.
This part of the algorithm is encapsulated in the FindColliderEdgesPerTileInTileGroup function, which is called like so:
// ----------------------------------------------------------
// Step 2: Find outer edges for each outer tile in the group.
// ----------------------------------------------------------
std::vector<std::vector<std::pair<int, int>>> groupsEdges;
for (const auto& group : tileGroups)
{
std::vector<std::pair<int, int>> tileEdges;
FindColliderEdgesPerTileInTileGroup(group, tileEdges);
if (!tileEdges.empty()) groupsEdges.push_back(tileEdges);
}
To determine whether a cell is considered an "outer cell" we need to look at its neighbours in the terrain. If there is at least one neighbour that does not belong in the group, then we are looking at an outer cell. I use the following algorithm to determine that:
for (const auto tileIndex : group)
{
// check the 4 neighbors of the tile, looking for a neighbor that isn't part of the group.
std::vector<int> directions = {1, -1, -1, 1}; // Up, down, left, right
for (int i = 0; i < directions.size(); i++)
{
auto tileCoords = IndexToCoords(tileIndex, m_data->m_width);
if (i < 2)
// up, down
tileCoords.y += directions[i];
else
// left, right
tileCoords.x += directions[i];
int tileIndexToCheck = CoordsToIndex(tileCoords, m_data->m_width);
// add vertices if the neighbor tile isn't part of the group.
if (std::find(group.begin(), group.end(), tileIndexToCheck) == group.end() || !IsTileInTerrain(tileCoords))
{
// We found an outer cell!
// [...]
}
Next, we need to take this cell and determine which edges are exposed to the outside. We know that an outer edge is one that is shared with a cell which doesn't belong in the current group. Looking at the code above, we also notice that we iterate through the numbers in the following order: up, down, left, right.
Using the loop's iterator index i, we know exactly which edge is being checked. We can then use the tileIndex to calculate the indices of the two points that form the edge, within the terrain mesh.
In the following snippet, m_data is a repository for terrain-related data and m_width is the width of the terrain measured in tiles => (m_width + 1) is the width of the terrain measured in points. The snippet fills the if-statement of the previous one.
// add vertices if the neighbor tile isn't part of the group.
if (std::find(group.begin(), group.end(), tileIndexToCheck) == group.end() || !IsTileInTerrain(tileCoords))
{
enum Directions
{
Up,
Down,
Left,
Right
};
// vertex indices (A, B, C, D)
int x = tileIndex % m_data->m_width;
int y = tileIndex / m_data->m_width;
int a = x + y * m_data->m_width + y;
switch (i)
{
case static_cast<int>(Up): // C, D
{
int c = a + (m_data->m_width + 1) + 1;
int d = a + (m_data->m_width + 1);
result.push_back(std::pair<int, int>(c, d));
break;
}
case static_cast<int>(Down): // A, B
{
int b = a + 1;
result.push_back(std::pair<int, int>(a, b));
break;
}
case static_cast<int>(Left): // D, A
{
int d = a + (m_data->m_width + 1);
result.push_back(std::pair<int, int>(d, a));
break;
}
case static_cast<int>(Right): // B, C
{
int b = a + 1;
int c = a + (m_data->m_width + 1) + 1;
result.push_back(std::pair<int, int>(b, c));
break;
}
default:
break;
}
//
}
In the end, we end up with a vector of vectors of <int, int> pairs to store the outer edges for each collider group - std::vector<std::vector<std::pair<int, int>>> groupsEdges.
Step 3 and 4: Take the unique Corner points
Step 3 and 4: Take the unique Corner points
After executing the previous step, we have a vector of edges for each collider group. Let's assume the current collider group is the one on the left. We need some way of determining only the corner points. Notice how the only places where a corner point occurs is where the "direction" (going CCW) of the edges changes.
For this step, we use yet another function called FindColliderCorner points, which is called like so:
// -------------------------------------------------
// Step 3: Reduce points by taking only the corners.
// -------------------------------------------------
std::vector<std::vector<int>> groupsColliderPoints;
for (const auto& edgeGroup : groupsEdges)
{
std::vector<int> colliderCornerPoints;
FindColliderCornerPoints(edgeGroup, colliderCornerPoints);
if (!colliderCornerPoints.empty()) groupsColliderPoints.push_back(colliderCornerPoints);
}
In order to find at which points the direction of the edges changes, we first need a method for traversing the group edge by edge. This is important since the vector of pairs we get from the previous step isn't sorted in any way.
We start iterating the edge vector from the first index. Before the iteration, we also setup a direction enum, direction values and declare the starting direction which is Right (counter-clockwise):
int firstCornerIndex = edgeGroup[0].first;
result.push_back(firstCornerIndex);
int currentSecondPoint = edgeGroup[0].second;
enum Direction
{
Up, Down, Left, Right
};
Direction currentDirection = Direction::Right;
std::vector<int> directions = {m_data->m_width, -m_data->m_width, -1, 1};
In this code, the currentSecondPoint represents the second point in each pair that we'll iterate over. This is important because the second point in an arbitrary edge within the group is always the first point in another edge. This helps us traverse the vector in a way that follows the outline of the group edge by edge. We do this until we end up at the start (firstCornerIndex). Here is how it looks in code:
while (firstCornerIndex != currentSecondPoint)
{
// iterate through the edges in a CCW fashion.
// D <- C
// *--*
// | | | ^
// v | | |
// *--*
// A -> B
// find next tile edge ( A->B, B->C, C->D, D->A)
auto edge_it = std::find_if(edgeGroup.begin(), edgeGroup.end(),
[currentSecondPoint](const std::pair<int, int>& element)
{ return element.first == currentSecondPoint; });
currentSecondPoint = edge_it->second;
[...]
}
After we find the edge, we need to determine whether the direction changed between the current one and the last one. Since all we use is the indices of the points, we can calculate that using purely integer operations. First, we calculate the direction of the current edge by subtracting its two points. Then, we compare that direction with the direction of the previous edge. If they are NOT the same, it means that we are currently standing on a corner point and we should add it to the result vector. This is done in code like so (taking off right after the previous snippet):
if (edge_it != edgeGroup.end())
{
int indexDifference = edge_it->second - edge_it->first;
Direction edgeDirection = Direction::Up; // just a default value. The next if-statement will always return true once.
for (int i = 0; i < directions.size(); i++)
{
if (indexDifference == directions[i]) edgeDirection = static_cast<Direction>(i);
}
// if the direction changed, we found a corner point
if (currentDirection != edgeDirection)
{
currentDirection = edgeDirection;
result.push_back(edge_it->first);
}
}
Bonus Step 5: Creating the Collider
Bonus Step 5: Creating the Collider
After following all the steps above, we end up with a vector of points for each collider group on the terrain. The points are also sorted in a counter-clockwise fashion, which is important because that is the order required by the Physics System in our engine.
The collider itself is created by the Physics System in order to keep proper separation of responsibility. The Terrain System only needs to provide the correct data, nothing more.
In the code, we call one final function that makes use of the of the Entity Component System to create a "Collider Entity":
bee::Entity lvle::TerrainSystem::CreateTerrainColliderEntity(const std::vector<int>& pointsIndices, const std::string& name)
{
// make a vector with the actual coordinates
std::vector<glm::vec2> colliderPoints;
for (const auto index : pointsIndices) colliderPoints.push_back(m_data->m_vertices[index].position);
auto colliderEntity = Engine.ECS().CreateEntity();
auto& transform = Engine.ECS().CreateComponent<bee::Transform>(colliderEntity);
transform.Translation = vec3(0.0f);
transform.Name = name;
auto& body = Engine.ECS().CreateComponent<bee::physics::Body>(colliderEntity, bee::physics::Body::Type::Static, 1.0f, 0.0f);
auto& polygonCollider = Engine.ECS().CreateComponent<bee::physics::PolygonCollider>(colliderEntity, colliderPoints);
return colliderEntity;
}
Conclusion
Conclusion
Coming up with this algorithm was a wonderful programming exercise that had strong practical impact, while working on Owlet. I am proud of how it turned out and of the purpose it served within the project! my goal for it was to be as modular as possible as well as easy to use by other developers. As you saw, the logic inside is convoluted and there is no need for others to be directly exposed to it - they only need to know how to use it. Even though I think the solution is quite elegant, there are obviously parts that feel a bit clunky and could be better streamlined. Problems like always grind my gears and I would always take up on such a challenge.
Page updated
Google Sites
Report abuse