OpenTTD AI which builds a road network between all towns it can reach.

Pathfinder.Road.nut 45KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050
  1. /* RoadPathfinder v.9 [2012-12-28],
  2. * part of Minchinweb's MetaLibrary v.5,
  3. * originally part of WmDOT v.4 r.50 [2011-04-06]
  4. * Copyright © 2011-14 by W. Minchin. For more info,
  5. * please visit https://github.com/MinchinWeb/openttd-metalibrary
  6. */
  7. /* $Id: main.nut 15101 2009-01-16 00:05:26Z truebrain $ */
  8. /** \note This file is licensed under the original license -- **LGPL v2.1** --
  9. * and is based on the NoAI Team's Road Pathfinder v3.
  10. *
  11. *
  12. * \brief A Road Pathfinder (and extras)
  13. * \version v.9 (2012-12-28)
  14. * \author NoAI Team
  15. * \author W. Minchin (%MinchinWeb)
  16. * \since MetaLibrary v.1
  17. *
  18. * This road pathfinder tries to find a buildable / existing route for
  19. * road vehicles. You can changes the costs below using for example
  20. * `roadpf.cost.turn = 30`. Note that it's not allowed to change the cost
  21. * between consecutive calls to FindPath. You can change the cost before
  22. * the first call to FindPath and after FindPath has returned an actual
  23. * route. To use only existing roads, set `roadpf.cost.only_existing_road =
  24. * True`.
  25. *
  26. * The pathfinder has been extended to provide 'presets' for configuration,
  27. * store the found path, and build the found path.
  28. *
  29. * \requires Graph.AyStar v6
  30. * \see \\_MinchinWeb\\_DLS\\_
  31. * \see \\_MinchinWeb\\_ShipPathfinder\\_
  32. */
  33. /* This file provides functions:
  34. MinchinWeb.RoadPathfinder.InitializePath(sources, goals)
  35. Set up the pathfinder
  36. MinchinWeb.RoadPathfinder.FindPath(iterations)
  37. Run the pathfinder; returns false if it isn't finished the path
  38. if it has finished, and null if it can't find a path
  39. MinchinWeb.RoadPathfinder.cost.[xx]
  40. Allows you to set or find out the pathfinder costs directly.
  41. See the function below for valid entries
  42. MinchinWeb.RoadPathfinder.Info.GetVersion()
  43. .GetMinorVersion()
  44. .GetRevision()
  45. .GetDate()
  46. .GetName()
  47. Useful for check provided version or debugging screen output
  48. MinchinWeb.RoadPathfinder.PresetOriginal()
  49. .PresetPerfectPath()
  50. .PresetQuickAndDirty()
  51. .PresetCheckExisting()
  52. .PresetMode6()
  53. .PresetStreetcar()
  54. Presets for the pathfinder parameters
  55. MinchinWeb.RoadPathfinder.GetBuildCost() // How much would it be to build the path?
  56. MinchinWeb.RoadPathfinder.BuildPath() // Build the path
  57. MinchinWeb.RoadPathfinder.GetPathLength() // How long is the path?
  58. MinchinWeb.RoadPathfinder.LoadPath(Path) // Provide your own path
  59. MinchinWeb.RoadPathfinder.GetPath() // Returns the path as stored by the pathfinder
  60. MinchinWeb.RoadPathfinder.InitializePathOnTowns(StartTown, EndTown)
  61. Initializes the pathfinder using the seed tiles to the given towns
  62. MinchinWeb.RoadPathfinder.PathToTilePairs()
  63. Returns a 2D array that has each pair of tiles that path joins
  64. MinchinWeb.RoadPathfinder.TilesPairsToBuild()
  65. Similar to PathToTilePairs(), but only returns those pairs
  66. where there isn't a current road connection
  67. */
  68. /** \todo upgrade slow bridges along path
  69. * \todo convert existing level crossings (road/rail) to road bridge
  70. * \todo do something about one-way roads - build a pair? route around?
  71. *
  72. * if(AIRoad.AreRoadTilesConnected(new_tile, prev_tile) &&
  73. * !AIRoad.AreRoadTilesConnected(prev_tile, new_tile))
  74. * \todo allow pre-building of tunnels and bridges
  75. * \todo Add example usage code.
  76. */
  77. class _RoadPathfinder_ {
  78. _aystar_class = import("graph.aystar", "", 6);
  79. _max_cost = null; ///< The maximum cost for a route.
  80. _cost_tile = null; ///< The cost for a single tile.
  81. _cost_no_existing_road = null; ///< The cost that is added to `_cost_tile` if no road exists yet.
  82. _cost_clearfirst = null; ///< The cost for clearing a tile first.
  83. _cost_turn = null; ///< The cost that is added to `_cost_tile` if the direction changes.
  84. _cost_slope = null; ///< The extra cost if a road tile is sloped.
  85. _cost_bridge_per_tile = null; ///< The cost per tile of a new bridge, this is added to `_cost_tile`.
  86. _cost_tunnel_per_tile = null; ///< The cost per tile of a new tunnel, this is added to `_cost_tile`.
  87. _cost_coast = null; ///< The extra cost for a coast tile.
  88. _cost_level_crossing = null; ///< the extra cost for rail/road level crossings.
  89. _cost_drivethru_station = null; ///< The extra cost for drive-thru road stations.
  90. _pathfinder = null; ///< A reference to the used AyStar object.
  91. _max_bridge_length = null; ///< The maximum length of a bridge that will be build.
  92. _max_tunnel_length = null; ///< The maximum length of a tunnel that will be build.
  93. _cost_only_existing_roads = null; ///< Choose whether to only search through existing connected roads
  94. _distance_penalty = null; ///< Penalty to use to speed up pathfinder, 1 is no penalty
  95. _road_type = null;
  96. cost = null; ///< Used to change the costs.
  97. _mypath = null; ///< Used to store the path after it's been found for Building functions
  98. _running = null;
  99. info = null;
  100. // presets = null;
  101. constructor() {
  102. this._max_cost = 10000000;
  103. this._cost_tile = 100;
  104. this._cost_no_existing_road = 40;
  105. this._cost_clearfirst = 50;
  106. this._cost_turn = 100;
  107. this._cost_slope = 200;
  108. this._cost_bridge_per_tile = 150;
  109. this._cost_tunnel_per_tile = 120;
  110. this._cost_coast = 20;
  111. this._cost_level_crossing = 0;
  112. this._cost_drivethru_station = 0;
  113. this._max_bridge_length = 10;
  114. this._max_tunnel_length = 20;
  115. this._cost_only_existing_roads = false;
  116. this._pathfinder = this._aystar_class(this, this._Cost, this._Estimate, this._Neighbours, this._CheckDirection);
  117. this._distance_penalty = 1;
  118. this._road_type = AIRoad.ROADTYPE_ROAD;
  119. this._mypath = null;
  120. this.cost = this.Cost(this);
  121. this.info = this.Info(this);
  122. // this.presets = this.Presets(this);
  123. this._running = false;
  124. }
  125. /**
  126. * \publicsection
  127. * \brief Initialize a path search between sources and goals.
  128. * @param sources The source tiles.
  129. * @param goals The target tiles.
  130. * @see AyStar::InitializePath()
  131. * \see InitializePathOnTowns()
  132. */
  133. function InitializePath(sources, goals) {
  134. local nsources = [];
  135. foreach (node in sources) {
  136. nsources.push([node, 0xFF]);
  137. }
  138. this._pathfinder.InitializePath(nsources, goals);
  139. this._mypath = null;
  140. }
  141. /**
  142. * \brief Try to find the path as indicated with InitializePath with the
  143. * lowest cost.
  144. * @param iterations After how many iterations it should abort for a moment.
  145. * This value should either be -1 for infinite, or > 0. Any other value
  146. * aborts immediately and will never find a path.
  147. * @return A route if one was found, or false if the amount of iterations was
  148. * reached, or null if no path was found.
  149. * You can call this function over and over as long as it returns false,
  150. * which is an indication it is not yet done looking for a route.
  151. * @see AyStar::FindPath()
  152. */
  153. function FindPath(iterations);
  154. /** \brief The settings in the original (v3) pathfinder by NoAI Team.
  155. */
  156. function PresetOriginal();
  157. /** \brief Good preset for reusing existing roads.
  158. *
  159. * My slightly updated version of PresetOriginal().
  160. */
  161. function PresetPerfectPath();
  162. /** \brief Quick but messy preset.
  163. *
  164. * Runs in as little as 5% of the time of PresetPerfectPath(), but builds
  165. * odd bridges and loops.
  166. */
  167. function PresetQuickAndDirty();
  168. /** \brief Preset that only uses existing roads.
  169. *
  170. * Based on PerfectPath, but uses only existing roads. Useful for checking
  171. * if there an existing route and how long it is.
  172. */
  173. function PresetCheckExisting();
  174. /** \brief Reserved.
  175. *
  176. * Reserved preset for future use for intraurban tram lines.
  177. */
  178. function PresetStreetcar();
  179. /** \brief Cost to build found path.
  180. *
  181. * Turns to 'test mode,' builds the route provided, and returns the cost.
  182. * \note All money for AI's is in British Pounds.
  183. * \note Due to inflation, this value can get stale
  184. * \return Cost to build path
  185. * \return `False` if the test build fails somewhere
  186. */
  187. function GetBuildCost();
  188. /** \brief Build the found path.
  189. * \see BuildPath()
  190. */
  191. function BuildPath();
  192. /** \brief Load an existing path.
  193. *
  194. * 'Loads' a path to allow GetBuildCost(), BuildPath() and GetPathLength()
  195. * to be used.
  196. * \see GetBuildCost()
  197. * \see FindPath()
  198. */
  199. function LoadPath();
  200. /** \brief Export the found path.
  201. * \return The path stored by the pathfinder
  202. * \see GetPath()
  203. * \see BuildPath()
  204. */
  205. function GetPath();
  206. /** \brief Get the length of the found path.
  207. *
  208. * Runs over the path to determine its length.
  209. * \return The length of the path in tiles.
  210. * \see LoadPath()
  211. */
  212. function GetPathLength();
  213. /** \brief Initializes the pathfinder using two towns.
  214. * \note Assumes that the town centres are road tiles. If this is not the
  215. * case, the pathfinder will still run, but it will take a long
  216. * time and eventually fail to return a path. This is generally not
  217. * an issue because on map creation the centre of town will be a
  218. * road tile.
  219. * \see InitializePath()
  220. */
  221. function InitializePathOnTowns();
  222. /** \brief Get the found path as tile pairs.
  223. * \return 2D array that has each pair of tiles that path joins.
  224. * \see TilePairsToBuild()
  225. * \see PathToTiles()
  226. */
  227. function PathToTilePairs();
  228. /** \brief Get a list of all the tiles in the path.
  229. * \return 1D array that has each pair of tiles that path covers.
  230. * \see PathToTilePairs()
  231. */
  232. function PathToTiles();
  233. /** \brief Tiles in the path that need to be built.
  234. *
  235. * Similar to PathToTilePairs(), but only returns those pairs where there
  236. * isn't a current road connection.
  237. * \return 2D array that has each pair of tiles that path joins that are
  238. * not currently joined by road.
  239. * \see BuildPath()
  240. */
  241. function TilePairsToBuild();
  242. /** \privatesection
  243. */
  244. function _GetBridgeNumSlopes(end_a, end_b);
  245. function _Cost(self, path, new_tile, new_direction);
  246. function _Estimate(self, cur_tile, cur_direction, goal_tiles);
  247. function _Neighbours(self, path, cur_node);
  248. function _CheckDirection(self, tile, existing_direction, new_direction);
  249. function _GetDirection(from, to, is_bridge);
  250. function _GetTunnelsBridges(last_node, cur_node, bridge_dir);
  251. function _IsSlopedRoad(start, middle, end);
  252. function _CheckTunnelBridge(current_tile, new_tile);
  253. };
  254. class _RoadPathfinder_.Cost {
  255. _main = null;
  256. function _set(idx, val) {
  257. if (this._main._running) throw("You are not allowed to change parameters of a running pathfinder.");
  258. switch (idx) {
  259. case "max_cost": this._main._max_cost = val; break;
  260. case "tile": this._main._cost_tile = val; break;
  261. case "no_existing_road": this._main._cost_no_existing_road = val; break;
  262. case "turn": this._main._cost_turn = val; break;
  263. case "slope": this._main._cost_slope = val; break;
  264. case "bridge_per_tile": this._main._cost_bridge_per_tile = val; break;
  265. case "tunnel_per_tile": this._main._cost_tunnel_per_tile = val; break;
  266. case "coast": this._main._cost_coast = val; break;
  267. case "level_crossing": this._main._cost_level_crossing = val; break;
  268. case "max_bridge_length": this._main._max_bridge_length = val; break;
  269. case "max_tunnel_length": this._main._max_tunnel_length = val; break;
  270. case "only_existing_roads": this._main._cost_only_existing_roads = val; break;
  271. case "drivethru_station": this._main._cost_drivethru_station = val; break;
  272. case "distance_penalty": this._main._distance_penalty = val; break;
  273. default: throw("the index '" + idx + "' does not exist");
  274. }
  275. return val;
  276. }
  277. function _get(idx) {
  278. switch (idx) {
  279. case "max_cost": return this._main._max_cost;
  280. case "tile": return this._main._cost_tile;
  281. case "no_existing_road": return this._main._cost_no_existing_road;
  282. case "turn": return this._main._cost_turn;
  283. case "slope": return this._main._cost_slope;
  284. case "bridge_per_tile": return this._main._cost_bridge_per_tile;
  285. case "tunnel_per_tile": return this._main._cost_tunnel_per_tile;
  286. case "coast": return this._main._cost_coast;
  287. case "level_crossing": return this._main._cost_level_crossing;
  288. case "max_bridge_length": return this._main._max_bridge_length;
  289. case "max_tunnel_length": return this._main._max_tunnel_length;
  290. case "only_existing_roads": return this._main._cost_only_existing_roads;
  291. case "drivethru_station": return this._main._cost_drivethru_station;
  292. case "distance_penalty": return this._main._distance_penalty;
  293. default: throw("the index '" + idx + "' does not exist");
  294. }
  295. }
  296. constructor(main)
  297. {
  298. this._main = main;
  299. }
  300. };
  301. function _RoadPathfinder_::FindPath(iterations) {
  302. local test_mode = AITestMode();
  303. local ret = this._pathfinder.FindPath(iterations);
  304. this._running = (ret == false) ? true : false;
  305. if (this._running == false) { this._mypath = ret; }
  306. return ret;
  307. }
  308. function _RoadPathfinder_::_GetBridgeNumSlopes(end_a, end_b) {
  309. local slopes = 0;
  310. local direction = (end_b - end_a) / AIMap.DistanceManhattan(end_a, end_b);
  311. local slope = AITile.GetSlope(end_a);
  312. if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
  313. (slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
  314. slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
  315. slopes++;
  316. }
  317. local slope = AITile.GetSlope(end_b);
  318. direction = -direction;
  319. if (!((slope == AITile.SLOPE_NE && direction == 1) || (slope == AITile.SLOPE_SE && direction == -AIMap.GetMapSizeX()) ||
  320. (slope == AITile.SLOPE_SW && direction == -1) || (slope == AITile.SLOPE_NW && direction == AIMap.GetMapSizeX()) ||
  321. slope == AITile.SLOPE_N || slope == AITile.SLOPE_E || slope == AITile.SLOPE_S || slope == AITile.SLOPE_W)) {
  322. slopes++;
  323. }
  324. return slopes;
  325. }
  326. function _RoadPathfinder_::_Cost(self, path, new_tile, new_direction) {
  327. /* path == null means this is the first node of a path, so the cost is 0. */
  328. if (path == null) return 0;
  329. local prev_tile = path.GetTile();
  330. /* If the new tile is (already) a bridge / tunnel tile, check whether we
  331. * came from the other end of the bridge / tunnel or if we just entered the
  332. * bridge / tunnel. */
  333. if (AIBridge.IsBridgeTile(new_tile)) {
  334. if (AIBridge.GetOtherBridgeEnd(new_tile) != prev_tile) {
  335. return path.GetCost() + self._cost_tile;
  336. } else {
  337. return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
  338. }
  339. }
  340. if (AITunnel.IsTunnelTile(new_tile)) {
  341. if (AITunnel.GetOtherTunnelEnd(new_tile) != prev_tile) return path.GetCost() + self._cost_tile;
  342. return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * self._cost_tile;
  343. }
  344. /* If the two tiles are more then 1 tile apart, the pathfinder wants a
  345. * bridge or tunnel to be build. It isn't an existing bridge / tunnel, as
  346. * that case is already handled. */
  347. if (AIMap.DistanceManhattan(new_tile, prev_tile) > 1) {
  348. /* Check if we should build a bridge or a tunnel. */
  349. if (AITunnel.GetOtherTunnelEnd(new_tile) == prev_tile) {
  350. return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_tunnel_per_tile);
  351. } else {
  352. return path.GetCost() + AIMap.DistanceManhattan(new_tile, prev_tile) * (self._cost_tile + self._cost_bridge_per_tile) + self._GetBridgeNumSlopes(new_tile, prev_tile) * self._cost_slope;
  353. }
  354. }
  355. /* Check for a turn. We do this by substracting the TileID of the current node from
  356. * the TileID of the previous node and comparing that to the difference between the
  357. * previous node and the node before that. */
  358. local cost = self._cost_tile;
  359. if (path.GetParent() != null && (prev_tile - path.GetParent().GetTile()) != (new_tile - prev_tile) &&
  360. AIMap.DistanceManhattan(path.GetParent().GetTile(), prev_tile) == 1) {
  361. cost += self._cost_turn;
  362. }
  363. /* Check if the new tile is a coast tile. */
  364. if (AITile.IsCoastTile(new_tile)) {
  365. cost += self._cost_coast;
  366. }
  367. /* Check if the new tile is a coast tile. */
  368. if (AITile.IsFarmTile(new_tile) || AITile.IsRockTile(new_tile) || AITile.IsRoughTile(new_tile) /*|| AITile.HasTreeOnTile(new_tile)*/ ) {
  369. cost += self._cost_clearfirst;
  370. }
  371. /* Check if the last tile was sloped. */
  372. if (path.GetParent() != null && !AIBridge.IsBridgeTile(prev_tile) && !AITunnel.IsTunnelTile(prev_tile) &&
  373. self._IsSlopedRoad(path.GetParent().GetTile(), prev_tile, new_tile)) {
  374. cost += self._cost_slope;
  375. }
  376. /* Add a cost to "outcost" all paths that aren't using already existing
  377. * roads, if that's what we're after */
  378. if (!AIRoad.AreRoadTilesConnected(prev_tile, new_tile)) {
  379. cost += self._cost_no_existing_road;
  380. }
  381. /* Add a penalty for road/rail level crossings. */
  382. if(AITile.HasTransportType(new_tile, AITile.TRANSPORT_RAIL)) {
  383. cost += self._cost_level_crossing;
  384. }
  385. /* Add a penalty for exisiting drive thru road stations */
  386. if(AIRoad.IsDriveThroughRoadStationTile(new_tile)) {
  387. cost += self._cost_drivethru_station;
  388. }
  389. /* Add penalty for building near towns */
  390. local town = AITile.GetClosestTown(new_tile);
  391. local dist2town = AIMap.DistanceManhattan(new_tile, AITown.GetLocation(town));
  392. if (dist2town < 10) {
  393. cost += 100-(dist2town*10);
  394. }
  395. return path.GetCost() + cost;
  396. }
  397. function _RoadPathfinder_::_Estimate(self, cur_tile, cur_direction, goal_tiles) {
  398. local min_cost = self._max_cost;
  399. /* As estimate we multiply the lowest possible cost for a single tile with
  400. * with the minimum number of tiles we need to traverse. */
  401. foreach (tile in goal_tiles) {
  402. min_cost = min(AIMap.DistanceManhattan(cur_tile, tile) * self._cost_tile * self._distance_penalty, min_cost);
  403. }
  404. return min_cost;
  405. }
  406. function _RoadPathfinder_::_Neighbours(self, path, cur_node) {
  407. /* self._max_cost is the maximum path cost, if we go over it, the path isn't valid. */
  408. if (path.GetCost() >= self._max_cost) return [];
  409. local tiles = [];
  410. /* Check if the current tile is part of a bridge or tunnel. */
  411. if ((AIBridge.IsBridgeTile(cur_node) || AITunnel.IsTunnelTile(cur_node)) &&
  412. AITile.HasTransportType(cur_node, AITile.TRANSPORT_ROAD)) {
  413. local other_end = AIBridge.IsBridgeTile(cur_node) ? AIBridge.GetOtherBridgeEnd(cur_node) : AITunnel.GetOtherTunnelEnd(cur_node);
  414. local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
  415. if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) {
  416. tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
  417. }
  418. /* The other end of the bridge / tunnel is a neighbour. */
  419. tiles.push([other_end, self._GetDirection(next_tile, cur_node, true) << 4]);
  420. } else if (path.GetParent() != null && AIMap.DistanceManhattan(cur_node, path.GetParent().GetTile()) > 1) {
  421. local other_end = path.GetParent().GetTile();
  422. local next_tile = cur_node + (cur_node - other_end) / AIMap.DistanceManhattan(cur_node, other_end);
  423. if (AIRoad.AreRoadTilesConnected(cur_node, next_tile) || AIRoad.BuildRoad(cur_node, next_tile)) {
  424. tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
  425. }
  426. } else {
  427. local offsets = [AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1),
  428. AIMap.GetTileIndex(1, 0), AIMap.GetTileIndex(-1, 0)];
  429. /* Check all tiles adjacent to the current tile. */
  430. foreach (offset in offsets) {
  431. local next_tile = cur_node + offset;
  432. /* We add them to the to the neighbours-list if one of the following applies:
  433. * 1) There already is a connections between the current tile and the next tile.
  434. * 2) We can build a road to the next tile.
  435. * 3) The next tile is the entrance of a tunnel / bridge in the correct direction. */
  436. if (AIRoad.AreRoadTilesConnected(cur_node, next_tile)) {
  437. tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
  438. } else if ((self._cost_only_existing_roads != true) && (AITile.IsBuildable(next_tile) || AIRoad.IsRoadTile(next_tile)) &&
  439. (path.GetParent() == null || AIRoad.CanBuildConnectedRoadPartsHere(cur_node, path.GetParent().GetTile(), next_tile)) &&
  440. AIRoad.BuildRoad(cur_node, next_tile)) {
  441. // WM - add '&& (only_existing_roads != true)' so that non-connected roads are ignored
  442. tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
  443. } else if ((self._cost_only_existing_roads != true) && self._CheckTunnelBridge(cur_node, next_tile)) {
  444. tiles.push([next_tile, self._GetDirection(cur_node, next_tile, false)]);
  445. }
  446. // Test for water (i.e. rivers or canals or rails to bridge over them
  447. local iTile = cur_node + offset;
  448. local BridgeLength = 2;
  449. while (AITile.HasTransportType(iTile, AITile.TRANSPORT_RAIL) || AITile.IsWaterTile(iTile)) {
  450. iTile += offset;
  451. BridgeLength++;
  452. }
  453. // test to see if we could actually build said bridge
  454. // TO-DO: Check to see if this test is done elsewhere...
  455. if (BridgeLength > 2) {
  456. // TO-DO: test for map wraparound... _SuperLib_Tile::IsStraight(tile1, tile2)
  457. local BridgeList = AIBridgeList_Length(BridgeLength);
  458. if ((BridgeList.Count()) > 0 && (AIBridge.BuildBridge(AIVehicle.VT_ROAD, BridgeList.Begin(), cur_node, iTile))) {
  459. local PathCheck = path;
  460. local PathParent = path.GetParent();
  461. // _MinchinWeb_Log_.Note("Adding Bridge-over tile: " + _MinchinWeb_Array_.ToStringTiles1D([cur_node]) + _MinchinWeb_Array_.ToStringTiles1D([iTile]) + " . " + (self._GetDirection(iTile, cur_node, true) << 4), 7);
  462. tiles.push([iTile, self._GetDirection(iTile, cur_node, true) << 4]);
  463. }
  464. }
  465. }
  466. if (path.GetParent() != null) {
  467. local bridges = self._GetTunnelsBridges(path.GetParent().GetTile(), cur_node, self._GetDirection(path.GetParent().GetTile(), cur_node, true) << 4);
  468. foreach (tile in bridges) {
  469. tiles.push(tile);
  470. }
  471. }
  472. }
  473. return tiles;
  474. }
  475. function _RoadPathfinder_::_CheckDirection(self, tile, existing_direction, new_direction) {
  476. return false;
  477. }
  478. function _RoadPathfinder_::_GetDirection(from, to, is_bridge) {
  479. if (!is_bridge && AITile.GetSlope(to) == AITile.SLOPE_FLAT) return 0xFF;
  480. if (from - to == 1) return 1;
  481. if (from - to == -1) return 2;
  482. if (from - to == AIMap.GetMapSizeX()) return 4;
  483. if (from - to == -AIMap.GetMapSizeX()) return 8;
  484. // for bridges that don't have a parent tile
  485. local direction = from - to;
  486. if (direction > 0) {
  487. // so direction is positive
  488. if (direction < (AIMap.GetMapSizeX() / 2 - 1)) return 1;
  489. else return 4;
  490. } else {
  491. if ((direction * -1) < (AIMap.GetMapSizeX() / 2 - 1)) return 2;
  492. else return 8;
  493. }
  494. }
  495. /**
  496. * Get a list of all bridges and tunnels that can be build from the
  497. * current tile. Bridges will only be build starting on non-flat tiles
  498. * for performance reasons. Tunnels will only be build if no terraforming
  499. * is needed on both ends.
  500. */
  501. function _RoadPathfinder_::_GetTunnelsBridges(last_node, cur_node, bridge_dir) {
  502. // By rights, adding bridge over railroads and water should be added here
  503. local slope = AITile.GetSlope(cur_node);
  504. if (slope == AITile.SLOPE_FLAT) return [];
  505. local tiles = [];
  506. for (local i = 2; i < this._max_bridge_length; i++) {
  507. local bridge_list = AIBridgeList_Length(i + 1);
  508. local target = cur_node + i * (cur_node - last_node);
  509. if (!bridge_list.IsEmpty() && AIBridge.BuildBridge(AIVehicle.VT_ROAD, bridge_list.Begin(), cur_node, target)) {
  510. tiles.push([target, bridge_dir]);
  511. }
  512. }
  513. if (slope != AITile.SLOPE_SW && slope != AITile.SLOPE_NW && slope != AITile.SLOPE_SE && slope != AITile.SLOPE_NE) return tiles;
  514. local other_tunnel_end = AITunnel.GetOtherTunnelEnd(cur_node);
  515. if (!AIMap.IsValidTile(other_tunnel_end)) return tiles;
  516. local tunnel_length = AIMap.DistanceManhattan(cur_node, other_tunnel_end);
  517. local prev_tile = cur_node + (cur_node - other_tunnel_end) / tunnel_length;
  518. if (AITunnel.GetOtherTunnelEnd(other_tunnel_end) == cur_node && tunnel_length >= 2 &&
  519. prev_tile == last_node && tunnel_length < _max_tunnel_length && AITunnel.BuildTunnel(AIVehicle.VT_ROAD, cur_node)) {
  520. tiles.push([other_tunnel_end, bridge_dir]);
  521. }
  522. return tiles;
  523. }
  524. function _RoadPathfinder_::_IsSlopedRoad(start, middle, end) {
  525. local NW = 0; //Set to true if we want to build a road to / from the north-west
  526. local NE = 0; //Set to true if we want to build a road to / from the north-east
  527. local SW = 0; //Set to true if we want to build a road to / from the south-west
  528. local SE = 0; //Set to true if we want to build a road to / from the south-east
  529. if (middle - AIMap.GetMapSizeX() == start || middle - AIMap.GetMapSizeX() == end) NW = 1;
  530. if (middle - 1 == start || middle - 1 == end) NE = 1;
  531. if (middle + AIMap.GetMapSizeX() == start || middle + AIMap.GetMapSizeX() == end) SE = 1;
  532. if (middle + 1 == start || middle + 1 == end) SW = 1;
  533. /* If there is a turn in the current tile, it can't be sloped. */
  534. if ((NW || SE) && (NE || SW)) return false;
  535. local slope = AITile.GetSlope(middle);
  536. /* A road on a steep slope is always sloped. */
  537. if (AITile.IsSteepSlope(slope)) return true;
  538. /* If only one corner is raised, the road is sloped. */
  539. if (slope == AITile.SLOPE_N || slope == AITile.SLOPE_W) return true;
  540. if (slope == AITile.SLOPE_S || slope == AITile.SLOPE_E) return true;
  541. if (NW && (slope == AITile.SLOPE_NW || slope == AITile.SLOPE_SE)) return true;
  542. if (NE && (slope == AITile.SLOPE_NE || slope == AITile.SLOPE_SW)) return true;
  543. return false;
  544. }
  545. function _RoadPathfinder_::_CheckTunnelBridge(current_tile, new_tile) {
  546. if (!AIBridge.IsBridgeTile(new_tile) && !AITunnel.IsTunnelTile(new_tile)) return false;
  547. local dir = new_tile - current_tile;
  548. local other_end = AIBridge.IsBridgeTile(new_tile) ? AIBridge.GetOtherBridgeEnd(new_tile) : AITunnel.GetOtherTunnelEnd(new_tile);
  549. local dir2 = other_end - new_tile;
  550. if ((dir < 0 && dir2 > 0) || (dir > 0 && dir2 < 0)) return false;
  551. dir = abs(dir);
  552. dir2 = abs(dir2);
  553. if ((dir >= AIMap.GetMapSizeX() && dir2 < AIMap.GetMapSizeX()) ||
  554. (dir < AIMap.GetMapSizeX() && dir2 >= AIMap.GetMapSizeX())) return false;
  555. return true;
  556. }
  557. /* These are supplementary to the Road Pathfinder itself, but will
  558. * hopefully prove useful either directly or as a model for writing your
  559. * own functions. They include:
  560. * - Info class - useful for outputting the details of the library to the debug
  561. * screen
  562. * - Build function - used to build the path generated by the pathfinder
  563. * - Cost function - used to determine the cost of building the path generated
  564. * by the pathfinder
  565. * - Length - used to determine how long the generated path is
  566. * - Presets - a combination of settings for the pathfinder for using it in
  567. * different circumstances
  568. * - Original - the settings in the original (v3) pathfinder by NoAI Team
  569. * - PerfectPath - my slightly updated version of Original. Good for
  570. * reusing existing roads
  571. * - Dirty - quick but messy preset. Runs in as little as 5% of the time
  572. * of 'PerfectPath', but builds odd bridges and loops
  573. * - ExistingCheck - based on PerfectPath, but uses only existing roads.
  574. * Useful for checking if there an existing route and how long it is
  575. * - Streetcar - reserved for future use for intraurban tram lines
  576. * If you would like a preset added here, I would be happy to include it
  577. * in future versions!
  578. */
  579. class _RoadPathfinder_.Info
  580. {
  581. _main = null;
  582. function GetVersion() { return 9; }
  583. // function GetMinorVersion() { return 0; }
  584. function GetRevision() { return 121228; }
  585. function GetDate() { return "2012-12-28"; }
  586. function GetName() { return "Road Pathfinder (Wm)"; }
  587. constructor(main)
  588. {
  589. this._main = main;
  590. }
  591. }
  592. // Presets
  593. function _RoadPathfinder_::PresetOriginal() {
  594. // the settings in the original (v3) pathfinder by NoAI Team
  595. this._max_cost = 10000000;
  596. this._cost_tile = 100;
  597. this._cost_no_existing_road = 40;
  598. this._cost_turn = 100;
  599. this._cost_slope = 200;
  600. this._cost_bridge_per_tile = 150;
  601. this._cost_tunnel_per_tile = 120;
  602. this._cost_coast = 20;
  603. this._max_bridge_length = 10;
  604. this._max_tunnel_length = 20;
  605. this._cost_only_existing_roads = false;
  606. this._distance_penalty = 1;
  607. this._road_type = AIRoad.ROADTYPE_ROAD;
  608. this._cost_level_crossing = 0;
  609. this._cost_drivethru_station = 0;
  610. return;
  611. }
  612. function _RoadPathfinder_::PresetPerfectPath() {
  613. // my slightly updated version of Original. Good for reusing existing
  614. // roads
  615. this._max_cost = 100000;
  616. this._cost_tile = 30;
  617. this._cost_no_existing_road = 40;
  618. this._cost_turn = 100;
  619. this._cost_slope = 200;
  620. this._cost_bridge_per_tile = 150;
  621. this._cost_tunnel_per_tile = 120;
  622. this._cost_coast = 20;
  623. this._max_bridge_length = 10;
  624. this._max_tunnel_length = 20;
  625. this._cost_only_existing_roads = false;
  626. this._distance_penalty = 1;
  627. this._road_type = AIRoad.ROADTYPE_ROAD;
  628. this._cost_level_crossing = 0;
  629. this._cost_drivethru_station = 0;
  630. return;
  631. }
  632. function _RoadPathfinder_::PresetQuickAndDirty() {
  633. // quick but messy preset. Runs in as little as 5% of the time of
  634. // 'PerfectPath', but builds odd bridges and loops
  635. // v4 DOT
  636. this._max_cost = 100000;
  637. this._cost_tile = 30;
  638. this._cost_no_existing_road = 120;
  639. this._cost_turn = 50;
  640. this._cost_slope = 300;
  641. this._cost_bridge_per_tile = 200;
  642. this._cost_tunnel_per_tile = 120;
  643. this._cost_coast = 20;
  644. this._max_bridge_length = 16;
  645. this._max_tunnel_length = 10;
  646. this._cost_only_existing_roads = false;
  647. this._distance_penalty = 5;
  648. this._road_type = AIRoad.ROADTYPE_ROAD;
  649. // new for WmDOT v8
  650. this._cost_level_crossing = 700;
  651. this._cost_drivethru_station = 100;
  652. return;
  653. }
  654. function _RoadPathfinder_::PresetCheckExisting() {
  655. // based on PerfectPath, but uses only existing roads. Useful for checking
  656. // if there an existing route and how long it is
  657. this._max_cost = 100000;
  658. this._cost_tile = 30;
  659. this._cost_no_existing_road = 40;
  660. this._cost_turn = 100;
  661. this._cost_slope = 200;
  662. this._cost_bridge_per_tile = 150;
  663. this._cost_tunnel_per_tile = 120;
  664. this._cost_coast = 20;
  665. this._max_bridge_length = 9999;
  666. this._max_tunnel_length = 9999;
  667. this._cost_only_existing_roads = true;
  668. this._distance_penalty = 3;
  669. this._road_type = AIRoad.ROADTYPE_ROAD;
  670. this._cost_level_crossing = 0;
  671. this._cost_drivethru_station = 0;
  672. return;
  673. }
  674. function _RoadPathfinder_::PresetStreetcar() {
  675. // reserved for future use for intraurban tram lines
  676. return;
  677. }
  678. function _RoadPathfinder_::GetBuildCost() {
  679. // Turns to 'test mode,' builds the route provided, and returns the cost
  680. // (all money for AI's is in British Pounds)
  681. // Note that due to inflation, this value can get stale
  682. // Returns false if the test build fails somewhere
  683. if (this._running) {
  684. AILog.Warning("You can't find the build costs while there's a running pathfinder.");
  685. return false;
  686. }
  687. if (this._mypath == null) {
  688. AILog.Warning("You have tried to get the build costs of a 'null' path.");
  689. return false;
  690. }
  691. local BeanCounter = AIAccounting();
  692. local TestMode = AITestMode();
  693. local Path = this._mypath;
  694. AIRoad.SetCurrentRoadType(this._road_type);
  695. while (Path != null) {
  696. local SubPath = Path.GetParent();
  697. if (SubPath != null) {
  698. local Node = Path.GetTile();
  699. if (AIMap.DistanceManhattan(Path.GetTile(), SubPath.GetTile()) == 1) {
  700. // MD == 1 == road joining the two tiles
  701. if (!AIRoad.BuildRoad(Path.GetTile(), SubPath.GetTile())) {
  702. // If we get here, then the road building has failed
  703. // Possible that the road already exists
  704. // TO-DO
  705. // - fail the road builder if the road cannot be built and
  706. // does not already exist
  707. // return null;
  708. }
  709. } else {
  710. // Implies that we're building either a tunnel or a bridge
  711. if (!AIBridge.IsBridgeTile(Path.GetTile()) && !AITunnel.IsTunnelTile(Path.GetTile())) {
  712. if (AIRoad.IsRoadTile(Path.GetTile())) {
  713. // Original example demolishes tile if it's already a road
  714. // tile to get around expanded roadbits.
  715. // I don't like this approach as it could destroy
  716. // Railway tracks/tram tracks/station
  717. // TO-DO
  718. // - figure out a way to do this while keeping the
  719. // other things I've built on the tile
  720. // (can I just remove the road?)
  721. AITile.DemolishTile(Path.GetTile());
  722. }
  723. if (AITunnel.GetOtherTunnelEnd(Path.GetTile()) == SubPath.GetTile()) {
  724. if (!AITunnel.BuildTunnel(AIVehicle.VT_ROAD, Path.GetTile())) {
  725. // At this point, an error has occurred while
  726. // building the tunnel.
  727. // Fail the pathfinder
  728. // return null;
  729. AILog.Warning("MinchinWeb.RoadPathfinder.GetBuildCost can't build a tunnel from " + AIMap.GetTileX(Path.GetTile()) + "," + AIMap.GetTileY(Path.GetTile()) + " to " + AIMap.GetTileX(SubPath.GetTile()) + "," + AIMap.GetTileY(SubPath.GetTile()) + "!!" );
  730. }
  731. } else {
  732. // if not a tunnel, we assume we're building a bridge
  733. local BridgeList = AIBridgeList_Length(AIMap.DistanceManhattan(Path.GetTile(), SubPath.GetTile() + 1));
  734. BridgeList.Valuate(AIBridge.GetMaxSpeed);
  735. BridgeList.Sort(AIList.SORT_BY_VALUE, false);
  736. if (!AIBridge.BuildBridge(AIVehicle.VT_ROAD, BridgeList.Begin(), Path.GetTile(), SubPath.GetTile())) {
  737. // At this point, an error has occurred while
  738. // building the bridge.
  739. // Fail the pathfinder
  740. // return null;
  741. AILog.Warning("MinchinWeb.RoadPathfinder.GetBuildCost can't build a bridge from " + AIMap.GetTileX(Path.GetTile()) + "," + AIMap.GetTileY(Path.GetTile()) + " to " + AIMap.GetTileX(SubPath.GetTile()) + "," + AIMap.GetTileY(SubPath.GetTile()) + "!!" );
  742. }
  743. }
  744. }
  745. }
  746. }
  747. Path = SubPath;
  748. }
  749. // End build sequence
  750. return BeanCounter.GetCosts();
  751. }
  752. function _RoadPathfinder_::BuildPath() {
  753. if (this._running) {
  754. AILog.Warning("You can't build a path while there's a running pathfinder.");
  755. return false;
  756. }
  757. if (this._mypath == null) {
  758. AILog.Warning("You have tried to build a 'null' path.");
  759. return false;
  760. }
  761. local TestMode = AIExecMode(); // We're really doing this!
  762. local Path = this._mypath;
  763. AIRoad.SetCurrentRoadType(this._road_type);
  764. while (Path != null) {
  765. local SubPath = Path.GetParent();
  766. if (SubPath != null) {
  767. local Node = Path.GetTile();
  768. if (AIMap.DistanceManhattan(Path.GetTile(), SubPath.GetTile()) == 1) {
  769. // MD == 1 == road joining the two tiles
  770. if (!AIRoad.BuildRoad(Path.GetTile(), SubPath.GetTile())) {
  771. // If we get here, then the road building has failed
  772. // Possible that the road already exists
  773. // TO-DO:
  774. // - fail the road builder if the road cannot be built and
  775. // does not already exist
  776. // return null;
  777. }
  778. } else {
  779. // Implies that we're building either a tunnel or a bridge
  780. if (!AIBridge.IsBridgeTile(Path.GetTile()) && !AITunnel.IsTunnelTile(Path.GetTile())) {
  781. if (AIRoad.IsRoadTile(Path.GetTile())) {
  782. // Original example demolishes tile if it's already a
  783. // road tile to get around expanded roadbits.
  784. // I don't like this approach as it could destroy
  785. // Railway tracks/tram tracks/station
  786. // TO-DO:
  787. // - figure out a way to do this while keeping the
  788. // other things I've built on the tile
  789. // (can I just remove the road?)
  790. AITile.DemolishTile(Path.GetTile());
  791. }
  792. if (AITunnel.GetOtherTunnelEnd(Path.GetTile()) == SubPath.GetTile()) {
  793. // The assumption here is that the land hasn't changed
  794. // from when the pathfinder was run and when we try
  795. // to build the path. If the tunnel building fails,
  796. // we get the 'can't build tunnel' message, but if
  797. // the land has changed such that the tunnel end is
  798. // at a different spot than is was when the
  799. // pathfinder ran, we skip tunnel building and try
  800. // and build a bridge instead, which will fail
  801. // because the slopes are wrong...
  802. if (!AITunnel.BuildTunnel(AIVehicle.VT_ROAD, Path.GetTile())) {
  803. // At this point, an error has occurred while
  804. // building the tunnel.
  805. // Fail the pathfinder
  806. // return null;
  807. AILog.Warning("MinchinWeb.RoadPathfinder.BuildPath can't build a tunnel from " + AIMap.GetTileX(Path.GetTile()) + "," + AIMap.GetTileY(Path.GetTile()) + " to " + AIMap.GetTileX(SubPath.GetTile()) + "," + AIMap.GetTileY(SubPath.GetTile()) + "!!" );
  808. }
  809. } else {
  810. // if not a tunnel, we assume we're building a bridge
  811. local BridgeList = AIBridgeList_Length(AIMap.DistanceManhattan(Path.GetTile(), SubPath.GetTile() + 1));
  812. BridgeList.Valuate(AIBridge.GetMaxSpeed);
  813. BridgeList.Sort(AIList.SORT_BY_VALUE, false);
  814. if (!AIBridge.BuildBridge(AIVehicle.VT_ROAD, BridgeList.Begin(), Path.GetTile(), SubPath.GetTile())) {
  815. // At this point, an error has occurred while
  816. // building the bridge.
  817. // Fail the pathfinder
  818. // return null;
  819. AILog.Warning("MinchinWeb.RoadPathfinder.BuildPath can't build a bridge from " + AIMap.GetTileX(Path.GetTile()) + "," + AIMap.GetTileY(Path.GetTile()) + " to " + AIMap.GetTileX(SubPath.GetTile()) + "," + AIMap.GetTileY(SubPath.GetTile()) + "!! (or the tunnel end moved...)" );
  820. }
  821. }
  822. }
  823. }
  824. }
  825. Path = SubPath;
  826. }
  827. // End build sequence
  828. return true;
  829. }
  830. function _RoadPathfinder_::LoadPath (Path) {
  831. // 'Loads' a path to allow GetBuildCost(), BuildPath() and GetPathLength()
  832. // to be used
  833. if (this._running) {
  834. AILog.Warning("You can't load a path while there's a running pathfinder.");
  835. return false;
  836. }
  837. this._mypath = Path;
  838. }
  839. function _RoadPathfinder_::GetPath() {
  840. // Returns the path stored by the pathfinder
  841. if (this._running) {
  842. AILog.Warning("You can't get the path while there's a running pathfinder.");
  843. return false;
  844. }
  845. return this._mypath;
  846. }
  847. function _RoadPathfinder_::GetPathLength() {
  848. // Runs over the path to determine its length
  849. if (this._running) {
  850. AILog.Warning("You can't get the path length while there's a running pathfinder.");
  851. return false;
  852. }
  853. if (this._mypath == null) {
  854. AILog.Warning("You have tried to get the length of a 'null' path.");
  855. return false;
  856. }
  857. return this._mypath.GetLength();
  858. }
  859. function _RoadPathfinder_::InitializePathOnTowns(StartTown, EndTown) {
  860. // Initializes the pathfinder using two towns
  861. // Assumes that the town centres are road tiles (if this is not the case,
  862. // the pathfinder will still run, but it will take a long time and
  863. // eventually fail to return a path)
  864. return this.InitializePath([AITown.GetLocation(StartTown)], [AITown.GetLocation(EndTown)]);
  865. }
  866. function _RoadPathfinder_::PathToTilePairs() {
  867. // Returns a 2D array that has each pair of tiles that path joins
  868. if (this._running) {
  869. AILog.Warning("You can't convert a path while there's a running pathfinder.");
  870. return false;
  871. }
  872. if (this._mypath == null) {
  873. AILog.Warning("You have tried to convert a 'null' path.");
  874. return false;
  875. }
  876. local Path = this._mypath;
  877. local TilePairs = [];
  878. while (Path != null) {
  879. local SubPath = Path.GetParent();
  880. if (SubPath != null) {
  881. TilePairs.push([Path.GetTile(), SubPath.GetTile()]);
  882. }
  883. Path = SubPath;
  884. }
  885. // End build sequence
  886. return TilePairs;
  887. }
  888. function _RoadPathfinder_::PathToTiles() {
  889. // Returns a 1D array that has each pair of tiles that path covers
  890. if (this._running) {
  891. AILog.Warning("You can't convert a path while there's a running pathfinder.");
  892. return false;
  893. }
  894. if (this._mypath == null) {
  895. AILog.Warning("You have tried to convert a 'null' path.");
  896. return false;
  897. }
  898. local Path = this._mypath;
  899. local Tiles = [];
  900. while (Path != null) {
  901. Tiles.push(Path.GetTile());
  902. Path = Path.GetParent();
  903. }
  904. return Tiles;
  905. }
  906. function _RoadPathfinder_::TilePairsToBuild() {
  907. // Similar to PathToTilePairs(), but only returns those pairs where there
  908. // isn't a current road connection
  909. if (this._running) {
  910. AILog.Warning("You can't convert a (partial) path while there's a running pathfinder.");
  911. return false;
  912. }
  913. if (this._mypath == null) {
  914. AILog.Warning("You have tried to convert a (partial) 'null' path.");
  915. return false;
  916. }
  917. local Path = this._mypath;
  918. local TilePairs = [];
  919. while (Path != null) {
  920. local SubPath = Path.GetParent();
  921. if (SubPath != null) {
  922. if (AIMap.DistanceManhattan(Path.GetTile(), SubPath.GetTile()) == 1) {
  923. // Could join with a road
  924. if (AIRoad.AreRoadTilesConnected(Path.GetTile(), SubPath.GetTile()) != true) {
  925. TilePairs.push([Path.GetTile(), SubPath.GetTile()]);
  926. }
  927. } else {
  928. // Implies that we're building either a tunnel or a bridge
  929. if (!AIBridge.IsBridgeTile(Path.GetTile()) && !AITunnel.IsTunnelTile(Path.GetTile())) {
  930. TilePairs.push([Path.GetTile(), SubPath.GetTile()]);
  931. }
  932. }
  933. }
  934. Path = SubPath;
  935. }
  936. // End build sequence
  937. return TilePairs;
  938. }
  939. // EOF