1 /* $Id$ */

     2 

     3 #include "stdafx.h"

     4 #include "openttd.h"

     5 #include "debug.h"

     6 #include "functions.h"

     7 #include "map.h"

     8 #include "tile.h"

     9 #include "command.h"

    10 #include "ai_new.h"

    11 #include "depot.h"

    12 #include "variables.h"

    13 

    14 #define TEST_STATION_NO_DIR 0xFF

    15 

    16 // Tests if a station can be build on the given spot

    17 // TODO: make it train compatible

    18 static bool TestCanBuildStationHere(TileIndex tile, byte dir)

    19 {

    20 	Player *p = GetPlayer(_current_player);

    21 

    22 	if (dir == TEST_STATION_NO_DIR) {

    23 		int32 ret;

    24 		// TODO: currently we only allow spots that can be access from al 4 directions...

    25 		//  should be fixed!!!

    26 		for (dir = 0; dir < 4; dir++) {

    27 			ret = AiNew_Build_Station(p, p->ainew.tbt, tile, 1, 1, dir, DC_QUERY_COST);

    28 			if (!CmdFailed(ret)) return true;

    29 		}

    30 		return false;

    31 	}

    32 

    33 	// return true if command succeeded, so the inverse of CmdFailed()

    34 	return !CmdFailed(AiNew_Build_Station(p, p->ainew.tbt, tile, 1, 1, dir, DC_QUERY_COST));

    35 }

    36 

    37 

    38 static bool IsRoad(TileIndex tile)

    39 {

    40 	return

    41 		// MP_STREET, but not a road depot?

    42 		(IsTileType(tile, MP_STREET) && !IsTileDepotType(tile, TRANSPORT_ROAD)) ||

    43 		(IsTileType(tile, MP_TUNNELBRIDGE) && (

    44 			// road tunnel?

    45 			((_m[tile].m5 & 0x80) == 0 && (_m[tile].m5 & 0x4) == 0x4) ||

    46 			// road bridge?

    47 			((_m[tile].m5 & 0x80) != 0 && (_m[tile].m5 & 0x2) == 0x2)

    48 		));

    49 }

    50 

    51 

    52 // Checks if a tile 'a' is between the tiles 'b' and 'c'

    53 #define TILES_BETWEEN(a, b, c) (TileX(a) >= TileX(b) && TileX(a) <= TileX(c) && TileY(a) >= TileY(b) && TileY(a) <= TileY(c))

    54 

    55 

    56 // Check if the current tile is in our end-area

    57 static int32 AyStar_AiPathFinder_EndNodeCheck(AyStar *aystar, OpenListNode *current)

    58 {

    59 	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;

    60 	// It is not allowed to have a station on the end of a bridge or tunnel ;)

    61 	if (current->path.node.user_data[0] != 0) return AYSTAR_DONE;

    62 	if (TILES_BETWEEN(current->path.node.tile, PathFinderInfo->end_tile_tl, PathFinderInfo->end_tile_br))

    63 		if (IsTileType(current->path.node.tile, MP_CLEAR) || IsTileType(current->path.node.tile, MP_TREES))

    64 			if (current->path.parent == NULL || TestCanBuildStationHere(current->path.node.tile, AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile)))

    65 				return AYSTAR_FOUND_END_NODE;

    66 

    67 	return AYSTAR_DONE;

    68 }

    69 

    70 

    71 // Calculates the hash

    72 //   Currently it is a 10 bit hash, so the hash array has a max depth of 6 bits (so 64)

    73 static uint AiPathFinder_Hash(uint key1, uint key2)

    74 {

    75 	return (TileX(key1) & 0x1F) + ((TileY(key1) & 0x1F) << 5);

    76 }

    77 

    78 

    79 // Clear the memory of all the things

    80 static void AyStar_AiPathFinder_Free(AyStar *aystar)

    81 {

    82 	AyStarMain_Free(aystar);

    83 	free(aystar);

    84 }

    85 

    86 

    87 static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);

    88 static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);

    89 static void AyStar_AiPathFinder_FoundEndNode(AyStar *aystar, OpenListNode *current);

    90 static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current);

    91 

    92 

    93 // This creates the AiPathFinder

    94 AyStar *new_AyStar_AiPathFinder(int max_tiles_around, Ai_PathFinderInfo *PathFinderInfo)

    95 {

    96 	PathNode start_node;

    97 	uint x;

    98 	uint y;

    99 	// Create AyStar

   100 	AyStar *result = malloc(sizeof(AyStar));

   101 	init_AyStar(result, AiPathFinder_Hash, 1 << 10);

   102 	// Set the function pointers

   103 	result->CalculateG = AyStar_AiPathFinder_CalculateG;

   104 	result->CalculateH = AyStar_AiPathFinder_CalculateH;

   105 	result->EndNodeCheck = AyStar_AiPathFinder_EndNodeCheck;

   106 	result->FoundEndNode = AyStar_AiPathFinder_FoundEndNode;

   107 	result->GetNeighbours = AyStar_AiPathFinder_GetNeighbours;

   108 

   109 	result->BeforeExit = NULL;

   110 

   111 	result->free = AyStar_AiPathFinder_Free;

   112 

   113 	// Set some information

   114 	result->loops_per_tick = AI_PATHFINDER_LOOPS_PER_TICK;

   115 	result->max_path_cost = 0;

   116 	result->max_search_nodes = AI_PATHFINDER_MAX_SEARCH_NODES;

   117 

   118 	// Set the user_data to the PathFinderInfo

   119 	result->user_target = PathFinderInfo;

   120 

   121 	// Set the start node

   122 	start_node.parent = NULL;

   123 	start_node.node.direction = 0;

   124 	start_node.node.user_data[0] = 0;

   125 

   126 	// Now we add all the starting tiles

   127 	for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) {

   128 		for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) {

   129 			start_node.node.tile = TileXY(x, y);

   130 			result->addstart(result, &start_node.node, 0);

   131 		}

   132 	}

   133 

   134 	return result;

   135 }

   136 

   137 

   138 // To reuse AyStar we sometimes have to clean all the memory

   139 void clean_AyStar_AiPathFinder(AyStar *aystar, Ai_PathFinderInfo *PathFinderInfo)

   140 {

   141 	PathNode start_node;

   142 	uint x;

   143 	uint y;

   144 

   145 	aystar->clear(aystar);

   146 

   147 	// Set the user_data to the PathFinderInfo

   148 	aystar->user_target = PathFinderInfo;

   149 

   150 	// Set the start node

   151 	start_node.parent = NULL;

   152 	start_node.node.direction = 0;

   153 	start_node.node.user_data[0] = 0;

   154 	start_node.node.tile = PathFinderInfo->start_tile_tl;

   155 

   156 	// Now we add all the starting tiles

   157 	for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) {

   158 		for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) {

   159 			if (!(IsTileType(TileXY(x, y), MP_CLEAR) || IsTileType(TileXY(x, y), MP_TREES))) continue;

   160 			if (!TestCanBuildStationHere(TileXY(x, y), TEST_STATION_NO_DIR)) continue;

   161 			start_node.node.tile = TileXY(x, y);

   162 			aystar->addstart(aystar, &start_node.node, 0);

   163 		}

   164 	}

   165 }

   166 

   167 

   168 // The h-value, simple calculation

   169 static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)

   170 {

   171 	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;

   172 	int r, r2;

   173 	if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION) {

   174 		// The station is pointing to a direction, add a tile towards that direction, so the H-value is more accurate

   175 		r = DistanceManhattan(current->tile, PathFinderInfo->end_tile_tl + TileOffsByDir(PathFinderInfo->end_direction));

   176 		r2 = DistanceManhattan(current->tile, PathFinderInfo->end_tile_br + TileOffsByDir(PathFinderInfo->end_direction));

   177 	} else {

   178 		// No direction, so just get the fastest route to the station

   179 		r = DistanceManhattan(current->tile, PathFinderInfo->end_tile_tl);

   180 		r2 = DistanceManhattan(current->tile, PathFinderInfo->end_tile_br);

   181 	}

   182 	// See if the bottomright is faster than the topleft..

   183 	if (r2 < r) r = r2;

   184 	return r * AI_PATHFINDER_H_MULTIPLER;

   185 }

   186 

   187 

   188 // We found the end.. let's get the route back and put it in an array

   189 static void AyStar_AiPathFinder_FoundEndNode(AyStar *aystar, OpenListNode *current)

   190 {

   191 	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;

   192 	uint i = 0;

   193 	PathNode *parent = &current->path;

   194 

   195 	do {

   196 		PathFinderInfo->route_extra[i] = parent->node.user_data[0];

   197 		PathFinderInfo->route[i++] = parent->node.tile;

   198 		if (i > lengthof(PathFinderInfo->route)) {

   199 			// We ran out of space for the PathFinder

   200 			DEBUG(ai, 0)("[AiPathFinder] Ran out of space in the route[] array!!!");

   201 			PathFinderInfo->route_length = -1; // -1 indicates out of space

   202 			return;

   203 		}

   204 		parent = parent->parent;

   205 	} while (parent != NULL);

   206 	PathFinderInfo->route_length = i;

   207 	DEBUG(ai, 1)("[Ai-PathFinding] Found route of %d nodes long in %d nodes of searching", i, Hash_Size(&aystar->ClosedListHash));

   208 }

   209 

   210 

   211 // What tiles are around us.

   212 static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current)

   213 {

   214 	uint i;

   215 	int ret;

   216 	int dir;

   217 

   218 	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;

   219 

   220 	aystar->num_neighbours = 0;

   221 

   222 	// Go through all surrounding tiles and check if they are within the limits

   223 	for (i = 0; i < 4; i++) {

   224 		TileIndex ctile = current->path.node.tile; // Current tile

   225 		TileIndex atile = ctile + TileOffsByDir(i); // Adjacent tile

   226 

   227 		if (TileX(atile) > 1 && TileX(atile) < MapMaxX() - 1 &&

   228 				TileY(atile) > 1 && TileY(atile) < MapMaxY() - 1) {

   229 			// We also directly test if the current tile can connect to this tile..

   230 			//  We do this simply by just building the tile!

   231 

   232 			// If the next step is a bridge, we have to enter it the right way

   233 			if (!PathFinderInfo->rail_or_road && IsRoad(atile)) {

   234 				if (IsTileType(atile, MP_TUNNELBRIDGE)) {

   235 					// An existing bridge... let's test the direction ;)

   236 					if ((_m[atile].m5 & 1U) != (i & 1)) continue;

   237 					// This problem only is valid for tunnels:

   238 					// When the last tile was not yet a tunnel, check if we enter from the right side..

   239 					if ((_m[atile].m5 & 0x80) == 0) {

   240 						if (i != (_m[atile].m5 & 3U)) continue;

   241 					}

   242 				}

   243 			}

   244 			// But also if we are on a bridge, we can only move a certain direction

   245 			if (!PathFinderInfo->rail_or_road && IsRoad(ctile)) {

   246 				if (IsTileType(ctile, MP_TUNNELBRIDGE)) {

   247 					// An existing bridge/tunnel... let's test the direction ;)

   248 					if ((_m[ctile].m5 & 1U) != (i & 1)) continue;

   249 				}

   250 			}

   251 

   252 			if ((AI_PATHFINDER_FLAG_BRIDGE & current->path.node.user_data[0]) != 0 ||

   253 					(AI_PATHFINDER_FLAG_TUNNEL & current->path.node.user_data[0]) != 0) {

   254 				// We are a bridge/tunnel, how cool!!

   255 				//  This means we can only point forward.. get the direction from the user_data

   256 				if (i != (current->path.node.user_data[0] >> 8)) continue;

   257 			}

   258 			dir = 0;

   259 

   260 			// First, check if we have a parent

   261 			if (current->path.parent == NULL && current->path.node.user_data[0] == 0) {

   262 				// If not, this means we are at the starting station

   263 				if (PathFinderInfo->start_direction != AI_PATHFINDER_NO_DIRECTION) {

   264 					// We do need a direction?

   265 					if (AiNew_GetDirection(ctile, atile) != PathFinderInfo->start_direction) {

   266 						// We are not pointing the right way, invalid tile

   267 						continue;

   268 					}

   269 				}

   270 			} else if (current->path.node.user_data[0] == 0) {

   271 				if (PathFinderInfo->rail_or_road) {

   272 					// Rail check

   273 					dir = AiNew_GetRailDirection(current->path.parent->node.tile, ctile, atile);

   274 					ret = DoCommandByTile(ctile, 0, dir, DC_AUTO | DC_NO_WATER, CMD_BUILD_SINGLE_RAIL);

   275 					if (CmdFailed(ret)) continue;

   276 #ifdef AI_PATHFINDER_NO_90DEGREES_TURN

   277 					if (current->path.parent->parent != NULL) {

   278 						// Check if we don't make a 90degree curve

   279 						int dir1 = AiNew_GetRailDirection(current->path.parent->parent->node.tile, current->path.parent->node.tile, ctile);

   280 						if (_illegal_curves[dir1] == dir || _illegal_curves[dir] == dir1) {

   281 							continue;

   282 						}

   283 					}

   284 #endif

   285 				} else {

   286 					// Road check

   287 					dir = AiNew_GetRoadDirection(current->path.parent->node.tile, ctile, atile);

   288 					if (IsRoad(ctile)) {

   289 						if (IsTileType(ctile, MP_TUNNELBRIDGE)) {

   290 							// We have a bridge, how nicely! We should mark it...

   291 							dir = 0;

   292 						} else {

   293 							// It already has road.. check if we miss any bits!

   294 							if ((_m[ctile].m5 & dir) != dir) {

   295 								// We do miss some pieces :(

   296 								dir &= ~_m[ctile].m5;

   297 							} else {

   298 								dir = 0;

   299 							}

   300 						}

   301 					}

   302 					// Only destruct things if it is MP_CLEAR of MP_TREES

   303 					if (dir != 0) {

   304 						ret = DoCommandByTile(ctile, dir, 0, DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD);

   305 						if (CmdFailed(ret)) continue;

   306 					}

   307 				}

   308 			}

   309 

   310 			// The tile can be connected

   311 			aystar->neighbours[aystar->num_neighbours].tile = atile;

   312 			aystar->neighbours[aystar->num_neighbours].user_data[0] = 0;

   313 			aystar->neighbours[aystar->num_neighbours++].direction = 0;

   314 		}

   315 	}

   316 

   317 	// Next step, check for bridges and tunnels

   318 	if (current->path.parent != NULL && current->path.node.user_data[0] == 0) {

   319 		TileInfo ti;

   320 		// First we get the dir from this tile and his parent

   321 		int dir = AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile);

   322 		// It means we can only walk with the track, so the bridge has to be in the same direction

   323 		TileIndex tile = current->path.node.tile;

   324 		TileIndex new_tile = tile;

   325 

   326 		FindLandscapeHeightByTile(&ti, tile);

   327 

   328 		// Bridges can only be build on land that is not flat

   329 		//  And if there is a road or rail blocking

   330 		if (ti.tileh != 0 ||

   331 				(PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_STREET)) ||

   332 				(!PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_RAILWAY))) {

   333 			for (;;) {

   334 				new_tile += TileOffsByDir(dir);

   335 

   336 				// Precheck, is the length allowed?

   337 				if (!CheckBridge_Stuff(0, GetBridgeLength(tile, new_tile))) break;

   338 

   339 				// Check if we hit the station-tile.. we don't like that!

   340 				if (TILES_BETWEEN(new_tile, PathFinderInfo->end_tile_tl, PathFinderInfo->end_tile_br)) break;

   341 

   342 				// Try building the bridge..

   343 				ret = DoCommandByTile(tile, new_tile, (0 << 8) + (MAX_BRIDGES / 2), DC_AUTO, CMD_BUILD_BRIDGE);

   344 				if (CmdFailed(ret)) continue;

   345 				// We can build a bridge here.. add him to the neighbours

   346 				aystar->neighbours[aystar->num_neighbours].tile = new_tile;

   347 				aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_BRIDGE + (dir << 8);

   348 				aystar->neighbours[aystar->num_neighbours++].direction = 0;

   349 				// We can only have 12 neighbours, and we need 1 left for tunnels

   350 				if (aystar->num_neighbours == 11) break;

   351 			}

   352 		}

   353 

   354 		// Next, check for tunnels!

   355 		// Tunnels can only be build with tileh of 3, 6, 9 or 12, depending on the direction

   356 		//  For now, we check both sides for this tile.. terraforming gives fuzzy result

   357 		if ((dir == 0 && ti.tileh == 12) ||

   358 				(dir == 1 && ti.tileh == 6) ||

   359 				(dir == 2 && ti.tileh == 3) ||

   360 				(dir == 3 && ti.tileh == 9)) {

   361 			// Now simply check if a tunnel can be build

   362 			ret = DoCommandByTile(tile, (PathFinderInfo->rail_or_road?0:0x200), 0, DC_AUTO, CMD_BUILD_TUNNEL);

   363 			FindLandscapeHeightByTile(&ti, _build_tunnel_endtile);

   364 			if (!CmdFailed(ret) && (ti.tileh == 3 || ti.tileh == 6 || ti.tileh == 9 || ti.tileh == 12)) {

   365 				aystar->neighbours[aystar->num_neighbours].tile = _build_tunnel_endtile;

   366 				aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_TUNNEL + (dir << 8);

   367 				aystar->neighbours[aystar->num_neighbours++].direction = 0;

   368 			}

   369 		}

   370 	}

   371 }

   372 

   373 

   374 extern uint GetRailFoundation(uint tileh, uint bits);

   375 extern uint GetRoadFoundation(uint tileh, uint bits);

   376 extern uint GetBridgeFoundation(uint tileh, byte direction);

   377 enum {

   378 	BRIDGE_NO_FOUNDATION = 1 << 0 | 1 << 3 | 1 << 6 | 1 << 9 | 1 << 12,

   379 };

   380 

   381 // The most important function: it calculates the g-value

   382 static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)

   383 {

   384 	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;

   385 	int r, res = 0;

   386 	TileInfo ti, parent_ti;

   387 

   388 	// Gather some information about the tile..

   389 	FindLandscapeHeightByTile(&ti, current->tile);

   390 	FindLandscapeHeightByTile(&parent_ti, parent->path.node.tile);

   391 

   392 	// Check if we hit the end-tile

   393 	if (TILES_BETWEEN(current->tile, PathFinderInfo->end_tile_tl, PathFinderInfo->end_tile_br)) {

   394 		// We are at the end-tile, check if we had a direction or something...

   395 		if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION && AiNew_GetDirection(current->tile, parent->path.node.tile) != PathFinderInfo->end_direction) {

   396 			// We are not pointing the right way, invalid tile

   397 			return AYSTAR_INVALID_NODE;

   398 		}

   399 		// If it was valid, drop out.. we don't build on the endtile

   400 		return 0;

   401 	}

   402 

   403 	// Give everything a small penalty

   404 	res += AI_PATHFINDER_PENALTY;

   405 

   406 	if (!PathFinderInfo->rail_or_road) {

   407 		// Road has the lovely advantage it can use other road... check if

   408 		//  the current tile is road, and if so, give a good bonus

   409 		if (IsRoad(current->tile)) {

   410 			res -= AI_PATHFINDER_ROAD_ALREADY_EXISTS_BONUS;

   411 		}

   412 	}

   413 

   414 	// We should give a penalty when the tile is going up or down.. this is one way to do so!

   415 	//  Too bad we have to count it from the parent.. but that is not so bad.

   416 	// We also dislike long routes on slopes, since they do not look too realistic

   417 	//  when there is a flat land all around, they are more expensive to build, and

   418 	//  especially they essentially block the ability to connect or cross the road

   419 	//  from one side.

   420 	if (parent_ti.tileh != 0 && parent->path.parent != NULL) {

   421 		// Skip if the tile was from a bridge or tunnel

   422 		if (parent->path.node.user_data[0] == 0 && current->user_data[0] == 0) {

   423 			if (PathFinderInfo->rail_or_road) {

   424 				r = GetRailFoundation(parent_ti.tileh, 1 << AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile));

   425 				// Maybe is BRIDGE_NO_FOUNDATION a bit strange here, but it contains just the right information..

   426 				if (r >= 15 || (r == 0 && (BRIDGE_NO_FOUNDATION & (1 << ti.tileh)))) {

   427 					res += AI_PATHFINDER_TILE_GOES_UP_PENALTY;

   428 				} else {

   429 					res += AI_PATHFINDER_FOUNDATION_PENALTY;

   430 				}

   431 			} else {

   432 				if (!(IsRoad(parent->path.node.tile) && IsTileType(parent->path.node.tile, MP_TUNNELBRIDGE))) {

   433 					r = GetRoadFoundation(parent_ti.tileh, AiNew_GetRoadDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile));

   434 					if (r >= 15 || r == 0)

   435 						res += AI_PATHFINDER_TILE_GOES_UP_PENALTY;

   436 					else

   437 						res += AI_PATHFINDER_FOUNDATION_PENALTY;

   438 				}

   439 			}

   440 		}

   441 	}

   442 

   443 	// Are we part of a tunnel?

   444 	if ((AI_PATHFINDER_FLAG_TUNNEL & current->user_data[0]) != 0) {

   445 		// Tunnels are very expensive when build on long routes..

   446 		// Ironicly, we are using BridgeCode here ;)

   447 		r = AI_PATHFINDER_TUNNEL_PENALTY * GetBridgeLength(current->tile, parent->path.node.tile);

   448 		res += r + (r >> 8);

   449 	}

   450 

   451 	// Are we part of a bridge?

   452 	if ((AI_PATHFINDER_FLAG_BRIDGE & current->user_data[0]) != 0) {

   453 		// That means for every length a penalty

   454 		res += AI_PATHFINDER_BRIDGE_PENALTY * GetBridgeLength(current->tile, parent->path.node.tile);

   455 		// Check if we are going up or down, first for the starting point

   456 		// In user_data[0] is at the 8th bit the direction

   457 		if (!(BRIDGE_NO_FOUNDATION & (1 << parent_ti.tileh))) {

   458 			if (GetBridgeFoundation(parent_ti.tileh, (current->user_data[0] >> 8) & 1) < 15)

   459 				res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;

   460 		}

   461 		// Second for the end point

   462 		if (!(BRIDGE_NO_FOUNDATION & (1 << ti.tileh))) {

   463 			if (GetBridgeFoundation(ti.tileh, (current->user_data[0] >> 8) & 1) < 15)

   464 				res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;

   465 		}

   466 		if (parent_ti.tileh == 0) res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;

   467 		if (ti.tileh == 0) res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;

   468 	}

   469 

   470 	//  To prevent the AI from taking the fastest way in tiles, but not the fastest way

   471 	//    in speed, we have to give a good penalty to direction changing

   472 	//  This way, we get almost the fastest way in tiles, and a very good speed on the track

   473 	if (!PathFinderInfo->rail_or_road) {

   474 		if (parent->path.parent != NULL &&

   475 				AiNew_GetDirection(current->tile, parent->path.node.tile) != AiNew_GetDirection(parent->path.node.tile, parent->path.parent->node.tile)) {

   476 			// When road exists, we don't like turning, but its free, so don't be to piggy about it

   477 			if (IsRoad(parent->path.node.tile))

   478 				res += AI_PATHFINDER_DIRECTION_CHANGE_ON_EXISTING_ROAD_PENALTY;

   479 			else

   480 				res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY;

   481 		}

   482 	} else {

   483 		// For rail we have 1 exeption: diagonal rail..

   484 		// So we fetch 2 raildirection. That of the current one, and of the one before that

   485 		if (parent->path.parent != NULL && parent->path.parent->parent != NULL) {

   486 			int dir1 = AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile);

   487 			int dir2 = AiNew_GetRailDirection(parent->path.parent->parent->node.tile, parent->path.parent->node.tile, parent->path.node.tile);

   488 			// First, see if we are on diagonal path, that is better than straight path

   489 			if (dir1 > 1) { res -= AI_PATHFINDER_DIAGONAL_BONUS; }

   490 

   491 			// First see if they are different

   492 			if (dir1 != dir2) {

   493 				// dir 2 and 3 are 1 diagonal track, and 4 and 5.

   494 				if (!(((dir1 == 2 || dir1 == 3) && (dir2 == 2 || dir2 == 3)) || ((dir1 == 4 || dir1 == 5) && (dir2 == 4 || dir2 == 5)))) {

   495 					// It is not, so we changed of direction

   496 					res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY;

   497 				}

   498 				if (parent->path.parent->parent->parent != NULL) {

   499 					int dir3 = AiNew_GetRailDirection(parent->path.parent->parent->parent->node.tile, parent->path.parent->parent->node.tile, parent->path.parent->node.tile);

   500 					// Check if we changed 3 tiles of direction in 3 tiles.. bad!!!

   501 					if ((dir1 == 0 || dir1 == 1) && dir2 > 1 && (dir3 == 0 || dir3 == 1)) {

   502 						res += AI_PATHFINDER_CURVE_PENALTY;

   503 					}

   504 				}

   505 			}

   506 		}

   507 	}

   508 

   509 	// Res should never be below zero.. if so, make it zero!

   510 	if (res < 0) { res = 0; }

   511 

   512 	// Return our value

   513 	return res;

   514 }