1

/* $Id$ */

     2

     3

/**

     4

 * A Road Pathfinder.

     5

 *  This road pathfinder tries to find a buildable / existing route for

     6

 *  road vehicles. You can changes the costs below using for example

     7

 *  roadpf.cost.turn = 30. Note that it's not allowed to change the cost

     8

 *  between consecutive calls to FindPath. You can change the cost before

     9

 *  the first call to FindPath and after FindPath has returned an actual

    10

 *  route. To use only existing roads, set cost.no_existing_road to

    11

 *  cost.max_cost.

    12

 */

    13

class Road

    14

{

    15

	_aystar_class = import("graph.aystar", "", 3);

    16

	_max_cost = null;              ///< The maximum cost for a route.

    17

	_cost_tile = null;             ///< The cost for a single tile.

    18

	_cost_no_existing_road = null; ///< The cost that is added to _cost_tile if no road exists yet.

    19

	_cost_turn = null;             ///< The cost that is added to _cost_tile if the direction changes.

    20

	_cost_slope = null;            ///< The extra cost if a road tile is sloped.

    21

	_cost_bridge_per_tile = null;  ///< The cost per tile of a bridge.

    22

	_cost_tunnel_per_tile = null;  ///< The cost per tile of a tunnel.

    23

	_cost_coast = null;            ///< The extra cost for a coast tile.

    24

	_pathfinder = null;            ///< A reference to the used AyStar object.

    25

	_lowest_cost = null;           ///< min(_cost_tile, _cost_bridge_per_tile, _cost_tunnel_per_tile)

    26

    27

	cost = null;                   ///< Used to change the costs.

    28

	_running = null;

    29

    30

	constructor()

    31

	{

    32

		this._max_cost = 2000000000;

    33

		this._cost_tile = 100;

    34

		this._cost_no_existing_road = 40;

    35

		this._cost_turn = 100;

    36

		this._cost_slope = 200;

    37

		this._cost_bridge_per_tile = 105;

    38

		this._cost_tunnel_per_tile = 105;

    39

		this._cost_coast = 20;

    40

		this._pathfinder = this._aystar_class(this._Cost, this._Estimate, this._Neighbours, this, this, this);

    41

    42

		this.cost = this.Cost(this);

    43

		this._running = false;

    44

		this._lowest_cost = 0;

    45

	}

    46

    47

	/**

    48

	 * Initialize a path search between sources and goals.

    49

	 * @param sources The source nodes.

    50

	 * @param goals The target nodes.

    51

	 * @see AyStar::InitializePath()

    52

	 */

    53

	function InitializePath(sources, goals) { this._pathfinder.InitializePath(sources, goals); }

    54

    55

	/**

    56

	 * Try to find the path as indicated with InitializePath with the lowest cost.

    57

	 * @param iterations After how many iterations it should abort for a moment.

    58

	 *  This value should either be -1 for infinite, or > 0. Any other value

    59

	 *  aborts immediatly and will never find a path.

    60

	 * @return A route if one was found, or false if the amount of iterations was

    61

	 *  reached, or null if no path was found.

    62

	 *  You can call this function over and over as long as it returns false,

    63

	 *  which is an indication it is not yet done looking for a route.

    64

	 * @see AyStar::FindPath()

    65

	 */

    66

	function FindPath(iterations);

    67

}

    68

    69

class Road.Cost

    70

{

    71

	_main = null;

    72

    73

	function _set(idx, val)

    74

	{

    75

		if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");

    76

    77

		switch (idx) {

    78

			case "max_cost":         this._main._max_cost = val; break;

    79

			case "tile":             this._main._cost_tile = val; break;

    80

			case "no_existing_road": this._main._cost_no_existing_road = val; break;

    81

			case "turn":             this._main._cost_turn = val; break;

    82

			case "slope":            this._main._cost_slope = val; break;

    83

			case "bridge_per_tile":  this._main._cost_bridge_per_tile = val; break;

    84

			case "tunnel_per_tile":  this._main._cost_tunnel_per_tile = val; break;

    85

			case "coast":            this._main._cost_coast = val; break;

    86

			default: throw("the index '" + idx + "' does not exist");

    87

		}

    88

    89

		return val;

    90

	}

    91

    92

	function _get(idx)

    93

	{

    94

		switch (idx) {

    95

			case "max_cost":         return this._main._max_cost;

    96

			case "tile":             return this._main._cost_tile;

    97

			case "no_existing_road": return this._main._cost_no_existing_road;

    98

			case "turn":             return this._main._cost_turn;

    99

			case "slope":            return this._main._cost_slope;

   100

			case "bridge_per_tile":  return this._main._cost_bridge_per_tile;

   101

			case "tunnel_per_tile":  return this._main._cost_tunnel_per_tile;

   102

			case "coast":            return this._main._cost_coast;

   103

			default: throw("the index '" + idx + "' does not exist");

   104

		}

   105

	}

   106

   107

	function constructor(main)

   108

	{

   109

		this._main = main;

   110

	}

   111

}

   112

   113

function Road::FindPath(iterations)

   114

{

   115

	this._lowest_cost = min(min(this._cost_tile, this._cost_bridge_per_tile), this._cost_tunnel_per_tile);

   116

	local ret = this._pathfinder.FindPath(iterations);

   117

	this._running = (ret == false) ? true : false;

   118

	return ret;

   119

}

   120

   121

function Road::_Cost(path, new_node, self)

   122

{

   123

	/* path == null means this is the first node of a path, so the cost is 0. */

   124

	if (path == null) return 0;

   125

   126

	local prev_node = path.GetNode();

   127

   128

	/* If the new tile is a bridge / tunnel tile, check wether we came from the other

   129

	 * end of the bridge / tunnel or if we just entered the bridge / tunnel. */

   130

	if (AIBridge.IsBridgeTile(new_node)) {

   131

		if (AIBridge.GetOtherBridgeEnd(new_node) != prev_node) return path.GetCost() + self._cost_tile;

   132

		return path.GetCost() + AIMap.DistanceManhattan(new_node, prev_node) * self._cost_bridge_per_tile;

   133

	}

   134

	if (AITunnel.IsTunnelTile(new_node)) {

   135

		if (AITunnel.GetOtherTunnelEnd(new_node) != prev_node) return path.GetCost() + self._cost_tile;

   136

		return path.GetCost() + AIMap.DistanceManhattan(new_node, prev_node) * self._cost_tunnel_per_tile;

   137

	}

   138

   139

	/* Check for a turn. We do this by substracting the TileID of the current node from

   140

	 * the TileID of the previous node and comparing that to the difference between the

   141

	 * previous node and the node before that. */

   142

   143

	local cost = self._cost_tile;

   144

	if (path.GetParent() != null && (prev_node - path.GetParent().GetNode()) != (new_node - prev_node)) {

   145

		cost += self._cost_turn;

   146

	}

   147

	/* Check if the new tile is a coast tile. */

   148

	if (AITile.IsCoastTile(new_node)) {

   149

		cost += self._cost_coast;

   150

	}

   151

	/* Check if the last tile was sloped. */

   152

	if (path.GetParent() != null && !AIBridge.IsBridgeTile(path.GetNode()) && !AITunnel.IsTunnelTile(path.GetNode()) &&

   153

	    self._IsSlopedRoad(path.GetParent().GetNode(), path.GetNode(), new_node)) {

   154

		cost += self._cost_slope;

   155

	}

   156

	if (!AIRoad.AreRoadTilesConnected(prev_node, new_node)) {

   157

		cost += self._cost_no_existing_road;

   158

	}

   159

	return path.GetCost() + cost;

   160

}

   161

   162

function Road::_Estimate(cur_tile, goal_tiles, self)

   163

{

   164

	local min_cost = self._max_cost;

   165

	/* As estimate we multiply the lowest possible cost for a single tile with

   166

	 * with the minimum number of tiles we need to traverse. */

   167

	foreach (tile in goal_tiles) {

   168

		min_cost = min(AIMap.DistanceManhattan(cur_tile, tile) * self._lowest_cost, min_cost);

   169

	}

   170

	return min_cost;

   171

}

   172

   173

function Road::_Neighbours(path, cur_node, self)

   174

{

   175

	/* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */

   176

	if (path.GetCost() >= self._max_cost) return [];

   177

	local tiles = [];

   178

   179

	/* Check if the current tile is part of a bridge or tunnel */

   180

	if ((AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) &&

   181

	     AITile.HasTransportType(cur_node, AITile.TRANSPORT_ROAD)) {

   182

		local other_end = AIBridge.IsBridgeTile(cur_node) ? AIBridge.GetOtherBridgeEnd(cur_node) : AITunnel.GetOtherTunnelEnd(cur_node);

   183

		/* The other end of the bridge / tunnel is a neighbour. */

   184

		tiles.push(other_end);

   185

		local next_tile = null;

   186

		if (other_end < cur_node) {

   187

			if (other_end <= cur_node - AIMap.GetMapSizeX()) {

   188

				next_tile = cur_node + AIMap.GetMapSizeX();

   189

			} else {

   190

				next_tile = cur_node + 1;

   191

			}

   192

		} else {

   193

			if (other_end >= cur_node + AIMap.GetMapSizeX()) {

   194

				next_tile = cur_node - AIMap.GetMapSizeX();

   195

			} else {

   196

				next_tile = cur_node - 1;

   197

			}

   198

		}

   199

		if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AITile.IsBuildable(next_tile) ||

   200

				AIRoad.IsRoadTile(next_tile)) {

   201

			tiles.push(next_tile);

   202

		}

   203

	} else {

   204

		local offsets = [AIMap.GetTileIndex(0,1), AIMap.GetTileIndex(0, -1),

   205

		                 AIMap.GetTileIndex(1,0), AIMap.GetTileIndex(-1,0)];

   206

		/* Check all tiles adjacent to the current tile. */

   207

		foreach (offset in offsets) {

   208

			local next_tile = cur_node + offset;

   209

			/* We add them to the to the neighbours-list if one of the following applies:

   210

			 * 1) There already is a connections between the current tile and the next tile.

   211

			 * 2) We can build a road to the next tile.

   212

			 * 3) The next tile is the entrance of a tunnel / bridge in the correct direction. */

   213

			if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {

   214

				tiles.push(next_tile);

   215

			} else if ((AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) &&

   216

					(path.GetParent() == null || self._CheckSlopes(path.GetParent().GetNode(), cur_node, next_tile))) {

   217

				tiles.push(next_tile);

   218

			} else if (self._CheckTunnelBridge(cur_node, next_tile)) {

   219

				tiles.push(next_tile);

   220

			}

   221

		}

   222

	}

   223

	return tiles;

   224

}

   225

   226

function Road::_IsSlopedRoad(start, middle, end)

   227

{

   228

	local NW = 0; //Set to true if we want to build a road to / from the north-west

   229

	local NE = 0; //Set to true if we want to build a road to / from the north-east

   230

	local SW = 0; //Set to true if we want to build a road to / from the south-west

   231

	local SE = 0; //Set to true if we want to build a road to / from the south-east

   232

   233

	if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;

   234

	if (middle - 1 == start || middle - 1 == end) NE = 1;

   235

	if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;

   236

	if (middle + 1 == start || middle + 1 == end) SW = 1;

   237

   238

	/* If there is a turn in the current tile, it can't be sloped. */

   239

	if ((NW || SE) && (NE || SW)) return false;

   240

   241

	local slope = AITile.GetSlope(middle);

   242

	/* A road on a steep slope is always sloped. */

   243

	if (AITile.IsSteepSlope(slope)) return true;

   244

   245

	/* If only one corner is raised, the road is sloped. */

   246

	if (slope == AITile.SLOPE_N || slope == AITile.SLOPE_W) return true;

   247

	if (slope == AITile.SLOPE_S || slope == AITile.SLOPE_E) return true;

   248

   249

	if (NW && (slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SE)) return true;

   250

	if (NE && (slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SW)) return true;

   251

   252

	return false;

   253

}

   254

   255

function Road::_CheckSlopes(start, middle, end)

   256

{

   257

	local NW = 0; //Set to true if we want to build a road to / from the north-west

   258

	local NE = 0; //Set to true if we want to build a road to / from the north-east

   259

	local SW = 0; //Set to true if we want to build a road to / from the south-west

   260

	local SE = 0; //Set to true if we want to build a road to / from the south-east

   261

   262

	if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;

   263

	if (middle - 1 == start || middle - 1 == end) NE = 1;

   264

	if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;

   265

	if (middle + 1 == start || middle + 1 == end) SW = 1;

   266

   267

	{

   268

		local test_mode = AITestMode();

   269

		if (!AIRoad.AreRoadTilesConnected(start, middle) && !AIRoad.BuildRoad(start, middle)) return false;

   270

		if (!AIRoad.AreRoadTilesConnected(middle, end) && !AIRoad.BuildRoad(middle, end)) return false;

   271

	}

   272

   273

	if ((NW && SE) || (NE && SW)) return true;

   274

   275

	local slope = AITile.GetSlope(middle);

   276

	if (AITile.IsSteepSlope(slope)) return false;

   277

   278

	if (slope == AITile.SLOPE_NS || slope == AITile.SLOPE_EW) return true;

   279

   280

	if (NW && SW && (slope == AITile.SLOPE_E || slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SE)) return false;

   281

	if (NE && SE && (slope == AITile.SLOPE_W || slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SW)) return false;

   282

	if (NW && NE && (slope == AITile.SLOPE_S || slope == AITile.SLOPE_SE || slope == AITile.SLOPE_SW)) return false;

   283

	if (SW && SE && (slope == AITile.SLOPE_N || slope == AITile.SLOPE_NE || slope == AITile.SLOPE_NW)) return false;

   284

   285

	return true;

   286

}

   287

   288

function Road::_CheckTunnelBridge(current_node, new_node)

   289

{

   290

	if (!AIBridge.IsBridgeTile(new_node) && !AITunnel.IsTunnelTile(new_node)) return false;

   291

	local dir = new_node - current_node;

   292

	local other_end = AIBridge.IsBridgeTile(new_node) ? AIBridge.GetOtherBridgeEnd(new_node) : AITunnel.GetOtherTunnelEnd(new_node);

   293

	local dir2 = other_end - new_node;

   294

	if ((dir < 0 && dir2 > 0) || (dir > 0 && dir2 < 0)) return false;

   295

	dir = abs(dir);

   296

	dir2 = abs(dir2);

   297

	if ((dir >= AIMap.GetMapSizeX() && dir2 < AIMap.GetMapSizeX()) ||

   298

	    (dir < AIMap.GetMapSizeX() && dir2 >= AIMap.GetMapSizeX())) return false;

   299

   300

	return true;

   301

}