npf.c
author Darkvater
Tue, 08 Mar 2005 23:20:47 +0000
changeset 1465 e595fff78af2
parent 1464 fe5fcc14b2a2
child 1502 620b1d5904c4
permissions -rw-r--r--
(svn r1969) - GUI: Replace vehicle dropdown menu now looks a bit more comform the ones used throughout the game.
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     1
#include "stdafx.h"
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     2
#include "ttd.h"
1299
39c06aba09aa (svn r1803) Move debugging stuff into files of it's own
tron
parents: 1248
diff changeset
     3
#include "debug.h"
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     4
#include "npf.h"
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     5
#include "aystar.h"
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     6
#include "macros.h"
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     7
#include "pathfind.h"
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     8
#include "station.h"
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
     9
#include "tile.h"
1313
f1013ec3d318 (svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents: 1299
diff changeset
    10
#include "depot.h"
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    11
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    12
AyStar _train_find_station;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    13
AyStar _train_find_depot;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    14
AyStar _road_find_station;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    15
AyStar _road_find_depot;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    16
AyStar _npf_aystar;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    17
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    18
/* Maps a trackdir to the bit that stores its status in the map arrays, in the
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    19
 * direction along with the trackdir */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    20
const byte _signal_along_trackdir[14] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    21
	0x80, 0x80, 0x80, 0x20, 0x40, 0x10, 0, 0,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    22
	0x40, 0x40, 0x40, 0x10, 0x80, 0x20
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    23
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    24
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    25
/* Maps a trackdir to the bit that stores its status in the map arrays, in the
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    26
 * direction against the trackdir */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    27
const byte _signal_against_trackdir[14] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    28
	0x40, 0x40, 0x40, 0x10, 0x80, 0x20, 0, 0,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    29
	0x80, 0x80, 0x80, 0x20, 0x40, 0x10
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    30
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    31
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    32
/* Maps a trackdir to the trackdirs that can be reached from it (ie, when
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    33
 * entering the next tile */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    34
const uint16 _trackdir_reaches_trackdirs[14] = {
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
    35
	0x1009, 0x0016, 0x1009, 0x0016, 0x0520, 0x0016, 0, 0,
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
    36
	0x0520, 0x2A00, 0x2A00, 0x0520, 0x2A00, 0x1009
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    37
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    38
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    39
/* Maps a trackdir to all trackdirs that make 90 deg turns with it. */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    40
const uint16 _trackdir_crosses_trackdirs[14] = {
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
    41
	0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C, 0, 0,
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
    42
	0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    43
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    44
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    45
/* Maps a track to all tracks that make 90 deg turns with it. */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    46
const byte _track_crosses_tracks[6] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    47
	0x2, /* Track 1 -> Track 2 */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    48
	0x1, /* Track 2 -> Track 1 */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    49
	0x30, /* Upper -> Left | Right */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    50
	0x30, /* Lower -> Left | Right */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    51
	0x0C, /* Left -> Upper | Lower */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    52
	0x0C, /* Right -> Upper | Lower */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    53
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    54
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    55
/* Maps a trackdir to the (4-way) direction the tile is exited when following
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    56
 * that trackdir */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    57
const byte _trackdir_to_exitdir[14] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    58
	0,1,0,1,2,1, 0,0,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    59
	2,3,3,2,3,0,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    60
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    61
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    62
const byte _track_exitdir_to_trackdir[6][4] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    63
	{0,    0xff, 8,    0xff},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    64
	{0xff, 1,    0xff, 9},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    65
	{2,    0xff, 0xff, 10},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    66
	{0xff, 3,    11,   0xf},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    67
	{0xff, 0xff, 4,    12},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    68
	{13,   5,    0xff, 0xff}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    69
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    70
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    71
const byte _track_direction_to_trackdir[6][8] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    72
	{0xff, 0,    0xff, 0xff, 0xff, 8,    0xff, 0xff},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    73
	{0xff, 0xff, 0xff, 1,    0xff, 0xff, 0xff, 9},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    74
	{0xff, 0xff, 2,    0xff, 0xff, 0xff, 10,   0xff},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    75
	{0xff, 0xff, 3,    0xff, 0xff, 0xff, 11,   0xff},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    76
	{12,   0xff, 0xff, 0xff, 4,    0xff, 0xff, 0xff},
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    77
	{13,   0xff, 0xff, 0xff, 5,    0xff, 0xff, 0xff}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    78
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    79
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    80
const byte _dir_to_diag_trackdir[4] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    81
	0, 1, 8, 9,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    82
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    83
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    84
const byte _reverse_dir[4] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    85
	2, 3, 0, 1
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    86
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    87
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    88
const byte _reverse_trackdir[14] = {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    89
	8, 9, 10, 11, 12, 13, 0xFF, 0xFF,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    90
	0, 1, 2,  3,  4,  5
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    91
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    92
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    93
/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    94
 * the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    95
 */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    96
#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * 0.7071)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
    97
static const uint _trackdir_length[14] = {
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
    98
	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH,
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
    99
	0, 0,
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   100
	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   101
};
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   102
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   103
uint NTPHash(uint key1, uint key2)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   104
{
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   105
	return PATHFIND_HASH_TILE(key1);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   106
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   107
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   108
int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   109
	return 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   110
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   111
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   112
/* Calcs the tile of given station that is closest to a given tile
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   113
 * for this we assume the station is a rectangle,
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   114
 * as defined by its top tile (st->train_tile) and its width/height (st->trainst_w, st->trainst_h)
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   115
 */
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   116
TileIndex CalcClosestStationTile(int station, TileIndex tile) {
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   117
	const Station* st = GetStation(station);
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   118
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   119
	int x1,x2,x3,tx;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   120
	int y1,y2,y3,ty;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   121
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   122
	x1 = TileX(st->train_tile);  y1 = TileY(st->train_tile);  // topmost corner of station
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   123
	x2 = x1 + st->trainst_w - 1; y2 = y1 + st->trainst_h - 1; // lowermost corner of station
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   124
	x3 = TileX(tile);            y3 = TileY(tile);            // tile we take the distance from
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   125
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   126
	// we are going the aim for the x coordinate of the closest corner
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   127
	// but if we are between those coordinates, we will aim for our own x coordinate
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   128
	if (x3 < x1)
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   129
		tx = x1;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   130
	else if (x3 > x2)
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   131
		tx = x2;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   132
	else
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   133
		tx = x3;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   134
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   135
	// same for y coordinate, see above comment
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   136
	if (y3 < y1)
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   137
		ty = y1;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   138
	else if (y3 > y2)
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   139
		ty = y2;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   140
	else
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   141
		ty = y3;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   142
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   143
	// return the tile of our target coordinates
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   144
	return TILE_XY(tx,ty);
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   145
};
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   146
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   147
/* Calcs the heuristic to the target tile (using NPFFindStationOrTileData).
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   148
 * If the target is a station, the heuristic is probably "wrong"! Normally
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   149
 * this shouldn't matter, but if it turns out to be a problem, we could use
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   150
 * the heuristic below?
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   151
 * Afterthis  will save the heuristic into NPFFoundTargetData if it is the
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   152
 * smallest until now. It will then also save
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   153
 * AyStarNode.user_data[NPF_TRACKDIR_CHOICE] in best_trackdir
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   154
 */
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   155
int32 NPFCalcTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   156
	NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   157
	NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   158
	TileIndex from = current->tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   159
	TileIndex to = fstd->dest_coords;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   160
	uint dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   161
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   162
	if (dist < ftd->best_bird_dist) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   163
		ftd->best_bird_dist = dist;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   164
		ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   165
	}
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   166
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   167
	debug("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   168
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   169
	return dist;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   170
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   171
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   172
/* Calcs the heuristic to the target station or tile. Almost the same as above
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   173
 * function, but calculates the distance to train stations with
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   174
 * CalcClosestStationTile instead. So is somewhat more correct for stations
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   175
 * (truly optimistic), but this added correctness is not really required we
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   176
 * believe (matthijs & Hackykid)
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   177
 */
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   178
int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) {
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   179
	NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   180
	NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   181
	TileIndex from = current->tile;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   182
	TileIndex to = fstd->dest_coords;
1453
a97bad7fc002 (svn r1957) Compilation fix.
pasky
parents: 1452
diff changeset
   183
	uint dist;
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   184
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   185
	// for train-stations, we are going to aim for the closest station tile
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   186
	if ((as->user_data[NPF_TYPE] == TRANSPORT_RAIL) && (fstd->station_index != -1))
1453
a97bad7fc002 (svn r1957) Compilation fix.
pasky
parents: 1452
diff changeset
   187
		to = CalcClosestStationTile(fstd->station_index, from);
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   188
1453
a97bad7fc002 (svn r1957) Compilation fix.
pasky
parents: 1452
diff changeset
   189
	dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   190
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   191
	if (dist < ftd->best_bird_dist) {
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   192
		ftd->best_bird_dist = dist;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   193
		ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE];
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   194
	}
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   195
#ifdef NPF_DEBUG
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   196
	debug("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   197
#endif
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   198
	return dist;
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   199
}
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   200
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   201
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   202
/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   203
 * get here, either getting it from the current choice or from the parent's
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   204
 * choice */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   205
void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   206
{
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   207
	if (parent->path.parent == NULL) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   208
		byte trackdir = current->direction;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   209
		/* This is a first order decision, so we'd better save the
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   210
		 * direction we chose */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   211
		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   212
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   213
		debug("Saving trackdir: %#x", trackdir);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   214
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   215
	} else {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   216
		/* We've already made the decision, so just save our parent's
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   217
		 * decision */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   218
		current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   219
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   220
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   221
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   222
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   223
/* Will return the cost of the tunnel. If it is an entry, it will return the
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   224
 * cost of that tile. If the tile is an exit, it will return the tunnel length
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   225
 * including the exit tile. Requires that this is a Tunnel tile */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   226
uint NPFTunnelCost(AyStarNode* current) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   227
	byte exitdir = _trackdir_to_exitdir[current->direction];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   228
	TileIndex tile = current->tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   229
	if ( (uint)(_map5[tile] & 3) == _reverse_dir[exitdir]) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   230
		/* We just popped out if this tunnel, since were
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   231
		 * facing the tunnel exit */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   232
		FindLengthOfTunnelResult flotr;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   233
		flotr = FindLengthOfTunnel(tile, _reverse_dir[exitdir]);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   234
		return flotr.length * NPF_TILE_LENGTH;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   235
		//TODO: Penalty for tunnels?
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   236
	} else {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   237
		/* We are entering the tunnel, the enter tile is just a
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   238
		 * straight track */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   239
		return NPF_TILE_LENGTH;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   240
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   241
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   242
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   243
uint NPFSlopeCost(AyStarNode* current) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   244
	TileIndex next = current->tile + TileOffsByDir(_trackdir_to_exitdir[current->direction]);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   245
	if (GetTileZ(next) > GetTileZ(current->tile)) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   246
		/* Slope up */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   247
		return _patches.npf_rail_slope_penalty;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   248
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   249
	return 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   250
	/* Should we give a bonus for slope down? Probably not, we
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   251
	 * could just substract that bonus from the penalty, because
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   252
	 * there is only one level of steepness... */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   253
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   254
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   255
void NPFMarkTile(TileIndex tile) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   256
	switch(GetTileType(tile)) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   257
		case MP_RAILWAY:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   258
		case MP_STREET:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   259
			/* DEBUG: mark visited tiles by mowing the grass under them
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   260
			 * ;-) */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   261
			_map2[tile] &= ~15;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   262
			MarkTileDirtyByTile(tile);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   263
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   264
		default:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   265
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   266
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   267
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   268
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   269
int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   270
	//TileIndex tile = current->tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   271
	int32 cost = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   272
	byte trackdir = current->direction;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   273
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   274
	cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   275
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   276
	/* TODO Penalties? */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   277
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   278
	return cost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   279
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   280
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   281
/* Determine the cost of this node, for road tracks */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   282
int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   283
	TileIndex tile = current->tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   284
	int32 cost = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   285
	/* Determine base length */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   286
	switch (GetTileType(tile)) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   287
		case MP_TUNNELBRIDGE:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   288
			if ((_map5[tile] & 0xF0)==0) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   289
				cost = NPFTunnelCost(current);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   290
				break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   291
			}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   292
			/* Fall through if above if is false, it is a bridge
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   293
			 * then. We treat that as ordinary rail */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   294
		case MP_STREET:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   295
			cost = NPF_TILE_LENGTH;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   296
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   297
		default:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   298
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   299
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   300
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   301
	/* Determine extra costs */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   302
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   303
	/* Check for slope */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   304
	cost += NPFSlopeCost(current);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   305
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   306
	/* Check for turns */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   307
	//TODO
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   308
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   309
#ifdef NPF_MARKROUTE
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   310
	NPFMarkTile(tile);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   311
#endif
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   312
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   313
	debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   314
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   315
	return cost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   316
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   317
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   318
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   319
/* Determine the cost of this node, for railway tracks */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   320
int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   321
	TileIndex tile = current->tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   322
	byte trackdir = current->direction;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   323
	int32 cost = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   324
	/* Determine base length */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   325
	switch (GetTileType(tile)) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   326
		case MP_TUNNELBRIDGE:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   327
			if ((_map5[tile] & 0xF0)==0) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   328
				cost = NPFTunnelCost(current);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   329
				break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   330
			}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   331
			/* Fall through if above if is false, it is a bridge
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   332
			 * then. We treat that as ordinary rail */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   333
		case MP_RAILWAY:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   334
			cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   335
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   336
		case MP_STREET: /* Railway crossing */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   337
			cost = NPF_TILE_LENGTH;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   338
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   339
		default:
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   340
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   341
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   342
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   343
	/* Determine extra costs */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   344
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   345
	/* Check for signals */
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   346
	if (IsTileType(tile, MP_RAILWAY) && (_map5[tile] & 0xC0) == 0x40) {
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   347
		/* Ordinary track with signals */
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   348
		if ((_map2[tile] & _signal_along_trackdir[trackdir]) == 0) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   349
			/* Signal facing us is red */
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   350
			if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   351
				/* Penalize the first signal we
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   352
				 * encounter, if it is red */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   353
				cost += _patches.npf_rail_firstred_penalty;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   354
			}
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   355
			/* Record the state of this signal */
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   356
			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true);
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   357
		} else {
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   358
			/* Record the state of this signal */
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   359
			NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   360
		}
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   361
		NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   362
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   363
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   364
	/* Penalise the tile if it is a target tile and the last signal was
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   365
	 * red */
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   366
	if (as->EndNodeCheck(as, current) && NPFGetFlag(current, NPF_FLAG_LAST_SIGNAL_RED))
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   367
		cost += _patches.npf_rail_lastred_penalty;
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   368
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   369
	/* Check for slope */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   370
	cost += NPFSlopeCost(current);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   371
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   372
	/* Check for turns */
1460
86d703cbdd3a (svn r1964) - Add: [NPF] Added a penalty
matthijs
parents: 1459
diff changeset
   373
	if (current->direction != parent->path.node.direction)
86d703cbdd3a (svn r1964) - Add: [NPF] Added a penalty
matthijs
parents: 1459
diff changeset
   374
		cost += _patches.npf_rail_curve_penalty;
86d703cbdd3a (svn r1964) - Add: [NPF] Added a penalty
matthijs
parents: 1459
diff changeset
   375
	//TODO, with realistic acceleration, also the amount of straight track between
86d703cbdd3a (svn r1964) - Add: [NPF] Added a penalty
matthijs
parents: 1459
diff changeset
   376
	//      curves should be taken into account, as this affects the speed limit.
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   377
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   378
	/* Check for occupied track */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   379
	//TODO
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   380
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   381
	/* Check for station tiles */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   382
	if (IsTileType(tile, MP_STATION)) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   383
		/* We give a station tile a penalty. Logically we would only
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   384
		 * want to give station tiles that are not our destination
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   385
		 * this penalty. This would discourage trains to drive through
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   386
		 * busy stations. But, we can just give any station tile a
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   387
		 * penalty, because every possible route will get this penalty
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   388
		 * exactly once, on its end tile (if it's a station) and it
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   389
		 * will therefore not make a difference. */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   390
		cost += _patches.npf_rail_station_penalty;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   391
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   392
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   393
#ifdef NPF_MARKROUTE
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   394
	NPFMarkTile(tile);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   395
#endif
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   396
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   397
	debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   398
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   399
	return cost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   400
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   401
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   402
/* Will find any depot */
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   403
int32 NPFFindDepot(AyStar* as, AyStarNode *node) {
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   404
	TileIndex tile = node->tile;
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   405
	if (IsTileDepotType(tile, as->user_data[NPF_TYPE]))
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   406
		return AYSTAR_FOUND_END_NODE;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   407
	else
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   408
		return AYSTAR_DONE;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   409
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   410
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   411
/* Will find a station identified using the NPFFindStationOrTileData */
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   412
int32 NPFFindStationOrTile(AyStar* as, AyStarNode *node) {
1464
fe5fcc14b2a2 (svn r1968) - Fix: [NPF] Mixed declarations and statements
matthijs
parents: 1463
diff changeset
   413
	NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target;
fe5fcc14b2a2 (svn r1968) - Fix: [NPF] Mixed declarations and statements
matthijs
parents: 1463
diff changeset
   414
	TileIndex tile = node->tile;
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   415
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   416
	/* See if we checked this before */
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   417
	if (NPFGetFlag(node, NPF_FLAG_TARGET_CHECKED))
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   418
		return NPFGetFlag(node, NPF_FLAG_IS_TARGET);
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   419
	/* We're gonna check this now and store the result, let's mark that */
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   420
	NPFSetFlag(node, NPF_FLAG_TARGET_CHECKED, true);
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   421
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   422
	/* If GetNeighbours said we could get here, we assume the station type
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   423
	 * is correct */
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   424
	if (
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   425
		(fstd->station_index == -1 && tile == fstd->dest_coords) || /* We've found the tile, or */
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   426
		(IsTileType(tile, MP_STATION) && _map2[tile] == fstd->station_index) /* the station */
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   427
	) {
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   428
		NPFSetFlag(node, NPF_FLAG_TARGET_CHECKED, true);
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   429
		return AYSTAR_FOUND_END_NODE;
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   430
	} else {
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   431
		NPFSetFlag(node, NPF_FLAG_TARGET_CHECKED, false);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   432
		return AYSTAR_DONE;
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   433
	}
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   434
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   435
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   436
/* To be called when current contains the (shortest route to) the target node.
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   437
 * Will fill the contents of the NPFFoundTargetData using
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   438
 * AyStarNode[NPF_TRACKDIR_CHOICE].
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   439
 */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   440
void NPFSaveTargetData(AyStar* as, OpenListNode* current) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   441
	NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   442
	ftd->best_trackdir = current->path.node.user_data[NPF_TRACKDIR_CHOICE];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   443
	ftd->best_path_dist = current->g;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   444
	ftd->best_bird_dist = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   445
	ftd->node = current->path.node;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   446
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   447
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   448
/* Will just follow the results of GetTileTrackStatus concerning where we can
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   449
 * go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   450
 * an argument to GetTileTrackStatus. Will skip tunnels, meaning that the
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   451
 * entry and exit are neighbours. Will fill
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   452
 * AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an appropriate value, and
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   453
 * copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   454
void NPFFollowTrack(AyStar* aystar, OpenListNode* current) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   455
	byte src_trackdir = current->path.node.direction;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   456
	TileIndex src_tile = current->path.node.tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   457
	byte src_exitdir = _trackdir_to_exitdir[src_trackdir];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   458
	FindLengthOfTunnelResult flotr;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   459
	TileIndex dst_tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   460
	int i = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   461
	uint trackdirs, ts;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   462
	TransportType type = aystar->user_data[NPF_TYPE];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   463
	/* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   464
	aystar->num_neighbours = 0;
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   465
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   466
	debug("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   467
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   468
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   469
	/* Find dest tile */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   470
	if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (_map5[src_tile] & 3) == src_exitdir) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   471
		/* This is a tunnel. We know this tunnel is our type,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   472
		 * otherwise we wouldn't have got here. It is also facing us,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   473
		 * so we should skip it's body */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   474
		flotr = FindLengthOfTunnel(src_tile, src_exitdir);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   475
		dst_tile = flotr.tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   476
	} else {
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   477
		if (IsTileDepotType(src_tile, type)){
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   478
			/* This is a road station or a train or road depot. We can enter and exit
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   479
			 * those from one side only. Trackdirs don't support that (yet), so we'll
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   480
			 * do this here. */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   481
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   482
			byte exitdir;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   483
			/* Find out the exit direction first */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   484
			if (IsRoadStationTile(src_tile))
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   485
				exitdir = GetRoadStationDir(src_tile);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   486
			else /* Train or road depot. Direction is stored the same for both, in map5 */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   487
				exitdir = _map5[src_tile] & 3; /* Extract the direction from the map */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   488
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   489
			/* Let's see if were headed the right way */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   490
			if (src_trackdir != _dir_to_diag_trackdir[exitdir])
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   491
				/* Not going out of the station/depot through the exit, but the back. No
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   492
				 * neighbours then. */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   493
				return;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   494
		}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   495
		/* This a normal tile, a bridge, a tunnel exit, etc. */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   496
		dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDir(_trackdir_to_exitdir[src_trackdir]));
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   497
		if (dst_tile == INVALID_TILE) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   498
			/* We reached the border of the map */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   499
			/* TODO Nicer control flow for this */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   500
			return;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   501
		}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   502
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   503
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   504
	// TODO: check correct rail type (mono, maglev, etc)
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   505
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   506
	/* Check the owner of the tile */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   507
	if (
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   508
		IsTileType(dst_tile, MP_RAILWAY) /* Rail tile */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   509
		|| IsTileDepotType(dst_tile, TRANSPORT_ROAD) /* Road depot tile */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   510
		|| IsTileType(dst_tile, MP_STATION) /* Station tile */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   511
		|| IsTileDepotType(dst_tile, TRANSPORT_WATER) /* Water depot tile */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   512
	) /* TODO: Crossings, tunnels and bridges are "public" now */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   513
		/* The above cases are "private" tiles, we need to check the owner */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   514
		if (!IsTileOwner(dst_tile, aystar->user_data[NPF_OWNER]))
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   515
			return;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   516
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   517
	/* Determine available tracks */
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   518
	if (type == TRANSPORT_ROAD && (IsRoadStationTile(dst_tile) || IsTileDepotType(dst_tile, TRANSPORT_ROAD))){
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   519
		/* Road stations and depots return 0 on GTTS, so we have to do this by hand... */
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   520
		byte exitdir;
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   521
		if (IsRoadStationTile(dst_tile))
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   522
			exitdir = GetRoadStationDir(dst_tile);
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   523
		else /* Road depot */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   524
			/* Find the trackdirs that are available for a depot with this orientation. They are in both directions */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   525
			exitdir = _map5[dst_tile] & 3; /* Extract the direction from the map */
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   526
			ts = (1 << _dir_to_diag_trackdir[exitdir])
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   527
			     | (1 << _dir_to_diag_trackdir[_reverse_dir[exitdir]]);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   528
	} else {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   529
		ts = GetTileTrackStatus(dst_tile, type);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   530
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   531
	trackdirs = ts & 0x3F3F; /* Filter out signal status and the unused bits */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   532
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   533
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   534
	debug("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirs);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   535
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   536
	/* Select only trackdirs we can reach from our current trackdir */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   537
	trackdirs &= _trackdir_reaches_trackdirs[src_trackdir];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   538
	if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   539
		trackdirs &= ~_trackdir_crosses_trackdirs[src_trackdir];
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   540
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   541
	debug("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirs);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   542
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   543
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   544
	/* Enumerate possible track */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   545
	while (trackdirs != 0) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   546
		byte dst_trackdir;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   547
		dst_trackdir =  FindFirstBit2x64(trackdirs);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   548
		trackdirs = KillFirstBit2x64(trackdirs);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   549
#ifdef NPF_DEBUG
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   550
		debug("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirs);
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   551
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   552
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   553
		/* Check for oneway signal against us */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   554
		if (IsTileType(dst_tile, MP_RAILWAY) && (_map5[dst_tile]&0xC0) == 0x40) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   555
			// the tile has a signal
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   556
			byte signal_present = _map3_lo[dst_tile];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   557
			if (!(signal_present & _signal_along_trackdir[dst_trackdir])) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   558
				// if one way signal not pointing towards us, stop going in this direction.
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   559
				if (signal_present & _signal_against_trackdir[dst_trackdir])
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   560
					break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   561
			}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   562
		}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   563
		{
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   564
			/* We've found ourselves a neighbour :-) */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   565
			AyStarNode* neighbour = &aystar->neighbours[i];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   566
			neighbour->tile = dst_tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   567
			neighbour->direction = dst_trackdir;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   568
			/* Save user data */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   569
			neighbour->user_data[NPF_NODE_FLAGS] = current->path.node.user_data[NPF_NODE_FLAGS];
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   570
			NPFFillTrackdirChoice(neighbour, current);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   571
		}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   572
		i++;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   573
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   574
	aystar->num_neighbours = i;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   575
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   576
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   577
/*
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   578
 * Plan a route to the specified target (which is checked by target_proc),
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   579
 * from start1 and if not NULL, from start2 as well. The type of transport we
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   580
 * are checking is in type.
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   581
 * When we are looking for one specific target (optionally multiple tiles), we
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   582
 * should use a good heuristic to perform aystar search. When we search for
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   583
 * multiple targets that are spread around, we should perform a breadth first
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   584
 * search by specifiying CalcZero as our heuristic.
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   585
 */
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   586
NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   587
	int r;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   588
	NPFFoundTargetData result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   589
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   590
	/* Initialize procs */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   591
	_npf_aystar.CalculateH = heuristic_proc;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   592
	_npf_aystar.EndNodeCheck = target_proc;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   593
	_npf_aystar.FoundEndNode = NPFSaveTargetData;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   594
	_npf_aystar.GetNeighbours = NPFFollowTrack;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   595
	if (type == TRANSPORT_RAIL)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   596
		_npf_aystar.CalculateG = NPFRailPathCost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   597
	else if (type == TRANSPORT_ROAD)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   598
		_npf_aystar.CalculateG = NPFRoadPathCost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   599
	else if (type == TRANSPORT_WATER)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   600
		_npf_aystar.CalculateG = NPFWaterPathCost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   601
	else
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   602
		assert(0);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   603
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   604
	/* Initialize Start Node(s) */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   605
	start1->user_data[NPF_TRACKDIR_CHOICE] = 0xff;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   606
	start1->user_data[NPF_NODE_FLAGS] = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   607
	_npf_aystar.addstart(&_npf_aystar, start1);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   608
	if (start2) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   609
		start2->user_data[NPF_TRACKDIR_CHOICE] = 0xff;
1459
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   610
		start2->user_data[NPF_NODE_FLAGS] = 0;
19333d7f99b3 (svn r1963) - Add: [NPF] Penalty for a red signal that is the last signal on the path.
matthijs
parents: 1453
diff changeset
   611
		NPFSetFlag(start2, NPF_FLAG_REVERSE, true);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   612
		_npf_aystar.addstart(&_npf_aystar, start2);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   613
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   614
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   615
	/* Initialize result */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   616
	result.best_bird_dist = (uint)-1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   617
	result.best_path_dist = (uint)-1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   618
	result.best_trackdir = 0xff;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   619
	_npf_aystar.user_path = &result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   620
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   621
	/* Initialize target */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   622
	_npf_aystar.user_target = target;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   623
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   624
	/* Initialize user_data */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   625
	_npf_aystar.user_data[NPF_TYPE] = type;
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   626
	_npf_aystar.user_data[NPF_OWNER] = owner;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   627
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   628
	/* GO! */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   629
	r = AyStarMain_Main(&_npf_aystar);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   630
	assert(r != AYSTAR_STILL_BUSY);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   631
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   632
	if (result.best_bird_dist != 0) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   633
		if (target) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   634
			DEBUG(misc, 1) ("NPF: Could not find route to 0x%x from 0x%x.", target->dest_coords, start1->tile);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   635
		} else {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   636
			/* Assumption: target == NULL, so we are looking for a depot */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   637
			DEBUG(misc, 1) ("NPF: Could not find route to a depot from 0x%x.", start1->tile);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   638
		}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   639
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   640
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   641
	return result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   642
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   643
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   644
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   645
	AyStarNode start1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   646
	AyStarNode start2;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   647
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   648
	start1.tile = tile1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   649
	start2.tile = tile2;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   650
	start1.direction = trackdir1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   651
	start2.direction = trackdir2;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   652
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   653
	return NPFRouteInternal(&start1, &start2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   654
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   655
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   656
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   657
	AyStarNode start;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   658
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   659
	assert(tile != 0);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   660
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   661
	start.tile = tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   662
	start.direction = trackdir;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   663
	/* We set this in case the target is also the start tile, we will just
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   664
	 * return a not found then */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   665
	start.user_data[NPF_TRACKDIR_CHOICE] = 0xff;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   666
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   667
	return NPFRouteInternal(&start, NULL, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   668
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   669
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   670
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   671
	AyStarNode start;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   672
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   673
	start.tile = tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   674
	start.direction = trackdir;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   675
	/* We set this in case the target is also the start tile, we will just
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   676
	 * return a not found then */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   677
	start.user_data[NPF_TRACKDIR_CHOICE] = 0xff;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   678
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   679
	/* perform a breadth first search. Target is NULL,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   680
	 * since we are just looking for any depot...*/
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   681
	return NPFRouteInternal(&start, NULL, NULL, NPFFindDepot, NPFCalcZero, type, owner);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   682
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   683
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   684
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner) {
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   685
	/* Okay, what we're gonna do. First, we look at all depots, calculate
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   686
	 * the manhatten distance to get to each depot. We then sort them by
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   687
	 * distance. We start by trying to plan a route to the closest, then
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   688
	 * the next closest, etc. We stop when the best route we have found so
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   689
	 * far, is shorter than the manhattan distance. This will obviously
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   690
	 * always find the closest depot. It will probably be most efficient
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   691
	 * for ships, since the heuristic will not be to far off then. I hope.
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   692
	 */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   693
	Queue depots;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   694
	int r;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   695
	NPFFoundTargetData best_result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   696
	NPFFoundTargetData result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   697
	NPFFindStationOrTileData target;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   698
	AyStarNode start;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   699
	Depot* current;
1313
f1013ec3d318 (svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents: 1299
diff changeset
   700
	Depot *depot;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   701
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   702
	init_InsSort(&depots);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   703
	/* Okay, let's find all depots that we can use first */
1313
f1013ec3d318 (svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents: 1299
diff changeset
   704
	FOR_ALL_DEPOTS(depot) {
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   705
		/* Check if this is really a valid depot, it is of the needed type and
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   706
		 * owner */
1338
82951b57204a (svn r1842) Fix another typo made in r1834
tron
parents: 1330
diff changeset
   707
		if (IsValidDepot(depot) && IsTileDepotType(depot->xy, type) && IsTileOwner(depot->xy, owner))
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   708
			/* If so, let's add it to the queue, sorted by distance */
1313
f1013ec3d318 (svn r1817) -Codechange: Moved depot-functions to depot.c
truelight
parents: 1299
diff changeset
   709
			depots.push(&depots, depot, DistanceManhattan(tile, depot->xy));
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   710
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   711
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   712
	/* Now, let's initialise the aystar */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   713
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   714
	/* Initialize procs */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   715
	_npf_aystar.CalculateH = NPFCalcStationOrTileHeuristic;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   716
	_npf_aystar.EndNodeCheck = NPFFindStationOrTile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   717
	_npf_aystar.FoundEndNode = NPFSaveTargetData;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   718
	_npf_aystar.GetNeighbours = NPFFollowTrack;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   719
	if (type == TRANSPORT_RAIL)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   720
		_npf_aystar.CalculateG = NPFRailPathCost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   721
	else if (type == TRANSPORT_ROAD)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   722
		_npf_aystar.CalculateG = NPFRoadPathCost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   723
	else if (type == TRANSPORT_WATER)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   724
		_npf_aystar.CalculateG = NPFWaterPathCost;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   725
	else
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   726
		assert(0);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   727
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   728
	/* Initialize target */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   729
	target.station_index = -1; /* We will initialize dest_coords inside the loop below */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   730
	_npf_aystar.user_target = &target;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   731
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   732
	/* Initialize user_data */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   733
	_npf_aystar.user_data[NPF_TYPE] = type;
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   734
	_npf_aystar.user_data[NPF_OWNER] = owner;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   735
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   736
	/* Initialize Start Node */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   737
	start.tile = tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   738
	start.direction = trackdir; /* We will initialize user_data inside the loop below */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   739
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   740
	/* Initialize Result */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   741
	_npf_aystar.user_path = &result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   742
	best_result.best_path_dist = (uint)-1;
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   743
	best_result.best_bird_dist = (uint)-1;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   744
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   745
	/* Just iterate the depots in order of increasing distance */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   746
	while ((current = depots.pop(&depots))) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   747
		/* Check to see if we already have a path shorter than this
1330
5d76a0522a11 (svn r1834) - Fix: NPF does not check the owner of its target, busses try to enter other players' depots. TODO
matthijs
parents: 1313
diff changeset
   748
		 * depot's manhattan distance. HACK: We call DistanceManhattan
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   749
		 * again, we should probably modify the queue to give us that
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   750
		 * value... */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   751
		if ( DistanceManhattan(tile, current->xy * NPF_TILE_LENGTH) > best_result.best_path_dist)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   752
			break;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   753
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   754
		/* Initialize Start Node */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   755
		/* We set this in case the target is also the start tile, we will just
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   756
		 * return a not found then */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   757
		start.user_data[NPF_TRACKDIR_CHOICE] = 0xff;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   758
		start.user_data[NPF_NODE_FLAGS] = 0;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   759
		_npf_aystar.addstart(&_npf_aystar, &start);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   760
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   761
		/* Initialize result */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   762
		result.best_bird_dist = (uint)-1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   763
		result.best_path_dist = (uint)-1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   764
		result.best_trackdir = 0xff;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   765
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   766
		/* Initialize target */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   767
		target.dest_coords = current->xy;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   768
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   769
		/* GO! */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   770
		r = AyStarMain_Main(&_npf_aystar);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   771
		assert(r != AYSTAR_STILL_BUSY);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   772
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   773
		/* This depot is closer */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   774
		if (result.best_path_dist < best_result.best_path_dist)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   775
			best_result = result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   776
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   777
	if (result.best_bird_dist != 0) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   778
		DEBUG(misc, 1) ("NPF: Could not find route to any depot from 0x%x.", tile);
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   779
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   780
	return best_result;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   781
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   782
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   783
void InitializeNPF(void)
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   784
{
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   785
	init_AyStar(&_npf_aystar, NTPHash, 1024);
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   786
	_npf_aystar.loops_per_tick = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   787
	_npf_aystar.max_path_cost = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   788
	_npf_aystar.max_search_nodes = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   789
#if 0
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   790
	init_AyStar(&_train_find_station, NTPHash, 1024);
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   791
	init_AyStar(&_train_find_depot, NTPHash, 1024);
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   792
	init_AyStar(&_road_find_station, NTPHash, 1024);
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   793
	init_AyStar(&_road_find_depot, NTPHash, 1024);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   794
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   795
	_train_find_station.loops_per_tick = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   796
	_train_find_depot.loops_per_tick = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   797
	_road_find_station.loops_per_tick = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   798
	_road_find_depot.loops_per_tick = 0;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   799
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   800
	_train_find_station.max_path_cost = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   801
	_train_find_depot.max_path_cost = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   802
	_road_find_station.max_path_cost = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   803
	_road_find_depot.max_path_cost = 0;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   804
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   805
	_train_find_station.max_search_nodes = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   806
	_train_find_depot.max_search_nodes = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   807
	_road_find_station.max_search_nodes = 0;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   808
	_road_find_depot.max_search_nodes = 0;
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   809
1463
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   810
	_train_find_station.CalculateG = NPFRailPathCost;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   811
	_train_find_depot.CalculateG = NPFRailPathCost;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   812
	_road_find_station.CalculateG = NPFRoadPathCost;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   813
	_road_find_depot.CalculateG = NPFRoadPathCost;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   814
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   815
	_train_find_station.CalculateH = NPFCalcStationHeuristic;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   816
	_train_find_depot.CalculateH = NPFCalcStationHeuristic;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   817
	_road_find_station.CalculateH = NPFCalcStationHeuristic;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   818
	_road_find_depot.CalculateH = NPFCalcStationHeuristic;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   819
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   820
	_train_find_station.EndNodeCheck = NPFFindStationOrTile;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   821
	_train_find_depot.EndNodeCheck = NPFFindStationOrTile;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   822
	_road_find_station.EndNodeCheck = NPFFindStationOrTile;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   823
	_road_find_depot.EndNodeCheck = NPFFindStationOrTile;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   824
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   825
	_train_find_station.FoundEndNode = NPFSaveTargetData;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   826
	_train_find_depot.FoundEndNode = NPFSaveTargetData;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   827
	_road_find_station.FoundEndNode = NPFSaveTargetData;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   828
	_road_find_depot.FoundEndNode = NPFSaveTargetData;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   829
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   830
	_train_find_station.GetNeighbours = NPFFollowTrack;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   831
	_train_find_depot.GetNeighbours = NPFFollowTrack;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   832
	_road_find_station.GetNeighbours = NPFFollowTrack;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   833
	_road_find_depot.GetNeighbours = NPFFollowTrack;
85a05f2da980 (svn r1967) Codechange: A mix of mostly indentation-related tidyups.
pasky
parents: 1460
diff changeset
   834
#endif
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   835
}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   836
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   837
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   838
	/* Ships don't really reach their stations, but the tile in front. So don't
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   839
	 * save the station id for ships. For roadvehs we don't store it either,
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   840
	 * because multistop depends on vehicles actually reaching the exact
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   841
	 * dest_tile, not just any stop of that station.
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   842
	 * So only for train orders to stations we fill fstd->station_index, for all
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   843
	 * others only dest_coords */
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   844
	if ((v->current_order.type) == OT_GOTO_STATION && v->type == VEH_Train) {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   845
		fstd->station_index = v->current_order.station;
1452
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   846
		/* Let's take the closest tile of the station as our target for trains */
a978fdcbca3e (svn r1956) -Fix: [NPF] New target tile for heuristic should perform better with larger stations (HackyKid)
matthijs
parents: 1339
diff changeset
   847
		fstd->dest_coords = CalcClosestStationTile(v->current_order.station, v->tile);
1247
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   848
	} else {
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   849
		fstd->dest_coords = v->dest_tile;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   850
		fstd->station_index = -1;
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   851
	}
3851739bfd09 (svn r1751) - Feature: New PathFinder (NPF).
matthijs
parents:
diff changeset
   852
}