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.
No comments:
Post a Comment