OpenTTD Source  1.11.2
aystar.cpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * 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.
4  * 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.
5  * 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/>.
6  */
7 
16 /*
17  * Friendly reminder:
18  * Call (AyStar).free() when you are done with Aystar. It reserves a lot of memory
19  * And when not free'd, it can cause system-crashes.
20  * Also remember that when you stop an algorithm before it is finished, your
21  * should call clear() yourself!
22  */
23 
24 #include "../../stdafx.h"
25 #include "../../core/alloc_func.hpp"
26 #include "aystar.h"
27 
28 #include "../../safeguards.h"
29 
36 {
37  return (PathNode*)this->closedlist_hash.Get(node->tile, node->direction);
38 }
39 
46 {
47  /* Add a node to the ClosedList */
48  PathNode *new_node = MallocT<PathNode>(1);
49  *new_node = *node;
50  this->closedlist_hash.Set(node->node.tile, node->node.direction, new_node);
51 }
52 
59 {
60  return (OpenListNode*)this->openlist_hash.Get(node->tile, node->direction);
61 }
62 
69 {
70  /* Return the item the Queue returns.. the best next OpenList item. */
72  if (res != nullptr) {
73  this->openlist_hash.DeleteValue(res->path.node.tile, res->path.node.direction);
74  }
75 
76  return res;
77 }
78 
83 void AyStar::OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
84 {
85  /* Add a new Node to the OpenList */
86  OpenListNode *new_node = MallocT<OpenListNode>(1);
87  new_node->g = g;
88  new_node->path.parent = parent;
89  new_node->path.node = *node;
90  this->openlist_hash.Set(node->tile, node->direction, new_node);
91 
92  /* Add it to the queue */
93  this->openlist_queue.Push(new_node, f);
94 }
95 
99 void AyStar::CheckTile(AyStarNode *current, OpenListNode *parent)
100 {
101  int new_f, new_g, new_h;
102  PathNode *closedlist_parent;
103  OpenListNode *check;
104 
105  /* Check the new node against the ClosedList */
106  if (this->ClosedListIsInList(current) != nullptr) return;
107 
108  /* Calculate the G-value for this node */
109  new_g = this->CalculateG(this, current, parent);
110  /* If the value was INVALID_NODE, we don't do anything with this node */
111  if (new_g == AYSTAR_INVALID_NODE) return;
112 
113  /* There should not be given any other error-code.. */
114  assert(new_g >= 0);
115  /* Add the parent g-value to the new g-value */
116  new_g += parent->g;
117  if (this->max_path_cost != 0 && (uint)new_g > this->max_path_cost) return;
118 
119  /* Calculate the h-value */
120  new_h = this->CalculateH(this, current, parent);
121  /* There should not be given any error-code.. */
122  assert(new_h >= 0);
123 
124  /* The f-value if g + h */
125  new_f = new_g + new_h;
126 
127  /* Get the pointer to the parent in the ClosedList (the current one is to a copy of the one in the OpenList) */
128  closedlist_parent = this->ClosedListIsInList(&parent->path.node);
129 
130  /* Check if this item is already in the OpenList */
131  check = this->OpenListIsInList(current);
132  if (check != nullptr) {
133  uint i;
134  /* Yes, check if this g value is lower.. */
135  if (new_g > check->g) return;
136  this->openlist_queue.Delete(check, 0);
137  /* It is lower, so change it to this item */
138  check->g = new_g;
139  check->path.parent = closedlist_parent;
140  /* Copy user data, will probably have changed */
141  for (i = 0; i < lengthof(current->user_data); i++) {
142  check->path.node.user_data[i] = current->user_data[i];
143  }
144  /* Re-add it in the openlist_queue. */
145  this->openlist_queue.Push(check, new_f);
146  } else {
147  /* A new node, add him to the OpenList */
148  this->OpenListAdd(closedlist_parent, current, new_f, new_g);
149  }
150 }
151 
162 {
163  int i;
164 
165  /* Get the best node from OpenList */
166  OpenListNode *current = this->OpenListPop();
167  /* If empty, drop an error */
168  if (current == nullptr) return AYSTAR_EMPTY_OPENLIST;
169 
170  /* Check for end node and if found, return that code */
171  if (this->EndNodeCheck(this, current) == AYSTAR_FOUND_END_NODE && !CheckIgnoreFirstTile(&current->path)) {
172  if (this->FoundEndNode != nullptr) {
173  this->FoundEndNode(this, current);
174  }
175  free(current);
176  return AYSTAR_FOUND_END_NODE;
177  }
178 
179  /* Add the node to the ClosedList */
180  this->ClosedListAdd(&current->path);
181 
182  /* Load the neighbours */
183  this->GetNeighbours(this, current);
184 
185  /* Go through all neighbours */
186  for (i = 0; i < this->num_neighbours; i++) {
187  /* Check and add them to the OpenList if needed */
188  this->CheckTile(&this->neighbours[i], current);
189  }
190 
191  /* Free the node */
192  free(current);
193 
194  if (this->max_search_nodes != 0 && this->closedlist_hash.GetSize() >= this->max_search_nodes) {
195  /* We've expanded enough nodes */
196  return AYSTAR_LIMIT_REACHED;
197  } else {
198  /* Return that we are still busy */
199  return AYSTAR_STILL_BUSY;
200  }
201 }
202 
207 {
208  this->openlist_queue.Free(false);
209  /* 2nd argument above is false, below is true, to free the values only
210  * once */
211  this->openlist_hash.Delete(true);
212  this->closedlist_hash.Delete(true);
213 #ifdef AYSTAR_DEBUG
214  printf("[AyStar] Memory free'd\n");
215 #endif
216 }
217 
223 {
224  /* Clean the Queue, but not the elements within. That will be done by
225  * the hash. */
226  this->openlist_queue.Clear(false);
227  /* Clean the hashes */
228  this->openlist_hash.Clear(true);
229  this->closedlist_hash.Clear(true);
230 
231 #ifdef AYSTAR_DEBUG
232  printf("[AyStar] Cleared AyStar\n");
233 #endif
234 }
235 
246 {
247  int r, i = 0;
248  /* Loop through the OpenList
249  * Quit if result is no AYSTAR_STILL_BUSY or is more than loops_per_tick */
250  while ((r = this->Loop()) == AYSTAR_STILL_BUSY && (this->loops_per_tick == 0 || ++i < this->loops_per_tick)) { }
251 #ifdef AYSTAR_DEBUG
252  switch (r) {
253  case AYSTAR_FOUND_END_NODE: printf("[AyStar] Found path!\n"); break;
254  case AYSTAR_EMPTY_OPENLIST: printf("[AyStar] OpenList run dry, no path found\n"); break;
255  case AYSTAR_LIMIT_REACHED: printf("[AyStar] Exceeded search_nodes, no path found\n"); break;
256  default: break;
257  }
258 #endif
259  if (r != AYSTAR_STILL_BUSY) {
260  /* We're done, clean up */
261  this->Clear();
262  }
263 
264  switch (r) {
268  default: return AYSTAR_STILL_BUSY;
269  }
270 }
271 
280 void AyStar::AddStartNode(AyStarNode *start_node, uint g)
281 {
282 #ifdef AYSTAR_DEBUG
283  printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n",
284  TileX(start_node->tile), TileY(start_node->tile), start_node->direction);
285 #endif
286  this->OpenListAdd(nullptr, start_node, 0, g);
287 }
288 
293 void AyStar::Init(Hash_HashProc hash, uint num_buckets)
294 {
295  /* Allocated the Hash for the OpenList and ClosedList */
296  this->openlist_hash.Init(hash, num_buckets);
297  this->closedlist_hash.Init(hash, num_buckets);
298 
299  /* Set up our sorting queue
300  * BinaryHeap allocates a block of 1024 nodes
301  * When that one gets full it reserves another one, till this number
302  * That is why it can stay this high */
303  this->openlist_queue.Init(102400);
304 }
AyStar::openlist_queue
BinaryHeap openlist_queue
The open queue.
Definition: aystar.h:160
AYSTAR_LIMIT_REACHED
@ AYSTAR_LIMIT_REACHED
The AyStar::max_search_nodes limit has been reached, aborting search.
Definition: aystar.h:31
AyStar::closedlist_hash
Hash closedlist_hash
The actual closed list.
Definition: aystar.h:159
BinaryHeap::Clear
void Clear(bool free_values)
Clears the queue, by removing all values from it.
Definition: queue.cpp:31
AYSTAR_EMPTY_OPENLIST
@ AYSTAR_EMPTY_OPENLIST
All items are tested, and no path has been found.
Definition: aystar.h:28
Hash::Delete
void Delete(bool free_values)
Deletes the hash and cleans up.
Definition: queue.cpp:253
AyStar::ClosedListIsInList
PathNode * ClosedListIsInList(const AyStarNode *node)
This looks in the hash whether a node exists in the closed list.
Definition: aystar.cpp:35
BinaryHeap::Delete
bool Delete(void *item, int priority)
Deletes the item from the queue.
Definition: queue.cpp:133
TileY
static uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:215
AyStar::Main
int Main()
This is the function you call to run AyStar.
Definition: aystar.cpp:245
AyStar::OpenListPop
OpenListNode * OpenListPop()
Gets the best node from the open list.
Definition: aystar.cpp:68
TileX
static uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:205
AyStar::Init
void Init(Hash_HashProc hash, uint num_buckets)
Initialize an AyStar.
Definition: aystar.cpp:293
AYSTAR_NO_PATH
@ AYSTAR_NO_PATH
No path to the goal was found.
Definition: aystar.h:30
AyStar::ClosedListAdd
void ClosedListAdd(const PathNode *node)
This adds a node to the closed list.
Definition: aystar.cpp:45
AyStar::Free
void Free()
This function frees the memory it allocated.
Definition: aystar.cpp:206
AyStar::openlist_hash
Hash openlist_hash
An extra hash to speed up the process of looking up an element in the open list.
Definition: aystar.h:161
PathNode
A path of nodes.
Definition: aystar.h:45
Hash::GetSize
uint GetSize() const
Gets the current size of the hash.
Definition: queue.h:97
Hash::Init
void Init(Hash_HashProc *hash, uint num_buckets)
Builds a new hash in an existing struct.
Definition: queue.cpp:232
AyStar::loops_per_tick
byte loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done.
Definition: aystar.h:138
Hash::Set
void * Set(uint key1, uint key2, void *value)
Sets the value associated with the given key pair to the given value.
Definition: queue.cpp:452
Hash::DeleteValue
void * DeleteValue(uint key1, uint key2)
Deletes the value with the specified key pair from the hash and returns that value.
Definition: queue.cpp:409
AYSTAR_STILL_BUSY
@ AYSTAR_STILL_BUSY
Some checking was done, but no path found yet, and there are still items left to try.
Definition: aystar.h:29
AyStar::OpenListIsInList
OpenListNode * OpenListIsInList(const AyStarNode *node)
Check whether a node is in the open list.
Definition: aystar.cpp:58
AyStarNode
Node in the search.
Definition: aystar.h:38
OpenListNode
Internal node.
Definition: aystar.h:55
AyStar::Clear
void Clear()
This function make the memory go back to zero.
Definition: aystar.cpp:222
Hash::Get
void * Get(uint key1, uint key2) const
Gets the value associated with the given key pair, or nullptr when it is not present.
Definition: queue.cpp:487
AYSTAR_FOUND_END_NODE
@ AYSTAR_FOUND_END_NODE
An end node was found.
Definition: aystar.h:27
AyStar::Loop
int Loop()
This function is the core of AyStar.
Definition: aystar.cpp:161
PathNode::parent
PathNode * parent
The parent of this item.
Definition: aystar.h:47
AyStar::OpenListAdd
void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
Adds a node to the open list.
Definition: aystar.cpp:83
AYSTAR_INVALID_NODE
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
Definition: aystar.h:35
BinaryHeap::Pop
void * Pop()
Pops the first element from the queue.
Definition: queue.cpp:192
lengthof
#define lengthof(x)
Return the length of an fixed size array.
Definition: stdafx.h:369
AyStar::max_path_cost
uint max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
Definition: aystar.h:139
BinaryHeap::Free
void Free(bool free_values)
Frees the queue, by reclaiming all memory allocated by it.
Definition: queue.cpp:68
BinaryHeap::Push
bool Push(void *item, int priority)
Pushes an element into the queue, at the appropriate place for the queue.
Definition: queue.cpp:84
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:456
AyStar::AddStartNode
void AddStartNode(AyStarNode *start_node, uint g)
Adds a node from where to start an algorithm.
Definition: aystar.cpp:280
aystar.h
BinaryHeap::Init
void Init(uint max_size)
Initializes a binary heap and allocates internal memory for maximum of max_size elements.
Definition: queue.cpp:210
Hash::Clear
void Clear(bool free_values)
Cleans the hash, but keeps the memory allocated.
Definition: queue.cpp:335
Hash_HashProc
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
Definition: queue.h:70
AyStar::max_search_nodes
uint max_search_nodes
The maximum number of nodes that will be expanded, 0 = infinite.
Definition: aystar.h:140
AyStar::CheckTile
void CheckTile(AyStarNode *current, OpenListNode *parent)
Checks one tile and calculate its f-value.
Definition: aystar.cpp:99