How can I follow a path around an obstacle closely enough that I'm guaranteed to never find myself on top of the obstacle? Let's say I've got a grid, and I have a path moving around an obstacle (unwalkable tiles on the grid). But I'm moving across this grid at a rate greater than 1 tile per tick (how about 2 units per tick). Now let's say I'm at (1,1), and the next node in my path is at (2,1), and there's a wall at (3,1). So I detect that I need to move in the (1,0) direction, and since I'm moving at a rate of 2 units per tick I am now at (3,1), on top of the wall. No big deal as long as I continue to follow the path, since I'll just move off of it next tick. But wait! I decide I don't want to follow the path anymore (maybe I found something better to do). Now I'm stranded on top of a wall, and since the wall is unwalkable I can't find a way off the wall, and I'm stuck. What to do? Should I just be doing collision detection while following a path?

Quote: Original post by BradDaBug
No big deal as long as I continue to follow the path

What do you mean, no big deal? You should never allow your agents do impossible stuff like standing on a wall... if you're still planning to follow that path, you should either distribute your movement speed across the path or slow down if you're capping the speed at which your agent can rotate, otherwise, if your path follower works correctly, you should be standing on valid ground and be allowed to switch to what ever other behavior you want to switch to.

Sounds like the problem is in your path finder, not your path follower. In games, a path finder will generally return a path that, if followed literally, will result in no collision. You need more nodes, or a bump and steer algorithm. The latter will impose constraints on how your level geometry must be constructed (for bump and steer, everything should be convex).

There are other types of clever path following you could do, but i think the easiest solution would be an auto-generated node network.

-me

I'm not sure how you are implementing unwalkable tiles. It sounds like you are either checking if the tile is walkable after you have already moved on top of it, or you are only checking the tiles directly adjacent to you. Wait, I guess it is probably the latter. If you are moving 2 units you would have to check both units, not only the adjacent one. Regardless, it sounds like a good thing to look into is an A* algorithm. It sounds like you already have a grid system in place, and there are tutorials available online... a really good one on GameDev if I remember correctly. Hope that helps.

I'm already using A*, and as far as I can tell the path it returns is fine.

Here's a picture that might explain what I'm asking a little better:


Here the agent is simply moving too quickly to "make the turn." On Tick A the entity is one block west of the wall, the next path node he needs to move to is one block to the east, so he moves east. By the time the next tick comes around (Tick B), the entity is sitting on top of the wall.

Here's a related question (the more I think about it the more I suspect this might have more to do with the problem I'm having than the situation above):


Here I'm allowing diagonal movement. The agent begins moving east, then arrives at the second node in the path (the tile), then begins moving in the direction of the third node. In doing so, the agent cuts across an unwalkable tile. Technically the path is valid, but the path following isn't. How could I fix that? I don't want to disable diagonal movement.

Quote: Original post by Palidine
In games, a path finder will generally return a path that, if followed literally, will result in no collision.

I guess my problem is I don't know how to literally follow a path.

Quote: You need more nodes, or a bump and steer algorithm.

Is the second problem up there the kind of situation where I'd need more nodes? Like an extra node at the corner there to prevent the agent from cutting across corners?

Quote: Original post by xEricx
if you're still planning to follow that path, you should either distribute your movement speed across the path or slow down if you're capping the speed at which your agent can rotate

What exactly do you mean by distributing the movement speed?

The problem is that the agent is not following the path. The path is represented by nodes with the assumption that the agent would be moving along line segments connecting the nodes. The nodes are not the path, the line segments are the path. The nodes are only an implicit representation of that path.

To correct this problem, add code to ensure that the agent does not overshoot past a node. There are a few ways this can be done depending on how you are calculating the agent's position and movement.

To allow diagonal movement while not allowing corner cutting you just need to make the diagonal edge not exist in cases where it would be cutting across an obstacle.

The nodes you are using seem to be loosely defined, with the node representing any position in its grid cell. Unless the agent's geometry is a point this could create situations where the agent will overlap with walls and slightly cut corners when the agent is near the edge of a cell if you are assuming the path is collision free and are not performing collision detection.

The first question you should ask yourself - "is this a discrete or continuous problem?"

If the problem is continuous (the agent movement is described by a set of differential equations) the way you solve the problem needs to change. See http://msl.cs.uiuc.edu/rrt/ for some ideas on alternatives. You'll also need some kind of controller to track the path. In general continuous path planning following is still an active area of research.

If the problem is discrete, you should only add edges between tiles that your agent can actually achieve. For the full set of available inputs to the agent including direction (up, down, left, right, up-left, ...) and distance (1 tile, 2 tiles), build a set of final locations that you can arrive at from a given initial state. When you need to follow a path, simply look at the gap between nodes to select the action.

Consider a simplified subset of actions

Action -> Result
L1 -> -1, 0
R1 -> +1, 0
U1 -> 0,-1
D1 -> 0, 1

Gap between nodes (0,1), action to choose should be D1

BradDaBug, you've just highlighted one of the most common mistakes made in robotics path planning (which comes up in games too). You've assumed that the controller governing the motion of your agent/robot/object can follow any path returned by your path planner.

Quite simply, the achievable dynamics of your object must constrain the paths your planner returns. In your example, since the moving objects cannot turn corners quickly, that path should not be considered viable by the planner (since the planner should expand a graph of next states based on achievable states for that moving object).

Unfortunately this adds complexity to your planning problem. Ideally, you would fix your planner, but most often, the solution is to enforce a change on the moving object to conform to a reasonable path (in this case, make it slow down and turn more sharply than it normally would), as has been mentioned above.

If you choose to fix your planner, then you must take into account the moving objects dynamics when creating your search tree. Don't just assume that it can move to each adjacent, open node. Check whether that node is 'reachable' given the current configuration of the object.

Cheers,

Timkin

(And I've just noted the previous poster tried to make this same point... my apologies if this information is superfluous).

I don't think it's clear if BradDaBug's problem is from constraints on the allowed motions of the agent or if it's just from trying to implement variable movement speeds (with unconstrained dynamics) and not accounting for the agent moving off the path by not checking that it has reached the waypoint it was moving towards.

If it's the latter case then fixing the problem is much simpler since it only requires checking that the movement didn't make the agent go through the waypoint. It may be better to think of a path like this as being a function from time to positions. What position does path(now+delta) evaluate to?

Quote: Original post by BradDaBug

Quote: Original post by xEricx
if you're still planning to follow that path, you should either distribute your movement speed across the path or slow down if you're capping the speed at which your agent can rotate

What exactly do you mean by distributing the movement speed?

What I mean is that you don't need to blindly spend all your movement units along the first direction you computed. You should check if you're overshooting your destination, if so deduce from this frame's movement the movement you'll have to spend to reach the node, then pick the next node and spend the remaining units toward this node.

This technique assumes your agent can follow the path exactly and can rotate instantly to any direction or that it can switch from walking forward, strafe left/right, backward...

Hope this helps

Eric