Created
November 21, 2012 20:07
-
-
Save homelinen/4127326 to your computer and use it in GitHub Desktop.
My A* Algorithm for AI
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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