A* Pathfinding help

[MaD[Lion]]

Ok im making a pathfinding system. Just for learning. Its working great. Just that the algorithm doesnt return the best path. Im new to pathfinding.
And i wonder if anyone here have skills in this stuff.
The 2 screenshots show the red line as i want the path to be as close to as possible.

The small dots are the nodes checked and big glowing dots represent the path found

 

[Soga-]

How are you implementing it? You're using the F = G + H equation properly, correct?

More importantly, are you maintaining the open, closed, and on-the-path lists correctly?

 

[MaD[Lion]]

its all correct, else the algorithm wouldnt find the path.
and ye the cost is F=H+G
I asume it was the Heuristic tat was wrong. I changed it to pythagoras now and works alow better. Now i need to find an optimization to workaround the operation limit and to allow a more straitght movement

 

[Soga-]

How are you assigning G costs? What's your rule for moving diagonally?

 

[MaD[Lion]]

G cos is basically just if orthogonal then 10, if diagonal then 14 since squareroot(10^2+10^2) = 14.142...
so it is:
D_COST = 14
O_COST = 10
for x=-1 to 1
for y=-1 to 1
set Cost = O_COST+Abs(x*y)*(D_COST-O_COST)

 

[Soga-]

Cost is local to each of the correlating circle, right? Just checking...

But anyway, the route your algorithm is currently taking is of minimal distance (in your first screenshot, it shows 15 bright dots, and I counted along a more straight path and it is still 15), although its path isn't quite straight. I believe to get a truly straight path, you should prefer a diagonal path if you can move diagonally. Of course, you could also make D_COST = 10. That would make it not always favor orthogonal movement over diagonal movement. The G cost is kind of like a priority factor, the lower it is, the more the algorithm prioritizes it. You could also check diagonally adjacent nodes BEFORE orthogonally adjacent nodes. That way, if it finds a diagonally adjacent node it likes, it will tend to not override that node with an orthogonal one.

However, if that doesn't work quite as expected (prefers to move diagonally too much?) you can just have it check diagonally first IF and only IF the unit's X AND Y values do not match the target point (meaning they're NOT either on the same X axis or Y axis). Otherwise, check orthogonally first.

 

[MaD[Lion]]

it is the heuristic tat determine. Ive changed the cost constants, doesnt effect much. It only effect if D cost is lower than O cost or more than 2 its size. This is because of the part where it check if pathing through current node is better than going straight, like mountains and stuffs. But in wc3 it doesnt have mountains so its same thing.
Ive made it work now, just need tip on operation limit

 

[Soga-]

Operation limit? Like how far you can move?

 

[MaD[Lion]]

ye wc3 stop on 10k loops, and tats easily reached if u have 100 nodes (O(n^2)) in openlist, currently algorithm will reach the operation limit very fast.
Im implementing binary heap to reduce the loop alot. SO it will prolly be able to handle more. And then i will make it periodically then there will be no op limit.
Just im researching on how to make smooth path with shortest euclidean space path.
But now im too tired to read about it

 

[Soga-]

Ah, considering I'm working on a TBSRPG, the # of nodes are pretty small in my project, so I've never run into that problem. I suppose you could try taking some shortcuts such as distancing the nodes a bit and maybe making them bigger. Other than that, there's really not much I can help with.

 

[MaD[Lion]]

dunno wat TBSRPG is. BUt i asume ther eu have predefined path, not open terrain walking like wat im intending to do

 

[Soga-]

Turn based strategy RPG; like Fire Emblem. If you haven't played that, then it's like Ghost's Battle Tactics map. But yeah, there are these circles of power that represent the different "spaces" on the board. So yeah, it's a lot cheaper (performance and memory) than open terrain.

But how's the binary heap solution coming along?

 

[Dr Super Good]

You can create slight pauses or start new "threads" (if you can call them that) and pass the values to them.

 

[MaD[Lion]]

Turn based strategy RPG; like Fire Emblem. If you haven't played that, then it's like Ghost's Battle Tactics map. But yeah, there are these circles of power that represent the different "spaces" on the board. So yeah, it's a lot cheaper (performance and memory) than open terrain.

But how's the binary heap solution coming along?

Just finished coding the binary heap (or i call it NodeHeap), need to implement it into the algorithm