|
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 } |