1

/* $Id$ */

     2

     3

/** @file pathfinder.cpp Pathfinder support for the trolly AI. */

     4

     5

#include "../../stdafx.h"

     6

#include "../../openttd.h"

     7

#include "../../bridge_map.h"

     8

#include "../../debug.h"

     9

#include "../../command_func.h"

    10

#include "trolly.h"

    11

#include "../../tunnel_map.h"

    12

#include "../../bridge.h"

    13

#include "../../tunnelbridge_map.h"

    14

#include "../ai.h"

    15

#include "../../variables.h"

    16

#include "../../player_base.h"

    17

#include "../../player_func.h"

    18

#include "../../tunnelbridge.h"

    19

    20

    21

#define TEST_STATION_NO_DIR 0xFF

    22

    23

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

    24

// TODO: make it train compatible

    25

static bool TestCanBuildStationHere(TileIndex tile, byte dir)

    26

{

    28

    29

	if (dir == TEST_STATION_NO_DIR) {

    30

		CommandCost ret;

    31

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

    32

		//  should be fixed!!!

    33

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

    35

			if (CmdSucceeded(ret)) return true;

    36

		}

    37

		return false;

    38

	}

    39

    40

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

    42

}

    43

    44

    45

static bool IsRoad(TileIndex tile)

    46

{

    47

	return

    48

		// MP_ROAD, but not a road depot?

    49

		(IsTileType(tile, MP_ROAD) && !IsRoadDepot(tile)) ||

    50

		(IsTileType(tile, MP_TUNNELBRIDGE) && GetTunnelBridgeTransportType(tile) == TRANSPORT_ROAD);

    51

}

    52

    53

    54

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

    55

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

    56

    57

    58

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

    59

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

    60

{

    61

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

    62

    63

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

    64

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

    65

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

    66

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

    67

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

    68

				return AYSTAR_FOUND_END_NODE;

    69

    70

	return AYSTAR_DONE;

    71

}

    72

    73

    74

// Calculates the hash

    75

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

    76

static uint AiPathFinder_Hash(uint key1, uint key2)

    77

{

    78

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

    79

}

    80

    81

    82

// Clear the memory of all the things

    83

static void AyStar_AiPathFinder_Free(AyStar *aystar)

    84

{

    85

	AyStarMain_Free(aystar);

    86

	delete aystar;

    87

}

    88

    89

    90

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

    91

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

    92

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

    93

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

    94

    95

    96

// This creates the AiPathFinder

    97

AyStar *new_AyStar_AiPathFinder(int max_tiles_around, Ai_PathFinderInfo *PathFinderInfo)

    98

{

    99

	PathNode start_node;

   100

	uint x;

   101

	uint y;

   102

	// Create AyStar

   103

	AyStar *result = new AyStar();

   104

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

   105

	// Set the function pointers

   106

	result->CalculateG = AyStar_AiPathFinder_CalculateG;

   107

	result->CalculateH = AyStar_AiPathFinder_CalculateH;

   108

	result->EndNodeCheck = AyStar_AiPathFinder_EndNodeCheck;

   109

	result->FoundEndNode = AyStar_AiPathFinder_FoundEndNode;

   110

	result->GetNeighbours = AyStar_AiPathFinder_GetNeighbours;

   111

   112

	result->free = AyStar_AiPathFinder_Free;

   113

   114

	// Set some information

   115

	result->loops_per_tick = AI_PATHFINDER_LOOPS_PER_TICK;

   116

	result->max_path_cost = 0;

   117

	result->max_search_nodes = AI_PATHFINDER_MAX_SEARCH_NODES;

   118

   119

	// Set the user_data to the PathFinderInfo

   120

	result->user_target = PathFinderInfo;

   121

   122

	// Set the start node

   123

	start_node.parent = NULL;

   124

	start_node.node.direction = 0;

   125

	start_node.node.user_data[0] = 0;

   126

   127

	// Now we add all the starting tiles

   128

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

   129

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

   130

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

   131

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

   132

		}

   133

	}

   134

   135

	return result;

   136

}

   137

   138

   139

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

   140

void clean_AyStar_AiPathFinder(AyStar *aystar, Ai_PathFinderInfo *PathFinderInfo)

   141

{

   142

	PathNode start_node;

   143

	uint x;

   144

	uint y;

   145

   146

	aystar->clear(aystar);

   147

   148

	// Set the user_data to the PathFinderInfo

   149

	aystar->user_target = PathFinderInfo;

   150

   151

	// Set the start node

   152

	start_node.parent = NULL;

   153

	start_node.node.direction = 0;

   154

	start_node.node.user_data[0] = 0;

   155

	start_node.node.tile = PathFinderInfo->start_tile_tl;

   156

   157

	// Now we add all the starting tiles

   158

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

   159

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

   160

			TileIndex tile = TileXY(x, y);

   161

   162

			if (!IsTileType(tile, MP_CLEAR) && !IsTileType(tile, MP_TREES)) continue;

   163

			if (!TestCanBuildStationHere(tile, TEST_STATION_NO_DIR)) continue;

   164

			start_node.node.tile = tile;

   165

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

   166

		}

   167

	}

   168

}

   169

   170

   171

// The h-value, simple calculation

   172

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

   173

{

   174

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

   175

	int r, r2;

   176

   177

	if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION) {

   178

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

   179

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

   180

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

   181

	} else {

   182

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

   183

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

   184

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

   185

	}

   186

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

   187

	if (r2 < r) r = r2;

   188

	return r * AI_PATHFINDER_H_MULTIPLER;

   189

}

   190

   191

   192

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

   193

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

   194

{

   195

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

   196

	uint i = 0;

   197

	PathNode *parent = &current->path;

   198

   199

	do {

   200

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

   201

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

   202

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

   203

			// We ran out of space for the PathFinder

   204

			DEBUG(ai, 0, "No more space in pathfinder route[] array");

   205

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

   206

			return;

   207

		}

   208

		parent = parent->parent;

   209

	} while (parent != NULL);

   210

	PathFinderInfo->route_length = i;

   211

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

   212

}

   213

   214

   215

// What tiles are around us.

   216

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

   217

{

   218

	CommandCost ret;

   219

	int dir;

   220

   221

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

   222

   223

	aystar->num_neighbours = 0;

   224

   225

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

   226

	for (DiagDirection i = DIAGDIR_BEGIN; i < DIAGDIR_END; i++) {

   227

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

   228

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

   229

   230

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

   231

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

   232

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

   233

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

   234

   235

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

   236

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

   237

				if (IsTileType(atile, MP_TUNNELBRIDGE)) {

   238

					if (GetTunnelBridgeDirection(atile) != i) continue;

   239

				}

   240

			}

   241

   242

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

   243

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

   244

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

   245

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

   246

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

   247

			}

   248

			dir = 0;

   249

   250

			// First, check if we have a parent

   251

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

   252

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

   253

				if (PathFinderInfo->start_direction != AI_PATHFINDER_NO_DIRECTION) {

   254

					// We do need a direction?

   255

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

   256

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

   257

						continue;

   258

					}

   259

				}

   260

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

   261

				if (PathFinderInfo->rail_or_road) {

   262

					// Rail check

   263

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

   264

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

   265

					if (CmdFailed(ret)) continue;

   266

#ifdef AI_PATHFINDER_NO_90DEGREES_TURN

   267

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

   268

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

   269

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

   270

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

   271

							continue;

   272

						}

   273

					}

   274

#endif

   275

				} else {

   276

					// Road check

   277

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

   278

					if (IsRoad(ctile)) {

   279

						if (IsTileType(ctile, MP_TUNNELBRIDGE)) {

   280

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

   281

							dir = 0;

   282

						} else {

   283

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

   284

							if ((GetAnyRoadBits(ctile, ROADTYPE_ROAD) & dir) != dir) {

   285

								// We do miss some pieces :(

   286

								dir &= ~GetAnyRoadBits(ctile, ROADTYPE_ROAD);

   287

							} else {

   288

								dir = 0;

   289

							}

   290

						}

   291

					}

   292

					// Only destruct things if it is MP_CLEAR of MP_TREES

   293

					if (dir != 0) {

   294

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

   295

						if (CmdFailed(ret)) continue;

   296

					}

   297

				}

   298

			}

   299

   300

			// The tile can be connected

   301

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

   302

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

   303

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

   304

		}

   305

	}

   306

   307

	// Next step, check for bridges and tunnels

   308

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

   309

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

   310

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

   311

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

   312

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

   313

		TileIndex new_tile = tile;

   314

		Slope tileh = GetTileSlope(tile, NULL);

   315

   316

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

   317

		//  And if there is a road or rail blocking

   318

		if (tileh != SLOPE_FLAT ||

   319

				(PathFinderInfo->rail_or_road && IsTileType(tile + TileOffsByDiagDir(dir), MP_ROAD)) ||

   320

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

   321

			for (;;) {

   322

				new_tile += TileOffsByDiagDir(dir);

   323

   324

				// Precheck, is the length allowed?

   325

				if (!CheckBridge_Stuff(0, GetTunnelBridgeLength(tile, new_tile))) break;

   326

   327

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

   328

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

   329

   330

				// Try building the bridge..

   331

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

   332

				if (CmdFailed(ret)) continue;

   333

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

   334

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

   335

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

   336

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

   337

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

   338

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

   339

			}

   340

		}

   341

   342

		// Next, check for tunnels!

   343

		// Tunnels can only be built on slopes corresponding to the direction

   344

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

   345

		if (tileh == InclinedSlope(dir)) {

   346

			// Now simply check if a tunnel can be build

   347

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

   348

			tileh = GetTileSlope(_build_tunnel_endtile, NULL);

   349

			if (CmdSucceeded(ret) && IsInclinedSlope(tileh)) {

   350

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

   351

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

   352

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

   353

			}

   354

		}

   355

	}

   356

}

   357

   358

   359

extern Foundation GetRailFoundation(Slope tileh, TrackBits bits); // XXX function declaration in .c

   360

extern Foundation GetRoadFoundation(Slope tileh, RoadBits bits); // XXX function declaration in .c

   361

   362

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

   363

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

   364

{

   365

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

   366

	int res = 0;

   367

	Slope tileh = GetTileSlope(current->tile, NULL);

   368

	Slope parent_tileh = GetTileSlope(parent->path.node.tile, NULL);

   369

   370

	// Check if we hit the end-tile

   371

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

   372

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

   373

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

   374

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

   375

			return AYSTAR_INVALID_NODE;

   376

		}

   377

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

   378

		return 0;

   379

	}

   380

   381

	// Give everything a small penalty

   382

	res += AI_PATHFINDER_PENALTY;

   383

   384

	if (!PathFinderInfo->rail_or_road) {

   385

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

   386

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

   387

		if (IsRoad(current->tile)) {

   388

			res -= AI_PATHFINDER_ROAD_ALREADY_EXISTS_BONUS;

   389

		}

   390

	}

   391

   392

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

   393

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

   394

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

   395

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

   396

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

   397

	//  from one side.

   398

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

   399

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

   400

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

   401

			if (PathFinderInfo->rail_or_road) {

   402

				Foundation f = GetRailFoundation(parent_tileh, (TrackBits)(1 << AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile)));

   403

				if (IsInclinedFoundation(f) || (!IsFoundation(f) && IsInclinedSlope(parent_tileh))) {

   404

					res += AI_PATHFINDER_TILE_GOES_UP_PENALTY;

   405

				} else {

   406

					res += AI_PATHFINDER_FOUNDATION_PENALTY;

   407

				}

   408

			} else {

   409

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

   410

					Foundation f = GetRoadFoundation(parent_tileh, (RoadBits)AiNew_GetRoadDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile));

   411

					if (IsInclinedFoundation(f) || (!IsFoundation(f) && IsInclinedSlope(parent_tileh))) {

   412

						res += AI_PATHFINDER_TILE_GOES_UP_PENALTY;

   413

					} else {

   414

						res += AI_PATHFINDER_FOUNDATION_PENALTY;

   415

					}

   416

				}

   417

			}

   418

		}

   419

	}

   420

   421

	// Are we part of a tunnel?

   422

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

   423

		int r;

   424

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

   425

		// Ironicly, we are using BridgeCode here ;)

   426

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

   427

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

   428

	}

   429

   430

	// Are we part of a bridge?

   431

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

   432

		// That means for every length a penalty

   433

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

   434

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

   435

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

   436

		if (!HasBridgeFlatRamp(parent_tileh, (Axis)((current->user_data[0] >> 8) & 1))) res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;

   437

		// Second for the end point

   438

		if (!HasBridgeFlatRamp(tileh, (Axis)((current->user_data[0] >> 8) & 1))) res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY;

   439

	}

   440

   441

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

   442

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

   443

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

   444

	if (!PathFinderInfo->rail_or_road) {

   445

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

   446

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

   447

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

   448

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

   449

				res += AI_PATHFINDER_DIRECTION_CHANGE_ON_EXISTING_ROAD_PENALTY;

   450

			} else {

   451

				res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY;

   452

			}

   453

		}

   454

	} else {

   455

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

   456

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

   457

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

   458

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

   459

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

   460

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

   461

			if (dir1 > 1) res -= AI_PATHFINDER_DIAGONAL_BONUS;

   462

   463

			// First see if they are different

   464

			if (dir1 != dir2) {

   465

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

   466

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

   467

					// It is not, so we changed of direction

   468

					res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY;

   469

				}

   470

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

   471

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

   472

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

   473

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

   474

						res += AI_PATHFINDER_CURVE_PENALTY;

   475

					}

   476

				}

   477

			}

   478

		}

   479

	}

   480

   481

	return (res < 0) ? 0 : res;

   482

}