Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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;
    }
}
share|improve this question
    
Quick point: your foreach in the Heuristic function could do with a break inside the if statement. You don't need to keep iterating through the path once you've found the point. –  tenpn Aug 26 '11 at 16:17
    
...And it's been a while since I've written an A* implementation, but that doesn't look right to me. You have no closed list to stop you looping back on yourself. But it seems to be some kind of timesliced implementation so maybe I'm wrong. –  tenpn Aug 26 '11 at 16:22
    
It does add the points to a open and closed list, I've just added the method which does to the question –  dbomb101 Aug 26 '11 at 16:26

1 Answer 1

up vote 0 down vote accepted

Wait...

node.DistanceTraveled > result.DistanceTraveled

shouldn't that be:

node.DistanceTraveled < result.DistanceTraveled

Otherwise it's trying to pick tiles with a slightly longer path, no?

share|improve this answer
    
Tried it out, still no luck –  dbomb101 Aug 26 '11 at 17:00
    
@dbomb101, Also... this should add 10 instead of 1, no? SearchNode mapTile = new SearchNode(point, StepDistanceToEnd(point), newOpenListNode.DistanceTraveled + 1); –  John McDonald Aug 26 '11 at 17:11
    
That is just to search for different nodes the actual calculations took place in the second method listed –  dbomb101 Aug 26 '11 at 18:11
    
@dbomb101: Did this really answer the question? Of not, I'd need access to the source in order to help out some more. PM me –  John McDonald Aug 31 '11 at 14:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.