1
\$\begingroup\$

I am developing simple 2D game. I render tiled map and several moving entities, one of which is the character controlled by a player, and other ones are NPCs that are moved by simple AI strategy - chase a character using shortest path finding algorithm (tiled map data structure contains graph property that allows entities to find paths by BFS or Dijkstra).

I am wondering how should I handle collisions between those entities. I am currently able to handle collisions between an entity and tile map objects. But the problem is when more than 1 NPCs are engaged in chasing, they can end up overlapping each other, which is not what I want to see.

I was thinking about bounding box based collision detection, but it doesn't work well with path traversing algorithm, since sometimes velocity changes result in not natural chaotic movement.

Another way is to check if tile is currently occupied by an entity and prevent movement if needed. However this lead to a problem of recreating path (graph should be copied and reduced by one node, path should be generated again)

Third option is to create some kind of relation between all NPCs to prevent collisions or change their coordinates on demand. However this is not quite scalable solution.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ If all your agents are pathing to the same goal, you might want to consider using a flow field. Then if one NPC blicks a tile in the shortest route, agents can move to the next closest nearby cell without re-pathing cost \$\endgroup\$
    – DMGregory ♦
    Mar 25 at 8:28
  • \$\begingroup\$ @DMGregory thanks for mentioning flow fields. If I understood the idea correctly, my cost field will be filled out depending on whether tiles will be blocked by entities or not and all paths will be created at once. However that makes me wonder, how do I allow entity to intersect a part of the existing path of another entity, while that part is not blocked. Feels like combining contionuous collision detection and flow field \$\endgroup\$
    – Steyrix
    Mar 25 at 10:58

1 Answer 1

Reset to default
1
\$\begingroup\$

Sounds like you could implement a grid system where each cell contains a list of all entities currently overlapping that cell. Based on that you can do continuous collision detection and even move and slide between colliding entities and tiles so they never overlap.

It's quite an undertaking with literally many edge and corner cases to keep in mind but it can be done.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thank you for the answer. I actually managed to do something alike using a graph structure, where each node has "cost" property. \$\endgroup\$
    – Steyrix
    Apr 13 at 8:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .