# Efficiently detect path failure?

This topic is 918 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey,

let's say a path finding algorithm detected this path: 2, 3, 4, 5:

Imagine a bot fails to jump from 3 to 4 because of some blocking issue and fell down. How could I efficiently detect it, so that I can generate a new path? One way could be to check which link a bot is currently intersecting and if it's not a link between previous and next waypoint - it failed. But that would probably be really inefficient, what do you guys suggest?

Edited by Gintas Z.

##### Share on other sites

You can estimate (upper bound of) time of arrival to the next waypoint (e.g. 4) and reset path if bot fails to arrive in time. I think it is the easiest and the most robust solution.

Also you can raytrace from bot to waypoint from time to time and check if ray hits something. However it may not always work and as raytracing is quite expensive I'd do this only in special cases such as when jumping is required to reach the waypoint.

Or if jumping mechanics is simple you can quickly precalculate landing position if something happens to the bot (collision). Just simple physics formulas, no collisions etc. Find T from acceleration.y*T^2 + velocity.y * T + position.y = waypoint.Y, use T to find x = acceleration.x * T^2 + ... and compare x with waypoint.x. If it is too far away - recalculate path.

P.S.: Are you using some kind of automatic waypoints placement?

##### Share on other sites

How could I efficiently detect it, so that I can generate a new path? One way could be to check which link a bot is currently intersecting and if it's not a link between previous and next waypoint - it failed. But that would probably be really inefficient, what do you guys suggest?
My first idea would be to run a path generation cycle after each jump, you broke contact with 'safe' earth, who knows what happened :p

Next, you probably want to limit the number of attempts to reach some way point if you repeatedly fail. Eg after 3 failed tries to to make progress towards point 4, make it "nonreachable", and path-find to 5 again.

##### Share on other sites

@Alex Mekhed, thanks, you can check that link in my signature

I think I have found a way to detect it quite simply and super efficiently:

Waypoint currentGoingToWaypoint = pathArray.get(0);
float diff = Math.abs(bot.getPosX() - currentGoingToWaypoint.position.x);
if (bot.getPosX() > currentGoingToWaypoint.position.x && diff > 1f * Constants.UNITSCALE)
bot.getPlayer().setMovementAction(Constants.MOVEMENT_ACTION_LEFT);
else if (bot.getPosX() < currentGoingToWaypoint.position.x && diff > 1f * Constants.UNITSCALE)
bot.getPlayer().setMovementAction(Constants.MOVEMENT_ACTION_RIGHT);
else {
bot.getPlayer().setMovementAction(Constants.MOVEMENT_ACTION_STOP);

// check if failed to reach
if(bot.isTouchingGround() && Math.abs(currentGoingToWaypoint.position.y - bot.getPosY()) > 10f * Constants.UNITSCALE)
{
// regenerate new path
goTo(getFinalDestinationWaypointId());
Debug.log("failed");
}
}


Simply just check the difference of current Y to waypoint Y when arrived by X.

Edited by Gintas Z.

##### Share on other sites

Running pathfinding/planning again when the character finishes landing after a jump (from wherever he ended up, without assumptions but possibly with a special case to keep the previous plan after detecting a successful jump) should be as safe as detecting jump failure with a timeout, significantly simpler, and visibly faster (no spurious waiting).

1. 1
2. 2
3. 3
frob
20
4. 4
Rutin
20
5. 5

• 32
• 13
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
632559
• Total Posts
3007079

×