Astar with New Heuristic

I noticed when coding up the ARA* path planner that the heuristic function I used was not correctly implemented. I used the Manhattan distance between pacman and the goal location divide by two. Since pacman is able to use the side tunnels to move from the left to the right this heuristic was not always a lower bound. Now I use the new heuristic function where the Manhattan distance is calculated in the following way:


H = min[abs(pacManX-goalX),...
abs(pacManX-rightSide)+abs(goalX-leftSide),...
abs(pacManX-leftSide)+abs(goalX-rightSide)]+...
abs(pacManY-goalY)

where the first term is the x straight-line distance; the second term is the x-distance if it is shorter for pacman to move through the right tunnel to get to the goal; and the third term is the x distance if pacman must move through the left tunnel to reach the goal. The last term is the y distance.

I have rerun the results for the Astar algorithms, leading to improvement from the old heuristic.