I've been reading this: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
But there are some things I don't understand, for example the article says to use something like this for pathfinding with diagonal movement:
function heuristic(node) = dx = abs(node.x - goal.x) dy = abs(node.y - goal.y) return D * max(dx, dy)
I don't know how do set D to get a natural looking path like in the article, I set D to the lowest cost between adjacent squares like it said, and I don't know what they meant by the stuff about the heuristic should be 4*D, that does not seem to change any thing.
This is my heuristic function and move function:
def heuristic(self, node, goal): D = 5 dx = abs(node.x - goal.x) dy = abs(node.y - goal.y) return D * max(dx, dy) def move_cost(self, current, node): cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1 return 7 if cross else 5
The smooth sailing path we want to happen:
The rest of my code: http://pastebin.com/TL2cEkeX
This is the best solution I have found so far:
def heuristic(node, start, goal): dx1 = node.x - goal.x dy1 = node.y - goal.y dx2 = start.x - goal.x dy2 = start.y - goal.y cross = abs(dx1*dy2 - dx2*dy1) dx3 = abs(dx1) dy3 = abs(dy1) return 5 + (cross*0.01) * (dx3+dy3) + (sqrt(2)-2) * min(dx3, dy3) def move_cost(current, node): cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1 return 7 if cross else 5
It produces the desired path from the second pic, but does not handle obstacles very well (tends to crawl on walls) and fails to produce optimal paths sometimes on longer distances.
What are some tweaks and optimizations I can apply to improve it?