Pathfinding distance algorithm

Newbie & Debugging Questions
#1

Hi. I implemented a pathfinding solution with gdx-ai in my tile basede game, and I used Manhattan distance formula in estimation:

Math.abs(startX - endX) + Math.abs(startY - endY)

If the shortest path from point A to point B is diagonal, it’s OK for ground units, the movement a little bit like zigzag, but it’s OK.

I was thinking if there is a better solution to avoid that zigzag behavior to get a smooth movement, like in starcraft2. I tried pythagorean:

Math.pow(Math.abs(startX-endX),2)+Math.pow(Math.abs(startY-endY),2)

and Euclidean

Math.sqrt(Math.pow(Math.abs(endX-startX),2) + Math.pow(Math.abs(endY-startY),2))

,

but both resulted me a similar result.

So if the map looks like this:
01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16
and the point A is at 13, point B is at 04, than those takes a path like: 13->14->10->11->07->08->04 instead of 13->10->07->04

Any idea how can I achieve this?

UPDATE: is that a good idea to add the diagonal nodes to the node’s connections?

#2

You need to post-process the generated path. You can probably remove 90% of the nodes that make up your path.

Let’s say you have these three nodes somewhere in your path:

…)->(1)->(2)->(3)->(…

If there is direct line of sight between node 1 and node 3 you can skip/remove node 2. Then do the same check for the next pair of nodes. If you do multiple of these reduction passes you’ll end up with a pretty good path. For me the sweet spot was around 10 times (for every second node of the path, not just 10 removals but 10 full passes), which is still very cheap compared to the pathfinding itself and produces good results.

This will already remove 90% of the zig-zagginess, it won’t be perfect but much better then the raw path.

[quote]UPDATE: is that a good idea to add the diagonal nodes to the node’s connections?
[/quote]
Just try it, it’ll make your path more accurate.

#3

Tried to connect diagonal nodes, it looks totally OK now, zigzag effect went away.

#4

Just google some tutorials on the " A* - algorithm ", its pretty neat for beginners to learn how pathfinding works