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.

Improve this question
\$\endgroup\$
5
  • 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, 2014 at 22:04
  • 4
    \$\begingroup\$ aigamedev.com/open/article/clearance-based-pathfinding \$\endgroup\$
    – SpartanDonut
    Jan 10, 2014 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, 2014 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, 2014 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, 2014 at 6:22

1 Answer 1

Reset to default
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.

Improve this answer
\$\endgroup\$
2
  • \$\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, 2014 at 6:06
  • \$\begingroup\$ @levand I will respond more thoroughly tomorrow if someone hasn't answered your question by then. \$\endgroup\$
    – Engineer
    Jan 11, 2014 at 10:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .