Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » What should I add to this pathfinding tool?

This thread is locked; no one can reply to it. rss feed Print
What should I add to this pathfinding tool?
amarillion
Member #940
January 2001
avatar

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"}612659

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?

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

DanielH
Member #934
January 2001
avatar

I'm watching this thinking, does your pathfinder know where the red dot is? How does it trend to the final spot? The idea of a pathfinder is that you don't know and it finds the shortest path.

amarillion
Member #940
January 2001
avatar

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

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

It's amazing how much faster and more efficient A* is than Djikstra.

Remind me, what's the manhattan distance again?

;D, I made my hexagons align NS instead of EW.

DanielH
Member #934
January 2001
avatar

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

amarillion
Member #940
January 2001
avatar

Well, I've added touch controls and some other tweaks so it works better on mobile.

So if you have a few minutes to kill at the bus stop...

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

Elias
Member #358
May 2000

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.

--
"Either help out or stop whining" - Evert

amarillion
Member #940
January 2001
avatar

Elias said:

What is the cost and heuristic functions?

The cost function is simply 1 for each edge, except for diagonal paths in the 8-way rectangular grid, they cost SQRT(2).

The heuristic function is distance function + 0.001 * tiebreaker function.

I'll add something to show the actual values in each cell as you hover over them, so it becomes more clear.

Quote:

Maybe have another dropbox which selects from several cost and heuristic functions.

It's already there :) But the heuristic is composed of two parts, distance + tiebreaker. I guess I should make that more clear.

Quote:

The A* I know would go in a straight line towards the red dot

Doesn't it do that? If you picked the appropriate distance function, and the field is open, it will beeline straight for the goal.

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

Elias
Member #358
May 2000

Doesn't it do that?

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"}612667

--
"Either help out or stop whining" - Evert

amarillion
Member #940
January 2001
avatar

I see, in your case it's more like a greedy search. Quoting Amit's A* pages:

Quote:

If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.
At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into Greedy Best-First-Search.

So you can get this behavior by making your heuristic overestimate the actual cost. Definitely a good suggestion, I'm going to add this option to the tool.

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

RmBeer2
Member #16,660
April 2017
avatar

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.

🌈🌈🌈 🌟 C/C++ 🌟 GNU/Linux 🌟 IceCream/Cornet 🌟 🌈🌈🌈

Rm Beer for Emperor 2020!

amarillion
Member #940
January 2001
avatar

{"name":"612669","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/1\/61b286a098ae79f8fb871401398ff2c6.png","w":1210,"h":719,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/1\/61b286a098ae79f8fb871401398ff2c6"}612669

The new version has a "greedy" checkbox to make the heuristic 50% more greedy. This should correspond more to what Elias is saying.

I've also added tooltips with explanations, and the values of f, g and h. This is the minimum I can do right now, but a full explanation would probably require a whole tutorial.

Here is that link again: https://amarillion.github.io/helixgraph/examples/d3/

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

Elias
Member #358
May 2000

The "greedy" is indeed how mine works :)

--
"Either help out or stop whining" - Evert

amarillion
Member #940
January 2001
avatar

Aw, did I offend your algorithm by calling it greedy? :P

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

Arthur Kalliokoski
Second in Command
February 2005
avatar

DanielH said:

I'm watching this thinking, does your pathfinder know where the red dot is? How does it trend to the final spot? The idea of a pathfinder is that you don't know and it finds the shortest path.

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.

They all watch too much MSNBC... they get ideas.

amarillion
Member #940
January 2001
avatar

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.

Well, pathfinding is just a tool. You as game programmer get to choose how you employ it.

For example, you could mark all tiles covered by fog of war as passable (even if they are not), so the computer won't avoid obstacles it can't see yet.

You could apply some random offset to the target if it's covered by the fog of war. As though the computer suspects the target is somewhere in that region, but doesn't know exactly where.

You could use the greedy variant of the algorithm that I described, as this gives a more instinct-driven path instead of a path derived from full information.

In the end, you have to use some form of pathfinding to give the NPCs a modicum of intelligence.

--
Martijn van Iersel | My Blog | Sin & Cos | Food Chain Farm | Krampushack 2020

Go to: