A Star (A*) Algorithm with Caching – Java Implementation

Route calculation is computationally an expensive operation. There are several ways how to reduce computational load on the backend. I’ll show you how I optimized my computational resources.

There are times where a bunch of people is heading to the same event using the same or at least similar paths. Following this logic, it is possible to pre-calculate some routes or implement some lazy-caching system which caches already calculated routes and makes them accessible in O(1) time.

The lazy-caching saves the route after it has been calculated. If the new searched route has the same start and end point it serves the result directly from the cache. Another advantage is that for new routes, at least some part of it can be taken from the cache.

‘Nuff said. Here’s the code.

The “caching” class.

/**
*
* @author Dzenan Hamzic
*
* this nested class is used for caching of already calculated routes
*
*/
private class RouteCache{
	// from, to->list
	private Map<GeographicPoint, Map<GeographicPoint, LinkedList<GeographicPoint>>> routeCache = new HashMap<GeographicPoint, Map<GeographicPoint,LinkedList<GeographicPoint>>>();

	public void put(GeographicPoint start, GeographicPoint end, LinkedList<GeographicPoint> route){
			routeCache.put(start, new HashMap<GeographicPoint,LinkedList<GeographicPoint>>(){{put(end, route);}});
		}

		public LinkedList<GeographicPoint> get(GeographicPoint start, GeographicPoint end){
			if(isCached(start, end)) return new LinkedList<GeographicPoint>(routeCache.get(start).get(end));
			else return new LinkedList<>();
		}

		public boolean isCached(GeographicPoint start, GeographicPoint end){
			// check if route already cached
			if(!routeCache.containsKey(start)) return false;
			if(!routeCache.get(start).containsKey(end)) return false;
			return true;
		}
	}

 

The A Star Algorithm with Caching. Check out the lines 12 and 37.

/** Find the path from start to goal using A-Star search
	 *
	 * @param start The starting location
	 * @param goal The goal location
	 * @return The list of intersections that form the shortest path from
	 *   start to goal (including both start and goal).
	 */
	public List<GeographicPoint> aStarSearch(GeographicPoint start,
											 GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
	{
		// check if route has already once been found and return it from cache
		if(this.cache.isCached(start, goal)) return this.cache.get(start, goal);

		MapNode startNode = pointNodeMap.get(start);
		MapNode endNode = pointNodeMap.get(goal);

		// setup to begin BFS
		HashMap<MapNode,MapNode> parentMap = new HashMap<MapNode,MapNode>();
		HashSet<MapNode> visited = new HashSet<MapNode>();
		Map<MapNode, Double> distances = initializeAllToInfinity();

		Queue<MapNode> priorityQueue = initQueue();

		//  enque StartNode, with distance 0
		startNode.setDistanceToStart(new Double(0));
		distances.put(startNode, new Double(0));
		priorityQueue.add(startNode);
		MapNode current = null;

		while (!priorityQueue.isEmpty()) {
			current = priorityQueue.remove();

			if (!visited.contains(current) ){
				visited.add(current);

				// check if there is cached route from this node to the end
				if (this.cache.isCached(current.getLocation(), goal)) return mergePathWithCache(goal, startNode, parentMap, current);

				// if last element in PQ reached
				if (current.equals(endNode)) return reconstructPath(parentMap, startNode, endNode);

				Set<MapNode> neighbors = getNeighbors(current);
				for (MapNode neighbor : neighbors) {
					if (!visited.contains(neighbor) ){	

						// calculate predicted distance to the end node
						double predictedDistance = neighbor.getLocation().distance(endNode.getLocation());

						// 1. calculate distance to neighbor. 2. calculate dist from start node
						double neighborDistance = current.calculateDistance(neighbor);
						double totalDistance = current.getDistanceToStart() + neighborDistance + predictedDistance;

						// check if distance smaller
						if(totalDistance < distances.get(neighbor) ){
							// update n's distance
							distances.put(neighbor, totalDistance);
							// used for PriorityQueue
							neighbor.setDistanceToStart(totalDistance);
							neighbor.setPredictedDistance(predictedDistance);
							// set parent
							parentMap.put(neighbor, current);
							// enqueue
							priorityQueue.add(neighbor);
						}
					}
				}
			}
		}
		return null;
	}

The merging route part:

/**
	 * Concatenate new part of the route with pre-cached route
	 * @return Full route (new and cached one combined)
	 */
	private List<GeographicPoint> mergePathWithCache(GeographicPoint goal, MapNode startNode,
			HashMap<MapNode, MapNode> parentMap, MapNode current) {
		System.out.println("this part of the path:["+ startNode.getLocation()+", to:"+ goal +"]is already in cache.");
		List<GeographicPoint> newRoute = reconstructPath(parentMap, startNode, current);
		List<GeographicPoint> cachedSubRoute = this.cache.get(current.getLocation(), goal);

		// remove last element
		newRoute.remove(newRoute.size()-1);
		// combine with cached route
		newRoute.addAll(cachedSubRoute);

		// cache the whole route
		this.cache.put(startNode.getLocation(), goal, (LinkedList)newRoute);
		// return result
		return newRoute;
	}

Additionally, you could persist the routes to the Redis key-value memory-store with Time To Live(TTL) attribute set to few hours so you don’t have to worry about storage capacity. This way the server would perform best during the flash crowds and scale automatically when needed.

For the missing parts check my previous blog posts.
A Star Algorithm Java Implementation
Dijskstra’s Algorithm Java Implementation

Enjoy the source and have fun.

Cheers!