How can I test if an object will "fit" during pathfinding?

Question

I'm tinkering around with a 2d game where obstacles are polygons of arbitrary shapes, sizes and locations, and movable entities (players/enemies) can also be of arbitrary sizes.

What's a good general approach for detecting whether a given entity can "fit" between two obstacles during pathfinding? Basic graph-based pathfinding algorithms like Dijkstra's or A* typically involve merely a boolean (and possibly a weight). It's not immediately clear to me what's the best way of extending that to restrict narrow passages to small entities.

Presumably each entity size would need to have its own graph of the map?

I'm not familiar with the literature on this subject but I'm sure it exists - any pointers would be welcome.

Answer 1

Typically the process is something like this...

1. Determine the object's motion vector
2. Mass-project the object's vertices onto a line (2D) or plane (3D) along the motion vector to see whether they intersect the obstacles.

(There may be cheaper ways to rapidly reduce the object's vertices to two points which represent the maximal profile of the polygon, but I doubt it would be less than O(n) anyway, unless of course you aim for the bounding circle of sphere instead.)

This is the simple case, where we assume that the object will not twist or turn back and forth to fit through the gap; this is essentially just the same as checking whether the convex hull could fit, but only at a single orientation. For instance, an ellipsoid might jam going in broadside-first, but going head-on, it might fit through. So you may at least want to check the profile of the object at multiple orientations to see if it might fit. Then if your object were smart, it could calculate the time taken to reach the obstacles at current velocity, and lerp to that orientation before then.