A* Pathfinding Project

How to custom the path by adjust the cost of the connections in pointgraph


#1

I have got a tile-based game with pointgraph show in the picture


the white line is the path generated by ABPath,but I need the red one
the rule is
1,keep walking down
2,turn the later the better
3,avoid walking back(if possible)

so, i change the cost of the connects in the graph
1,up–>down cost set to be 1000
2,down–>up cost set to be 1000000
3,–>left or -->right 2000*(MAXROW-ROW) (so the cost of upper row is bigger than the next row)

with this setting rule1 and rule2 works but rule3 never works

how can i get the custom path ,is there another way?


#2

Hi

That white path is actually shorter than the red path with your rules. It will save a large cost by moving downwards before walking right, more than it saves by having to walk back up again.

Unfortunately I’m not sure if those rules can be enforced by tweaking the path costs…
You might get a slight improvement by using the Manhattan heuristic though (A* Inspector -> Settings -> Heuristic).
See https://www.arongranberg.com/astar/documentation/dev_4_1_8_94c97625/pathfinding.html#Heuristic


#3

thank you for reply
i don’t know why i get the white path in the second image
the cost of moving backwards is set to be 1000000 much more than the cost of walking right

is it means the Astar only consider the current cost during pathfinding,ignore the total cost of the all path?


#4

so ,does it means
I can’t get the path with my rules in Astar?


#5

Ah. Right.
By default the pathfinding system assumes that all cost values are equal for bidirectional connections. I was thinking only of using bidirectional costs.
You can fix this by commenting out these lines in the PointNode.cs script

//Or if the path from the other node to this one is better

pathNode.parent = pathOther;
pathNode.cost = tmpCost;

UpdateRecursiveG(path, pathNode, handler);