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 8 /** 9 * @file aystar.h 10 * This file has the header for %AyStar. 11 * %AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding. 12 * For more information about AyStar (A* Algorithm), you can look at 13 * <A HREF='http://en.wikipedia.org/wiki/A-star_search_algorithm'>http://en.wikipedia.org/wiki/A-star_search_algorithm</A>. 14 */ 15 16 #ifndef AYSTAR_H 17 #define AYSTAR_H 18 19 #include "queue.h" 20 #include "../../tile_type.h" 21 #include "../../track_type.h" 22 23 //#define AYSTAR_DEBUG 24 25 /** Return status of #AyStar methods. */ 26 enum AystarStatus { 27 AYSTAR_FOUND_END_NODE, ///< An end node was found. 28 AYSTAR_EMPTY_OPENLIST, ///< All items are tested, and no path has been found. 29 AYSTAR_STILL_BUSY, ///< Some checking was done, but no path found yet, and there are still items left to try. 30 AYSTAR_NO_PATH, ///< No path to the goal was found. 31 AYSTAR_LIMIT_REACHED, ///< The #AyStar::max_search_nodes limit has been reached, aborting search. 32 AYSTAR_DONE, ///< Not an end-tile, or wrong direction. 33 }; 34 35 static const int AYSTAR_INVALID_NODE = -1; ///< Item is not valid (for example, not walkable). 36 37 /** Node in the search. */ 38 struct AyStarNode { 39 TileIndex tile; 40 Trackdir direction; 41 uint user_data[2]; 42 }; 43 44 /** A path of nodes. */ 45 struct PathNode { 46 AyStarNode node; 47 PathNode *parent; ///< The parent of this item. 48 }; 49 50 /** 51 * Internal node. 52 * @note We do not save the h-value, because it is only needed to calculate the f-value. 53 * h-value should \em always be the distance left to the end-tile. 54 */ 55 struct OpenListNode { 56 int g; 57 PathNode path; 58 }; 59 60 bool CheckIgnoreFirstTile(const PathNode *node); 61 62 struct AyStar; 63 64 /** 65 * Check whether the end-tile is found. 66 * @param aystar %AyStar search algorithm data. 67 * @param current Node to exam one. 68 * @note The 2nd parameter should be #OpenListNode, and \em not #AyStarNode. #AyStarNode is 69 * part of #OpenListNode and so it could be accessed without any problems. 70 * The good part about #OpenListNode is, and how AIs use it, that you can 71 * access the parent of the current node, and so check if you, for example 72 * don't try to enter the file tile with a 90-degree curve. So please, leave 73 * this an #OpenListNode, it works just fine. 74 * @return Status of the node: 75 * - #AYSTAR_FOUND_END_NODE : indicates this is the end tile 76 * - #AYSTAR_DONE : indicates this is not the end tile (or direction was wrong) 77 */ 78 typedef int32 AyStar_EndNodeCheck(const AyStar *aystar, const OpenListNode *current); 79 80 /** 81 * Calculate the G-value for the %AyStar algorithm. 82 * @return G value of the node: 83 * - #AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable) 84 * - Any value >= 0 : the g-value for this tile 85 */ 86 typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent); 87 88 /** 89 * Calculate the H-value for the %AyStar algorithm. 90 * Mostly, this must return the distance (Manhattan way) between the current point and the end point. 91 * @return The h-value for this tile (any value >= 0) 92 */ 93 typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent); 94 95 /** 96 * This function requests the tiles around the current tile and put them in #neighbours. 97 * #neighbours is never reset, so if you are not using directions, just leave it alone. 98 * @warning Never add more #neighbours than memory allocated for it. 99 */ 100 typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current); 101 102 /** 103 * If the End Node is found, this function is called. 104 * It can do, for example, calculate the route and put that in an array. 105 */ 106 typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current); 107 108 /** 109 * %AyStar search algorithm struct. 110 * Before calling #Init(), fill #CalculateG, #CalculateH, #GetNeighbours, #EndNodeCheck, and #FoundEndNode. 111 * If you want to change them after calling #Init(), first call #Free() ! 112 * 113 * The #user_path, #user_target, and #user_data[10] are intended to be used by the user routines. The data not accessed by the #AyStar code itself. 114 * The user routines can change any moment they like. 115 */ 116 struct AyStar { 117 /* These fields should be filled before initing the AyStar, but not changed 118 * afterwards (except for user_data and user_path)! (free and init again to change them) */ 119 120 /* These should point to the application specific routines that do the 121 * actual work */ 122 AyStar_CalculateG *CalculateG; 123 AyStar_CalculateH *CalculateH; 124 AyStar_GetNeighbours *GetNeighbours; 125 AyStar_EndNodeCheck *EndNodeCheck; 126 AyStar_FoundEndNode *FoundEndNode; 127 128 /* These are completely untouched by AyStar, they can be accessed by 129 * the application specific routines to input and output data. 130 * user_path should typically contain data about the resulting path 131 * afterwards, user_target should typically contain information about 132 * what you where looking for, and user_data can contain just about 133 * everything */ 134 void *user_path; 135 void *user_target; 136 void *user_data; 137 138 byte loops_per_tick; ///< How many loops are there called before Main() gives control back to the caller. 0 = until done. 139 uint max_path_cost; ///< If the g-value goes over this number, it stops searching, 0 = infinite. 140 uint max_search_nodes; ///< The maximum number of nodes that will be expanded, 0 = infinite. 141 142 /* These should be filled with the neighbours of a tile by 143 * GetNeighbours */ 144 AyStarNode neighbours[12]; 145 byte num_neighbours; 146 147 void Init(Hash_HashProc hash, uint num_buckets); 148 149 /* These will contain the methods for manipulating the AyStar. Only 150 * Main() should be called externally */ 151 void AddStartNode(AyStarNode *start_node, uint g); 152 int Main(); 153 int Loop(); 154 void Free(); 155 void Clear(); 156 void CheckTile(AyStarNode *current, OpenListNode *parent); 157 158 protected: 159 Hash closedlist_hash; ///< The actual closed list. 160 BinaryHeap openlist_queue; ///< The open queue. 161 Hash openlist_hash; ///< An extra hash to speed up the process of looking up an element in the open list. 162 163 void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g); 164 OpenListNode *OpenListIsInList(const AyStarNode *node); 165 OpenListNode *OpenListPop(); 166 167 void ClosedListAdd(const PathNode *node); 168 PathNode *ClosedListIsInList(const AyStarNode *node); 169 }; 170 171 #endif /* AYSTAR_H */ 172