4
\$\begingroup\$

In my game, there are many agents. Agents request a path, then after attaining a path to "goal" they follow the path. However player and many other things in the world can impact their position by pushing them or pulling them.

When agents get pushed and they happen to advance forward closer to "goal", I want them to smartly follow the previously given path.

I have pictures below to enhance your understanding of my situation.

I COULD recalculate path every a few seconds or when agent gets out of path BUT I have DOZENS of these little agents. I don't want to do path finding for DOZENS of agents again, again, again, and again whenever they walk out of the path.

enter image description here enter image description here enter image description hereenter image description here enter image description here

\$\endgroup\$
  • 1
    \$\begingroup\$ Do the agents know when they've been acted on by external forces? Are said forces instantaneous or applied over time? Given the options between the green & orange solutions, how concerned are you trying to minimize the distance to re-establish the path versus minimizing the time to the goal? \$\endgroup\$ – Pikalek May 3 '18 at 21:14
  • \$\begingroup\$ Are your agents all moving toward one or a small set of destinations (like mobs in a tower defense all seeking the closest target building)? If so, you may have simpler options available like flow fields. \$\endgroup\$ – DMGregory May 3 '18 at 22:59
  • 1
    \$\begingroup\$ Nice pictures. :) \$\endgroup\$ – HolyBlackCat Jun 4 '18 at 15:42
0
\$\begingroup\$

EDIT2: A series of heuristics is likely in order using the below. If within distance that node scores some points. Then if it's angular difference to the next node is close to 0, it scores (a lot) more points. Then if none of that works out, recalculate. If it does work out, simply move to the highest scoring node.


First, you should probably maintain a rough angle between the agent and it's goal, that way you can approximate the direction it's supposed to be going.

Second, you might have an impacted agent perform a distance calc on the next nodes in the path. If it's within distance then just go to the nearest node (+1) of that path and follow it. If it's outside of distance then recalculate. The nearest node (+1) (maybe recalculate just to this node) will look fairly natural I think.

This should save you most of your A* calculations and give a natural looking move.

\$\endgroup\$
0
\$\begingroup\$

The way you generally do this is to run the path-finding algorithm again every so often.

For lots of units, you can speed things up using hierarchical pathfinding and/or swarm pathfinding and/or using predefined paths between waypoints and merely pathing to the nearest waypoint.

\$\endgroup\$
0
\$\begingroup\$

There are many possibilities to do it:

1) Repath

2) Use path segments directions - and check if at goal like follows:

If (dot(playerToGoalDirection,SegmentDirection) < 0) Go to the next path point update path segment.

You can add some tracing to sieve out waypoints that you dont want to move to after being hit.

For example trace to the next point if success trace to the next-next point if success remove the next point and path to next-next point

Remark: PlayerToGoalDirection is the direction to the current waypoint

You can see the second in action here:

https://drive.google.com/file/d/1x4MPTSwyEtNeSRd1YHjr4nzOG41cp5Sc/view?usp=drivesdk

\$\endgroup\$
0
\$\begingroup\$

As already mentioned, there can be multiple solutions to this. Depends on project setup and your preferences, so just one more idea to add:

Maybe you can just recalculate path only after collision. So let's say logic could be following:

  1. calculate path just once for each object and let them move
  2. whenever any of those objects will collide (maybe only with respective layer/tag), stop navigation
  3. let that object to stop (check for velocity) and once stopped recalculate only then the path again

That would minimize amount of agent recalculation unlike calculating it each frame. Letting object to stop can also emulate visually some "confusion" effect caused by hit, which can eventually be enhanced if you wait some time before you initiate agent movement after hit again

Again it depends on your project setup, but can give some hint on how to take this

\$\endgroup\$

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.