Sign in to follow this  

Getting the right way around corners

This topic is 2846 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

Hi all, I have a problem where my agents sometimes get on the wrong side of corners. See here: The agent has a waypoint path from tile 4 to 1 that it tries to follow. However, it can get displaced a bit so it drifts towards tile 2. When it hits the blocking wall between tile 1 and 2 I would like it to find its way around to tile 1, instead of repathing or sliding along the wall into tile 2. You see, I have some 'sliding' code that causes the agent to drift along a blocked wall for a bit to see if it can get around it, instead of cancelling and repathing right away. However this only works properly when the blocking wall is between tile 4 and 2 instead of tile 1 and 2. Preferably, I would like the agent to steer around obstacles instead of bumping into them, it doesn't look too good. But I am not sure what methods are appropriate. I seem to remember that steering behaviours have some limitations with regards to the shape of obstacles... so thank you for any advice. Oh, I forgot to mention that the depiction is not entirely accurate. The "wall" is represented by a blocked edge between tiles1 and 2 - it doesn't have any geometry.

Share this post


Link to post
Share on other sites
It seems to me it might be easier to set up your pathfinding so that situations like the one you describe won't come up in practice. For example, in this case, the path could go from 4 to 3 to 1, rather than directly from 4 to 1.

I don't know how you're representing the environment, but if it's grid-based, it seems like it would be fairly straightforward to disallow direct traversal from 4 to 1 based on the fact that the edge between cells 2 and 1 is obstructed, which in turn would force the path to go around the obstacle. If path smoothness is a concern, you could then postprocess the path using, say, the funnel algorithm (although in order to keep the same problem from popping up again, you'd need to take the agent's radius into account when building the smoothed path).

As for your question, it seems like figuring out that the agent should go left rather than right when it runs into the obstruction would be kind of a mini-pathfinding problem in and of itself, which is why it seems dealing with the problem during the pathfinding stage might be preferable. That said, maybe something like this would work: when an obstacle is encountered, check to see whether the bulk of the obstacle lies to the left or right of the current path segment, and navigate accordingly.

Personally though, I'd probably just set up the pathfinder so that the paths were built around such obstacles, and then use a smoothing algorithm to smooth out the paths.

Share this post


Link to post
Share on other sites
If I do as you say, and block the diagonal edges from 4 to 1 and 3 to 2, along with the edge from 1 to 2, then the agent would go 4-3-1 instead of 4-1.

The problem is now that it may look like the agent is taking a rather long detour around whatever it is that blocks the edge between 1 and 2. It may not be a wall, it could be tree also.

So you are suggesting I could use the Funnel algorithm to make this look better? (I hadn't heard of it until now - the path smoothing algorithm I am using is the one from Mat Buckland's book "Programming Game AI by Example".)

Share this post


Link to post
Share on other sites
Quote:
Original post by captain_crunch
If I do as you say, and block the diagonal edges from 4 to 1 and 3 to 2, along with the edge from 1 to 2, then the agent would go 4-3-1 instead of 4-1.

The problem is now that it may look like the agent is taking a rather long detour around whatever it is that blocks the edge between 1 and 2. It may not be a wall, it could be tree also.

So you are suggesting I could use the Funnel algorithm to make this look better? (I hadn't heard of it until now - the path smoothing algorithm I am using is the one from Mat Buckland's book "Programming Game AI by Example".)
That's right - you allow the pathfinder to build a path that is safe but possibly non-optimal (e.g. 4-3-1, from cell center to cell center), and then use a path smoothing algorithm to make the path optimal (or nearly so).

Visibility-based smoothing algorithms (which, IIRC, are what is described in 'Programming Game AI by Example') can be suitable in some cases, but may not always generate optimal paths. In your example, for instance, visibility-based path smoothing probably wouldn't work.

What you really want is a path that 'wraps around' the obstacle as if the obstacle were 'rounded', with a virtual radius equal to the agent's radius. This is what the (modified) funnel algorithm will give you: an exact geodesic path from the start point to the end point (given a particular sequence of cells).

The modified funnel algorithm can be a bit tricky to implement; it's been discussed quite a bit lately on this forum though, so a search of the forum archives for 'funnel algorithm' should lead you to some decent references. (Unfortunately, the modified version of the funnel algorithm in particular isn't very well documented, so you may kind of have to piece it together from multiple sources.)

Also, it may be possible to simplify the algorithm considerably if the environment is grid-based. I haven't given it much thought myself, but it seems that applying the funnel algorithm to a sequence of cells in a regular grid would be considerably more straightforward than the general case.

Share this post


Link to post
Share on other sites
Thank you, but I have to say... I'm not too keen on it. I spent a lot of time getting the path smoothing to work, and replacing that code with something that is even harder to program such as the funnel algorithm is not something I would look forward to.

Perhaps one of the steering behaviours for obstacle avoidance would work? Then I would get dynamic obstacle avoidance too, which would be very cool.

Share this post


Link to post
Share on other sites
Quote:
Thank you, but I have to say... I'm not too keen on it. I spent a lot of time getting the path smoothing to work, and replacing that code with something that is even harder to program such as the funnel algorithm is not something I would look forward to.
Sure, fair enough. Maybe dynamic obstacle avoidance would work, although I'm not sure it could be counted on to reliably make the 'right' decision in the example case you gave.

The only other thing I can think of at the moment is what I suggested previously: choose a direction based on what side of the current path segment the obstacle lies on. The details depend on how your environment is represented, but given what you've described, it seems it could be as simple as checking to see to which side of the path segment the obstacle center lies.

Maybe someone else can offer a better suggestion though...

Share this post


Link to post
Share on other sites
My solution was to build a "safe" path, as advocated by the others, and then for the agent to begin following that.

However, every x frames, the agent would look ahead to see whether they could directly reach nodes further on the path, by ray casting through the scene geometry from the corners of their bounding box. If the way was clear, then they could skip a path node, and so on.

In the event of being knocked off course, and their destination node becoming obscured, they would retrace back through the path until they found a node that they could reach.

It worked very well for me, and the linear nature of the movement wasn't noticeable during the game, especially since there was some momentum to smooth things out.

Share this post


Link to post
Share on other sites
Quote:
Original post by Encho
My solution was to build a "safe" path, as advocated by the others, and then for the agent to begin following that.

However, every x frames, the agent would look ahead to see whether they could directly reach nodes further on the path, by ray casting through the scene geometry from the corners of their bounding box. If the way was clear, then they could skip a path node, and so on.

In the event of being knocked off course, and their destination node becoming obscured, they would retrace back through the path until they found a node that they could reach.

It worked very well for me, and the linear nature of the movement wasn't noticeable during the game, especially since there was some momentum to smooth things out.


This sounds actually quite good... raycasting to waypoints further ahead, and cutting corners if possible. It sounds like it could work for me. And if you actually got it to work, even better.

Now I think about it, the raycasting is something I would need to implement anyways to prevent agents bumbing into obstacles before they repath. I think this is one of the more stupid-looking AI behaviours, and I would like to avoid it.

Thanks a lot for the great suggestions.

Share this post


Link to post
Share on other sites

This topic is 2846 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this