I've been modifying a pathfinding example from XNA Pathfinding example as described in my previous question Link to question here I had an issue where the character moved kept moving back and forth in a line. John McD suggestion made the brilliant I alert the way that the Heuristic calculation so that any nodes on the existing path had a lower value.
From what I've debugged in the project the new calculation seems to work fine, despite that the problem still persists. I was wondering if I implemented the Heuristic method wrong.
This is the method which houses the A* algorithm
/// <summary>
/// This Method looks at everything in the open list and chooses the next
/// path to visit based on which search type is currently selected.
/// </summary>
/// <param name="result">The node to be visited</param>
/// <returns>Whether or not SelectNodeToVisit found a node to examine
/// </returns>
private bool SelectNodeToVisit(out SearchNode result)
{
result = new SearchNode();
bool success = false;
float smallestCost = float.PositiveInfinity;
float currentCost = 0f;
if (openList.Count > 0)
{
foreach (SearchNode node in openList)
{
currentCost = Heuristic(node);
// The heuristic value gives us our optimistic estimate
// for the path length, while any path with the same
// heuristic value is equally ‘good’ in this case we’re
// favoring paths that have the same heuristic value
// but are longer.
if (currentCost <= smallestCost)
{
if (currentCost < smallestCost)
{
success = true;
result = node;
smallestCost = currentCost;
}
else if (currentCost == smallestCost &&
node.DistanceTraveled > result.DistanceTraveled)
{
success = true;
result = node;
smallestCost = currentCost;
}
}
}
}
return success;
}
This is the method which does the new Heuristic calculation
/// <summary>
/// Generates an optimistic estimate of the total path length to the goal
/// from the given position.
/// </summary>
/// <param name="location">Location to examine</param>
/// <returns>Path length estimate</returns>
private float Heuristic(SearchNode location)
{
int Nodecost = 10;
foreach (Point point in Currentpath)
{
if (location.Position == point)
Nodecost = 7;
}
return location.DistanceTraveled + location.DistanceToGoal + Nodecost;
}
This is the method which adds the point to their respective list once
/// <summary>
/// This method find the next path node to visit, puts that node on the
/// closed list and adds any nodes adjacent to the visited node to the
/// open list.
/// </summary>
private void DoSearchStep(TileMap tileMap)
{
SearchNode newOpenListNode;
bool foundNewNode = SelectNodeToVisit(out newOpenListNode);
if (foundNewNode)
{
Point currentPos = newOpenListNode.Position;
foreach (Point point in level.OpenMapTiles(currentPos, tileMap))
{
SearchNode mapTile = new SearchNode(point,
StepDistanceToEnd(point),
newOpenListNode.DistanceTraveled + 1);
if (!InList(openList, point) &&
!InList(closedList, point))
{
openList.Add(mapTile);
paths[point] = newOpenListNode.Position;
}
}
if (currentPos == endPlace)
{
searchStatus = SearchStatus.PathFound;
}
openList.Remove(newOpenListNode);
closedList.Add(newOpenListNode);
}
else
{
searchStatus = SearchStatus.NoPath;
}
}
