Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

How to display all explored nodes with A*?

This topic is 1096 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My goal is to debug the A* program.

So whenever a node is opened, I want to display it visually.

 

Despite all the programming flaws (due to testing purposes only), how do I keep a SortedSet of ArrayList

of Opened Nodes?

 

In this case, I just keep all the nodes that are opened along the correct path.

How do I display all other opened/discarded nodes as well?

 

Thanks

Jack

 

public synchronized Path2 findPath(Node2 from, Node2 to, Unit unit) throws NoPathException {
        if (unit == null)
           throw new NullPointerException("context is null");        
        
        unit.clearOpenedNodes();
        try {
             
            Node2 current = null;
            
            openList.clear();
            if (useBitSet)
                bitSetClosedList.clear();
            else intSetClosedList.clear();
            
            int maxOpenSize = 0;  
            
            from.transition = null;
            from.h = from.getActualTimelessCost(to);
            if (from.h < 0)
                throw new NoPathException("initial cost: " + from.h);
            from.g = 0;
            from.f = from.h;             
            
            openList.add(from);
            
            // Add backup node to the unit object             
            PathPoint2 pp = new PathPoint2(from.x, from.z, 0);
            pp.f = from.getF();
            pp.g = from.getG();
            pp.h = from.getH();
            unit.AddOpenedNode(pp);                            
            
            while (! openList.isEmpty()) {
                current = openList.first();
                if (! openList.remove(current))
                    assert false;
           
                
                
                // find nodes in open list till it is exhausted
                if (useBitSet) {
                    bitSetClosedList.set(current.id);
                } else {
                    intSetClosedList.add(current.id);
                }
                
                if (current.x == to.x && current.z == to.z) {
                    float totalCost = current.g;
                    List<AStar2.Transition2> transitions = new ArrayList<AStar2.Transition2>();
                    while (current.transition != null) {
                        transitions.add(0, current.transition);                        
                        current = current.transition.fromNode();
                    }
                    
                    return new AStar2.Path2(from, transitions, totalCost);
                }
                
                for (Transition2 transition : current.getTransitions()) {
                    float cost = transition.getCost(unit);
                    if (cost < 0)
                        continue;
                    
                    // new a node out, id will not be the same, so a new node is produced
                    Node2 neighbour = transition.toNode();
                    
                    if (useBitSet) {
                        if (bitSetClosedList.get(neighbour.id))
                            continue;
                    } else {
                        if (intSetClosedList.contains(neighbour.id))
                            continue;
                    }
                    
                    if (openList.contains(neighbour))
                    {
                        // check if this path is better
                        if (current.g + cost < neighbour.g)
                        {                            
                            if (!openList.remove(neighbour))
                                assert false;
                            
                            neighbour.transition = transition;
                            neighbour.g = current.g + cost;
                            neighbour.f = neighbour.g + neighbour.h;
                             
                            pp = new PathPoint2(neighbour.x, neighbour.z, 0);
                            pp.f = neighbour.getF();
                            pp.g = neighbour.getG();
                            pp.h = neighbour.getH();
                            unit.AddOpenedNode(pp);                            
                            openList.add(neighbour);
                            
                         }
                        
                    } else { // if neighbour in openList
                        
                        neighbour.transition = transition;
                        neighbour.g = current.g + cost;
                        neighbour.h = neighbour.getActualTimelessCost(to);
                        neighbour.f = neighbour.g + neighbour.h;
                         
                        // Add backup node to the unit object                         
                        pp = new PathPoint2(neighbour.x, neighbour.z, 0);
                        pp.f = neighbour.getF();
                        pp.g = neighbour.getG();
                        pp.h = neighbour.getH();
                        unit.AddOpenedNode(pp);                                                     
                        openList.add(neighbour);
                    }  
                }
            }
              
        } finally {}
        
        throw new NoPathException();
         
}

Share this post


Link to post
Share on other sites
Advertisement

There is no such thing as a discarded node in A*. There are only open and closed nodes. You always close the node that has the lowest heuristic value and make new open nodes around it. You can't discard any unused open nodes or you break the whole idea. Looking at the code it seems to be doing the right thing so I assume you are just using different terminology because of a language barrier or something. If you want to display rest of the nodes you need to save the opennodes and closed nodes into the AStar2.Path2.

Edited by PunCrathod

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!