# aystar.h

Go to the documentation of this file.

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