author | rubidium |
Sun, 25 May 2008 19:17:03 +0000 | |
changeset 9354 | 845e07db4549 |
parent 9111 | 48ce04029fe4 |
permissions | -rw-r--r-- |
2186 | 1 |
/* $Id$ */ |
2 |
||
9111
48ce04029fe4
(svn r12971) -Documentation: add @file in files that missed them and add something more than whitespace as description of files that don't have a description.
rubidium
parents:
8130
diff
changeset
|
3 |
/** @file aystar.cpp Implementation of A*. */ |
6117
6507b2a7e71d
(svn r8853) -Cleanup: doxygen changes. Correct forgotten c files to cpp files with the @file tag as well as a few general comments style
belugas
parents:
5609
diff
changeset
|
4 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
5 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
6 |
* This file has the core function for AyStar |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
7 |
* AyStar is a fast pathfinding routine and is used for things like |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
8 |
* AI_pathfinding and Train_pathfinding. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
9 |
* For more information about AyStar (A* Algorithm), you can look at |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
10 |
* http://en.wikipedia.org/wiki/A-star_search_algorithm |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
11 |
*/ |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
12 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
13 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
14 |
* Friendly reminder: |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
15 |
* Call (AyStar).free() when you are done with Aystar. It reserves a lot of memory |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
16 |
* And when not free'd, it can cause system-crashes. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
17 |
* Also remember that when you stop an algorithm before it is finished, your |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
18 |
* should call clear() yourself! |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
19 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
20 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
21 |
#include "stdafx.h" |
1891
862800791170
(svn r2397) - CodeChange: rename all "ttd" files to "openttd" files.
Darkvater
parents:
1777
diff
changeset
|
22 |
#include "openttd.h" |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
23 |
#include "aystar.h" |
8130
d2eb7d04f6e1
(svn r11691) -Codechange: move+rename helpers.hpp and only include it when it is really needed.
rubidium
parents:
6120
diff
changeset
|
24 |
#include "core/alloc_func.hpp" |
3900
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
2916
diff
changeset
|
25 |
|
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
2916
diff
changeset
|
26 |
int _aystar_stats_open_size; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
2916
diff
changeset
|
27 |
int _aystar_stats_closed_size; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
2916
diff
changeset
|
28 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
29 |
// This looks in the Hash if a node exists in ClosedList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
30 |
// If so, it returns the PathNode, else NULL |
4171 | 31 |
static PathNode* AyStarMain_ClosedList_IsInList(AyStar *aystar, const AyStarNode *node) |
1095 | 32 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
33 |
return (PathNode*)Hash_Get(&aystar->ClosedListHash, node->tile, node->direction); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
34 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
35 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
36 |
// This adds a node to the ClosedList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
37 |
// It makes a copy of the data |
4171 | 38 |
static void AyStarMain_ClosedList_Add(AyStar *aystar, const PathNode *node) |
1095 | 39 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
40 |
// Add a node to the ClosedList |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
41 |
PathNode *new_node = MallocT<PathNode>(1); |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
42 |
*new_node = *node; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
43 |
Hash_Set(&aystar->ClosedListHash, node->node.tile, node->node.direction, new_node); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
44 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
45 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
46 |
// Checks if a node is in the OpenList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
47 |
// If so, it returns the OpenListNode, else NULL |
4171 | 48 |
static OpenListNode *AyStarMain_OpenList_IsInList(AyStar *aystar, const AyStarNode *node) |
1095 | 49 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
50 |
return (OpenListNode*)Hash_Get(&aystar->OpenListHash, node->tile, node->direction); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
51 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
52 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
53 |
// Gets the best node from OpenList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
54 |
// returns the best node, or NULL of none is found |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
55 |
// Also it deletes the node from the OpenList |
1095 | 56 |
static OpenListNode *AyStarMain_OpenList_Pop(AyStar *aystar) |
57 |
{ |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
58 |
// Return the item the Queue returns.. the best next OpenList item. |
4171 | 59 |
OpenListNode *res = (OpenListNode*)aystar->OpenListQueue.pop(&aystar->OpenListQueue); |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
60 |
if (res != NULL) { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
61 |
Hash_Delete(&aystar->OpenListHash, res->path.node.tile, res->path.node.direction); |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
62 |
} |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
63 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
64 |
return res; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
65 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
66 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
67 |
// Adds a node to the OpenList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
68 |
// It makes a copy of node, and puts the pointer of parent in the struct |
4171 | 69 |
static void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, const AyStarNode *node, int f, int g) |
1095 | 70 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
71 |
// Add a new Node to the OpenList |
5609
dc6a58930ba4
(svn r8066) - Codechange: MallocT(), CallocT(), ReallocT() now return the pointer to allocated memory instead of modifying the pointer given as parameter
KUDr
parents:
5587
diff
changeset
|
72 |
OpenListNode *new_node = MallocT<OpenListNode>(1); |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
73 |
new_node->g = g; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
74 |
new_node->path.parent = parent; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
75 |
new_node->path.node = *node; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
76 |
Hash_Set(&aystar->OpenListHash, node->tile, node->direction, new_node); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
77 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
78 |
// Add it to the queue |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
79 |
aystar->OpenListQueue.push(&aystar->OpenListQueue, new_node, f); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
80 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
81 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
82 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
83 |
* Checks one tile and calculate his f-value |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
84 |
* return values: |
4434
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
85 |
* AYSTAR_DONE : indicates we are done |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
86 |
*/ |
4171 | 87 |
int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent) |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
88 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
89 |
int new_f, new_g, new_h; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
90 |
PathNode *closedlist_parent; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
91 |
OpenListNode *check; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
92 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
93 |
// Check the new node against the ClosedList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
94 |
if (AyStarMain_ClosedList_IsInList(aystar, current) != NULL) return AYSTAR_DONE; |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
95 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
96 |
// Calculate the G-value for this node |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
97 |
new_g = aystar->CalculateG(aystar, current, parent); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
98 |
// If the value was INVALID_NODE, we don't do anything with this node |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
99 |
if (new_g == AYSTAR_INVALID_NODE) return AYSTAR_DONE; |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
100 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
101 |
// There should not be given any other error-code.. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
102 |
assert(new_g >= 0); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
103 |
// Add the parent g-value to the new g-value |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
104 |
new_g += parent->g; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
105 |
if (aystar->max_path_cost != 0 && (uint)new_g > aystar->max_path_cost) return AYSTAR_DONE; |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
106 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
107 |
// Calculate the h-value |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
108 |
new_h = aystar->CalculateH(aystar, current, parent); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
109 |
// There should not be given any error-code.. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
110 |
assert(new_h >= 0); |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
111 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
112 |
// The f-value if g + h |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
113 |
new_f = new_g + new_h; |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
114 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
115 |
// Get the pointer to the parent in the ClosedList (the currentone is to a copy of the one in the OpenList) |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
116 |
closedlist_parent = AyStarMain_ClosedList_IsInList(aystar, &parent->path.node); |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
117 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
118 |
// Check if this item is already in the OpenList |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
119 |
check = AyStarMain_OpenList_IsInList(aystar, current); |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
120 |
if (check != NULL) { |
959
e6a3bbda610f
(svn r1451) Fix some of the signed/unsigned comparison warnings
tron
parents:
926
diff
changeset
|
121 |
uint i; |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
122 |
// Yes, check if this g value is lower.. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
123 |
if (new_g > check->g) return AYSTAR_DONE; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
124 |
aystar->OpenListQueue.del(&aystar->OpenListQueue, check, 0); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
125 |
// It is lower, so change it to this item |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
126 |
check->g = new_g; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
127 |
check->path.parent = closedlist_parent; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
128 |
/* Copy user data, will probably have changed */ |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
129 |
for (i = 0; i < lengthof(current->user_data); i++) { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
130 |
check->path.node.user_data[i] = current->user_data[i]; |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
131 |
} |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
132 |
// Readd him in the OpenListQueue |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
133 |
aystar->OpenListQueue.push(&aystar->OpenListQueue, check, new_f); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
134 |
} else { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
135 |
// A new node, add him to the OpenList |
1777
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1617
diff
changeset
|
136 |
AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g); |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
137 |
} |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
138 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
139 |
return AYSTAR_DONE; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
140 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
141 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
142 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
143 |
* This function is the core of AyStar. It handles one item and checks |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
144 |
* his neighbour items. If they are valid, they are added to be checked too. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
145 |
* return values: |
4434
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
146 |
* AYSTAR_EMPTY_OPENLIST : indicates all items are tested, and no path |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
147 |
* has been found. |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
148 |
* AYSTAR_LIMIT_REACHED : Indicates that the max_nodes limit has been |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
149 |
* reached. |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
150 |
* AYSTAR_FOUND_END_NODE : indicates we found the end. Path_found now is true, and in path is the path found. |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
151 |
* AYSTAR_STILL_BUSY : indicates we have done this tile, did not found the path yet, and have items left to try. |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
152 |
*/ |
4171 | 153 |
int AyStarMain_Loop(AyStar *aystar) |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
154 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
155 |
int i, r; |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
156 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
157 |
// Get the best node from OpenList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
158 |
OpenListNode *current = AyStarMain_OpenList_Pop(aystar); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
159 |
// If empty, drop an error |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
160 |
if (current == NULL) return AYSTAR_EMPTY_OPENLIST; |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
161 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
162 |
// Check for end node and if found, return that code |
1617
c3d3caad6d1e
(svn r2121) -Fix: changed the 2nd param of AyStar_EndNodeCheck back to what it should be
truelight
parents:
1459
diff
changeset
|
163 |
if (aystar->EndNodeCheck(aystar, current) == AYSTAR_FOUND_END_NODE) { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
164 |
if (aystar->FoundEndNode != NULL) |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
165 |
aystar->FoundEndNode(aystar, current); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
166 |
free(current); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
167 |
return AYSTAR_FOUND_END_NODE; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
168 |
} |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
169 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
170 |
// Add the node to the ClosedList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
171 |
AyStarMain_ClosedList_Add(aystar, ¤t->path); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
172 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
173 |
// Load the neighbours |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
174 |
aystar->GetNeighbours(aystar, current); |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
175 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
176 |
// Go through all neighbours |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
177 |
for (i = 0; i < aystar->num_neighbours; i++) { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
178 |
// Check and add them to the OpenList if needed |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
179 |
r = aystar->checktile(aystar, &aystar->neighbours[i], current); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
180 |
} |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
181 |
|
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
182 |
// Free the node |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
183 |
free(current); |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
184 |
|
3949 | 185 |
if (aystar->max_search_nodes != 0 && Hash_Size(&aystar->ClosedListHash) >= aystar->max_search_nodes) { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
186 |
/* We've expanded enough nodes */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
187 |
return AYSTAR_LIMIT_REACHED; |
3949 | 188 |
} else { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
189 |
// Return that we are still busy |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
190 |
return AYSTAR_STILL_BUSY; |
3949 | 191 |
} |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
192 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
193 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
194 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
195 |
* This function frees the memory it allocated |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
196 |
*/ |
4171 | 197 |
void AyStarMain_Free(AyStar *aystar) |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
198 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
199 |
aystar->OpenListQueue.free(&aystar->OpenListQueue, false); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
200 |
/* 2nd argument above is false, below is true, to free the values only |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
201 |
* once */ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
202 |
delete_Hash(&aystar->OpenListHash, true); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
203 |
delete_Hash(&aystar->ClosedListHash, true); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
204 |
#ifdef AYSTAR_DEBUG |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
205 |
printf("[AyStar] Memory free'd\n"); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
206 |
#endif |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
207 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
208 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
209 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
210 |
* This function make the memory go back to zero |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
211 |
* This function should be called when you are using the same instance again. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
212 |
*/ |
4171 | 213 |
void AyStarMain_Clear(AyStar *aystar) |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
214 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
215 |
// Clean the Queue, but not the elements within. That will be done by |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
216 |
// the hash. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
217 |
aystar->OpenListQueue.clear(&aystar->OpenListQueue, false); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
218 |
// Clean the hashes |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
219 |
clear_Hash(&aystar->OpenListHash, true); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
220 |
clear_Hash(&aystar->ClosedListHash, true); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
221 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
222 |
#ifdef AYSTAR_DEBUG |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
223 |
printf("[AyStar] Cleared AyStar\n"); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
224 |
#endif |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
225 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
226 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
227 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
228 |
* This is the function you call to run AyStar. |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
229 |
* return values: |
4434
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
230 |
* AYSTAR_FOUND_END_NODE : indicates we found an end node. |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
231 |
* AYSTAR_NO_PATH : indicates that there was no path found. |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
232 |
* AYSTAR_STILL_BUSY : indicates we have done some checked, that we did not found the path yet, and that we still have items left to try. |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
233 |
* When the algorithm is done (when the return value is not AYSTAR_STILL_BUSY) |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
234 |
* aystar->clear() is called. Note that when you stop the algorithm halfway, |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
235 |
* you should still call clear() yourself! |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
236 |
*/ |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
237 |
int AyStarMain_Main(AyStar *aystar) { |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
238 |
int r, i = 0; |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
239 |
// Loop through the OpenList |
826 | 240 |
// Quit if result is no AYSTAR_STILL_BUSY or is more than loops_per_tick |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
241 |
while ((r = aystar->loop(aystar)) == AYSTAR_STILL_BUSY && (aystar->loops_per_tick == 0 || ++i < aystar->loops_per_tick)) { } |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
242 |
#ifdef AYSTAR_DEBUG |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
243 |
switch (r) { |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
244 |
case AYSTAR_FOUND_END_NODE: printf("[AyStar] Found path!\n"); break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
245 |
case AYSTAR_EMPTY_OPENLIST: printf("[AyStar] OpenList run dry, no path found\n"); break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
246 |
case AYSTAR_LIMIT_REACHED: printf("[AyStar] Exceeded search_nodes, no path found\n"); break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
247 |
default: break; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
248 |
} |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
249 |
#endif |
3944
7b1b00c8541d
(svn r5090) -Fix: [NPF] broken by me - r4366 (thanks Tron)
KUDr
parents:
3900
diff
changeset
|
250 |
if (r != AYSTAR_STILL_BUSY) { |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
251 |
/* We're done, clean up */ |
3900
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
2916
diff
changeset
|
252 |
_aystar_stats_open_size = aystar->OpenListHash.size; |
2c84ed52709d
(svn r4987) Feature: Merged YAPF into trunk. Thanks to devs for continuous support and users for testing.
KUDr
parents:
2916
diff
changeset
|
253 |
_aystar_stats_closed_size = aystar->ClosedListHash.size; |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
254 |
aystar->clear(aystar); |
3944
7b1b00c8541d
(svn r5090) -Fix: [NPF] broken by me - r4366 (thanks Tron)
KUDr
parents:
3900
diff
changeset
|
255 |
} |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
256 |
|
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
257 |
switch (r) { |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
258 |
case AYSTAR_FOUND_END_NODE: return AYSTAR_FOUND_END_NODE; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
259 |
case AYSTAR_EMPTY_OPENLIST: |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
260 |
case AYSTAR_LIMIT_REACHED: return AYSTAR_NO_PATH; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
261 |
default: return AYSTAR_STILL_BUSY; |
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
262 |
} |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
263 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
264 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
265 |
/* |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
266 |
* Adds a node from where to start an algorithm. Multiple nodes can be added |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
267 |
* if wanted. You should make sure that clear() is called before adding nodes |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
268 |
* if the AyStar has been used before (though the normal main loop calls |
193
0a7025304867
(svn r194) -Codechange: stripping trailing-spaces. Please keep this that way!
truelight
parents:
110
diff
changeset
|
269 |
* clear() automatically when the algorithm finishes |
1777
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1617
diff
changeset
|
270 |
* g is the cost for starting with this node. |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
271 |
*/ |
4171 | 272 |
void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g) |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
273 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
274 |
#ifdef AYSTAR_DEBUG |
926
a6d140a6a4de
(svn r1414) Move TileIndex, TILE_MASK and GET_TILE_[XY] to map.h and turn the latter into inline functions names Tile[XY]
tron
parents:
826
diff
changeset
|
275 |
printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n", |
a6d140a6a4de
(svn r1414) Move TileIndex, TILE_MASK and GET_TILE_[XY] to map.h and turn the latter into inline functions names Tile[XY]
tron
parents:
826
diff
changeset
|
276 |
TileX(start_node->tile), TileY(start_node->tile), start_node->direction); |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
277 |
#endif |
1777
f703cf05b5b9
(svn r2281) - Fix: [ 1115204 ] [NPF] When pressing the goto depot button, trains will now also look behind it if there is no depot in front. If so, the train reverses immediately. This also work anywhere, not just at stations.
matthijs
parents:
1617
diff
changeset
|
278 |
AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, g); |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
279 |
} |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
280 |
|
4171 | 281 |
void init_AyStar(AyStar *aystar, Hash_HashProc hash, uint num_buckets) |
4000
4009d092b306
(svn r5210) Many small changes which piled up: const, unsigned, variable scope, CSE for readability, DeMorgan, if cascades -> switch, whitespace, parentheses, bracing, misc.
tron
parents:
3949
diff
changeset
|
282 |
{ |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
283 |
// Allocated the Hash for the OpenList and ClosedList |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
284 |
init_Hash(&aystar->OpenListHash, hash, num_buckets); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
285 |
init_Hash(&aystar->ClosedListHash, hash, num_buckets); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
286 |
|
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
287 |
// Set up our sorting queue |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
288 |
// BinaryHeap allocates a block of 1024 nodes |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
289 |
// When thatone gets full it reserves an otherone, till this number |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
290 |
// That is why it can stay this high |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
291 |
init_BinaryHeap(&aystar->OpenListQueue, 102400); |
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
292 |
|
4434
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
293 |
aystar->addstart = AyStarMain_AddStartNode; |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
294 |
aystar->main = AyStarMain_Main; |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
295 |
aystar->loop = AyStarMain_Loop; |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
296 |
aystar->free = AyStarMain_Free; |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
297 |
aystar->clear = AyStarMain_Clear; |
a08cb4b5c179
(svn r6204) -Cleanup: replace non-indentation with spaces; like '}<TAB>else {' -> '} else {', tabs between code and comment, etc.
rubidium
parents:
4171
diff
changeset
|
298 |
aystar->checktile = AyStarMain_CheckTile; |
110
a22a6b07904b
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
truelight
parents:
84
diff
changeset
|
299 |
} |