# aystar.h

Go to the documentation of this file.

    00001 /* $Id: aystar.h 18364 2009-12-01 22:45:39Z rubidium $ */
    00002
    00003 /*
    00004  * This file is part of OpenTTD.
    00005  * 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.
    00006  * 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.
    00007  * 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/>.
    00008  */
    00009
    00018 #ifndef AYSTAR_H
    00019 #define AYSTAR_H
    00020
    00021 #include "queue.h"
    00022 #include "../../tile_type.h"
    00023 #include "../../track_type.h"
    00024
    00025 //#define AYSTAR_DEBUG
    00026 enum {
    00027   AYSTAR_FOUND_END_NODE,
    00028   AYSTAR_EMPTY_OPENLIST,
    00029   AYSTAR_STILL_BUSY,
    00030   AYSTAR_NO_PATH,
    00031   AYSTAR_LIMIT_REACHED,
    00032   AYSTAR_DONE
    00033 };
    00034
    00035 enum{
    00036   AYSTAR_INVALID_NODE = -1,
    00037 };
    00038
    00039 struct AyStarNode {
    00040   TileIndex tile;
    00041   Trackdir direction;
    00042   uint user_data[2];
    00043 };
    00044
    00045 /* The resulting path has nodes looking like this. */
    00046 struct PathNode {
    00047   AyStarNode node;
    00048   /* The parent of this item */
    00049   PathNode *parent;
    00050 };
    00051
    00052 /* For internal use only
    00053  * We do not save the h-value, because it is only needed to calculate the f-value.
    00054  *  h-value should _always_ be the distance left to the end-tile. */
    00055 struct OpenListNode {
    00056   int g;
    00057   PathNode path;
    00058 };
    00059
    00060 struct AyStar;
    00061 /*
    00062  * This function is called to check if the end-tile is found
    00063  *  return values can be:
    00064  *   AYSTAR_FOUND_END_NODE : indicates this is the end tile
    00065  *   AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)
    00066  */
    00067 /*
    00068  * The 2nd parameter should be OpenListNode, and NOT AyStarNode. AyStarNode is
    00069  * part of OpenListNode and so it could be accessed without any problems.
    00070  * The good part about OpenListNode is, and how AIs use it, that you can
    00071  * access the parent of the current node, and so check if you, for example
    00072  * don't try to enter the file tile with a 90-degree curve. So please, leave
    00073  * this an OpenListNode, it works just fine -- TrueLight
    00074  */
    00075 typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current);
    00076
    00077 /*
    00078  * This function is called to calculate the G-value for AyStar Algorithm.
    00079  *  return values can be:
    00080  *   AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
    00081  *   Any value >= 0 : the g-value for this tile
    00082  */
    00083 typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
    00084
    00085 /*
    00086  * This function is called to calculate the H-value for AyStar Algorithm.
    00087  *  Mostly, this must result the distance (Manhattan way) between the
    00088  *   current point and the end point
    00089  *  return values can be:
    00090  *   Any value >= 0 : the h-value for this tile
    00091  */
    00092 typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
    00093
    00094 /*
    00095  * This function request the tiles around the current tile and put them in tiles_around
    00096  *  tiles_around is never resetted, so if you are not using directions, just leave it alone.
    00097  * Warning: never add more tiles_around than memory allocated for it.
    00098  */
    00099 typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
    00100
    00101 /*
    00102  * If the End Node is found, this function is called.
    00103  *  It can do, for example, calculate the route and put that in an array
    00104  */
    00105 typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
    00106
    00107 /* For internal use, see aystar.cpp */
    00108 typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);
    00109 typedef int AyStar_Main(AyStar *aystar);
    00110 typedef int AyStar_Loop(AyStar *aystar);
    00111 typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
    00112 typedef void AyStar_Free(AyStar *aystar);
    00113 typedef void AyStar_Clear(AyStar *aystar);
    00114
    00115 struct AyStar {
    00116 /* These fields should be filled before initting the AyStar, but not changed
    00117  * afterwards (except for user_data and user_path)! (free and init again to change them) */
    00118
    00119   /* These should point to the application specific routines that do the
    00120    * actual work */
    00121   AyStar_CalculateG *CalculateG;
    00122   AyStar_CalculateH *CalculateH;
    00123   AyStar_GetNeighbours *GetNeighbours;
    00124   AyStar_EndNodeCheck *EndNodeCheck;
    00125   AyStar_FoundEndNode *FoundEndNode;
    00126
    00127   /* These are completely untouched by AyStar, they can be accesed by
    00128    * the application specific routines to input and output data.
    00129    * user_path should typically contain data about the resulting path
    00130    * afterwards, user_target should typically contain information about
    00131    * what where looking for, and user_data can contain just about
    00132    * everything */
    00133   void *user_path;
    00134   void *user_target;
    00135   uint user_data[10];
    00136
    00137   /* How many loops are there called before AyStarMain_Main gives
    00138    * control back to the caller. 0 = until done */
    00139   byte loops_per_tick;
    00140   /* If the g-value goes over this number, it stops searching
    00141    *  0 = infinite */
    00142   uint max_path_cost;
    00143   /* The maximum amount of nodes that will be expanded, 0 = infinite */
    00144   uint max_search_nodes;
    00145
    00146   /* These should be filled with the neighbours of a tile by
    00147    * GetNeighbours */
    00148   AyStarNode neighbours[12];
    00149   byte num_neighbours;
    00150
    00151   /* These will contain the methods for manipulating the AyStar. Only
    00152    * main() should be called externally */
    00153   AyStar_AddStartNode *addstart;
    00154   AyStar_Main *main;
    00155   AyStar_Loop *loop;
    00156   AyStar_Free *free;
    00157   AyStar_Clear *clear;
    00158   AyStar_CheckTile *checktile;
    00159
    00160   /* These will contain the open and closed lists */
    00161
    00162   /* The actual closed list */
    00163   Hash ClosedListHash;
    00164   /* The open queue */
    00165   Queue OpenListQueue;
    00166   /* An extra hash to speed up the process of looking up an element in
    00167    * the open list */
    00168   Hash OpenListHash;
    00169 };
    00170
    00171
    00172 int AyStarMain_Main(AyStar *aystar);
    00173 void AyStarMain_Clear(AyStar *aystar);
    00174
    00175 /* Initialize an AyStar. You should fill all appropriate fields before
    00176  * callling init_AyStar (see the declaration of AyStar for which fields are
    00177  * internal */
    00178 void init_AyStar(AyStar *aystar, Hash_HashProc hash, uint num_buckets);
    00179
    00180
    00181 #endif /* AYSTAR_H */