I made a thing:

{"name":"612659","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/8\/78d86d87fa339e74a4b20af619c305ec.gif","w":279,"h":279,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/8\/78d86d87fa339e74a4b20af619c305ec"}

It's a pathfinding sandbox. Play with different algorithms, grids, distance functions, and tie breaker functions. Made in JavaScript, with D3.js for visualization, and my own helixgraph library for pathfinding.

What else should I add?

DanielH, are you then asking how it works? Would you like me to explain, or...?

Nevermind, I misunderstood what it was doing at first glance.

What is the cost and heuristic functions? The A* I know would go in a straight line towards the red dot and backtrack around the walls, not start looking at nodes way in the beginning. Maybe have another dropbox which selects from several cost and heuristic functions.

What I mean is if you look at this screenshot then instead of going along nodes with the closest distance to the red dot, as soon as it hits the wall it starts looking at points close to the green dot. A heuristic function could minimize the total estimated path length (nodes traveled from green plus distance to red) and so that would not happen, instead if would look at nodes in a radius around the point where the wall was hit. It seems in your case it only looks at the total distance traveled so far ignoring the distance to red.

[edit:]
Looking at it again yours is actually the typical implementation, I just use a nonstandard version myself limiting the number of nodes (to get paths faster but not necessarily the shortest one).

So, just a possible additional heuristic to add

In my implementation it's not just a different heuristic but I also forbid overwriting nodes. So if the cost is 10 to reach a node right at the wall, and then 11 to go one along the wall - I will never consider a new path from the start to that same node with less than 11 even though it exists.

So for example if there is a 90˚ wall the final path around I find in my version would go towards the wall until about a 45˚ angle before going around the edge while in proper A* it would aim for the edge of the wall from the beginning. I just had remembered a test app like yours I made way back and how it worked but forgot I'm using a non-standard A*.

I liked my version also for the way the armies in my game move, instead of sometimes going off in a strange direction in the beginning (because the algorithm knows of obstacles far away) they always start heading straight for the enemy and only walk around obstacles more localized.

{"name":"612667","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/a\/daf448d3a5a65901e228745b0f841451.png","w":3320,"h":1830,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/d\/a\/daf448d3a5a65901e228745b0f841451"}

The difference is noticeable if the diagonal advance is included, in that case the path should be different. You should also try random obstacles like trees.

@Elias :
If the idea is to give you a bit of realism about whether you have to drift before a new obstacle, then it's better to add a shadow map to the algorithm.

The "greedy" is indeed how mine works

I know very little about this sort of thing, but it seems to me that if you have an army they wouldn't know about distant goals unless some sort of scout had discovered the goal previously, and wouldn't they be able to use his information about the terrain/obstacles?

I really hate games where the AI cheats.

EDIT: That's assuming the defending army doesn't stumble across this scout and killing him, or at least hurting him bad enough to quit scouting and go back to base.