Files
@ r10696:8dfe83e30d01
Branch filter:
Location: cpp/openttd-patchpack/source/bin/ai/library/pathfinder/rail/main.nut
r10696:8dfe83e30d01
15.8 KiB
text/plain
(svn r15027) -Merge: tomatos and bananas left to be, here is NoAI for all to see.
NoAI is an API (a framework) to build your own AIs in. See:
http://wiki.openttd.org/wiki/index.php/AI:Main_Page
With many thanks to:
- glx and Rubidium for their syncing, feedback and hard work
- Yexo for his feedback, patches, and AIs which tested the system very deep
- Morloth for his feedback and patches
- TJIP for hosting a challenge which kept NoAI on track
- All AI authors for testing our AI API, and all other people who helped in one way or another
-Remove: all old AIs and their cheats/hacks
NoAI is an API (a framework) to build your own AIs in. See:
http://wiki.openttd.org/wiki/index.php/AI:Main_Page
With many thanks to:
- glx and Rubidium for their syncing, feedback and hard work
- Yexo for his feedback, patches, and AIs which tested the system very deep
- Morloth for his feedback and patches
- TJIP for hosting a challenge which kept NoAI on track
- All AI authors for testing our AI API, and all other people who helped in one way or another
-Remove: all old AIs and their cheats/hacks
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 | /* $Id$ */
/**
* A Rail Pathfinder.
*/
class Rail
{
_aystar_class = import("graph.aystar", "", 4);
_max_cost = null; ///< The maximum cost for a route.
_cost_tile = null; ///< The cost for a single tile.
_cost_diagonal_tile = null; ///< The cost for a diagonal tile.
_cost_turn = null; ///< The cost that is added to _cost_tile if the direction changes.
_cost_slope = null; ///< The extra cost if a rail tile is sloped.
_cost_bridge_per_tile = null; ///< The cost per tile of a new bridge, this is added to _cost_tile.
_cost_tunnel_per_tile = null; ///< The cost per tile of a new tunnel, this is added to _cost_tile.
_cost_coast = null; ///< The extra cost for a coast tile.
_pathfinder = null; ///< A reference to the used AyStar object.
_max_bridge_length = null; ///< The maximum length of a bridge that will be build.
_max_tunnel_length = null; ///< The maximum length of a tunnel that will be build.
cost = null; ///< Used to change the costs.
_running = null;
_goals = null;
constructor()
{
this._max_cost = 10000000;
this._cost_tile = 100;
this._cost_diagonal_tile = 70;
this._cost_turn = 50;
this._cost_slope = 100;
this._cost_bridge_per_tile = 150;
this._cost_tunnel_per_tile = 120;
this._cost_coast = 20;
this._max_bridge_length = 6;
this._max_tunnel_length = 6;
this._pathfinder = this._aystar_class(this._Cost, this._Estimate, this._Neighbours, this._CheckDirection, this, this, this, this);
this.cost = this.Cost(this);
this._running = false;
}
/**
* Initialize a path search between sources and goals.
* @param sources The source tiles.
* @param goals The target tiles.
* @param ignored_tiles An array of tiles that cannot occur in the final path.
* @see AyStar::InitializePath()
*/
function InitializePath(sources, goals, ignored_tiles = []) {
local nsources = [];
foreach (node in sources) {
local path = this._pathfinder.Path(null, node[1], 0xFF, this._Cost, this);
path = this._pathfinder.Path(path, node[0], 0xFF, this._Cost, this);
nsources.push(path);
}
this._goals = goals;
this._pathfinder.InitializePath(nsources, goals, ignored_tiles);
}
/**
* Try to find the path as indicated with InitializePath with the lowest cost.
* @param iterations After how many iterations it should abort for a moment.
* This value should either be -1 for infinite, or > 0. Any other value
* aborts immediatly and will never find a path.
* @return A route if one was found, or false if the amount of iterations was
* reached, or null if no path was found.
* You can call this function over and over as long as it returns false,
* which is an indication it is not yet done looking for a route.
* @see AyStar::FindPath()
*/
function FindPath(iterations);
};
class Rail.Cost
{
_main = null;
function _set(idx, val)
{
if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");
switch (idx) {
case "max_cost": this._main._max_cost = val; break;
case "tile": this._main._cost_tile = val; break;
case "diagonal_tile": this._cost_diagonal_tile = val; break;
case "turn": this._main._cost_turn = val; break;
case "slope": this._main._cost_slope = val; break;
case "bridge_per_tile": this._main._cost_bridge_per_tile = val; break;
case "tunnel_per_tile": this._main._cost_tunnel_per_tile = val; break;
case "coast": this._main._cost_coast = val; break;
case "max_bridge_length": this._main._max_bridge_length = val; break;
case "max_tunnel_length": this._main._max_tunnel_length = val; break;
default: throw("the index '" + idx + "' does not exist");
}
return val;
}
function _get(idx)
{
switch (idx) {
case "max_cost": return this._main._max_cost;
case "tile": return this._main._cost_tile;
case "diagonal_tile": return this._cost_diagonal_tile;
case "turn": return this._main._cost_turn;
case "slope": return this._main._cost_slope;
case "bridge_per_tile": return this._main._cost_bridge_per_tile;
case "tunnel_per_tile": return this._main._cost_tunnel_per_tile;
case "coast": return this._main._cost_coast;
case "max_bridge_length": return this._main._max_bridge_length;
case "max_tunnel_length": return this._main._max_tunnel_length;
default: throw("the index '" + idx + "' does not exist");
}
}
constructor(main)
{
this._main = main;
}
};
function Rail::FindPath(iterations)
{
local test_mode = AITestMode();
local ret = this._pathfinder.FindPath(iterations);
this._running = (ret == false) ? true : false;
if (!this._running && ret != null) {
foreach (goal in this._goals) {
if (goal[0] == ret.GetTile()) {
return this._pathfinder.Path(ret, goal[1], 0, this._Cost, this);
}
}
}
return ret;
}
function Rail::_GetBridgeNumSlopes(end_a, end_b)
{
local slopes = 0;
local direction = (end_b - end_a) / AIMap.DistanceManhattan(end_a, end_b);
local slope = AITile.GetSlope(end_a);
if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
(slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
slopes++;
}
local slope = AITile.GetSlope(end_b);
direction = -direction;
if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
(slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
slopes++;
}
return slopes;
}
function Rail::_nonzero(a, b)
{
return a != 0 ? a : b;
}
function Rail::_Cost(path, new_tile, new_direction, self)
{
/* path == null means this is the first node of a path, so the cost is 0. */
if (path == null) return 0;
local prev_tile = path.GetTile();
/* If the new tile is a bridge / tunnel tile, check whether we came from the other
* end of the bridge / tunnel or if we just entered the bridge / tunnel. */
if (AIBridge.IsBridgeTile(new_tile)) {
if (AIBridge.GetOtherBridgeEnd(new_tile) != prev_tile) {
local cost = path.GetCost() + self._cost_tile;
if (path.GetParent() != null && path.GetParent().GetTile() - prev_tile != prev_tile - new_tile) cost += self._cost_turn;
return cost;
}
return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
}
if (AITunnel.IsTunnelTile(new_tile)) {
if (AITunnel.GetOtherTunnelEnd(new_tile) != prev_tile) {
local cost = path.GetCost() + self._cost_tile;
if (path.GetParent() != null && path.GetParent().GetTile() - prev_tile != prev_tile - new_tile) cost += self._cost_turn;
return cost;
}
return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile;
}
/* If the two tiles are more then 1 tile apart, the pathfinder wants a bridge or tunnel
* to be build. It isn't an existing bridge / tunnel, as that case is already handled. */
if (AIMap.DistanceManhattan(new_tile, prev_tile) > 1) {
/* Check if we should build a bridge or a tunnel. */
local cost = path.GetCost();
if (AITunnel.GetOtherTunnelEnd(new_tile) == prev_tile) {
cost += AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_tunnel_per_tile);
} else {
cost += AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_bridge_per_tile) + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
}
if (path.GetParent() != null && path.GetParent().GetParent() != null &&
path.GetParent().GetParent().GetTile() - path.GetParent().GetTile() != max(AIMap.GetTileX(prev_tile) - AIMap.GetTileX(new_tile), AIMap.GetTileY(prev_tile) - AIMap.GetTileY(new_tile)) / AIMap.DistanceManhattan(new_tile, prev_tile)) {
cost += self._cost_turn;
}
return cost;
}
/* Check for a turn. We do this by substracting the TileID of the current
* node from the TileID of the previous node and comparing that to the
* difference between the tile before the previous node and the node before
* that. */
local cost = self._cost_tile;
if (path.GetParent() != null && AIMap.DistanceManhattan(path.GetParent().GetTile(), prev_tile) == 1 && path.GetParent().GetTile() - prev_tile != prev_tile - new_tile) cost = self._cost_diagonal_tile;
if (path.GetParent() != null && path.GetParent().GetParent() != null &&
AIMap.DistanceManhattan(new_tile, path.GetParent().GetParent().GetTile()) == 3 &&
path.GetParent().GetParent().GetTile() - path.GetParent().GetTile() != prev_tile - new_tile) {
cost += self._cost_turn;
}
/* Check if the new tile is a coast tile. */
if (AITile.IsCoastTile(new_tile)) {
cost += self._cost_coast;
}
/* Check if the last tile was sloped. */
if (path.GetParent() != null && !AIBridge.IsBridgeTile(prev_tile) && !AITunnel.IsTunnelTile(prev_tile) &&
self._IsSlopedRail(path.GetParent().GetTile(), prev_tile, new_tile)) {
cost += self._cost_slope;
}
/* We don't use already existing rail, so the following code is unused. It
* assigns if no rail exists along the route. */
/*
if (path.GetParent() != null && !AIRail.AreTilesConnected(path.GetParent().GetTile(), prev_tile, new_tile)) {
cost += self._cost_no_existing_rail;
}
*/
return path.GetCost() + cost;
}
function Rail::_Estimate(cur_tile, cur_direction, goal_tiles, self)
{
local min_cost = self._max_cost;
/* As estimate we multiply the lowest possible cost for a single tile with
* with the minimum number of tiles we need to traverse. */
foreach (tile in goal_tiles) {
local dx = abs(AIMap.GetTileX(cur_tile) - AIMap.GetTileX(tile[0]));
local dy = abs(AIMap.GetTileY(cur_tile) - AIMap.GetTileY(tile[0]));
min_cost = min(min_cost, min(dx, dy) * self._cost_diagonal_tile * 2 + (max(dx, dy) - min(dx, dy)) * self._cost_tile);
}
return min_cost;
}
function Rail::_Neighbours(path, cur_node, self)
{
if (AITile.HasTransportType(cur_node, AITile.TRANSPORT_RAIL)) return [];
/* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */
if (path.GetCost() >= self._max_cost) return [];
local tiles = [];
local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
/* Check if the current tile is part of a bridge or tunnel. */
if (AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) {
/* We don't use existing rails, so neither existing bridges / tunnels. */
} else if (path.GetParent() != null && AIMap.DistanceManhattan(cur_node, path.GetParent().GetTile()) > 1) {
local other_end = path.GetParent().GetTile();
local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
foreach (offset in offsets) {
if (AIRail.BuildRail(cur_node, next_tile, next_tile + offset)) {
tiles.push([next_tile, self._GetDirection(other_end, cur_node, next_tile, true)]);
}
}
} else {
/* Check all tiles adjacent to the current tile. */
foreach (offset in offsets) {
local next_tile = cur_node + offset;
/* Don't turn back */
if (path.GetParent() != null && next_tile == path.GetParent().GetTile()) continue;
/* Disallow 90 degree turns */
if (path.GetParent() != null && path.GetParent().GetParent() != null &&
next_tile - cur_node == path.GetParent().GetParent().GetTile() - path.GetParent().GetTile()) continue;
/* We add them to the to the neighbours-list if we can build a rail to
* them and no rail exists there. */
if ((path.GetParent() == null || AIRail.BuildRail(path.GetParent().GetTile(), cur_node, next_tile))) {
if (path.GetParent() != null) {
tiles.push([next_tile, self._GetDirection(path.GetParent().GetTile(), cur_node, next_tile, false)]);
} else {
tiles.push([next_tile, self._GetDirection(null, cur_node, next_tile, false)]);
}
}
}
if (path.GetParent() != null && path.GetParent().GetParent() != null) {
local bridges = self._GetTunnelsBridges(path.GetParent().GetTile(), cur_node, self._GetDirection(path.GetParent().GetParent().GetTile(), path.GetParent().GetTile(), cur_node, true));
foreach (tile in bridges) {
tiles.push(tile);
}
}
}
return tiles;
}
function Rail::_CheckDirection(tile, existing_direction, new_direction, self)
{
return false;
}
function Rail::_dir(from, to)
{
if (from - to == 1) return 0;
if (from - to == -1) return 1;
if (from - to == AIMap.GetMapSizeX()) return 2;
if (from - to == -AIMap.GetMapSizeX()) return 3;
throw("Shouldn't come here in _dir");
}
function Rail::_GetDirection(pre_from, from, to, is_bridge)
{
if (is_bridge) {
if (from - to == 1) return 1;
if (from - to == -1) return 2;
if (from - to == AIMap.GetMapSizeX()) return 4;
if (from - to == -AIMap.GetMapSizeX()) return 8;
}
return 1 << (4 + (pre_from == null ? 0 : 4 * this._dir(pre_from, from)) + this._dir(from, to));
}
/**
* Get a list of all bridges and tunnels that can be build from the
* current tile. Bridges will only be build starting on non-flat tiles
* for performance reasons. Tunnels will only be build if no terraforming
* is needed on both ends.
*/
function Rail::_GetTunnelsBridges(last_node, cur_node, bridge_dir)
{
local slope = AITile.GetSlope(cur_node);
if (slope == AITile.SLOPE_FLAT && AITile.IsBuildable(cur_node + (cur_node - last_node))) return [];
local tiles = [];
for (local i = 2; i < this._max_bridge_length; i++) {
local bridge_list = AIBridgeList_Length(i + 1);
local target = cur_node + i * (cur_node - last_node);
if (!bridge_list.IsEmpty() && AIBridge.BuildBridge(AIVehicle.VEHICLE_RAIL, bridge_list.Begin(), cur_node, target)) {
tiles.push([target, bridge_dir]);
}
}
if (slope != AITile.SLOPE_SW && slope != AITile.SLOPE_NW && slope != AITile.SLOPE_SE && slope != AITile.SLOPE_NE) return tiles;
local other_tunnel_end = AITunnel.GetOtherTunnelEnd(cur_node);
if (!AIMap.IsValidTile(other_tunnel_end)) return tiles;
local tunnel_length = AIMap.DistanceManhattan(cur_node, other_tunnel_end);
local prev_tile = cur_node + (cur_node - other_tunnel_end) / tunnel_length;
if (AITunnel.GetOtherTunnelEnd(other_tunnel_end) == cur_node && tunnel_length >= 2 &&
prev_tile == last_node && tunnel_length < _max_tunnel_length && AITunnel.BuildTunnel(AIVehicle.VEHICLE_RAIL, cur_node)) {
tiles.push([other_tunnel_end, bridge_dir]);
}
return tiles;
}
function Rail::_IsSlopedRail(start, middle, end)
{
local NW = 0; // Set to true if we want to build a rail to / from the north-west
local NE = 0; // Set to true if we want to build a rail to / from the north-east
local SW = 0; // Set to true if we want to build a rail to / from the south-west
local SE = 0; // Set to true if we want to build a rail to / from the south-east
if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;
if (middle - 1 == start || middle - 1 == end) NE = 1;
if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;
if (middle + 1 == start || middle + 1 == end) SW = 1;
/* If there is a turn in the current tile, it can't be sloped. */
if ((NW || SE) && (NE || SW)) return false;
local slope = AITile.GetSlope(middle);
/* A rail on a steep slope is always sloped. */
if (AITile.IsSteepSlope(slope)) return true;
/* If only one corner is raised, the rail is sloped. */
if (slope == AITile.SLOPE_N || slope == AITile.SLOPE_W) return true;
if (slope == AITile.SLOPE_S || slope == AITile.SLOPE_E) return true;
if (NW && (slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SE)) return true;
if (NE && (slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SW)) return true;
return false;
}
|