Is path B better then path A? It looks like with path B units have more freedom of movement when they encounter obstacles. I`m having a difficult time coming up with an algorithm that transforms a type A path to a type B path that works in all directions. Any suggestion for how to get an algorithm working?

Calin said:
Any suggestion for how to get an algorithm working?

You could calculate the curvature of the path at each vertex, then sort the vertices by curvature, and remove vertices in that order if their path segments are still shorter than some given length.

To calculate curvature, you could use the angle between the two path segments adjacent to the vertex.
For the image, you would get an angle of zero for all the vertices you have removed.
The two remaining vertices in the middle would have angles of 45 degrees.
The other two remaining end points have only one segment, so i would set the max angle of 180 degrees to make sure they're not removed.

Calin said:
It looks like with path B units have more freedom of movement when they encounter obstacles.

Not really, since the reduced path for the given example is the exact same as the initial dense path.

Which is one argument why i think the idea to reduce the path won't give you what you really want.
Beside freedom of movement, there is the usual problem of smoothing a path as found from Dijkstra. Using them with a grid typically causes jaggy results, because all those paths i draw here have the same length:

The ‘natural’ path might be the green one, but both the others have the same length, and Dijkstra might return any of those, since they are all as good as the other.

It's a bit better if you allow diagonal movement, but the problem still remains.
Now i'm pretty sure Astar would always give a path close to the green one, since it considers direction towards the goal.
But even then, you still have those jaggies, and units following jagged paths does not look natural.

So i guess that's your real problem?

If so, the primary question is:
Do you smooth the path?
Or do smooth the movement trajectory, allowing units to diverge from the path as long aS THERE IS NO OBSTACLE BETWEEN THEIR TRAJECTORY AND THE PATH. (oops - caps lock)

The latter option seems much better to me, since it gives more flexibility on modeling behavior.

JoeJ said:
Now i'm pretty sure Astar would always give a path close to the green one, since it considers direction towards the goal.

Nope.

(assuming starting point is at bottom left of the drawing)

If your estimate is also counting horizontal + vertical edges of length 1, then all paths are equal and you trivially can get any of the paths (and a few more in-between than in your drawing).

If your estimate computes actual (diagonal) distance, then the longest diagonal estimated path is shortest and gets expanded first. However, even then, all paths eventually end at the rightmost vertical line or at the top line, at 1 or more steps distance from the endpoint at the top-right.

At those lines, the diagonal advantage doesn't exist anymore, so all other paths with a diagonal segment get expanded first until they are all the rightmost or top line. Then all paths are equal again, and any path can win 🙂

It's pretty common to have a change in direction have a movement cost, where traveling straight has no cost.

When computing weights or cost for moving, you can include a weight for turns or for angles of turns. If it's vector-based rather than box based, often angle squared gives a better result, a slight acute-angle turn is low cost but a right or obtuse angle has a much higher cost. Or maybe for you turning adds a slight cost like 0.1 if you want to discourage turning, or maybe it reduces the cost slightly if you want to encourage lots of small edges or an irregular path.

Adding that small factor to your pathfinding cost function can make a huge difference in how traveling around edges and bends get handled. Straight lines are either encouraged or discouraged with a tiny nudge. If continuing straight is preferable, “distance since last turn” can also be a weight, favoring or discouraging depending on which you want.

It can also be a different factor for different units. A vehicle that must take slow, deliberate turns would favor straight lines and be quite different from a creature that is expected to constantly dodge and sway, where you'd want to encourage taking a side-step whenever possible.

Thank you for feedback. After I had started the thread I have realized how an algorithm for the problem in question can be written. But if when using the second type of path units don’t perform better at avoiding each other then there’s no point in writing the algorithm I guess ( I understand there are other considerations too for wanting to use a non dense path )

Calin said:
But if when using the second type of path units don’t perform better at avoiding each other there’s no point in writing the algorithm I guess

Maybe.

There is one aspect of such optimization / simplification, which makes me doubtful.
Ofc. your second image uses less vertices for the same path, so it is more optimal, or efficient, or whatever.
But your data also becomes irregular. Which means the lengths of your path segments will differ wildly.
On a straight part of the path there will be few vertices, on a curved part there will be many.

This makes some things harder.
Say for example, we want to smooth out the jaggies.
To do so, we could for example calculate some local average direction considering the next 5 segments of the path.
It will work and will be easy to do.
But if using the optimized version of the path, the next 5 vertices might have a distance of say 1m, 2m, 10m, 12m, 50m. It's irregular, so a naive average of that won't be local, and will consider turns which are too far away. Considering this makes our algorithm more complex, eventually causing higher costs then the optimization gave us.

For a counter example, say we solve it not with simple smoothing, but with smart behavior.
The behavior could be: From the current positon, trace rays towards the next vertices of the path. If they hit no obstacle, we could walk towards this vertex directly in a straight line. No need to follow jaggy segments of the path itself.
After we moved a step, we can do the same thing again, and this time may find a spot even farther away on the path, and walking towards that causes a slight change in direction, leading to a curved path over time.
So this approach should work well too, probably better. But it's more expensive due to the ray tracing.
Thus, this approach would surely benefit from the optimized path version, since it needs less rays for the same distance.

So yeah, you might want to think about this for longer before you decide.
Which is not always possible or successful. Often we just have to try multiple options, picking the best in the end and throwing the others away. It's not really a waste of time imo.

I might explore the curved paths idea in the future. The immediate concern is that if I choose to add the optimized path feature the units while trying to avoid something will stray from their normal path and start walking on map obstacles

JoeJ said:
From the current positon, trace rays towards the next vertices of the path. If they hit no obstacle, we could walk towards this vertex directly in a straight line. No need to follow jaggy segments of the path itself. After we moved a step, we can do the same thing again, and this time may find a spot even farther away on the path, and walking towards that causes a slight change in direction, leading to a curved path over time.

+1 to this approach. You can also do some time-domain smoothing on the agent trajectory to avoid discontinuous velocity.

Calin said:
The immediate concern is that if I choose to add the optimized path feature the units while trying to avoid something will stray from their normal path and start walking on map obstacles

Calin said:
It looks like with path B units have more freedom of movement when they encounter obstacles.

Please explain why you expect those things.

Oh - maybe you worry about removing a vertex, and the newly merged segment now crosses an obstacle the original path did not? Like this:

This could be prevented with an extra check ofc., but then i'd ask why you really want to do this in the first place?

It looks like with path B units have more freedom of movement when they encounter obstacles.

If you have a group of units gathered on the path of some unit, the unit in question will avoid the group sideways (scenario B) if it has an optimized path and go through the middle of the group if it has a dense path (scenario A)