4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – MooseBoys Jan 10 '14 at 22:04
  • 4
    \$\begingroup\$ aigamedev.com/open/article/clearance-based-pathfinding \$\endgroup\$ – SpartanDonut Jan 10 '14 at 22:12
  • \$\begingroup\$ @ToddersLegrande: That's a good article - why not write it up as an answer before I do. \$\endgroup\$ – Pieter Geerkens Jan 10 '14 at 23:06
  • \$\begingroup\$ @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. \$\endgroup\$ – SpartanDonut Jan 10 '14 at 23:44
  • \$\begingroup\$ 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. \$\endgroup\$ – levand Jan 11 '14 at 6:22
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hm, interesting. Although, I don't see how this approach helps you determine a motion vector to start with, as is required for pathfinding. Is your suggestion that you use a higher-level pathfinding algorithm that tries different motion vectors and accepts or eliminates them based on this? \$\endgroup\$ – levand Jan 11 '14 at 6:06
  • \$\begingroup\$ @levand I will respond more thoroughly tomorrow if someone hasn't answered your question by then. \$\endgroup\$ – Engineer Jan 11 '14 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.