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

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.

• It depends how aggressive you want to be. For example, consider an entity that's an S-shape, and a doorway that's slightly bigger than the thickness of the S. Technically, you could wiggle through, but proving that you can is difficult, especially if you have other geometry that may block the maneuver. Jan 10, 2014 at 22:04
• aigamedev.com/open/article/clearance-based-pathfinding Jan 10, 2014 at 22:12
• @ToddersLegrande: That's a good article - why not write it up as an answer before I do. Jan 10, 2014 at 23:06
• @PieterGeerkens I have the link around as a resource for when I need it. I haven't actually leveraged it as a resource for myself yet so while I understand the concepts I am far from an expert on the matter. Add to that the time I need to summarize what they've said in a useful manner for the OP without just pasting the link resulting in potential link rot, it's something I just don't have the time and current knowledge to undertake. Jan 10, 2014 at 23:44
• Thanks, @ToddersLegrande, that's precisely what I was looking for. Now I just need to figure out how to tweak item motion & placement so it doesn't look & feel like a tile based game (despite the fact that I'll be using discrete 'tiles') for pathfinding. Jan 11, 2014 at 6:22