route.java

Eclipse+repastS

/*
 * 〤opyright 2008 Nick Malleson

This file is part of RepastCity.

RepastCity is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

RepastCity is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with RepastCity.  If not, see <http://www.gnu.org/licenses/>.
 */
package repastcity.citycontext;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Vector;

import javax.units.NonSI;
import javax.units.SI;

import org.apache.commons.lang.ArrayUtils;

import repast.simphony.random.RandomHelper;
import repast.simphony.space.gis.Geography;
import repast.simphony.space.graph.Network;
import repast.simphony.space.graph.RepastEdge;
import repast.simphony.space.graph.ShortestPath;
import repastcity.ContextCreator;
import repastcity.GlobalVariables;
import repastcity.personcontext.SimplePerson;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.operation.distance.DistanceOp;

/**
 * Class which deals with moving people around the road network. When a Route object is created, it automatically
 * creates a route to the destination for the person who created the route. Also provides the travel function which
 * moves the person towards their destination.
 * 
 * <p>
 * Assumes that the required geographies (PersonGeography, JunctionGeography and RoadGeography) are in lat/long
 * decimal degrees. (If this is not the case then the convertToMeters and convertFromMeters functions will
 * need to be adjusted.
 * 
 * @author Nick Malleson
 *
 */

public class Route {
	
	private SimplePerson person;
	private Geography<SimplePerson> personGeography;
//	private Context<Object> mainContext;
	private Geography<Junction> junctionGeography;
	private Network<Junction> roadNetwork;
	private Geography<Road> roadGeography;
	private CityContext cityContext;
	
	private Coordinate destination;   // Can be used to check that this route is correct (agent's destination might change)
	private List<Coordinate> route; // The coordinates which describe how to get to the destination.
	private GeometryFactory geomFac;  // Used for creating Geometries
	
	// If the destination is not on a road segment we have to move to the closest road segment, then onto
	// the destination.
	private boolean destinationOnRoad;
	private Coordinate finalDestination;
	
	// The distance agents can travel each turn, not sure if this figure is any good
	private double travelPerTurn;
	
	// Buffers used for efficiency (so don't have to search for objects in entire space), 
	// not sure if these values are any good
	private double little_buffer_distance;
	private double big_buffer_distance;
	
	
	/**
	 * Create a new Route object for a Person and construct a route to the Person's destination. 
	 * @param person the person associated with this route
	 * @throws AtDestinationException if the person is already at their destination
	 * @throws NoRouteFoundException if a route cannot be made for some reason.
	 * @throws ItemNotFoundException if a required parameter cannot be found
	 */
	public Route(SimplePerson person, Coordinate destination) {
		this.person = person;
		this.destination = destination;
		// Create some useful pointers to contexts and projections
		this.personGeography = ContextCreator.getPersonGeography();
		this.junctionGeography = ContextCreator.getJunctionGeography();
		this.roadNetwork = ContextCreator.getRoadNetwork();
		this.roadGeography = ContextCreator.getRoadGeography();
		this.cityContext = (CityContext) ContextCreator.getCityContext();
		this.route = new ArrayList<Coordinate>();
		this.geomFac = new GeometryFactory();
		
		this.travelPerTurn = GlobalVariables.TRAVEL_PER_TURN;

		this.little_buffer_distance = 0.0001;
		this.big_buffer_distance = 100;
		
		this.createRoute(); // Create the list of Coordinates which make up the route 
		
//		System.out.println("RouteConstructor called for person: "+this.person.getName());
	}
	
	/** A route is a list of Coordinates which describe the route to a destination restricted to a road 
	 *  network. The algorithm consists of three major parts:
	 *  <ol> 
	 *  <li>Find out if the agent is on a road already, if not then move to the nearest road segment</li>
	 *  <li>Get from the current location (probably mid-point on a road) to the nearest junction</li>
	 *  <li>Travel to the junction which is closest to our destination (using Dijkstra's shortest path)</li> 
	 *  <li>Get from the final junction to the road which is nearest to the destination<li>
	 *  <li>Move from the road to the destination</li>
	 *  </ol>
	 */
	private void createRoute() {
		double time;
//		System.out.print("Planning route for person"+this.person.getId()+"..."); 
		time = System.currentTimeMillis();
		if (atDestination()) {
			System.out.println("Already at destination, cannot create a route for "+this.person.getName());
		}
		
		/* ** See if the current position and the destination are on road segments. ** */
		Coordinate currentCoord = personGeography.getGeometry(person).getCoordinate();
		Coordinate destCoord = this.destination;
		this.destinationOnRoad = true;
		if (!onRoad(currentCoord)) {
			// Not on a road so the first coordinate to add to the route is the point on the closest road segment.
			Coordinate nearestRoadCoord = getNearestRoadCoord(currentCoord); 
			route.add(nearestRoadCoord);
			currentCoord = nearestRoadCoord;
		}
		if (!onRoad(destCoord)) {
			// Not on a road, so need to set the destination to be the closest point on a road, and set the
			// destinationOnRoad boolean to false so we know to add the final dest coord at the end of the route
			Coordinate nearestRoadCoord = getNearestRoadCoord(destCoord);
			this.destinationOnRoad = false;
			this.finalDestination = destCoord;
			destCoord = nearestRoadCoord;
		}
		
		/* ** Find the nearest junction to our current position ** */ // XXXX: Bug: this does not necessarily find the junction closest to the destination, just the closest to the current agent's position (shouldn't cause problems because we use Dijkstra from the junction so the agent will just backtrack).
		// Find the road that this coordinate is on
		Road currentRoad = cityContext.findRoadAtCoordinates(currentCoord);
		// Find which Junction is closest to us on the road.
		Junction currentJunction = getNearestJunction(currentCoord, currentRoad);
		
		/* ** Add the coordinates describing how to get to the nearest junction** */
		route.addAll(this.getCoordsAlongRoad(
				currentCoord, junctionGeography.getGeometry(currentJunction).getCoordinate(), currentRoad, true));
		
		/* ** Find the junction which is nearest our destination ** */
		// Find the road that this coordinate is on
		Road destRoad = cityContext.findRoadAtCoordinates(destCoord);
		// Find which Junction connected to the edge is closest to the coordinate.
		Junction destJunction = getNearestJunction(destCoord, destRoad);

		/* ** Add the coordinates which describe how to get to the destination junction ** */
		route.addAll(getRouteBetweenJunctions(currentJunction, destJunction));
		
		/* ** Add the coordinates describing how to get from the final junction to the destination ** */
		route.addAll(this.getCoordsAlongRoad(
				junctionGeography.getGeometry(destJunction).getCoordinate(), destCoord, destRoad, false));
		
		if (!destinationOnRoad) {
			route.add(finalDestination);
		}

		removeDuplicateCoords(); // If the algorithm was better no coordinates would have been duplicated
		
//		System.out.println("...Finished ("+(System.currentTimeMillis()-time)+"ms)");
	}
	
	/**
	 * Travel towards our destination, as far as we can go this turn.
	 * <p> Also adds houses to the agent's cognitive environment. This is done by saving each coordinate
	 * the person passes, creating a polygon with a radius given by the "cognitive_map_search_radius" and
	 * adding all houses which touch the polygon.
	 * <p> Note: the agent might move their position many times depending on how far they are allowed to move
	 * each turn, this requires many calls to geometry.move(). This function could be improved (quite easily)
	 * by working out where the agent's final destination will be, then calling move() just once. 
	 * 
	 * @param housesPassed If not null then the buildings which the agent passed during their travels this iteration
	 * will be calculated and stored in this array. This can be useful if a burglar needs to know which houses it has just
	 * passed and, therefore, which are possible victims. This isn't done by default because it's quite an
	 * expensive operation (lots of geographic tests which must be carried out in each iteration). If the array is
	 * null then the houses passed are not calculated.
	 * @return null or the buildings passed during this iteration if housesPassed boolean is true
	 */
	public void travel() {
		if (atDestination()) {
//			System.out.println("Person "+this.person.getName()+" is at destination, not moving");
			return;
		}
//		ArrayList<Coordinate> cognitiveMapCoords = new ArrayList<Coordinate>();
		double time; // used for debugging
//		System.out.print("Travelling (person "+this.person.getName()+")..."); time = System.currentTimeMillis();

		double distTravelled = 0; // The distance travelled so far
		Coordinate currentCoord = null;	// Current location
		Coordinate target = null; 		// Target coordinate we're heading for (in route list)
		boolean travelledMaxDist = false;	// True when travelled maximum dist this iteration
		while (!travelledMaxDist && !atDestination() ) {
			currentCoord = personGeography.getGeometry(this.person).getCoordinate(); // Current location
//			cognitiveMapCoords.add(currentCoord);
			target = route.get(0);
			Geometry currentGeom = geomFac.createPoint(currentCoord);
			Geometry targetGeom = geomFac.createPoint(target);
			double distToTarget = DistanceOp.distance(currentGeom, targetGeom);
			// If we can get all the way to the next coords on the route then just go there
			if (distTravelled+distToTarget < travelPerTurn) {
				distTravelled += distToTarget;
				personGeography.move(person, targetGeom);
				route.remove(0);
//				cognitiveMapCoords.add(target);

			} // if
			else { // Otherwise move as far as we can towards the target along the road we're on
				// Get the angle between the two points (current and target) (http://forum.java.sun.com/thread.jspa?threadID=438608&messageID=1973655)
				double angle = angle(target, currentCoord)+Math.PI; // angle() returns range from -PI->PI, but moveByVector wants range 0->2PI				
				// Move along the vector the maximum distance we're allowed this turn
				double distToTravel = travelPerTurn-distTravelled;
				// Need to convert distance from long/lat degrees to meters
				double distToTravelM = Route.convertToMeters(distToTravel);
				personGeography.moveByVector(person, distToTravelM, angle);
//				cognitiveMapCoords.add(personGeography.getGeometry(this.person).getCoordinate());
				travelledMaxDist = true;
			} // else			
		} // while

				
//		System.out.println("...Finished Travelling("+(System.currentTimeMillis()-time)+"ms)");
	}
	
	/**
	 * Find the nearest coordinate which is part of a Road
	 * @param coord The coordinate from which to find the nearest road coordinate
	 * @return the nearest road coordinate
	 */
	private Coordinate getNearestRoadCoord(Coordinate coord) {
		// Search all roads in the vicinity, looking for the point which is nearest the person
		double minDist = 999999.9;
		//Road nearestRoad = null;
		Coordinate nearestPoint = null;
		Point coordGeom = geomFac.createPoint(coord);
		for (Road road:roadGeography.getObjectsWithin(coordGeom.buffer(big_buffer_distance).getEnvelopeInternal())) {
			// XXXX: BUG: if an agent is on a really long road, the long road will not be found by getObjectsWithin because it is not within the buffer 
			DistanceOp distOp = new DistanceOp(coordGeom, roadGeography.getGeometry(road));
			double thisDist = distOp.distance();
			if (thisDist < minDist) {
				minDist = thisDist;
				//nearestRoad = road;
				// Two coordinates returned by closestPoints(), need to find the one which isn''t the coord parameter
				for (Coordinate c:distOp.closestPoints()) {
					if (!c.equals(coord)) {
						nearestPoint = c;
						break;
					}
				}
			} // if thisDist < minDist
		} // for nearRoads
		return nearestPoint;
	}
	
	/**
	 * Gets the nearest junction to the current coordinate on the road that the coordinate lies on.
	 * 
	 * @param coord The coordinate we are interested in
	 * @param road The road which this coordinate is situated on
	 * @return the Junction which is closest to the coordinate.
	 */
	private Junction getNearestJunction(Coordinate coord, Road road) {
		// Find the associated edge in road network
		RepastEdge<?> edge;
		Junction j1 = null;
		Junction j2 = null;
		edge = cityContext.getEdgeFromID(road.getIdentifier());
		// Find which Junction connected to the edge is closest to the coordinate.
		j1 = (Junction) edge.getSource();
		j2 = (Junction) edge.getTarget();
		
		Geometry coordGeom = geomFac.createPoint(coord);
		Geometry geom1 = geomFac.createPoint(junctionGeography.getGeometry(j1).getCoordinate());
		Geometry geom2 = geomFac.createPoint(junctionGeography.getGeometry(j2).getCoordinate());
		DistanceOp dist1 = new DistanceOp(geom1, coordGeom);
		DistanceOp dist2 = new DistanceOp(geom2, coordGeom);
		if (dist1.distance() < dist2.distance())
			return j1;
		else
			return j2;
	}
	

	/**
	 * Returns the coordinates required to move an agent from their current position to the destination
	 * along a given road. The algorithm to do this is as follows:
	 * 		1. Starting from the destination coordinate, record each vertex and check inside the booundary of 
	 * 			each line segment until the destination point is found.