src/pathfinder/aystar.h

   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 "../track_func.h"
  20
  21 #include "../misc/hashtable.hpp"
  22 #include "../misc/binaryheap.hpp"
  23 #include "../misc/dbg_helpers.h"
  24
  25 #include "yapf/nodelist.hpp"
  26 #include "yapf/yapf_node.hpp"
  27
  28 static const int AYSTAR_DEF_MAX_SEARCH_NODES = 10000; ///< Reference limit for #AyStar::max_search_nodes
  29
  30 /** Return status of #AyStar methods. */
  31 enum AystarStatus {
  32         AYSTAR_FOUND_END_NODE, ///< An end node was found.
  33         AYSTAR_EMPTY_OPENLIST, ///< All items are tested, and no path has been found.
  34         AYSTAR_STILL_BUSY,     ///< Some checking was done, but no path found yet, and there are still items left to try.
  35         AYSTAR_NO_PATH,        ///< No path to the goal was found.
  36         AYSTAR_LIMIT_REACHED,  ///< The #AyStar::max_search_nodes limit has been reached, aborting search.
  37         AYSTAR_DONE,           ///< Not an end-tile, or wrong direction.
  38 };
  39
  40 static const int AYSTAR_INVALID_NODE = -1; ///< Item is not valid (for example, not walkable).
  41
  42 using AyStarNode = CYapfNodeKeyTrackDir;
  43
  44 struct PathNode : CYapfNodeT<AyStarNode, PathNode> {
  45 };
  46
  47 bool CheckIgnoreFirstTile(const PathNode *node);
  48
  49 struct AyStar;
  50
  51 /**
  52  * Check whether the end-tile is found.
  53  * @param aystar %AyStar search algorithm data.
  54  * @param current Node to exam one.
  55  * @note The 2nd parameter should be #OpenListNode, and \em not #AyStarNode. #AyStarNode is
  56  * part of #OpenListNode and so it could be accessed without any problems.
  57  * The good part about #OpenListNode is, and how AIs use it, that you can
  58  * access the parent of the current node, and so check if you, for example
  59  * don't try to enter the file tile with a 90-degree curve. So please, leave
  60  * this an #OpenListNode, it works just fine.
  61  * @return Status of the node:
  62  *  - #AYSTAR_FOUND_END_NODE : indicates this is the end tile
  63  *  - #AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)
  64  */
  65 typedef int32_t AyStar_EndNodeCheck(const AyStar *aystar, const PathNode *current);
  66
  67 /**
  68  * Calculate the G-value for the %AyStar algorithm.
  69  * @return G value of the node:
  70  *  - #AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
  71  *  - Any value >= 0 : the g-value for this tile
  72  */
  73 typedef int32_t AyStar_CalculateG(AyStar *aystar, AyStarNode *current, PathNode *parent);
  74
  75 /**
  76  * Calculate the H-value for the %AyStar algorithm.
  77  * Mostly, this must return the distance (Manhattan way) between the current point and the end point.
  78  * @return The h-value for this tile (any value >= 0)
  79  */
  80 typedef int32_t AyStar_CalculateH(AyStar *aystar, AyStarNode *current, PathNode *parent);
  81
  82 /**
  83  * This function requests the tiles around the current tile and put them in #neighbours.
  84  * #neighbours is never reset, so if you are not using directions, just leave it alone.
  85  * @warning Never add more #neighbours than memory allocated for it.
  86  */
  87 typedef void AyStar_GetNeighbours(AyStar *aystar, PathNode *current);
  88
  89 /**
  90  * If the End Node is found, this function is called.
  91  * It can do, for example, calculate the route and put that in an array.
  92  */
  93 typedef void AyStar_FoundEndNode(AyStar *aystar, PathNode *current);
  94
  95 /**
  96  * %AyStar search algorithm struct.
  97  * Before calling #Init(), fill #CalculateG, #CalculateH, #GetNeighbours, #EndNodeCheck, and #FoundEndNode.
  98  * If you want to change them after calling #Init(), first call #Free() !
  99  *
 100  * 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.
 101  * The user routines can change any moment they like.
 102  */
 103 struct AyStar {
 104 /* These fields should be filled before initing the AyStar, but not changed
 105  * afterwards (except for user_data)! (free and init again to change them) */
 106
 107         /* These should point to the application specific routines that do the
 108          * actual work */
 109         AyStar_CalculateG *CalculateG;
 110         AyStar_CalculateH *CalculateH;
 111         AyStar_GetNeighbours *GetNeighbours;
 112         AyStar_EndNodeCheck *EndNodeCheck;
 113         AyStar_FoundEndNode *FoundEndNode;
 114
 115         /* These are completely untouched by AyStar, they can be accessed by
 116          * the application specific routines to input and output data.
 117          * user_path should typically contain data about the resulting path
 118          * afterwards, user_target should typically contain information about
 119          * what you where looking for, and user_data can contain just about
 120          * everything */
 121         void *user_target;
 122         void *user_data;
 123
 124         uint8_t loops_per_tick;   ///< How many loops are there called before Main() gives control back to the caller. 0 = until done.
 125         int max_path_cost;    ///< If the g-value goes over this number, it stops searching, 0 = infinite.
 126         int max_search_nodes = AYSTAR_DEF_MAX_SEARCH_NODES; ///< The maximum number of nodes that will be expanded, 0 = infinite.
 127
 128         /* These should be filled with the neighbours of a tile by GetNeighbours */
 129         std::vector<AyStarNode> neighbours;
 130
 131         /* These will contain the methods for manipulating the AyStar. Only
 132          * Main() should be called externally */
 133         void AddStartNode(AyStarNode *start_node, int g);
 134         int Main();
 135         int Loop();
 136         void CheckTile(AyStarNode *current, PathNode *parent);
 137
 138 protected:
 139         CNodeList_HashTableT<PathNode, 8, 10> nodes;
 140
 141         void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g);
 142 };
 143
 144 #endif /* AYSTAR_H */