Selective grid erosion/preventing multicell characters from intersecting?

We have a case where characters in grid-based pathfinding have a size (i.e. take up more than one grid cell). To make this work, we used erosion to specify tags where “character of size X can stand”. We also use Grid Update Objects to block/unblock areas of grid where characters stand, and update erosion accordingly.

However, after some testing, it was determined that we don’t need erosion for all geometry in level - only for characters. I.e. character of any size can stand near the wall, but no character should be able to intersect with another character (which means their centers must remain R1+R2 meters apart).

I’m not sure how to implement this. I don’t think the erosion mechanics support anything like this selective application?

My current idea is to have my own copy of grid, which is updated at the beginning of turn for every character, in which cells that character shouldn’t be able to enter due to his size will be marked, and then use TraversalProvider to query this grid. But I don’t like the idea of storing a separate grid for that, seems somewhat inelegant. Maybe there is a solution I’m missing within this project’s API?

OK. the my initial idea was not workable: to calculate cells the character can traverse, I need the whole erosion process, so creating a separate non-Astar grid would be quite non-trivial.

In the end, I had to solve this by modifying the library’s code: I added a field erosionOnlyAroundCellsWithTag to GridGraph, and changed ErodeNodeWithTagsInit to avoid resetting this tag (frankly, it should never erase any tags that are greate than erosionFirstTag + erodeIterations) and ErosionAnyFalseConnections. The last change is slightly non-trivial: I added the following code to direction loop (for 4 directions):

if (erosionOnlyAroundCellsWithTag > 0 && !HasTagInDirection(node, i, erosionOnlyAroundCellsWithTag))

This code will prevent non-walkable cells which are not marked with special tag from participating in erosion calculation. HasTagInDirection gets a neighbour cell in specified direction WITHOUT checking if there is a connection (because in my case only unwalkable cells - blocked by other characters - are marked with the special tag):

int newIndex = node.NodeInGridIndex + neighbourOffsets[dir];
if (newIndex < 0 || newIndex >= nodes.Length)
    return false;

var neighbour = nodes[newIndex];
return neighbour.Tag == tag;

Then I made my Graph Update Objects set/reset tags when they mark cells blocked by a character, and that’s the whole thing.

1 Like