tron@2186: /* $Id$ */
tron@2186: 
truelight@84: /*
truelight@84:  * This file has the header for AyStar
truelight@84:  *  AyStar is a fast pathfinding routine and is used for things like
truelight@84:  *  AI_pathfinding and Train_pathfinding.
truelight@84:  *  For more information about AyStar (A* Algorithm), you can look at
truelight@84:  *	  http://en.wikipedia.org/wiki/A-star_search_algorithm
truelight@84:  */
truelight@84: 
truelight@84: #ifndef AYSTAR_H
truelight@84: #define AYSTAR_H
truelight@84: 
truelight@84: #include "queue.h"
truelight@84: 
truelight@84: //#define AYSTAR_DEBUG
truelight@84: enum {
truelight@84: 	AYSTAR_FOUND_END_NODE,
truelight@84: 	AYSTAR_EMPTY_OPENLIST,
truelight@84: 	AYSTAR_STILL_BUSY,
truelight@84: 	AYSTAR_NO_PATH,
truelight@84: 	AYSTAR_LIMIT_REACHED,
truelight@84: 	AYSTAR_DONE
truelight@84: };
truelight@84: 
truelight@84: enum{
truelight@84: 	AYSTAR_INVALID_NODE = -1,
truelight@84: };
truelight@84: 
truelight@84: typedef struct AyStarNode AyStarNode;
truelight@84: struct AyStarNode {
tron@1977: 	TileIndex tile;
truelight@84: 	uint direction;
truelight@84: 	uint user_data[2];
truelight@84: };
truelight@84: 
truelight@84: // The resulting path has nodes looking like this.
truelight@84: typedef struct PathNode PathNode;
truelight@84: struct PathNode {
truelight@84: 	AyStarNode node;
truelight@84: 	// The parent of this item
truelight@84: 	PathNode *parent;
truelight@84: };
truelight@84: 
truelight@84: // For internal use only
truelight@84: // We do not save the h-value, because it is only needed to calculate the f-value.
truelight@84: //  h-value should _always_ be the distance left to the end-tile.
truelight@84: typedef struct OpenListNode OpenListNode;
truelight@84: struct OpenListNode {
truelight@84: 	int g;
truelight@84: 	PathNode path;
truelight@84: };
truelight@84: 
truelight@84: typedef struct AyStar AyStar;
truelight@84: /*
truelight@84:  * This function is called to check if the end-tile is found
truelight@84:  *  return values can be:
truelight@84:  *	AYSTAR_FOUND_END_NODE : indicates this is the end tile
truelight@84:  *	AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)
truelight@84:  */
truelight@1617: /*
truelight@1617:  * The 2nd parameter should be OpenListNode, and NOT AyStarNode. AyStarNode is
truelight@1617:  * part of OpenListNode and so it could be accessed without any problems.
truelight@1617:  * The good part about OpenListNode is, and how AIs use it, that you can
truelight@1617:  * access the parent of the current node, and so check if you, for example
truelight@1617:  * don't try to enter the file tile with a 90-degree curve. So please, leave
truelight@1617:  * this an OpenListNode, it works just fine -- TrueLight
truelight@1617:  */
truelight@1617: typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current);
truelight@84: 
truelight@84: /*
truelight@84:  * This function is called to calculate the G-value for AyStar Algorithm.
truelight@84:  *  return values can be:
truelight@84:  *	AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
truelight@84:  *	Any value >= 0 : the g-value for this tile
truelight@84:  */
truelight@84: typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
truelight@84: 
truelight@84: /*
truelight@84:  * This function is called to calculate the H-value for AyStar Algorithm.
truelight@84:  *  Mostly, this must result the distance (Manhattan way) between the
truelight@84:  *   current point and the end point
truelight@84:  *  return values can be:
truelight@84:  *	Any value >= 0 : the h-value for this tile
truelight@84:  */
truelight@84: typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
truelight@84: 
truelight@84: /*
truelight@84:  * This function request the tiles around the current tile and put them in tiles_around
truelight@84:  *  tiles_around is never resetted, so if you are not using directions, just leave it alone.
truelight@84:  * Warning: never add more tiles_around than memory allocated for it.
truelight@84:  */
truelight@84: typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
truelight@84: 
truelight@84: /*
truelight@84:  * If the End Node is found, this function is called.
truelight@84:  *  It can do, for example, calculate the route and put that in an array
truelight@84:  */
truelight@84: typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
truelight@84: 
truelight@84: // For internal use, see aystar.c
matthijs@1777: typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode* start_node, uint g);
truelight@84: typedef int AyStar_Main(AyStar *aystar);
truelight@84: typedef int AyStar_Loop(AyStar *aystar);
truelight@84: typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
truelight@84: typedef void AyStar_Free(AyStar *aystar);
truelight@84: typedef void AyStar_Clear(AyStar *aystar);
truelight@84: 
truelight@84: struct AyStar {
truelight@84: /* These fields should be filled before initting the AyStar, but not changed
truelight@84:  * afterwards (except for user_data and user_path)! (free and init again to change them) */
truelight@84: 
truelight@84: 	/* These should point to the application specific routines that do the
truelight@84: 	 * actual work */
truelight@84: 	AyStar_CalculateG* CalculateG;
truelight@84: 	AyStar_CalculateH* CalculateH;
truelight@84: 	AyStar_GetNeighbours* GetNeighbours;
truelight@84: 	AyStar_EndNodeCheck* EndNodeCheck;
truelight@84: 	AyStar_FoundEndNode* FoundEndNode;
truelight@193: 
truelight@84: 	/* These are completely untouched by AyStar, they can be accesed by
truelight@84: 	 * the application specific routines to input and output data.
truelight@84: 	 * user_path should typically contain data about the resulting path
truelight@84: 	 * afterwards, user_target should typically contain information about
truelight@84: 	 * what where looking for, and user_data can contain just about
truelight@84: 	 * everything */
truelight@84: 	void *user_path;
truelight@84: 	void *user_target;
truelight@84: 	uint user_data[10];
truelight@193: 
truelight@84: 	/* How many loops are there called before AyStarMain_Main gives
truelight@84: 	 * control back to the caller. 0 = until done */
truelight@84: 	byte loops_per_tick;
truelight@84: 	/* If the g-value goes over this number, it stops searching
truelight@84: 	 *  0 = infinite */
truelight@84: 	uint max_path_cost;
truelight@84: 	/* The maximum amount of nodes that will be expanded, 0 = infinite */
truelight@193: 	uint max_search_nodes;
truelight@84: 
truelight@84: 	/* These should be filled with the neighbours of a tile by
truelight@84: 	 * GetNeighbours */
truelight@84: 	AyStarNode neighbours[12];
truelight@84: 	byte num_neighbours;
truelight@84: 
truelight@84: 	/* These will contain the methods for manipulating the AyStar. Only
truelight@84: 	 * main() should be called externally */
truelight@84: 	AyStar_AddStartNode* addstart;
truelight@84: 	AyStar_Main* main;
truelight@84: 	AyStar_Loop* loop;
truelight@84: 	AyStar_Free* free;
truelight@84: 	AyStar_Clear* clear;
truelight@84: 	AyStar_CheckTile* checktile;
truelight@193: 
truelight@84: 	/* These will contain the open and closed lists */
truelight@84: 
truelight@84: 	/* The actual closed list */
truelight@84: 	Hash ClosedListHash;
truelight@84: 	/* The open queue */
truelight@84: 	Queue OpenListQueue;
truelight@84: 	/* An extra hash to speed up the process of looking up an element in
truelight@84: 	 * the open list */
truelight@84: 	Hash OpenListHash;
truelight@84: };
truelight@84: 
truelight@84: 
matthijs@1777: void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);
truelight@84: int AyStarMain_Main(AyStar *aystar);
truelight@84: int AyStarMain_Loop(AyStar *aystar);
truelight@84: int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
truelight@84: void AyStarMain_Free(AyStar *aystar);
truelight@84: void AyStarMain_Clear(AyStar *aystar);
truelight@84: 
truelight@84: /* Initialize an AyStar. You should fill all appropriate fields before
truelight@84:  * callling init_AyStar (see the declaration of AyStar for which fields are
truelight@84:  * internal */
truelight@84: void init_AyStar(AyStar* aystar, Hash_HashProc hash, uint num_buckets);
truelight@193: 
truelight@84: 
Darkvater@2436: #endif /* AYSTAR_H */