diff options
| -rw-r--r-- | src/pathfinder/npf/aystar.cpp | 108 | ||||
| -rw-r--r-- | src/pathfinder/npf/aystar.h | 119 |
2 files changed, 120 insertions, 107 deletions
diff --git a/src/pathfinder/npf/aystar.cpp b/src/pathfinder/npf/aystar.cpp index 6fee93970..64a1735e4 100644 --- a/src/pathfinder/npf/aystar.cpp +++ b/src/pathfinder/npf/aystar.cpp @@ -7,14 +7,12 @@ * 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.cpp Implementation of A*. */ - -/* - * This file has the core function 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 +/** @file aystar.cpp Implementation of A*. + * + * This file has the core function for %AyStar. + * %AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding. + * For more information about %AyStar (A* Algorithm), you can look at + * <A HREF='http://en.wikipedia.org/wiki/A-star_search_algorithm'>http://en.wikipedia.org/wiki/A-star_search_algorithm</A>. */ /* @@ -29,15 +27,21 @@ #include "../../core/alloc_func.hpp" #include "aystar.h" -/* This looks in the Hash if a node exists in ClosedList - * If so, it returns the PathNode, else NULL */ +/** + * This looks in the hash whether a node exists in the closed list. + * @param node Node to search. + * @return The #PathNode if it is available, else \c NULL + */ PathNode *AyStar::ClosedListIsInList(const AyStarNode *node) { return (PathNode*)this->closedlist_hash.Get(node->tile, node->direction); } -/* This adds a node to the ClosedList - * It makes a copy of the data */ +/** + * This adds a node to the closed list. + * It makes a copy of the data. + * @param node Node to add to the closed list. + */ void AyStar::ClosedListAdd(const PathNode *node) { /* Add a node to the ClosedList */ @@ -46,16 +50,21 @@ void AyStar::ClosedListAdd(const PathNode *node) this->closedlist_hash.Set(node->node.tile, node->node.direction, new_node); } -/* Checks if a node is in the OpenList - * If so, it returns the OpenListNode, else NULL */ +/** + * Check whether a node is in the open list. + * @param node Node to search. + * @return If the node is available, it is returned, else \c NULL is returned. + */ OpenListNode *AyStar::OpenListIsInList(const AyStarNode *node) { return (OpenListNode*)this->openlist_hash.Get(node->tile, node->direction); } -/* Gets the best node from OpenList - * returns the best node, or NULL of none is found - * Also it deletes the node from the OpenList */ +/** + * Gets the best node from the open list. + * It deletes the returned node from the open list. + * @returns the best node available, or \c NULL of none is found. + */ OpenListNode *AyStar::OpenListPop() { /* Return the item the Queue returns.. the best next OpenList item. */ @@ -67,8 +76,10 @@ OpenListNode *AyStar::OpenListPop() return res; } -/* Adds a node to the OpenList - * It makes a copy of node, and puts the pointer of parent in the struct */ +/** + * Adds a node to the open list. + * It makes a copy of node, and puts the pointer of parent in the struct. + */ void AyStar::OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g) { /* Add a new Node to the OpenList */ @@ -82,8 +93,8 @@ void AyStar::OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g) this->openlist_queue.Push(new_node, f); } -/* - * Checks one tile and calculate his f-value +/** + * Checks one tile and calculate its f-value */ void AyStar::CheckTile(AyStarNode *current, OpenListNode *parent) { @@ -138,16 +149,14 @@ void AyStar::CheckTile(AyStarNode *current, OpenListNode *parent) } } -/* - * This function is the core of AyStar. It handles one item and checks - * his neighbour items. If they are valid, they are added to be checked too. - * return values: - * AYSTAR_EMPTY_OPENLIST : indicates all items are tested, and no path - * has been found. - * AYSTAR_LIMIT_REACHED : Indicates that the max_nodes limit has been - * reached. - * AYSTAR_FOUND_END_NODE : indicates we found the end. Path_found now is true, and in path is the path found. - * AYSTAR_STILL_BUSY : indicates we have done this tile, did not found the path yet, and have items left to try. +/** + * This function is the core of %AyStar. It handles one item and checks + * his neighbour items. If they are valid, they are added to be checked too. + * @return Possible values: + * - #AYSTAR_EMPTY_OPENLIST : indicates all items are tested, and no path has been found. + * - #AYSTAR_LIMIT_REACHED : Indicates that the max_nodes limit has been reached. + * - #AYSTAR_FOUND_END_NODE : indicates we found the end. Path_found now is true, and in path is the path found. + * - #AYSTAR_STILL_BUSY : indicates we have done this tile, did not found the path yet, and have items left to try. */ int AyStar::Loop() { @@ -191,7 +200,7 @@ int AyStar::Loop() } } -/* +/** * This function frees the memory it allocated */ void AyStar::Free() @@ -206,9 +215,9 @@ void AyStar::Free() #endif } -/* - * This function make the memory go back to zero - * This function should be called when you are using the same instance again. +/** + * This function make the memory go back to zero. + * This function should be called when you are using the same instance again. */ void AyStar::Clear() { @@ -224,15 +233,14 @@ void AyStar::Clear() #endif } -/* +/** * This is the function you call to run AyStar. - * return values: - * AYSTAR_FOUND_END_NODE : indicates we found an end node. - * AYSTAR_NO_PATH : indicates that there was no path found. - * 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. - * When the algorithm is done (when the return value is not AYSTAR_STILL_BUSY) - * this->Clear() is called. Note that when you stop the algorithm halfway, - * you should still call Clear() yourself! + * @return Possible values: + * - #AYSTAR_FOUND_END_NODE : indicates we found an end node. + * - #AYSTAR_NO_PATH : indicates that there was no path found. + * - #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. + * @note When the algorithm is done (when the return value is not #AYSTAR_STILL_BUSY) #Clear() is called automatically. + * When you stop the algorithm halfway, you should call #Clear() yourself! */ int AyStar::Main() { @@ -261,12 +269,13 @@ int AyStar::Main() } } -/* +/** * Adds a node from where to start an algorithm. Multiple nodes can be added - * if wanted. You should make sure that clear() is called before adding nodes - * if the AyStar has been used before (though the normal main loop calls - * clear() automatically when the algorithm finishes - * g is the cost for starting with this node. + * if wanted. You should make sure that #Clear() is called before adding nodes + * if the #AyStar has been used before (though the normal main loop calls + * #Clear() automatically when the algorithm finishes. + * @param start_node Node to start with. + * @param g the cost for starting with this node. */ void AyStar::AddStartNode(AyStarNode *start_node, uint g) { @@ -279,8 +288,7 @@ void AyStar::AddStartNode(AyStarNode *start_node, uint g) /** * Initialize an #AyStar. You should fill all appropriate fields before - * calling #Init (see the declaration of #AyStar for which fields are - * internal. + * calling #Init (see the declaration of #AyStar for which fields are internal). */ void AyStar::Init(Hash_HashProc hash, uint num_buckets) { diff --git a/src/pathfinder/npf/aystar.h b/src/pathfinder/npf/aystar.h index 3c346a80c..df6e59593 100644 --- a/src/pathfinder/npf/aystar.h +++ b/src/pathfinder/npf/aystar.h @@ -9,11 +9,10 @@ /** * @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 + * This file has the header for %AyStar. + * %AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding. + * For more information about AyStar (A* Algorithm), you can look at + * <A HREF='http://en.wikipedia.org/wiki/A-star_search_algorithm'>http://en.wikipedia.org/wiki/A-star_search_algorithm</A>. */ #ifndef AYSTAR_H @@ -24,87 +23,98 @@ #include "../../track_type.h" //#define AYSTAR_DEBUG + +/** Return status of #AyStar methods. */ enum AystarStatus { - AYSTAR_FOUND_END_NODE, - AYSTAR_EMPTY_OPENLIST, - AYSTAR_STILL_BUSY, - AYSTAR_NO_PATH, - AYSTAR_LIMIT_REACHED, - AYSTAR_DONE + AYSTAR_FOUND_END_NODE, ///< An end node was found. + AYSTAR_EMPTY_OPENLIST, ///< All items are tested, and no path has been found. + AYSTAR_STILL_BUSY, ///< Some checking was done, but no path found yet, and there are still items left to try. + AYSTAR_NO_PATH, ///< No path to the goal was found. + AYSTAR_LIMIT_REACHED, ///< The #max_nodes limit has been reached, aborting search. + AYSTAR_DONE, ///< Not an end-tile, or wrong direction. }; -static const int AYSTAR_INVALID_NODE = -1; +static const int AYSTAR_INVALID_NODE = -1; ///< Item is not valid (for example, not walkable). +/** Node in the search. */ struct AyStarNode { TileIndex tile; Trackdir direction; uint user_data[2]; }; -/* The resulting path has nodes looking like this. */ +/** A path of nodes. */ struct PathNode { AyStarNode node; - /* The parent of this item */ - PathNode *parent; + PathNode *parent; ///< The parent of this item. }; -/* 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. */ +/** + * Internal node. + * @note We do not save the h-value, because it is only needed to calculate the f-value. + * h-value should \em 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 + +/** + * Check whether the end-tile is found. + * @param aystar %AyStar search algorithm data. + * @param current Node to examone. + * @note The 2nd parameter should be #OpenListNode, and \em 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 + * this an #OpenListNode, it works just fine -- TrueLight + * @return Status of the node: + * - #AYSTAR_FOUND_END_NODE : indicates this is the end tile + * - #AYSTAR_DONE : indicates this is not the end tile (or direction was wrong) */ 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 +/** + * Calculate the G-value for the %AyStar algorithm. + * @return G value of the node: + * - #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 +/** + * Calculate the H-value for the %AyStar algorithm. + * Mostly, this must return the distance (Manhattan way) between the current point and the end point. + * @return The h-value for this tile (any value >= 0) */ 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. +/** + * This function requests the tiles around the current tile and put them in #tiles_around. + * #tiles_around is never reset, 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 + * It can do, for example, calculate the route and put that in an array. */ typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current); +/** + * %AyStar search algorithm struct. + * Before calling #Init(), fill #CalculateG, #CalculateH, #GetNeighbours, #EndNodeCheck, and #FoundEndNode. + * If you want to change them after calling #Init(), first call #Free() ! + * + * 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. + * The user routines can change any moment they like. + */ struct AyStar { -/* These fields should be filled before initting the AyStar, but not changed +/* These fields should be filled before initing 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 @@ -115,24 +125,19 @@ struct AyStar { AyStar_EndNodeCheck *EndNodeCheck; AyStar_FoundEndNode *FoundEndNode; - /* These are completely untouched by AyStar, they can be accesed by + /* These are completely untouched by AyStar, they can be accessed 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 + * what you 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; + byte loops_per_tick; ///< How many loops are there called before Main() gives control back to the caller. 0 = until done. + uint max_path_cost; ///< If the g-value goes over this number, it stops searching, 0 = infinite. + uint max_search_nodes; ///< The maximum number of nodes that will be expanded, 0 = infinite. /* These should be filled with the neighbours of a tile by * GetNeighbours */ |