Need Help with A star

[256mxr]

Hello!

I would like some help with a program I am developing at the moment. The objective is to implement an A star algorithm. I got this parcialy done on the web and I tried to do the missing parts.

The problem is that is not working as it should. What I have done was done in the AStarState class and Location class.

Help please :confused:

In the Location class done this:

public boolean equals(Location loc)
    {
    	return (this.xCoord==loc.xCoord && this.yCoord==loc.yCoord);    	
    }
    
    public int hashcode()
    {
    	return (this.xCoord*2+this.yCoord*2);
    }

And in the AStarState:

package astar_demo1;

import java.util.HashMap;
import java.util.Iterator;

/**
 * This class stores the basic state necessary for the A* algorithm to compute a
 * path across a map.  This state includes a collection of "open waypoints" and
 * another collection of "closed waypoints."  In addition, this class provides
 * the basic operations that the A* pathfinding algorithm needs to perform its
 * processing.
 **/
public class AStarState
{
    /** This is a reference to the map that the A* algorithm is navigating. **/
    private Map2D map;
    
    public HashMap open = new HashMap();
    public HashMap close = new HashMap();


    /**
     * Initialize a new state object for the A* pathfinding algorithm to use.
     **/
    public AStarState(Map2D map)
    {
        if (map == null)
            throw new NullPointerException("map cannot be null");

        this.map = map;
    }

    /** Returns the map that the A* pathfinder is navigating. **/
    public Map2D getMap()
    {
        return map;
    }

    /**
     * This method scans through all open waypoints, and returns the waypoint
     * with the minimum total cost.  If there are no open waypoints, this method
     * returns <code>null</code>.
     **/
    public Waypoint getMinOpenWaypoint()
    {
    	if(open.isEmpty())
    		return null;
    	else{
        // TODO:  Implement.
    		
    	    	
    	Iterator i = open.keySet().iterator();
    	
    	//int x=1;
    	//float min= 0;
    	
    	Waypoint aux,aux2=(Waypoint) open.get(i.next());
    	
    	while(i.hasNext())
    	{
    			aux = (Waypoint) open.get(i.next());
    			//if (x==1)
    				//aux2=aux;
    			//else
    			if(aux.getTotalCost()<aux2.getTotalCost())
    					aux2=aux;
    			
    		
    	}
    	return aux2;
    	
    	
        
    }
    }

    /**
     * This method adds a waypoint to (or potentially updates a waypoint already
     * in) the "open waypoints" collection.  If there is not already an open
     * waypoint at the new waypoint's location then the new waypoint is simply
     * added to the collection.  However, if there is already a waypoint at the
     * new waypoint's location, the new waypoint replaces the old one <em>only
     * if</em> the new waypoint's "previous cost" value is less than the current
     * waypoint's "previous cost" value.
     **/
    public boolean addOpenWaypoint(Waypoint newWP)
    {
        // TODO:  Implement.
    	
    	Location local = newWP.getLocation();
    	
    	if(!open.containsKey(local))	{
    		open.put(local,newWP);}
    	else{
    		Waypoint aux = (Waypoint) open.get(local);
    		if(newWP.getPreviousCost()< aux.getPreviousCost()){
    			open.put(local, newWP);
    			return true;
    			
    		}
    		
    		return false;
    	}
    	
    	return false;
    }


    /** Returns the current number of open waypoints. **/
    public int numOpenWaypoints()
    {
        // TODO:  Implement.
    	return open.size();
    	
        
    }


    /**
     * This method moves the waypoint at the specified location from the
     * open list to the closed list.
     **/
    public void closeWaypoint(Location loc)
    {
        // TODO:  Implement.
    	if (open.containsKey(loc)){
    		close.put(loc,open.get(loc));
    		open.remove(loc);
    	}
    	
    		
    	
    	
    	
    }

    /**
     * Returns true if the collection of closed waypoints contains a waypoint
     * for the specified location.
     **/
    public boolean isLocationClosed(Location loc)
    {
        // TODO:  Implement.
    	    		
    		if(close.containsKey(loc))
    			return true;
    		else
    	        return false;
    	
    }
}

You can get all the other classes in here:

http://feupload.fe.up.pt/get/GyAu6ItNASi5Mno

[256mxr]

The problem is in these last functions...the functions that work with the waypoints...

Is it ok to do cast of an iterator??

[256mxr]

The problem was at the Location class in the equals() and hashcode() functions.

[pellebye]

If your problem is solved you (are the only one who) can mark the thread solved from the tools menu on top of the thread.