I'm doing research in autonomous navigation for robotics, and this is a familiar problem. The real world analogy is you have two vehicles (a robotic motorcycle and a robotic tank) that have to decide on going through a narrow alleyway or not. Dimensions and positions are known by whatever means (radar, LIDAR, maps, GPS, etc)--how do you program such a decision?
Since either vehicle (and, in your case, the NPC that is walking around) are of "fixed" size for an orientation, here are the constraints:
- In general, vehicles travel along a particular axis of their own.
- We don't want to spend an inordinate amount of time doing orientation calculations.
- Software is dumb--it thinks in terms of point positions rather than whole body.
- The widest dimension (fender-to-fender plus whatever junk is hanging out there) of that movement axis is known.
So the approach is this:
- Adding a buffer zone to obstacles is common practice--make it 1/2 of your vehicle width.
- Use a "resolution" for your pathfinding that is proportional to your buffer.
The first part of the approach takes care of the collision part--the "point" of the vehicle/NPC is the same, but every potential collision object is buffered out so that your robotic motorcycle is not running into other cars (handlebars) or the tank is not taking out the corners of buildings.
The second part is an engineering/computation choice. If the space you want to go through is at least a little bit wider than the NPC, then you'll have to keep subdividing your quadtree down to match that buffer--and the algorithm can find a path through that's not occupied by either buffered obstacle.
If you're trying for an exact fit (space matches width of vehicle/NPC), then you're at an edge case that you'll either have to account for or call as a loser (no passage). As the resolution of your calculations (how small you're going to go down to) gets finer, the running time goes way up.
OTOH, the advantage of this approach is that the same process can account for a motorcycle-sized vehicle (which would add about a foot or so buffer) and a tank (8 feet or more), and would work in either case: The motorcycle goes through the alleyway, and the tank goes around the block.
Implementation details are specific to your setup, but I hope this helps get you started.