Skip to content

Instantly share code, notes, and snippets.

@homelinen
Created November 21, 2012 20:07
Show Gist options
  • Save homelinen/4127326 to your computer and use it in GitHub Desktop.
Save homelinen/4127326 to your computer and use it in GitHub Desktop.
My A* Algorithm for AI
package uk.calumgilchrist.ai.pathfinder;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import org.json.simple.JSONArray;
public class PathFinderAStar extends PathFinder implements FindPath {
private String start;
private String goal;
public PathFinderAStar(JSONArray array, String start) {
super(array);
this.start = start;
this.goal = start;
}
public void findPath() {
int curCost = 0;
PriorityQueue<CityNode> open = new PriorityQueue<>();
LinkedList<CityNode> closed = new LinkedList<CityNode>();
List<CityNode> neighbourCities = new LinkedList<CityNode>();
List<Route> routes = new LinkedList<Route>();
open.add(new CityNode(start, 0));
CityNode curCity;
CityNode tempCity;
CityNode tempCityDouble;
boolean inOpen = false;
boolean inClosed = false;
Iterator<CityNode> rIt;
while(!open.isEmpty() && open.element().getNumAncestors() < 8) {
curCity = open.remove();
closed.add(curCity);
routes = findOutGoingRoutes(curCity.getName());
neighbourCities = getNeighboursFromRoutes(curCity.getName(), routes);
rIt = neighbourCities.iterator();
int heuristic;
while (rIt.hasNext()) {
tempCity = rIt.next();
heuristic = 0;
if (!curCity.getName().equals(goal)) {
heuristic = getRoute(new Route(curCity.getName(), goal).hashCode()).getWeight();
}
curCost = curCity.getWeight() + tempCity.getWeight() + heuristic;
// Check if duplicates in open list are heavier and drop them
tempCityDouble = getCityFromList(tempCity.getName(), open);
inOpen = tempCityDouble != null;
if (inOpen && tempCityDouble.getWeight() > curCost) {
// remove neighbor from OPEN, because new path is better
open.remove(tempCityDouble);
}
closed.remove(getCityFromList(tempCity.getName(), closed));
tempCityDouble = getCityFromList(tempCity.getName(), curCity.getParents());
//Check if node is already in the path
if (tempCityDouble != null) {
// remove neighbor from OPEN, because new path is better
closed.add(new CityNode(tempCity.getName(), curCost, curCity));
}
inOpen = isCityPresentInList(tempCity.getName(), open);
inClosed = isCityPresentInList(tempCity.getName(), closed);
if (!inOpen && !inClosed) {
open.add(new CityNode(tempCity.getName(), curCost, curCity));
}
}
}
List<String> cityPath = findPathToNode(open.peek());
int pathWeight = getPathWeight(cityPath);
System.out.println("Winning Path: " + cityPath + " Weight: " + pathWeight);
}
/**
* Cycle through the parents of the node to get a path
* @param tempNode the last node in the path
* @return A list of city names in path order
*/
private List<String> findPathToNode(CityNode tempNode) {
List<String> cityPath = new LinkedList<String>();
//Add youngest to the list
cityPath.add(tempNode.getName());
//Add all ancestors to list until you reach an ancestor with no parent
while (tempNode.hasParent()) {
tempNode = tempNode.getParent();
cityPath.add(tempNode.getName());
}
//Flip the list as it is child -> Ancestor
Collections.reverse(cityPath);
//Add the goal on the end
cityPath.add(cityPath.size(), goal);
return cityPath;
}
/**
* Sum the weights between each city in the path
* @param cities List of city names
* @return Total Weight from beginning to end
*/
private int getPathWeight(Iterable<String> cities) {
Iterator<String> it = cities.iterator();
int pathWeight = 0;
String prevCity = it.next();
String curCity = null;
while (it.hasNext()) {
curCity = it.next();
pathWeight += getWeightBetweenCities(prevCity, curCity);
prevCity = curCity;
}
return pathWeight;
}
/**
* Find the weight of the direct route between two cities
* @param city1 Start city
* @param city2 End City
* @return The route weight
*/
private int getWeightBetweenCities(String city1, String city2) {
return getRoute(Route.hash(city1, city2)).getWeight();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment