5
\$\begingroup\$

I want to make a game where a player follows a mouse pointer. The game is not tile-based. I use quadtree for a collision detection and everything works fine. But now I want to develop a player pathfinding algorithm. I.e. when a user clicks somewhere the player should find the most expected way to go there and follows it. And I stuck with situations like on the picture:

Player is not just a dot. He has got specified size (2D volume). If I use centres of the quadtree regions as a path trajectory, then this tunnel looks impassable. But when I control the player directly from the keyboard, he of course, is able to pass through this place.

How can I make quadtree-based pathfinding works for such situations? Or should I use another technique to solve this problem maybe?

|improve this question
\$\endgroup\$
  • \$\begingroup\$ How do you create the quad-tree. I mean when do you divide a cell ? \$\endgroup\$ – Emadpres May 30 '15 at 20:10
  • \$\begingroup\$ I do it each time my environment (I mean walls' structure and players) changes. \$\endgroup\$ – Ivan Velichko May 30 '15 at 20:15
  • 1
    \$\begingroup\$ I hope I am wrong but this is probably going to be horribly difficult when the object is required to take turns through a narrow path and rotate around in order to go to the target position, since your object is not symmetrical like a square or circle. I doubt you will find a generic algorithm like A* for example for rectangles instead of squares. You will probably need to innovate a little bit. Have you made any efforts so far to help us out ? This an interesting question. \$\endgroup\$ – dimitris93 May 31 '15 at 23:35
  • \$\begingroup\$ @Shiro, I'm just in process now. And as soon as I realised that it's not so easy, I decide to ask here. \$\endgroup\$ – Ivan Velichko Jun 1 '15 at 11:19
3
\$\begingroup\$

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:

  1. In general, vehicles travel along a particular axis of their own.
  2. We don't want to spend an inordinate amount of time doing orientation calculations.
  3. Software is dumb--it thinks in terms of point positions rather than whole body.
  4. The widest dimension (fender-to-fender plus whatever junk is hanging out there) of that movement axis is known.

So the approach is this:

  1. Adding a buffer zone to obstacles is common practice--make it 1/2 of your vehicle width.
  2. 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.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Great answer padding the obstacles to reduce the pathing object to a single point. That's a great solution if it fits the needs. If not (if objects are various sizes) you can get a similar setup with delauny triangulation to know the maximum size that an object can be to traverse a section of a path, which will work for varied size objects, but is more complicated and doesn't fit the quad tree requirement. \$\endgroup\$ – Alan Wolfe Jun 7 '15 at 3:14
  • 1
    \$\begingroup\$ Thanks--I'm actually integrating Delaunay triangulation into my current work (more general case for multimodal sensor suites). I'm not an expert by any means (not yet), but these kinds of problems cross a lot of boundaries, and it's an approach that helped me. \$\endgroup\$ – angus_thermopylae Jun 7 '15 at 3:29
  • \$\begingroup\$ In case it helps your research in the future (and you haven't heard of it before) game physics are often implemented with support vector mapped shapes, using minkowski sums (differences) to reduce collusion tests of arbitrary svm shapes to point in shape tests. Some nice algorithms for point in test are GJK and MPR (minkowski portal refinement). Wanted to share to repay the awesome knowledge in your answer. Thanks for sharing (: \$\endgroup\$ – Alan Wolfe Jun 7 '15 at 3:51
  • \$\begingroup\$ I was rereading your first comment, and the approach I would take is that, when each object/NPC runs its own solution, it adds its own padding. I realize that causes re-computing every time the nav system switches "point of view", but it would make it very flexible in that NPC "A" (a mouse) can use the same algorithm as NPC "B" (an elephant). NPC "A" an NPC "B" would look at the terrain very differently, and may or may not come up with the same solution. This wouldn't scale to dozens of NPCs very well, but it should work for a small number. \$\endgroup\$ – angus_thermopylae Jun 11 '15 at 19:52
  • \$\begingroup\$ You could improve that and bucket it by common sizes too, so maybe have a variety of entity types, but they are all either small, medium or large, which are predefined sizes that determine which map they use to path \$\endgroup\$ – Alan Wolfe Jun 11 '15 at 19:54

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.