src/pathfinder/npf/aystar.h

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /**
  11  * @file aystar.h
  12  * This file has the header for %AyStar.
  13  * %AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding.
  14  * For more information about AyStar (A* Algorithm), you can look at
  15  * <A HREF='http://en.wikipedia.org/wiki/A-star_search_algorithm'>http://en.wikipedia.org/wiki/A-star_search_algorithm</A>.
  16  */
  17
  18 #ifndef AYSTAR_H
  19 #define AYSTAR_H
  20
  21 #include "queue.h"
  22 #include "../../tile_type.h"
  23 #include "../../track_type.h"
  24
  25 //#define AYSTAR_DEBUG
  26
  27 /** Return status of #AyStar methods. */
  28 enum AystarStatus {
  29         AYSTAR_FOUND_END_NODE, ///< An end node was found.
  30         AYSTAR_EMPTY_OPENLIST, ///< All items are tested, and no path has been found.
  31         AYSTAR_STILL_BUSY,     ///< Some checking was done, but no path found yet, and there are still items left to try.
  32         AYSTAR_NO_PATH,        ///< No path to the goal was found.
  33         AYSTAR_LIMIT_REACHED,  ///< The #max_nodes limit has been reached, aborting search.
  34         AYSTAR_DONE,           ///< Not an end-tile, or wrong direction.
  35 };
  36
  37 static const int AYSTAR_INVALID_NODE = -1; ///< Item is not valid (for example, not walkable).
  38
  39 /** Node in the search. */
  40 struct AyStarNode {
  41         TileIndex tile;
  42         Trackdir direction;
  43         uint user_data[2];
  44 };
  45
  46 /** A path of nodes. */
  47 struct PathNode {
  48         AyStarNode node;
  49         PathNode *parent; ///< The parent of this item.
  50 };
  51
  52 /**
  53  * Internal node.
  54  * @note We do not save the h-value, because it is only needed to calculate the f-value.
  55  *       h-value should \em always be the distance left to the end-tile.
  56  */
  57 struct OpenListNode {
  58         int g;
  59         PathNode path;
  60 };
  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(AyStar *aystar, 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 #tiles_around.
  97  * #tiles_around is never reset, so if you are not using directions, just leave it alone.
  98  * \warning Never add more tiles_around 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 */