How to smooth walking with waypoints?

Hi, I'm using my own pathfinding system for my game, and the player follows the path that was computed. The problem is it looks as if he zigzags a little bit when the path has a sort of... Stair type pattern. Is there a way to smooth the path out so it looks better?

Thanks in advanced!

 

Could you post a video or gif and your set up of the paths? I'm not really into path finding systems but i think that might make it easier for others who would like to help.

 

Yeah, I've been through this!

If your path is stair-stepped, then your pathfinding algorithm is probably working on a grid and using only the nearest (4) neighbors at each step. You can make it a little smoother by considering diagonal steps too.

But that's often still not very satisfactory. To get it better, you need to do some type of ray-casting. I tried a lot of post-processing steps to smooth the grid, casting rays to see where I could cut corners without running into anything. My final code ended up quite a bit more complex, but works really well; it computes a complete distance map to the goal (and these distance maps are cached, since in my game, a few points tend to be goals quite a lot), and then we simply walk this distance map, by casting rays in every direction from wherever we are, and picking the ray endpoint that's closest to the goal.

However, all that said... if your map is not a grid, or if the grid is mostly empty space, then you can probably do better with a standard A* algorithm, but instead of operating on a grid, you consider all the "key points" in the space. Key points are the corners of all the obstacles, plus the point you're trying to reach. So at each step, you cast a ray to see which of those key points you can reach without running into something, and consider those.

 

Well it does support diagonal movement.
Here is a little picture of what Im talking about:


The red squares represent the path that was computed. The blue line is where the character would move. If you notice, where I circled in yellow, when the character changes direction it's very sudden. It's not as smooth as I would like. I am trying to get those yellow circled areas to be smoother like this:

 

Yeah, that's what I figured — going to diagonals was just the first step.

Now I think you should consider the other steps I wrote about. They are pretty advanced, but I assumed you were pretty advanced already or you wouldn't be doing your own path-finding. (Not that A* on a grid is hard, but a lot of newbies find it intimidating.)

However, maybe I'm trying to answer a harder question than you're really asking. If you really do just want to smooth the motion a bit, while still following the basic 8-neighbors path, then this is much easier to do — you don't have to change your pathfinding at all. Instead, you just need to limit how quickly your agent can turn, and when it starts turning.

To limit how fast it can turn is the easiest bit: you can use Mathf.SmoothDampAngle, for example, to smoothly turn towards the "goal" direction at some rate you specify. The example in the docs isn't terribly helpful, but study the parameters and give it a whirl, and post here if you have trouble with it.

Then, you'll want to tweak when you start turning. Those grid cells are pretty big, so I would suggest this: as soon as you enter a cell, start turning towards where the path exits the cell (which will be either the middle of one of the sides, or one of the corners). Combined with appropriate SmoothDampAngle, I think that should look pretty good.

 

I like JoeStrout's idea of damping, and I would like to suggest an alternate way of damping that might work for you, depending on how tight your map is.

Instead of having the player follow the path, have an invisible proxy object follow it. This invisible proxy would be doing the stair-stepping and sharp turning but you wouldn't see that. Then make the player smoothly turn to try to "get close to" the invisible leader object. This would be a good place to use that turn damping that JoeStrout mentions.

If the player falls further behind, begin increasing his speed so that he starts to close the gap with the leader.

If you adjust the player's chase speed up and down in small increments and allow the player to lag back a ways behind the leader, the player will tend to take a much a much smoother path, effectively giving you some damping.

If the player is within a small distance of the invisible leader, have the player continue directly towards the leader at this speed until it reaches the leader, to "arrive" at the final goal nicely.

The downside is, if the path makes a sharp U turn around a narrow obstacle, the player following along behind could get either "snagged" on the wrong side of it, or pass through it, depending on how you are enforcing your collisions.

Kurt

 

I like Kurt Dekkers idea, might I suggest a slight alternative. A similar kind of idea, precompute the path once, and only recompute when the endPoint changes or exceeds a maximum distance, also you'd only need to recompute the path from where the path ends, unless the endPoint is drastically different. Then take the points that are computed, and pointA -> pointB as you go through the list of points, have it go to pointB when the character is within range of pointA (but using damping).

Hope this helps!

~
Another walk in the park.

 

Make a waypoint move on the line a few meters ahead of your character, and make the character try to reach it. It will automatically smooth the corners.

 

That's what I meant, I was getting tired when I wrote my idea!

 

Thanks everyone for your answers. I'll try that, it seems like a solid method!