Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


FantasyVII

Member Since 13 Jul 2012
Offline Last Active Today, 03:58 PM

Posts I've Made

In Topic: A* scanning extra nodes?

Today, 02:32 PM

Two thoughts:
1) Is that a floating point Vector2?  If that's your custom one, you might want to double check the comparison operator
2) Toss some parenthesis around that if, though I think it should be okay without them, if you're not getting in there, maybe that's the problem.
(OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score) < CurrentNode.G_Vaule
 
Also, why are you doing the if elseif above it, it looks like you have if(A) else if(!A), couldn't that just be if(A) else {//not A implied}

 
1) Yes, It's a floating point Vector2. Its not my custom class. Its in MonoGame/XNA.
2)I'm 100% sure that this line is the problem. I just don't know how to fix it.
 
Yeah true. It could be just if(A) else. But when I debugging I wanted things to be explicit. Idk.
 
I'm looking at the Wiki Pseudocode and I think i'm lost at this part.

tentative_g_score := g_score[current] + dist_between(current,neighbor)
if neighbor not in openset or tentative_g_score < g_score[neighbor] 

 
This is the full code

function A*(start,goal)
    closedset := the empty set    // The set of nodes already evaluated.
    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    // The map of navigated nodes.
 
    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
 
    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)
 
        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)
 
            if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset
 
    return failure
 
function reconstruct_path(came_from,current)
    total_path := [current]
    while current in came_from:
        current := came_from[current]
        total_path.append(current)
    return total_path

In Topic: A* scanning extra nodes?

Today, 12:39 PM

One thought off the top of my head is that when you're grabbing the most promising node off the open list, you're grabbing the first best one that you've found.  (At least, that's what I presume OpenList.FindIndex() does.)  That is, if you have multiple equally promising nodes, you'll process the one that was added to the list first, which is naturally dependent upon the order in which you add neighbors.

 

Other implementations are likely to use a priority queue to find the best node, which is going to have different properties in this regard.  In particular, they're likely to be semi-random in choosing amongst equally best nodes.  Even if the final paths they find are equal in cost to yours, many of the intermediate states, as well as the actual nuances of the final path itself, are bound to be different because of this difference in ordering.

 

 

Now that you pointed this out. I started debugging my code and I found out that the program never execute this part of the code. That is really odd.

        void GetNeighbor(Node Neighbor)
        {
            if (Neighbor.Position.X < GridSize.X && Neighbor.Position.X >= 0 && Neighbor.Position.Y >= 0 && Neighbor.Position.Y < GridSize.Y)
            {
                IsNodePassable(Neighbor);

                if (Neighbor.Passable)
                {
                    if (!ClosedList.Any(node => node.Position == Neighbor.Position))
                    {
                        if (!OpenList.Any(node => node.Position == Neighbor.Position))
                        {
                            Neighbor.Parent = CurrentNode;
                            Neighbor.G_Vaule = CurrentNode.G_Vaule + G_Score;
                            Neighbor.H_Value = GetHeuristicCost(Neighbor);
                            OpenList.Add(Neighbor);
                        }
                        else if (OpenList.Any(node => node.Position == Neighbor.Position))
                        {
//--------------------------This part of the code is never executed. From here 
                            if (OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score < CurrentNode.G_Vaule)
                            {
                                int NodeIndex = OpenList.FindIndex(node => node.Position == Neighbor.Position);

                                OpenList[NodeIndex].Parent = CurrentNode;
                                OpenList[NodeIndex].G_Vaule = CurrentNode.G_Vaule + G_Score;
                            }
//--------------------------To here
                        }
                    }
                }
            }
        }

 

 

This if statement is never true....

if (OpenList.SingleOrDefault(node => node.Position == Neighbor.Position).G_Vaule + G_Score < CurrentNode.G_Vaule)

In Topic: A* scanning extra nodes?

Today, 11:43 AM

I cleaned up the code and posted it. I do apologize again for not cleaning it up in the first place.

 

I don't think your diagram looks particularly problematic. It might just have been bad luck that you try to go right first, and in this particular instance that's not a good strategy.

 

I did tried to go in this order Top, Right, Bottom, Left and this happened.

void FindAllNeighborNodes()
{
    Node TopNeighbor = new Node(new Vector2(CurrentNode.Position.X, CurrentNode.Position.Y - 1));
    GetNeighbor(TopNeighbor);

    Node RightNeighbor = new Node(new Vector2(CurrentNode.Position.X + 1, CurrentNode.Position.Y));
    GetNeighbor(RightNeighbor);

    Node BottomNeighbor = new Node(new Vector2(CurrentNode.Position.X, CurrentNode.Position.Y + 1));
    GetNeighbor(BottomNeighbor);

    Node LeftNeighbor = new Node(new Vector2(CurrentNode.Position.X - 1, CurrentNode.Position.Y));
    GetNeighbor(LeftNeighbor); 
}

YZAXG1d.png?1

 

The same kind of thing happens if you go to the website and change the Weight to anything above 1 (example 2). But the website A* still searches less nodes than my algorithm. I don't understand what I'm doing wrong. Both my algorithm and the website algorithm are using the Manhattan Heuristic.

 

bc7gPBg.png?1


In Topic: A* scanning extra nodes?

Today, 11:10 AM

... in general, IMHO, if you are going to ask for help, and then post code, take that extra 5 minutes and refactor the code to make it cleaner.  I'm more likely to look at code that is concise that some cut and pasta dump.  

 

I agree. I do apologize. Being lazy is no excuse. I will clean it up.


In Topic: A* scanning extra nodes?

Today, 10:52 AM

Offhand, without looking at the code, it could just be a difference in heuristics.  You may want to look at the other pathfinder's heuristic code and see how it matches up.

 

EDIT: Also, you could really condense your code quite a bit, the different neighbor code is all virtually the same.

EDIT2:  Where is F value set on the node?  Or F_vaule.

The F value is calculated in the node class.

internal int F_Vaule
{
    get { return H_Value + G_Vaule; }
    private set { }
}

I don't think your diagram looks particularly problematic. It might just have been bad luck that you try to go right first, and in this particular instance that's not a good strategy.

 

You are the king of copying and pasting code. smile.png You should write a loop instead of four blocks of nearly identical code. For instance, you can write a function that returns a list of neighbors and then loop over them. I implemented A* as part of an engine to play Quoridor, and the implementation is 30 lines of code.

I see.

 

Hahahahaha biggrin.png

 

I know I can put the neighbour code in a single function and just make it 30 lines instead of 200. But When I wrote this code, I was just prototyping and see if I can get the algorithm to work tongue.png

 

I will clean it up. I was just too lazy tongue.png


PARTNERS