summaryrefslogtreecommitdiff
path: root/ai_pathfinder.c
blob: 76471a1234fe533f2172951da8344be341211785 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
#include "stdafx.h"
#include "ttd.h"
#include "debug.h"
#include "map.h"
#include "tile.h"
#include "command.h"
#include "ai.h"
#include "depot.h"

#define TEST_STATION_NO_DIR 0xFF

// Tests if a station can be build on the given spot
// TODO: make it train compatible
static bool TestCanBuildStationHere(uint tile, byte dir)
{
    Player *p = DEREF_PLAYER(_current_player);
    if (dir == TEST_STATION_NO_DIR) {
        // TODO: currently we only allow spots that can be access from al 4 directions...
        //  should be fixed!!!
        for (dir=0;dir<4;dir++) {
        	int res = AiNew_Build_Station(p, p->ainew.tbt, tile, 1, 1, dir, DC_QUERY_COST);
            if (res != CMD_ERROR)
            	return true;
        }
        return false;
    } else {
       	int res = AiNew_Build_Station(p, p->ainew.tbt, tile, 1, 1, dir, DC_QUERY_COST);
        if (res == CMD_ERROR)
        	return false;
    }
    return true;
}


static bool IsRoad(TileIndex tile)
{
	return
		// MP_STREET, but not a road depot?
		(IsTileType(tile, MP_STREET) && !(IsTileDepotType(tile, TRANSPORT_ROAD))) ||
		(IsTileType(tile, MP_TUNNELBRIDGE) && (
			// road tunnel?
			((_map5[tile] & 0x80) == 0 && (_map5[tile] & 0x4) == 0x4) ||
			// road bridge?
			((_map5[tile] & 0x80) != 0 && (_map5[tile] & 0x2) == 0x2)
		));
}


// Checks if a tile 'a' is between the tiles 'b' and 'c'
#define TILES_BETWEEN(a, b, c) (TileX(a) >= TileX(b) && TileX(a) <= TileX(c) && TileY(a) >= TileY(b) && TileY(a) <= TileY(c))

// Check if the current tile is in our end-area
static int32 AyStar_AiPathFinder_EndNodeCheck(AyStar *aystar, OpenListNode *current)
{
	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;
	// It is not allowed to have a station on the end of a bridge or tunnel ;)
	if (current->path.node.user_data[0] != 0) return AYSTAR_DONE;
	if (TILES_BETWEEN(current->path.node.tile, PathFinderInfo->end_tile_tl, PathFinderInfo->end_tile_br))
		if (IsTileType(current->path.node.tile, MP_CLEAR) || IsTileType(current->path.node.tile, MP_TREES))
			if (current->path.parent == NULL || TestCanBuildStationHere(current->path.node.tile,AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile)))
    			return AYSTAR_FOUND_END_NODE;

	return AYSTAR_DONE;
}

// Calculates the hash
//   Currently it is a 10 bit hash, so the hash array has a max depth of 6 bits (so 64)
static uint AiPathFinder_Hash(uint key1, uint key2)
{
	return (TileX(key1) & 0x1F) + ((TileY(key1) & 0x1F) << 5);
}

// Clear the memory of all the things
static void AyStar_AiPathFinder_Free(AyStar *aystar)
{
	AyStarMain_Free(aystar);
	free(aystar);
}

static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
static void AyStar_AiPathFinder_FoundEndNode(AyStar *aystar, OpenListNode *current);
static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current);

// This creates the AiPathFinder
AyStar *new_AyStar_AiPathFinder(int max_tiles_around, Ai_PathFinderInfo *PathFinderInfo) {
	PathNode start_node;
	uint x,y;
	// Create AyStar
	AyStar *result = malloc(sizeof(AyStar));
	init_AyStar(result, AiPathFinder_Hash, 1 << 10);
	// Set the function pointers
	result->CalculateG = AyStar_AiPathFinder_CalculateG;
	result->CalculateH = AyStar_AiPathFinder_CalculateH;
	result->EndNodeCheck = AyStar_AiPathFinder_EndNodeCheck;
	result->FoundEndNode = AyStar_AiPathFinder_FoundEndNode;
	result->GetNeighbours = AyStar_AiPathFinder_GetNeighbours;

	result->free = AyStar_AiPathFinder_Free;

	// Set some information
	result->loops_per_tick = AI_PATHFINDER_LOOPS_PER_TICK;
	result->max_path_cost = 0;
	result->max_search_nodes = AI_PATHFINDER_MAX_SEARCH_NODES;

	// Set the user_data to the PathFinderInfo
	result->user_target = PathFinderInfo;

	// Set the start node
	start_node.parent = NULL;
	start_node.node.direction = 0;
	start_node.node.user_data[0] = 0;

	// Now we add all the starting tiles
	for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) {
		for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) {
			start_node.node.tile = TILE_XY(x,y);
			result->addstart(result, &start_node.node);
		}
	}

	return result;
}

// To reuse AyStar we sometimes have to clean all the memory
void clean_AyStar_AiPathFinder(AyStar *aystar, Ai_PathFinderInfo *PathFinderInfo) {
	PathNode start_node;
	uint x,y;

	aystar->clear(aystar);

	// Set the user_data to the PathFinderInfo
	aystar->user_target = PathFinderInfo;

	// Set the start node
	start_node.parent = NULL;
	start_node.node.direction = 0;
	start_node.node.user_data[0] = 0;
	start_node.node.tile = PathFinderInfo->start_tile_tl;

	// Now we add all the starting tiles
	for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) {
		for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) {
			if (!(IsTileType(TILE_XY(x,y), MP_CLEAR) || IsTileType(TILE_XY(x,y), MP_TREES))) continue;
			if (!TestCanBuildStationHere(TILE_XY(x,y),TEST_STATION_NO_DIR)) continue;
			start_node.node.tile = TILE_XY(x,y);
			aystar->addstart(aystar, &start_node.node);
		}
	}
}

// The h-value, simple calculation
static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent) {
	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;
	int r, r2;
	if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION) {
		// The station is pointing to a direction, add a tile towards that direction, so the H-value is more accurate
		r = DistanceManhattan(current->tile, PathFinderInfo->end_tile_tl + TileOffsByDir(PathFinderInfo->end_direction));
		r2 = DistanceManhattan(current->tile, PathFinderInfo->end_tile_br + TileOffsByDir(PathFinderInfo->end_direction));
	} else {
		// No direction, so just get the fastest route to the station
		r = DistanceManhattan(current->tile, PathFinderInfo->end_tile_tl);
		r2 = DistanceManhattan(current->tile, PathFinderInfo->end_tile_br);
	}
	// See if the bottomright is faster than the topleft..
	if (r2 < r) r = r2;
	return r * AI_PATHFINDER_H_MULTIPLER;
}

// We found the end.. let's get the route back and put it in an array
static void AyStar_AiPathFinder_FoundEndNode(AyStar *aystar, OpenListNode *current) {
	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;
	uint i = 0;
	PathNode *parent = &current->path;

	do {
     	PathFinderInfo->route_extra[i] = parent->node.user_data[0];
		PathFinderInfo->route[i++] = parent->node.tile;
		if (i > lengthof(PathFinderInfo->route)) {
			// We ran out of space for the PathFinder
			DEBUG(ai,0)("[AiPathFinder] Ran out of spacein the route[] array!!!");
			PathFinderInfo->route_length = -1; // -1 indicates out of space
			return;
		}
		parent = parent->parent;
	} while (parent != NULL);
	PathFinderInfo->route_length = i;
	DEBUG(ai,1)("[Ai-PathFinding] Found route of %d nodes long in %d nodes of searching",i,Hash_Size(&aystar->ClosedListHash));
}

// What tiles are around us.
static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current) {
		uint i;
		int r;
		int dir;

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

    aystar->num_neighbours = 0;

  	// Go through all surrounding tiles and check if they are within the limits
   	for (i=0;i<4;i++) {
   		if (TileX(TileOffsByDir(i) + current->path.node.tile) > 1 &&
					TileX(TileOffsByDir(i) + current->path.node.tile) < MapMaxX() - 1 &&
       		TileY(TileOffsByDir(i) + current->path.node.tile) > 1 &&
					TileY(TileOffsByDir(i) + current->path.node.tile) < MapMaxY() - 1) {
       		// We also directly test if the current tile can connect to this tile..
       		//  We do this simply by just building the tile!

       		// If the next step is a bridge, we have to enter it the right way
       		if (!PathFinderInfo->rail_or_road && IsRoad(current->path.node.tile + TileOffsByDir(i))) {
       			if (IsTileType(current->path.node.tile + TileOffsByDir(i), MP_TUNNELBRIDGE)) {
       				// An existing bridge... let's test the direction ;)
       				if ((_map5[current->path.node.tile + TileOffsByDir(i)] & 1U) != (i & 1)) continue;
   					// This problem only is valid for tunnels:
       				// When the last tile was not yet a tunnel, check if we enter from the right side..
       				if ((_map5[current->path.node.tile + TileOffsByDir(i)] & 0x80) == 0) {
       					if (i != (_map5[current->path.node.tile + TileOffsByDir(i)] & 3U)) continue;
       				}
       			}
       		}
       		// But also if we are on a bridge, we can only move a certain direction
       		if (!PathFinderInfo->rail_or_road && IsRoad(current->path.node.tile)) {
       			if (IsTileType(current->path.node.tile, MP_TUNNELBRIDGE)) {
       				// An existing bridge/tunnel... let's test the direction ;)
       				if ((_map5[current->path.node.tile] & 1U) != (i & 1)) continue;
       			}
       		}

       		if ((AI_PATHFINDER_FLAG_BRIDGE & current->path.node.user_data[0]) != 0 ||
       			(AI_PATHFINDER_FLAG_TUNNEL & current->path.node.user_data[0]) != 0) {
       			// We are a bridge/tunnel, how cool!!
       			//  This means we can only point forward.. get the direction from the user_data
       			if (i != (current->path.node.user_data[0] >> 8)) continue;
       		}
       		dir = 0;

       		// First, check if we have a parent
       		if (current->path.parent == NULL && current->path.node.user_data[0] == 0) {
       			// If not, this means we are at the starting station
       			if (PathFinderInfo->start_direction != AI_PATHFINDER_NO_DIRECTION) {
		       		// We do need a direction?
		       		if (AiNew_GetDirection(current->path.node.tile, current->path.node.tile + TileOffsByDir(i)) != PathFinderInfo->start_direction)
		       			// We are not pointing the right way, invalid tile
		       			continue;
		       	}
       		} else if (current->path.node.user_data[0] == 0) {
       			if (PathFinderInfo->rail_or_road) {
       				// Rail check
       				dir = AiNew_GetRailDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + TileOffsByDir(i));
       				r = DoCommandByTile(current->path.node.tile, 0, dir, DC_AUTO | DC_NO_WATER, CMD_BUILD_SINGLE_RAIL);
       				if (r == CMD_ERROR) continue;
#ifdef AI_PATHFINDER_NO_90DEGREES_TURN
       				if (current->path.parent->parent != NULL) {
       					// Check if we don't make a 90degree curve
       					int dir1 = AiNew_GetRailDirection(current->path.parent->parent->node.tile, current->path.parent->node.tile, current->path.node.tile);
       					if (_illegal_curves[dir1] == dir || _illegal_curves[dir] == dir1) {
       						continue;
       					}
       				}
#endif
       			} else {
       				// Road check
       				dir = AiNew_GetRoadDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + TileOffsByDir(i));
       				if (IsRoad(current->path.node.tile)) {
       					if (IsTileType(current->path.node.tile, MP_TUNNELBRIDGE)) {
       						// We have a bridge, how nicely! We should mark it...
       						dir = 0;
       					} else {
	       					// It already has road.. check if we miss any bits!
	       					if ((_map5[current->path.node.tile] & dir) != dir) {
	       						// We do miss some pieces :(
	       						dir &= ~_map5[current->path.node.tile];
	       					} else {
	       						dir = 0;
    	   					}
    	   				}
       				}
       				// Only destruct things if it is MP_CLEAR of MP_TREES
       				if (dir != 0) {
       					r = DoCommandByTile(current->path.node.tile, dir, 0, DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD);
       					if (r == CMD_ERROR) continue;
       				}
       			}

       		}

			// The tile can be connected
   			aystar->neighbours[aystar->num_neighbours].tile = TileOffsByDir(i) + current->path.node.tile;
   			aystar->neighbours[aystar->num_neighbours].user_data[0] = 0;
   			aystar->neighbours[aystar->num_neighbours++].direction = 0;
       	}
    }

    // Next step, check for bridges and tunnels
    if (current->path.parent != NULL && current->path.node.user_data[0] == 0) {

        TileInfo ti;
        // First we get the dir from this tile and his parent
    	int dir = AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile);
    	// It means we can only walk with the track, so the bridge has to be in the same direction
    	TileIndex tile = current->path.node.tile;
    	TileIndex new_tile = tile;

    	FindLandscapeHeightByTile(&ti, tile);

   		// Bridges can only be build on land that is not flat
   		//  And if there is a road or rail blocking
   		if (ti.tileh != 0 ||
     		(PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_STREET)) ||
       		(!PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDir(dir), MP_RAILWAY))) {

    		for (;;) {
    			new_tile += TileOffsByDir(dir);

    	    	// Precheck, is the length allowed?
    	    	if (!CheckBridge_Stuff(0,GetBridgeLength(tile, new_tile))) break;

    	    	// Check if we hit the station-tile.. we don't like that!
    	    	if (TILES_BETWEEN(new_tile,PathFinderInfo->end_tile_tl,PathFinderInfo->end_tile_br)) break;

    	    	// Try building the bridge..
    	    	r = DoCommandByTile(tile, new_tile, (0<<8) + (MAX_BRIDGES / 2), DC_AUTO, CMD_BUILD_BRIDGE);
	    	   	if (r == CMD_ERROR) continue;
    		   	// We can build a bridge here.. add him to the neighbours
   				aystar->neighbours[aystar->num_neighbours].tile = new_tile;
	   			aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_BRIDGE + (dir << 8);
	   			aystar->neighbours[aystar->num_neighbours++].direction = 0;
				// We can only have 12 neighbours, and we need 1 left for tunnels
				if (aystar->num_neighbours == 11) break;
			}
    	}

    	// Next, check for tunnels!
    	// Tunnels can only be build with tileh of 3, 6, 9 or 12, depending on the direction
    	//  For now, we check both sides for this tile.. terraforming gives fuzzy result
    	if ((dir == 0 && ti.tileh == 12) ||
    		(dir == 1 && ti.tileh == 6) ||
    		(dir == 2 && ti.tileh == 3) ||
    		(dir == 3 && ti.tileh == 9)) {
    		// Now simply check if a tunnel can be build
    		r = DoCommandByTile(tile, (PathFinderInfo->rail_or_road?0:0x200), 0, DC_AUTO, CMD_BUILD_TUNNEL);
    		FindLandscapeHeightByTile(&ti, _build_tunnel_endtile);
    		if (r != CMD_ERROR && (ti.tileh == 3 || ti.tileh == 6 || ti.tileh == 9 || ti.tileh == 12)) {
    			aystar->neighbours[aystar->num_neighbours].tile = _build_tunnel_endtile;
	   			aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_TUNNEL + (dir << 8);
	   			aystar->neighbours[aystar->num_neighbours++].direction = 0;
    		}
    	}
  	}
}

extern uint GetRailFoundation(uint tileh, uint bits);
extern uint GetRoadFoundation(uint tileh, uint bits);
extern uint GetBridgeFoundation(uint tileh, byte direction);
enum {
    BRIDGE_NO_FOUNDATION = 1 << 0 | 1 << 3 | 1 << 6 | 1 << 9 | 1 << 12,
};

// The most important function: it calculates the g-value
static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent) {
	Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target;
	int r, res = 0;
	TileInfo ti, parent_ti;

	// Gather some information about the tile..
	FindLandscapeHeightByTile(&ti, current->tile);
	FindLandscapeHeightByTile(&parent_ti, parent->path.node.tile);

	// Check if we hit the end-tile
	if (TILES_BETWEEN(current->tile,PathFinderInfo->end_tile_tl,PathFinderInfo->end_tile_br)) {
		// We are at the end-tile, check if we had a direction or something...
		if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION && AiNew_GetDirection(current->tile, parent->path.node.tile) != PathFinderInfo->end_direction)
			// We are not pointing the right way, invalid tile
			return AYSTAR_INVALID_NODE;
		// If it was valid, drop out.. we don't build on the endtile
		return 0;
	}

	// Give everything a small penalty
	res += AI_PATHFINDER_PENALTY;

	if (!PathFinderInfo->rail_or_road) {
		// Road has the lovely advantage it can use other road... check if
		//  the current tile is road, and if so, give a good bonus
		if (IsRoad(current->tile)) {
			res -= AI_PATHFINDER_ROAD_ALREADY_EXISTS_BONUS;
		}
	}

	// We should give a penalty when the tile is going up or down.. this is one way to do so!
	//  Too bad we have to count it from the parent.. but that is not so bad
	if (parent_ti.tileh != 0 && parent->path.parent != NULL) {
		// Skip if the tile was from a bridge or tunnel
		if (parent->path.node.user_data[0] == 0 && current->user_data[0] == 0) {
			if (PathFinderInfo->rail_or_road) {
				r = GetRailFoundation(parent_ti.tileh, 1 << AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile));
				// Maybe is BRIDGE_NO_FOUNDATION a bit strange here, but it contains just the right information..
				if (r >= 15 || (r == 0 && (BRIDGE_NO_FOUNDATION & (1 << ti.tileh)))) {
					res += AI_PATHFINDER_TILE_GOES_UP_PENALTY;
				}
			} else {
				if (!(IsRoad(parent->path.node.tile) && IsTileType(parent->path.node.tile, MP_TUNNELBRIDGE))) {
					r = GetRoadFoundation(parent_ti.tileh, AiNew_GetRoadDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile));
					if (r >= 15 || r == 0)
						res += AI_PATHFINDER_TILE_GOES_UP_PENALTY;
				}
			}
		}
	}

	// Are we part of a tunnel?
	if ((AI_PATHFINDER_FLAG_TUNNEL & current->user_data[0]) != 0) {
		// Tunnels are very expensive when build on long routes..
		// Ironicly, we are using BridgeCode here ;)
		r = AI_PATHFINDER_TUNNEL_PENALTY * GetBridgeLength(current->tile, parent->path.node.tile);
		res += r + (r >> 8);
	}

	// Are we part of a bridge?
	if ((AI_PATHFINDER_FLAG_BRIDGE & current->user_data[0]) != 0) {
		// That means for every length a penalty
		res += AI_PATHFINDER_BRIDGE_PENALTY * GetBridgeLength(current->tile, parent->path.node.tile);
		// Check if we are going up or down, first for the starting point
		// In user_data[0] is at the 8th bit the direction
		if (!(BRIDGE_NO_FOUNDATION & (1 << parent_ti.tileh))) {
			if (GetBridgeFoundation(parent_ti.tileh, (current->user_data[0] >> 8) & 1) < 15)
				res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;
		}
		// Second for the end point
		if (!(BRIDGE_NO_FOUNDATION & (1 << ti.tileh))) {
			if (GetBridgeFoundation(ti.tileh, (current->user_data[0] >> 8) & 1) < 15)
				res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;
		}
		if (parent_ti.tileh == 0)
			res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;
		if (ti.tileh == 0)
			res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;
	}

	//  To prevent the AI from taking the fastest way in tiles, but not the fastest way
	//    in speed, we have to give a good penalty to direction changing
	//  This way, we get almost the fastest way in tiles, and a very good speed on the track
	if (!PathFinderInfo->rail_or_road) {
		if (parent->path.parent != NULL &&
			AiNew_GetDirection(current->tile, parent->path.node.tile) != AiNew_GetDirection(parent->path.node.tile, parent->path.parent->node.tile)) {
			// When road exists, we don't like turning, but its free, so don't be to piggy about it
			if (IsRoad(parent->path.node.tile))
				res += AI_PATHFINDER_DIRECTION_CHANGE_ON_EXISTING_ROAD_PENALTY;
			else
				res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY;
		}
	} else {
		// For rail we have 1 exeption: diagonal rail..
		// So we fetch 2 raildirection. That of the current one, and of the one before that
		if (parent->path.parent != NULL && parent->path.parent->parent != NULL) {
			int dir1 = AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile);
			int dir2 = AiNew_GetRailDirection(parent->path.parent->parent->node.tile, parent->path.parent->node.tile, parent->path.node.tile);
			// First, see if we are on diagonal path, that is better than straight path
			if (dir1 > 1) { res -= AI_PATHFINDER_DIAGONAL_BONUS; }

			// First see if they are different
			if (dir1 != dir2) {
				// dir 2 and 3 are 1 diagonal track, and 4 and 5.
				if (!(((dir1 == 2 || dir1 == 3) && (dir2 == 2 || dir2 == 3)) || ((dir1 == 4 || dir1 == 5) && (dir2 == 4 || dir2 == 5)))) {
					// It is not, so we changed of direction
					res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY;
				}
				if (parent->path.parent->parent->parent != NULL) {
					int dir3 = AiNew_GetRailDirection(parent->path.parent->parent->parent->node.tile, parent->path.parent->parent->node.tile, parent->path.parent->node.tile);
					// Check if we changed 3 tiles of direction in 3 tiles.. bad!!!
					if ((dir1 == 0 || dir1 == 1) && dir2 > 1 && (dir3 == 0 || dir3 == 1)) {
						res += AI_PATHFINDER_CURVE_PENALTY;
					}
				}
			}
		}
	}

	// Res should never be below zero.. if so, make it zero!
	if (res < 0) { res = 0; }

	// Return our value
	return res;
}