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

pathfinder.nut 8.8KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
  1. /*--------------------------------------------------------------------
  2. | |
  3. | PathFinder |
  4. | |
  5. --------------------------------------------------------------------*/
  6. class PathFinder
  7. {
  8. err = 0;
  9. constructor() {
  10. err = AIError.ERR_NONE;
  11. }
  12. function BuildRoad(tile1, tile2);
  13. }
  14. /*------------------------------------------------------------------*/
  15. function PathFinder::BuildRoad(start, target)
  16. {
  17. local retry_find = false;
  18. local plan_retries = 0;
  19. local pathfinder = RoadPathFinder();
  20. local path_len = 0;
  21. if(start == null || target == null ) {
  22. AILog.Info("PathFinder: BuildRoad: null tiles");
  23. return false;
  24. }
  25. if( !AIMap.IsValidTile(start) || !AIMap.IsValidTile(target)) {
  26. AILog.Info("PF:BuildRoad: no valid tile" );
  27. return false;
  28. }
  29. do {
  30. retry_find = false;
  31. pathfinder.InitializePath([start], [target]);
  32. pathfinder.cost.slope = 50;
  33. local path = false;
  34. while (path == false) {
  35. path = pathfinder.FindPath(100);
  36. AIController.Sleep(1);
  37. }
  38. // AILog.Info("PathFinder: FindPath ready " + (path == null));
  39. while (path != null) {
  40. path_len = path_len + 1;
  41. if (path.GetParent() != null) {
  42. local parnt = path.GetParent().GetTile();
  43. if (!AIRoad.AreRoadTilesConnected(path.GetTile(), parnt)
  44. && (!AIBridge.IsBridgeTile(path.GetTile())
  45. || AIBridge.GetOtherBridgeEnd(path.GetTile()) != parnt)) {
  46. local retry_build = false;
  47. local build_retries = 0;
  48. do {
  49. retry_build = false;
  50. if (AIMap.DistanceManhattan(path.GetTile(), parnt) == 1 ) {
  51. // AILog.Info("PathFinder: tiles " +
  52. // AIMap.GetTileX(path.GetTile()) + " " + AIMap.GetTileY(path.GetTile()) +
  53. // AIMap.GetTileX(parnt) + " " + AIMap.GetTileY(parnt));
  54. local built_road = AIRoad.BuildRoad(path.GetTile(), parnt);
  55. if (!built_road) {
  56. err = AIError.GetLastError();
  57. switch (err) {
  58. /* ignore these errors */
  59. case AIError.ERR_NONE:
  60. case AIError.ERR_ALREADY_BUILT:
  61. /* decrement retry counter, so it does not limit the nr of retries
  62. else after 35 tiles over existing road, the building stops
  63. */
  64. if (build_retries) build_retries = build_retries - 1;
  65. break;
  66. /* can't handle this locally, return unsuccessful */
  67. case AIError.ERR_PRECONDITION_FAILED:
  68. case AIError.ERR_NEWGRF_SUPPLIED_ERROR:
  69. case AIError.ERR_NOT_ENOUGH_CASH:
  70. case AIError.ERR_LOCAL_AUTHORITY_REFUSES:
  71. AILog.Info("Build road failed(fatal)"+ AIError.GetLastErrorString()+" "+
  72. AIMap.GetTileX(parnt)+" " + AIMap.GetTileY(parnt)
  73. +" "+AIMap.GetTileX(path.GetTile())+" " + AIMap.GetTileY(path.GetTile())+" " + AITile.GetSlope(path.GetTile())+" " +
  74. AITile.GetSlope(parnt));
  75. return false;
  76. break;
  77. case AIError.ERR_VEHICLE_IN_THE_WAY:
  78. AILog.Info("Build road failed (retry)"+ AIError.GetLastErrorString()+" "+
  79. AIMap.GetTileX(parnt)+" " + AIMap.GetTileY(parnt)
  80. +" "+AIMap.GetTileX(path.GetTile())+" " + AIMap.GetTileY(path.GetTile())+" " + AITile.GetSlope(path.GetTile())+" " +
  81. AITile.GetSlope(parnt));
  82. AIController.Sleep(1);
  83. retry_build = true;
  84. break;
  85. case AIError.ERR_AREA_NOT_CLEAR:
  86. AILog.Info("Build road failed (demolish + retry)"+ AIError.GetLastErrorString()+" "+
  87. AIMap.GetTileX(parnt)+" " + AIMap.GetTileY(parnt)
  88. +" "+AIMap.GetTileX(path.GetTile())+" " +
  89. AIMap.GetTileY(path.GetTile())+" " + AITile.GetSlope(path.GetTile())+" " +
  90. AITile.GetSlope(parnt));
  91. AITile.DemolishTile(path.GetTile());
  92. retry_build = false;
  93. retry_find = true;
  94. break;
  95. case AIError.ERR_OWNED_BY_ANOTHER_COMPANY :
  96. case AIError.ERR_FLAT_LAND_REQUIRED:
  97. case AIError.ERR_LAND_SLOPED_WRONG:
  98. case AIError.ERR_SITE_UNSUITABLE:
  99. case AIError.ERR_TOO_CLOSE_TO_EDGE:
  100. AILog.Info("Build road failed (replan)"+ AIError.GetLastErrorString()+" "+
  101. AIMap.GetTileX(parnt)+" " + AIMap.GetTileY(parnt)
  102. +" "+AIMap.GetTileX(path.GetTile())+" " + AIMap.GetTileY(path.GetTile())+" " + AITile.GetSlope(path.GetTile())+" " +
  103. AITile.GetSlope(parnt));
  104. retry_build = false;
  105. retry_find = true;
  106. break;
  107. case AIError.ERR_UNKNOWN:
  108. default:
  109. AILog.Info("Build road failed (replan)"+ AIError.GetLastErrorString()+" "+
  110. AIMap.GetTileX(parnt)+" " + AIMap.GetTileY(parnt)
  111. +" "+AIMap.GetTileX(path.GetTile())+" " +AIMap.GetTileY(path.GetTile())+" " + AITile.GetSlope(path.GetTile())+" " +
  112. AITile.GetSlope(parnt));
  113. retry_find = true;
  114. break;
  115. }
  116. }
  117. build_retries++;
  118. }
  119. else {
  120. AILog.Info("PathFinder: build bridge");
  121. /* Build a bridge or tunnel. */
  122. if (!AIBridge.IsBridgeTile(path.GetTile()) && !AITunnel.IsTunnelTile(path.GetTile())) {
  123. /* If it was a road tile, demolish it first. Do this to work around expended roadbits. */
  124. if (AIRoad.IsRoadTile(path.GetTile())) AITile.DemolishTile(path.GetTile());
  125. if (AITunnel.GetOtherTunnelEnd(path.GetTile()) == parnt) {
  126. if (!AITunnel.BuildTunnel(AIVehicle.VT_ROAD, path.GetTile())) {
  127. AILog.Info("Build tunnel failed");
  128. }
  129. } else {
  130. local bridge_list = AIBridgeList_Length(AIMap.DistanceManhattan(path.GetTile(), parnt) + 1);
  131. bridge_list.Valuate(AIBridge.GetMaxSpeed);
  132. bridge_list.Sort(AIList.SORT_BY_VALUE, false);
  133. if (!AIBridge.BuildBridge(AIVehicle.VT_ROAD, bridge_list.Begin(), path.GetTile(), parnt)) {
  134. AILog.Info("Build bridge failed");
  135. }
  136. }
  137. }
  138. }
  139. } while (retry_build && build_retries < 80 && !retry_find);
  140. }
  141. }
  142. path = path.GetParent();
  143. }
  144. plan_retries++;
  145. } while (retry_find && (plan_retries < 10));
  146. return path_len;
  147. }