truebrain@10943: /* $Id$ */
truebrain@10943: 
truebrain@10943: /**
truebrain@10943:  * A Road Pathfinder.
truebrain@10943:  *  This road pathfinder tries to find a buildable / existing route for
truebrain@10943:  *  road vehicles. You can changes the costs below using for example
truebrain@10943:  *  roadpf.cost.turn = 30. Note that it's not allowed to change the cost
truebrain@10943:  *  between consecutive calls to FindPath. You can change the cost before
truebrain@10943:  *  the first call to FindPath and after FindPath has returned an actual
truebrain@10943:  *  route. To use only existing roads, set cost.no_existing_road to
truebrain@10943:  *  cost.max_cost.
truebrain@10943:  */
truebrain@10943: class Road
truebrain@10943: {
truebrain@10943: 	_aystar_class = import("graph.aystar", "", 3);
truebrain@10943: 	_max_cost = null;              ///< The maximum cost for a route.
truebrain@10943: 	_cost_tile = null;             ///< The cost for a single tile.
truebrain@10943: 	_cost_no_existing_road = null; ///< The cost that is added to _cost_tile if no road exists yet.
truebrain@10943: 	_cost_turn = null;             ///< The cost that is added to _cost_tile if the direction changes.
truebrain@10943: 	_cost_slope = null;            ///< The extra cost if a road tile is sloped.
truebrain@10943: 	_cost_bridge_per_tile = null;  ///< The cost per tile of a bridge.
truebrain@10943: 	_cost_tunnel_per_tile = null;  ///< The cost per tile of a tunnel.
truebrain@10943: 	_cost_coast = null;            ///< The extra cost for a coast tile.
truebrain@10943: 	_pathfinder = null;            ///< A reference to the used AyStar object.
truebrain@10943: 	_lowest_cost = null;           ///< min(_cost_tile, _cost_bridge_per_tile, _cost_tunnel_per_tile)
truebrain@10943: 
truebrain@10943: 	cost = null;                   ///< Used to change the costs.
truebrain@10943: 	_running = null;
truebrain@10943: 
truebrain@10943: 	constructor()
truebrain@10943: 	{
truebrain@10943: 		this._max_cost = 2000000000;
truebrain@10943: 		this._cost_tile = 100;
truebrain@10943: 		this._cost_no_existing_road = 40;
truebrain@10943: 		this._cost_turn = 100;
truebrain@10943: 		this._cost_slope = 200;
truebrain@10943: 		this._cost_bridge_per_tile = 105;
truebrain@10943: 		this._cost_tunnel_per_tile = 105;
truebrain@10943: 		this._cost_coast = 20;
truebrain@10943: 		this._pathfinder = this._aystar_class(this._Cost, this._Estimate, this._Neighbours, this, this, this);
truebrain@10943: 
truebrain@10943: 		this.cost = this.Cost(this);
truebrain@10943: 		this._running = false;
truebrain@10943: 		this._lowest_cost = 0;
truebrain@10943: 	}
truebrain@10943: 
truebrain@10943: 	/**
truebrain@10943: 	 * Initialize a path search between sources and goals.
truebrain@10943: 	 * @param sources The source nodes.
truebrain@10943: 	 * @param goals The target nodes.
truebrain@10943: 	 * @see AyStar::InitializePath()
truebrain@10943: 	 */
truebrain@10943: 	function InitializePath(sources, goals) { this._pathfinder.InitializePath(sources, goals); }
truebrain@10943: 
truebrain@10943: 	/**
truebrain@10943: 	 * Try to find the path as indicated with InitializePath with the lowest cost.
truebrain@10943: 	 * @param iterations After how many iterations it should abort for a moment.
truebrain@10943: 	 *  This value should either be -1 for infinite, or > 0. Any other value
truebrain@10943: 	 *  aborts immediatly and will never find a path.
truebrain@10943: 	 * @return A route if one was found, or false if the amount of iterations was
truebrain@10943: 	 *  reached, or null if no path was found.
truebrain@10943: 	 *  You can call this function over and over as long as it returns false,
truebrain@10943: 	 *  which is an indication it is not yet done looking for a route.
truebrain@10943: 	 * @see AyStar::FindPath()
truebrain@10943: 	 */
truebrain@10943: 	function FindPath(iterations);
truebrain@10943: }
truebrain@10943: 
truebrain@10943: class Road.Cost
truebrain@10943: {
truebrain@10943: 	_main = null;
truebrain@10943: 
truebrain@10943: 	function _set(idx, val)
truebrain@10943: 	{
truebrain@10943: 		if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");
truebrain@10943: 
truebrain@10943: 		switch (idx) {
truebrain@10943: 			case "max_cost":         this._main._max_cost = val; break;
truebrain@10943: 			case "tile":             this._main._cost_tile = val; break;
truebrain@10943: 			case "no_existing_road": this._main._cost_no_existing_road = val; break;
truebrain@10943: 			case "turn":             this._main._cost_turn = val; break;
truebrain@10943: 			case "slope":            this._main._cost_slope = val; break;
truebrain@10943: 			case "bridge_per_tile":  this._main._cost_bridge_per_tile = val; break;
truebrain@10943: 			case "tunnel_per_tile":  this._main._cost_tunnel_per_tile = val; break;
truebrain@10943: 			case "coast":            this._main._cost_coast = val; break;
truebrain@10943: 			default: throw("the index '" + idx + "' does not exist");
truebrain@10943: 		}
truebrain@10943: 
truebrain@10943: 		return val;
truebrain@10943: 	}
truebrain@10943: 
truebrain@10943: 	function _get(idx)
truebrain@10943: 	{
truebrain@10943: 		switch (idx) {
truebrain@10943: 			case "max_cost":         return this._main._max_cost;
truebrain@10943: 			case "tile":             return this._main._cost_tile;
truebrain@10943: 			case "no_existing_road": return this._main._cost_no_existing_road;
truebrain@10943: 			case "turn":             return this._main._cost_turn;
truebrain@10943: 			case "slope":            return this._main._cost_slope;
truebrain@10943: 			case "bridge_per_tile":  return this._main._cost_bridge_per_tile;
truebrain@10943: 			case "tunnel_per_tile":  return this._main._cost_tunnel_per_tile;
truebrain@10943: 			case "coast":            return this._main._cost_coast;
truebrain@10943: 			default: throw("the index '" + idx + "' does not exist");
truebrain@10943: 		}
truebrain@10943: 	}
truebrain@10943: 
truebrain@10943: 	function constructor(main)
truebrain@10943: 	{
truebrain@10943: 		this._main = main;
truebrain@10943: 	}
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::FindPath(iterations)
truebrain@10943: {
truebrain@10943: 	this._lowest_cost = min(min(this._cost_tile, this._cost_bridge_per_tile), this._cost_tunnel_per_tile);
truebrain@10943: 	local ret = this._pathfinder.FindPath(iterations);
truebrain@10943: 	this._running = (ret == false) ? true : false;
truebrain@10943: 	return ret;
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::_Cost(path, new_node, self)
truebrain@10943: {
truebrain@10943: 	/* path == null means this is the first node of a path, so the cost is 0. */
truebrain@10943: 	if (path == null) return 0;
truebrain@10943: 
truebrain@10943: 	local prev_node = path.GetNode();
truebrain@10943: 
truebrain@10943: 	/* If the new tile is a bridge / tunnel tile, check wether we came from the other
truebrain@10943: 	 * end of the bridge / tunnel or if we just entered the bridge / tunnel. */
truebrain@10943: 	if (AIBridge.IsBridgeTile(new_node)) {
truebrain@10943: 		if (AIBridge.GetOtherBridgeEnd(new_node) != prev_node) return path.GetCost() + self._cost_tile;
truebrain@10943: 		return path.GetCost() + AIMap.DistanceManhattan(new_node, prev_node) * self._cost_bridge_per_tile;
truebrain@10943: 	}
truebrain@10943: 	if (AITunnel.IsTunnelTile(new_node)) {
truebrain@10943: 		if (AITunnel.GetOtherTunnelEnd(new_node) != prev_node) return path.GetCost() + self._cost_tile;
truebrain@10943: 		return path.GetCost() + AIMap.DistanceManhattan(new_node, prev_node) * self._cost_tunnel_per_tile;
truebrain@10943: 	}
truebrain@10943: 
truebrain@10943: 	/* Check for a turn. We do this by substracting the TileID of the current node from
truebrain@10943: 	 * the TileID of the previous node and comparing that to the difference between the
truebrain@10943: 	 * previous node and the node before that. */
truebrain@10943: 
truebrain@10943: 	local cost = self._cost_tile;
truebrain@10943: 	if (path.GetParent() != null && (prev_node - path.GetParent().GetNode()) != (new_node - prev_node)) {
truebrain@10943: 		cost += self._cost_turn;
truebrain@10943: 	}
truebrain@10943: 	/* Check if the new tile is a coast tile. */
truebrain@10943: 	if (AITile.IsCoastTile(new_node)) {
truebrain@10943: 		cost += self._cost_coast;
truebrain@10943: 	}
truebrain@10943: 	/* Check if the last tile was sloped. */
truebrain@10943: 	if (path.GetParent() != null && !AIBridge.IsBridgeTile(path.GetNode()) && !AITunnel.IsTunnelTile(path.GetNode()) &&
truebrain@10943: 	    self._IsSlopedRoad(path.GetParent().GetNode(), path.GetNode(), new_node)) {
truebrain@10943: 		cost += self._cost_slope;
truebrain@10943: 	}
truebrain@10943: 	if (!AIRoad.AreRoadTilesConnected(prev_node, new_node)) {
truebrain@10943: 		cost += self._cost_no_existing_road;
truebrain@10943: 	}
truebrain@10943: 	return path.GetCost() + cost;
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::_Estimate(cur_tile, goal_tiles, self)
truebrain@10943: {
truebrain@10943: 	local min_cost = self._max_cost;
truebrain@10943: 	/* As estimate we multiply the lowest possible cost for a single tile with
truebrain@10943: 	 * with the minimum number of tiles we need to traverse. */
truebrain@10943: 	foreach (tile in goal_tiles) {
truebrain@10943: 		min_cost = min(AIMap.DistanceManhattan(cur_tile, tile) * self._lowest_cost, min_cost);
truebrain@10943: 	}
truebrain@10943: 	return min_cost;
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::_Neighbours(path, cur_node, self)
truebrain@10943: {
truebrain@10943: 	/* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */
truebrain@10943: 	if (path.GetCost() >= self._max_cost) return [];
truebrain@10943: 	local tiles = [];
truebrain@10943: 
truebrain@10943: 	/* Check if the current tile is part of a bridge or tunnel */
truebrain@10943: 	if ((AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) &&
truebrain@10943: 	     AITile.HasTransportType(cur_node, AITile.TRANSPORT_ROAD)) {
truebrain@10943: 		local other_end = AIBridge.IsBridgeTile(cur_node) ? AIBridge.GetOtherBridgeEnd(cur_node) : AITunnel.GetOtherTunnelEnd(cur_node);
truebrain@10943: 		/* The other end of the bridge / tunnel is a neighbour. */
truebrain@10943: 		tiles.push(other_end);
truebrain@10943: 		local next_tile = null;
truebrain@10943: 		if (other_end < cur_node) {
truebrain@10943: 			if (other_end <= cur_node - AIMap.GetMapSizeX()) {
truebrain@10943: 				next_tile = cur_node + AIMap.GetMapSizeX();
truebrain@10943: 			} else {
truebrain@10943: 				next_tile = cur_node + 1;
truebrain@10943: 			}
truebrain@10943: 		} else {
truebrain@10943: 			if (other_end >= cur_node + AIMap.GetMapSizeX()) {
truebrain@10943: 				next_tile = cur_node - AIMap.GetMapSizeX();
truebrain@10943: 			} else {
truebrain@10943: 				next_tile = cur_node - 1;
truebrain@10943: 			}
truebrain@10943: 		}
truebrain@10943: 		if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AITile.IsBuildable(next_tile) ||
truebrain@10943: 				AIRoad.IsRoadTile(next_tile)) {
truebrain@10943: 			tiles.push(next_tile);
truebrain@10943: 		}
truebrain@10943: 	} else {
truebrain@10943: 		local offsets = [AIMap.GetTileIndex(0,1), AIMap.GetTileIndex(0, -1),
truebrain@10943: 		                 AIMap.GetTileIndex(1,0), AIMap.GetTileIndex(-1,0)];
truebrain@10943: 		/* Check all tiles adjacent to the current tile. */
truebrain@10943: 		foreach (offset in offsets) {
truebrain@10943: 			local next_tile = cur_node + offset;
truebrain@10943: 			/* We add them to the to the neighbours-list if one of the following applies:
truebrain@10943: 			 * 1) There already is a connections between the current tile and the next tile.
truebrain@10943: 			 * 2) We can build a road to the next tile.
truebrain@10943: 			 * 3) The next tile is the entrance of a tunnel / bridge in the correct direction. */
truebrain@10943: 			if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {
truebrain@10943: 				tiles.push(next_tile);
truebrain@10943: 			} else if ((AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) &&
truebrain@10943: 					(path.GetParent() == null || self._CheckSlopes(path.GetParent().GetNode(), cur_node, next_tile))) {
truebrain@10943: 				tiles.push(next_tile);
truebrain@10943: 			} else if (self._CheckTunnelBridge(cur_node, next_tile)) {
truebrain@10943: 				tiles.push(next_tile);
truebrain@10943: 			}
truebrain@10943: 		}
truebrain@10943: 	}
truebrain@10943: 	return tiles;
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::_IsSlopedRoad(start, middle, end)
truebrain@10943: {
truebrain@10943: 	local NW = 0; //Set to true if we want to build a road to / from the north-west
truebrain@10943: 	local NE = 0; //Set to true if we want to build a road to / from the north-east
truebrain@10943: 	local SW = 0; //Set to true if we want to build a road to / from the south-west
truebrain@10943: 	local SE = 0; //Set to true if we want to build a road to / from the south-east
truebrain@10943: 
truebrain@10943: 	if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;
truebrain@10943: 	if (middle - 1 == start || middle - 1 == end) NE = 1;
truebrain@10943: 	if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;
truebrain@10943: 	if (middle + 1 == start || middle + 1 == end) SW = 1;
truebrain@10943: 
truebrain@10943: 	/* If there is a turn in the current tile, it can't be sloped. */
truebrain@10943: 	if ((NW || SE) && (NE || SW)) return false;
truebrain@10943: 
truebrain@10943: 	local slope = AITile.GetSlope(middle);
truebrain@10943: 	/* A road on a steep slope is always sloped. */
truebrain@10943: 	if (AITile.IsSteepSlope(slope)) return true;
truebrain@10943: 
truebrain@10943: 	/* If only one corner is raised, the road is sloped. */
truebrain@10943: 	if (slope == AITile.SLOPE_N || slope == AITile.SLOPE_W) return true;
truebrain@10943: 	if (slope == AITile.SLOPE_S || slope == AITile.SLOPE_E) return true;
truebrain@10943: 
truebrain@10943: 	if (NW && (slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SE)) return true;
truebrain@10943: 	if (NE && (slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SW)) return true;
truebrain@10943: 
truebrain@10943: 	return false;
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::_CheckSlopes(start, middle, end)
truebrain@10943: {
truebrain@10943: 	local NW = 0; //Set to true if we want to build a road to / from the north-west
truebrain@10943: 	local NE = 0; //Set to true if we want to build a road to / from the north-east
truebrain@10943: 	local SW = 0; //Set to true if we want to build a road to / from the south-west
truebrain@10943: 	local SE = 0; //Set to true if we want to build a road to / from the south-east
truebrain@10943: 
truebrain@10943: 	if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;
truebrain@10943: 	if (middle - 1 == start || middle - 1 == end) NE = 1;
truebrain@10943: 	if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;
truebrain@10943: 	if (middle + 1 == start || middle + 1 == end) SW = 1;
truebrain@10943: 
truebrain@10943: 	{
truebrain@10943: 		local test_mode = AITestMode();
truebrain@10943: 		if (!AIRoad.AreRoadTilesConnected(start, middle) && !AIRoad.BuildRoad(start, middle)) return false;
truebrain@10943: 		if (!AIRoad.AreRoadTilesConnected(middle, end) && !AIRoad.BuildRoad(middle, end)) return false;
truebrain@10943: 	}
truebrain@10943: 
truebrain@10943: 	if ((NW && SE) || (NE && SW)) return true;
truebrain@10943: 
truebrain@10943: 	local slope = AITile.GetSlope(middle);
truebrain@10943: 	if (AITile.IsSteepSlope(slope)) return false;
truebrain@10943: 
truebrain@10943: 	if (slope == AITile.SLOPE_NS || slope == AITile.SLOPE_EW) return true;
truebrain@10943: 
truebrain@10943: 	if (NW && SW && (slope == AITile.SLOPE_E || slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SE)) return false;
truebrain@10943: 	if (NE && SE && (slope == AITile.SLOPE_W || slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SW)) return false;
truebrain@10943: 	if (NW && NE && (slope == AITile.SLOPE_S || slope == AITile.SLOPE_SE || slope == AITile.SLOPE_SW)) return false;
truebrain@10943: 	if (SW && SE && (slope == AITile.SLOPE_N || slope == AITile.SLOPE_NE || slope == AITile.SLOPE_NW)) return false;
truebrain@10943: 
truebrain@10943: 	return true;
truebrain@10943: }
truebrain@10943: 
truebrain@10943: function Road::_CheckTunnelBridge(current_node, new_node)
truebrain@10943: {
truebrain@10943: 	if (!AIBridge.IsBridgeTile(new_node) && !AITunnel.IsTunnelTile(new_node)) return false;
truebrain@10943: 	local dir = new_node - current_node;
truebrain@10943: 	local other_end = AIBridge.IsBridgeTile(new_node) ? AIBridge.GetOtherBridgeEnd(new_node) : AITunnel.GetOtherTunnelEnd(new_node);
truebrain@10943: 	local dir2 = other_end - new_node;
truebrain@10943: 	if ((dir < 0 && dir2 > 0) || (dir > 0 && dir2 < 0)) return false;
truebrain@10943: 	dir = abs(dir);
truebrain@10943: 	dir2 = abs(dir2);
truebrain@10943: 	if ((dir >= AIMap.GetMapSizeX() && dir2 < AIMap.GetMapSizeX()) ||
truebrain@10943: 	    (dir < AIMap.GetMapSizeX() && dir2 >= AIMap.GetMapSizeX())) return false;
truebrain@10943: 
truebrain@10943: 	return true;
truebrain@10943: }