Files
@ r16836:cf0fdabe17c4
Branch filter:
Location: cpp/openttd-patchpack/source/src/pathfinder/npf/aystar.h
r16836:cf0fdabe17c4
6.6 KiB
text/x-c
(svn r21580) -Codechange: Replace callback via pointer by a switch statement.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | /* $Id$ */
/*
* This file is part of OpenTTD.
* 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.
* 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.
* 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.h
* 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
#define AYSTAR_H
#include "queue.h"
#include "../../tile_type.h"
#include "../../track_type.h"
//#define AYSTAR_DEBUG
/** Return status of #AyStar methods. */
enum AystarStatus {
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; ///< Item is not valid (for example, not walkable).
/** Node in the search. */
struct AyStarNode {
TileIndex tile;
Trackdir direction;
uint user_data[2];
};
/** A path of nodes. */
struct PathNode {
AyStarNode node;
PathNode *parent; ///< The parent of this item.
};
/**
* 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;
/**
* 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
* @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);
/**
* 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);
/**
* 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 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.
*/
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 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
* actual work */
AyStar_CalculateG *CalculateG;
AyStar_CalculateH *CalculateH;
AyStar_GetNeighbours *GetNeighbours;
AyStar_EndNodeCheck *EndNodeCheck;
AyStar_FoundEndNode *FoundEndNode;
/* 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 you where looking for, and user_data can contain just about
* everything */
void *user_path;
void *user_target;
uint user_data[10];
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 */
AyStarNode neighbours[12];
byte num_neighbours;
void Init(Hash_HashProc hash, uint num_buckets);
/* These will contain the methods for manipulating the AyStar. Only
* Main() should be called externally */
void AddStartNode(AyStarNode *start_node, uint g);
int Main();
int Loop();
void Free();
void Clear();
void CheckTile(AyStarNode *current, OpenListNode *parent);
protected:
Hash closedlist_hash; ///< The actual closed list.
BinaryHeap openlist_queue; ///< The open queue.
Hash openlist_hash; ///< An extra hash to speed up the process of looking up an element in the open list.
void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g);
OpenListNode *OpenListIsInList(const AyStarNode *node);
OpenListNode *OpenListPop();
void ClosedListAdd(const PathNode *node);
PathNode *ClosedListIsInList(const AyStarNode *node);
};
#endif /* AYSTAR_H */
|