187 DEBUG(ai,1)("[Ai-PathFinding] Found route of %d nodes long in %d nodes of searching",i,Hash_Size(&aystar->ClosedListHash)); |
187 DEBUG(ai,1)("[Ai-PathFinding] Found route of %d nodes long in %d nodes of searching",i,Hash_Size(&aystar->ClosedListHash)); |
188 } |
188 } |
189 |
189 |
190 // What tiles are around us. |
190 // What tiles are around us. |
191 static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current) { |
191 static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current) { |
192 uint i; |
192 uint i; |
193 int ret; |
193 int ret; |
194 int dir; |
194 int dir; |
195 |
195 |
196 Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; |
196 Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; |
197 |
197 |
198 aystar->num_neighbours = 0; |
198 aystar->num_neighbours = 0; |
199 |
199 |
200 // Go through all surrounding tiles and check if they are within the limits |
200 // Go through all surrounding tiles and check if they are within the limits |
201 for (i=0;i<4;i++) { |
201 for (i = 0; i < 4; i++) { |
202 if (TileX(TileOffsByDir(i) + current->path.node.tile) > 1 && |
202 if (TileX(TileOffsByDir(i) + current->path.node.tile) > 1 && |
203 TileX(TileOffsByDir(i) + current->path.node.tile) < MapMaxX() - 1 && |
203 TileX(TileOffsByDir(i) + current->path.node.tile) < MapMaxX() - 1 && |
204 TileY(TileOffsByDir(i) + current->path.node.tile) > 1 && |
204 TileY(TileOffsByDir(i) + current->path.node.tile) > 1 && |
205 TileY(TileOffsByDir(i) + current->path.node.tile) < MapMaxY() - 1) { |
205 TileY(TileOffsByDir(i) + current->path.node.tile) < MapMaxY() - 1) { |
206 // We also directly test if the current tile can connect to this tile.. |
206 // We also directly test if the current tile can connect to this tile.. |
207 // We do this simply by just building the tile! |
207 // We do this simply by just building the tile! |
208 |
208 |
209 // If the next step is a bridge, we have to enter it the right way |
209 // If the next step is a bridge, we have to enter it the right way |
210 if (!PathFinderInfo->rail_or_road && IsRoad(current->path.node.tile + TileOffsByDir(i))) { |
210 if (!PathFinderInfo->rail_or_road && IsRoad(current->path.node.tile + TileOffsByDir(i))) { |
211 if (IsTileType(current->path.node.tile + TileOffsByDir(i), MP_TUNNELBRIDGE)) { |
211 if (IsTileType(current->path.node.tile + TileOffsByDir(i), MP_TUNNELBRIDGE)) { |
212 // An existing bridge... let's test the direction ;) |
212 // An existing bridge... let's test the direction ;) |
213 if ((_map5[current->path.node.tile + TileOffsByDir(i)] & 1U) != (i & 1)) continue; |
213 if ((_map5[current->path.node.tile + TileOffsByDir(i)] & 1U) != (i & 1)) continue; |
214 // This problem only is valid for tunnels: |
214 // This problem only is valid for tunnels: |
215 // When the last tile was not yet a tunnel, check if we enter from the right side.. |
215 // When the last tile was not yet a tunnel, check if we enter from the right side.. |
216 if ((_map5[current->path.node.tile + TileOffsByDir(i)] & 0x80) == 0) { |
216 if ((_map5[current->path.node.tile + TileOffsByDir(i)] & 0x80) == 0) { |
217 if (i != (_map5[current->path.node.tile + TileOffsByDir(i)] & 3U)) continue; |
217 if (i != (_map5[current->path.node.tile + TileOffsByDir(i)] & 3U)) continue; |
218 } |
218 } |
219 } |
219 } |
220 } |
220 } |
221 // But also if we are on a bridge, we can only move a certain direction |
221 // But also if we are on a bridge, we can only move a certain direction |
222 if (!PathFinderInfo->rail_or_road && IsRoad(current->path.node.tile)) { |
222 if (!PathFinderInfo->rail_or_road && IsRoad(current->path.node.tile)) { |
223 if (IsTileType(current->path.node.tile, MP_TUNNELBRIDGE)) { |
223 if (IsTileType(current->path.node.tile, MP_TUNNELBRIDGE)) { |
224 // An existing bridge/tunnel... let's test the direction ;) |
224 // An existing bridge/tunnel... let's test the direction ;) |
225 if ((_map5[current->path.node.tile] & 1U) != (i & 1)) continue; |
225 if ((_map5[current->path.node.tile] & 1U) != (i & 1)) continue; |
226 } |
226 } |
227 } |
227 } |
228 |
228 |
229 if ((AI_PATHFINDER_FLAG_BRIDGE & current->path.node.user_data[0]) != 0 || |
229 if ((AI_PATHFINDER_FLAG_BRIDGE & current->path.node.user_data[0]) != 0 || |
230 (AI_PATHFINDER_FLAG_TUNNEL & current->path.node.user_data[0]) != 0) { |
230 (AI_PATHFINDER_FLAG_TUNNEL & current->path.node.user_data[0]) != 0) { |
231 // We are a bridge/tunnel, how cool!! |
231 // We are a bridge/tunnel, how cool!! |
232 // This means we can only point forward.. get the direction from the user_data |
232 // This means we can only point forward.. get the direction from the user_data |
233 if (i != (current->path.node.user_data[0] >> 8)) continue; |
233 if (i != (current->path.node.user_data[0] >> 8)) continue; |
234 } |
234 } |
235 dir = 0; |
235 dir = 0; |
236 |
236 |
237 // First, check if we have a parent |
237 // First, check if we have a parent |
238 if (current->path.parent == NULL && current->path.node.user_data[0] == 0) { |
238 if (current->path.parent == NULL && current->path.node.user_data[0] == 0) { |
239 // If not, this means we are at the starting station |
239 // If not, this means we are at the starting station |
240 if (PathFinderInfo->start_direction != AI_PATHFINDER_NO_DIRECTION) { |
240 if (PathFinderInfo->start_direction != AI_PATHFINDER_NO_DIRECTION) { |
241 // We do need a direction? |
241 // We do need a direction? |
242 if (AiNew_GetDirection(current->path.node.tile, current->path.node.tile + TileOffsByDir(i)) != PathFinderInfo->start_direction) |
242 if (AiNew_GetDirection(current->path.node.tile, current->path.node.tile + TileOffsByDir(i)) != PathFinderInfo->start_direction) { |
243 // We are not pointing the right way, invalid tile |
243 // We are not pointing the right way, invalid tile |
244 continue; |
244 continue; |
245 } |
245 } |
246 } else if (current->path.node.user_data[0] == 0) { |
246 } |
247 if (PathFinderInfo->rail_or_road) { |
247 } else if (current->path.node.user_data[0] == 0) { |
248 // Rail check |
248 if (PathFinderInfo->rail_or_road) { |
249 dir = AiNew_GetRailDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + TileOffsByDir(i)); |
249 // Rail check |
250 ret = DoCommandByTile(current->path.node.tile, 0, dir, DC_AUTO | DC_NO_WATER, CMD_BUILD_SINGLE_RAIL); |
250 dir = AiNew_GetRailDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + TileOffsByDir(i)); |
251 if (CmdFailed(ret)) continue; |
251 ret = DoCommandByTile(current->path.node.tile, 0, dir, DC_AUTO | DC_NO_WATER, CMD_BUILD_SINGLE_RAIL); |
|
252 if (CmdFailed(ret)) continue; |
252 #ifdef AI_PATHFINDER_NO_90DEGREES_TURN |
253 #ifdef AI_PATHFINDER_NO_90DEGREES_TURN |
253 if (current->path.parent->parent != NULL) { |
254 if (current->path.parent->parent != NULL) { |
254 // Check if we don't make a 90degree curve |
255 // Check if we don't make a 90degree curve |
255 int dir1 = AiNew_GetRailDirection(current->path.parent->parent->node.tile, current->path.parent->node.tile, current->path.node.tile); |
256 int dir1 = AiNew_GetRailDirection(current->path.parent->parent->node.tile, current->path.parent->node.tile, current->path.node.tile); |
256 if (_illegal_curves[dir1] == dir || _illegal_curves[dir] == dir1) { |
257 if (_illegal_curves[dir1] == dir || _illegal_curves[dir] == dir1) { |
257 continue; |
258 continue; |
258 } |
259 } |
259 } |
260 } |
260 #endif |
261 #endif |
261 } else { |
262 } else { |
262 // Road check |
263 // Road check |
263 dir = AiNew_GetRoadDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + TileOffsByDir(i)); |
264 dir = AiNew_GetRoadDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + TileOffsByDir(i)); |
264 if (IsRoad(current->path.node.tile)) { |
265 if (IsRoad(current->path.node.tile)) { |
265 if (IsTileType(current->path.node.tile, MP_TUNNELBRIDGE)) { |
266 if (IsTileType(current->path.node.tile, MP_TUNNELBRIDGE)) { |
266 // We have a bridge, how nicely! We should mark it... |
267 // We have a bridge, how nicely! We should mark it... |
267 dir = 0; |
268 dir = 0; |
268 } else { |
269 } else { |
269 // It already has road.. check if we miss any bits! |
270 // It already has road.. check if we miss any bits! |
270 if ((_map5[current->path.node.tile] & dir) != dir) { |
271 if ((_map5[current->path.node.tile] & dir) != dir) { |
271 // We do miss some pieces :( |
272 // We do miss some pieces :( |
272 dir &= ~_map5[current->path.node.tile]; |
273 dir &= ~_map5[current->path.node.tile]; |
273 } else { |
274 } else { |
274 dir = 0; |
275 dir = 0; |
275 } |
276 } |
276 } |
277 } |
277 } |
278 } |
278 // Only destruct things if it is MP_CLEAR of MP_TREES |
279 // Only destruct things if it is MP_CLEAR of MP_TREES |
279 if (dir != 0) { |
280 if (dir != 0) { |
280 ret = DoCommandByTile(current->path.node.tile, dir, 0, DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD); |
281 ret = DoCommandByTile(current->path.node.tile, dir, 0, DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD); |
281 if (CmdFailed(ret)) continue; |
282 if (CmdFailed(ret)) continue; |
282 } |
283 } |
283 } |
284 } |
284 |
285 } |
285 } |
|
286 |
286 |
287 // The tile can be connected |
287 // The tile can be connected |
288 aystar->neighbours[aystar->num_neighbours].tile = TileOffsByDir(i) + current->path.node.tile; |
288 aystar->neighbours[aystar->num_neighbours].tile = TileOffsByDir(i) + current->path.node.tile; |
289 aystar->neighbours[aystar->num_neighbours].user_data[0] = 0; |
289 aystar->neighbours[aystar->num_neighbours].user_data[0] = 0; |
290 aystar->neighbours[aystar->num_neighbours++].direction = 0; |
290 aystar->neighbours[aystar->num_neighbours++].direction = 0; |
291 } |
291 } |
292 } |
292 } |
293 |
293 |
294 // Next step, check for bridges and tunnels |
294 // Next step, check for bridges and tunnels |
295 if (current->path.parent != NULL && current->path.node.user_data[0] == 0) { |
295 if (current->path.parent != NULL && current->path.node.user_data[0] == 0) { |
296 |
296 |
297 TileInfo ti; |
297 TileInfo ti; |
298 // First we get the dir from this tile and his parent |
298 // First we get the dir from this tile and his parent |
299 int dir = AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile); |
299 int dir = AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile); |
300 // It means we can only walk with the track, so the bridge has to be in the same direction |
300 // It means we can only walk with the track, so the bridge has to be in the same direction |
301 TileIndex tile = current->path.node.tile; |
301 TileIndex tile = current->path.node.tile; |
302 TileIndex new_tile = tile; |
302 TileIndex new_tile = tile; |
303 |
303 |
304 FindLandscapeHeightByTile(&ti, tile); |
304 FindLandscapeHeightByTile(&ti, tile); |
305 |
305 |
306 // Bridges can only be build on land that is not flat |
306 // Bridges can only be build on land that is not flat |
307 // And if there is a road or rail blocking |
307 // And if there is a road or rail blocking |
308 if (ti.tileh != 0 || |
308 if (ti.tileh != 0 || |
309 (PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_STREET)) || |
309 (PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_STREET)) || |
310 (!PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_RAILWAY))) { |
310 (!PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_RAILWAY))) { |
311 |
311 |
312 for (;;) { |
312 for (;;) { |
313 new_tile += TileOffsByDir(dir); |
313 new_tile += TileOffsByDir(dir); |
314 |
314 |
315 // Precheck, is the length allowed? |
315 // Precheck, is the length allowed? |
316 if (!CheckBridge_Stuff(0,GetBridgeLength(tile, new_tile))) break; |
316 if (!CheckBridge_Stuff(0,GetBridgeLength(tile, new_tile))) break; |
317 |
317 |
318 // Check if we hit the station-tile.. we don't like that! |
318 // Check if we hit the station-tile.. we don't like that! |
319 if (TILES_BETWEEN(new_tile,PathFinderInfo->end_tile_tl,PathFinderInfo->end_tile_br)) break; |
319 if (TILES_BETWEEN(new_tile,PathFinderInfo->end_tile_tl,PathFinderInfo->end_tile_br)) break; |
320 |
320 |
321 // Try building the bridge.. |
321 // Try building the bridge.. |
322 ret = DoCommandByTile(tile, new_tile, (0<<8) + (MAX_BRIDGES / 2), DC_AUTO, CMD_BUILD_BRIDGE); |
322 ret = DoCommandByTile(tile, new_tile, (0<<8) + (MAX_BRIDGES / 2), DC_AUTO, CMD_BUILD_BRIDGE); |
323 if (CmdFailed(ret)) continue; |
323 if (CmdFailed(ret)) continue; |
324 // We can build a bridge here.. add him to the neighbours |
324 // We can build a bridge here.. add him to the neighbours |
325 aystar->neighbours[aystar->num_neighbours].tile = new_tile; |
325 aystar->neighbours[aystar->num_neighbours].tile = new_tile; |
326 aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_BRIDGE + (dir << 8); |
326 aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_BRIDGE + (dir << 8); |
327 aystar->neighbours[aystar->num_neighbours++].direction = 0; |
327 aystar->neighbours[aystar->num_neighbours++].direction = 0; |
328 // We can only have 12 neighbours, and we need 1 left for tunnels |
328 // We can only have 12 neighbours, and we need 1 left for tunnels |
329 if (aystar->num_neighbours == 11) break; |
329 if (aystar->num_neighbours == 11) break; |
330 } |
330 } |
331 } |
331 } |
332 |
332 |
333 // Next, check for tunnels! |
333 // Next, check for tunnels! |
334 // Tunnels can only be build with tileh of 3, 6, 9 or 12, depending on the direction |
334 // Tunnels can only be build with tileh of 3, 6, 9 or 12, depending on the direction |
335 // For now, we check both sides for this tile.. terraforming gives fuzzy result |
335 // For now, we check both sides for this tile.. terraforming gives fuzzy result |
336 if ((dir == 0 && ti.tileh == 12) || |
336 if ((dir == 0 && ti.tileh == 12) || |
337 (dir == 1 && ti.tileh == 6) || |
337 (dir == 1 && ti.tileh == 6) || |
338 (dir == 2 && ti.tileh == 3) || |
338 (dir == 2 && ti.tileh == 3) || |
339 (dir == 3 && ti.tileh == 9)) { |
339 (dir == 3 && ti.tileh == 9)) { |
340 // Now simply check if a tunnel can be build |
340 // Now simply check if a tunnel can be build |
341 ret = DoCommandByTile(tile, (PathFinderInfo->rail_or_road?0:0x200), 0, DC_AUTO, CMD_BUILD_TUNNEL); |
341 ret = DoCommandByTile(tile, (PathFinderInfo->rail_or_road?0:0x200), 0, DC_AUTO, CMD_BUILD_TUNNEL); |
342 FindLandscapeHeightByTile(&ti, _build_tunnel_endtile); |
342 FindLandscapeHeightByTile(&ti, _build_tunnel_endtile); |
343 if (!CmdFailed(ret) && (ti.tileh == 3 || ti.tileh == 6 || ti.tileh == 9 || ti.tileh == 12)) { |
343 if (!CmdFailed(ret) && (ti.tileh == 3 || ti.tileh == 6 || ti.tileh == 9 || ti.tileh == 12)) { |
344 aystar->neighbours[aystar->num_neighbours].tile = _build_tunnel_endtile; |
344 aystar->neighbours[aystar->num_neighbours].tile = _build_tunnel_endtile; |
345 aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_TUNNEL + (dir << 8); |
345 aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_TUNNEL + (dir << 8); |
346 aystar->neighbours[aystar->num_neighbours++].direction = 0; |
346 aystar->neighbours[aystar->num_neighbours++].direction = 0; |
347 } |
347 } |
348 } |
348 } |
349 } |
349 } |
350 } |
350 } |
351 |
351 |
352 extern uint GetRailFoundation(uint tileh, uint bits); |
352 extern uint GetRailFoundation(uint tileh, uint bits); |
353 extern uint GetRoadFoundation(uint tileh, uint bits); |
353 extern uint GetRoadFoundation(uint tileh, uint bits); |
354 extern uint GetBridgeFoundation(uint tileh, byte direction); |
354 extern uint GetBridgeFoundation(uint tileh, byte direction); |
355 enum { |
355 enum { |
356 BRIDGE_NO_FOUNDATION = 1 << 0 | 1 << 3 | 1 << 6 | 1 << 9 | 1 << 12, |
356 BRIDGE_NO_FOUNDATION = 1 << 0 | 1 << 3 | 1 << 6 | 1 << 9 | 1 << 12, |
357 }; |
357 }; |
358 |
358 |
359 // The most important function: it calculates the g-value |
359 // The most important function: it calculates the g-value |
360 static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent) { |
360 static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent) { |
361 Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; |
361 Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; |