1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
/* $Id$ */
/*
* This file is part of OpenTTD.
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* @file aystar.h
* This file has the header for AyStar
* AyStar is a fast pathfinding routine and is used for things like
* AI_pathfinding and Train_pathfinding.
* For more information about AyStar (A* Algorithm), you can look at
* http://en.wikipedia.org/wiki/A-star_search_algorithm
*/
#ifndef AYSTAR_H
#define AYSTAR_H
#include "queue.h"
#include "../../tile_type.h"
#include "../../track_type.h"
//#define AYSTAR_DEBUG
enum AystarStatus {
AYSTAR_FOUND_END_NODE,
AYSTAR_EMPTY_OPENLIST,
AYSTAR_STILL_BUSY,
AYSTAR_NO_PATH,
AYSTAR_LIMIT_REACHED,
AYSTAR_DONE
};
static const int AYSTAR_INVALID_NODE = -1;
struct AyStarNode {
TileIndex tile;
Trackdir direction;
uint user_data[2];
};
/* The resulting path has nodes looking like this. */
struct PathNode {
AyStarNode node;
/* The parent of this item */
PathNode *parent;
};
/* For internal use only
* We do not save the h-value, because it is only needed to calculate the f-value.
* h-value should _always_ be the distance left to the end-tile. */
struct OpenListNode {
int g;
PathNode path;
};
struct AyStar;
/*
* This function is called to check if the end-tile is found
* return values can be:
* AYSTAR_FOUND_END_NODE : indicates this is the end tile
* AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)
*/
/*
* The 2nd parameter should be OpenListNode, and NOT AyStarNode. AyStarNode is
* part of OpenListNode and so it could be accessed without any problems.
* The good part about OpenListNode is, and how AIs use it, that you can
* access the parent of the current node, and so check if you, for example
* don't try to enter the file tile with a 90-degree curve. So please, leave
* this an OpenListNode, it works just fine -- TrueLight
*/
typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current);
/*
* This function is called to calculate the G-value for AyStar Algorithm.
* return values can be:
* AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
* Any value >= 0 : the g-value for this tile
*/
typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
/*
* This function is called to calculate the H-value for AyStar Algorithm.
* Mostly, this must result the distance (Manhattan way) between the
* current point and the end point
* return values can be:
* Any value >= 0 : the h-value for this tile
*/
typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
/*
* This function request the tiles around the current tile and put them in tiles_around
* tiles_around is never resetted, so if you are not using directions, just leave it alone.
* Warning: never add more tiles_around than memory allocated for it.
*/
typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
/*
* If the End Node is found, this function is called.
* It can do, for example, calculate the route and put that in an array
*/
typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
struct AyStar {
/* These fields should be filled before initting the AyStar, but not changed
* afterwards (except for user_data and user_path)! (free and init again to change them) */
/* These should point to the application specific routines that do the
* actual work */
AyStar_CalculateG *CalculateG;
AyStar_CalculateH *CalculateH;
AyStar_GetNeighbours *GetNeighbours;
AyStar_EndNodeCheck *EndNodeCheck;
AyStar_FoundEndNode *FoundEndNode;
/* These are completely untouched by AyStar, they can be accesed by
* the application specific routines to input and output data.
* user_path should typically contain data about the resulting path
* afterwards, user_target should typically contain information about
* what where looking for, and user_data can contain just about
* everything */
void *user_path;
void *user_target;
uint user_data[10];
/* How many loops are there called before Main() gives
* control back to the caller. 0 = until done */
byte loops_per_tick;
/* If the g-value goes over this number, it stops searching
* 0 = infinite */
uint max_path_cost;
/* The maximum amount of nodes that will be expanded, 0 = infinite */
uint max_search_nodes;
/* These should be filled with the neighbours of a tile by
* GetNeighbours */
AyStarNode neighbours[12];
byte num_neighbours;
void Init(Hash_HashProc hash, uint num_buckets);
/* These will contain the methods for manipulating the AyStar. Only
* Main() should be called externally */
void AddStartNode(AyStarNode *start_node, uint g);
int Main();
int Loop();
void Free();
void Clear();
void CheckTile(AyStarNode *current, OpenListNode *parent);
/* These will contain the open and closed lists */
/* The actual closed list */
Hash ClosedListHash;
/* The open queue */
BinaryHeap OpenListQueue;
/* An extra hash to speed up the process of looking up an element in
* the open list */
Hash OpenListHash;
};
#endif /* AYSTAR_H */
|
