Jump to content
  • Advertisement
Sign in to follow this  
zgintasz

Efficiently detect path failure?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey,

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

mFMyvqu.png

 

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 this post


Link to post
Share on other sites
Advertisement

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?

The game looks very good. Any more info? :)

Share this post


Link to post
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 this post


Link to post
Share on other sites

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

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 this post


Link to post
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).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!