1

/*

     2

 * This file has the header for AyStar

     3

 *  AyStar is a fast pathfinding routine and is used for things like

     4

 *  AI_pathfinding and Train_pathfinding.

     5

 *  For more information about AyStar (A* Algorithm), you can look at

     6

 *	  http://en.wikipedia.org/wiki/A-star_search_algorithm

     7

 */

     8

     9

#ifndef AYSTAR_H

    10

#define AYSTAR_H

    11

    12

#include "queue.h"

    13

    14

//#define AYSTAR_DEBUG

    15

enum {

    16

	AYSTAR_FOUND_END_NODE,

    17

	AYSTAR_EMPTY_OPENLIST,

    18

	AYSTAR_STILL_BUSY,

    19

	AYSTAR_NO_PATH,

    20

	AYSTAR_LIMIT_REACHED,

    21

	AYSTAR_DONE

    22

};

    23

    24

enum{

    25

	AYSTAR_INVALID_NODE = -1,

    26

};

    27

    28

typedef struct AyStarNode AyStarNode;

    29

struct AyStarNode {

    30

	TileIndex tile;

    31

	uint direction;

    32

	uint user_data[2];

    33

};

    34

    35

// The resulting path has nodes looking like this.

    36

typedef struct PathNode PathNode;

    37

struct PathNode {

    38

	AyStarNode node;

    39

	// The parent of this item

    40

	PathNode *parent;

    41

};

    42

    43

// For internal use only

    44

// We do not save the h-value, because it is only needed to calculate the f-value.

    45

//  h-value should _always_ be the distance left to the end-tile.

    46

typedef struct OpenListNode OpenListNode;

    47

struct OpenListNode {

    48

	int g;

    49

	PathNode path;

    50

};

    51

    52

typedef struct AyStar AyStar;

    53

/*

    54

 * This function is called to check if the end-tile is found

    55

 *  return values can be:

    56

 *	AYSTAR_FOUND_END_NODE : indicates this is the end tile

    57

 *	AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)

    58

 */

    59

/*

    60

 * The 2nd parameter should be OpenListNode, and NOT AyStarNode. AyStarNode is

    61

 * part of OpenListNode and so it could be accessed without any problems.

    62

 * The good part about OpenListNode is, and how AIs use it, that you can

    63

 * access the parent of the current node, and so check if you, for example

    64

 * don't try to enter the file tile with a 90-degree curve. So please, leave

    65

 * this an OpenListNode, it works just fine -- TrueLight

    66

 */

    67

typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current);

    68

    69

/*

    70

 * This function is called to calculate the G-value for AyStar Algorithm.

    71

 *  return values can be:

    72

 *	AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)

    73

 *	Any value >= 0 : the g-value for this tile

    74

 */

    75

typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);

    76

    77

/*

    78

 * This function is called to calculate the H-value for AyStar Algorithm.

    79

 *  Mostly, this must result the distance (Manhattan way) between the

    80

 *   current point and the end point

    81

 *  return values can be:

    82

 *	Any value >= 0 : the h-value for this tile

    83

 */

    84

typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);

    85

    86

/*

    87

 * This function request the tiles around the current tile and put them in tiles_around

    88

 *  tiles_around is never resetted, so if you are not using directions, just leave it alone.

    89

 * Warning: never add more tiles_around than memory allocated for it.

    90

 */

    91

typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);

    92

    93

/*

    94

 * If the End Node is found, this function is called.

    95

 *  It can do, for example, calculate the route and put that in an array

    96

 */

    97

typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);

    98

   104

// For internal use, see aystar.c

   105

typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode* start_node, uint g);

   106

typedef int AyStar_Main(AyStar *aystar);

   107

typedef int AyStar_Loop(AyStar *aystar);

   108

typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);

   109

typedef void AyStar_Free(AyStar *aystar);

   110

typedef void AyStar_Clear(AyStar *aystar);

   111

   112

struct AyStar {

   113

/* These fields should be filled before initting the AyStar, but not changed

   114

 * afterwards (except for user_data and user_path)! (free and init again to change them) */

   115

   116

	/* These should point to the application specific routines that do the

   117

	 * actual work */

   118

	AyStar_CalculateG* CalculateG;

   119

	AyStar_CalculateH* CalculateH;

   120

	AyStar_GetNeighbours* GetNeighbours;

   121

	AyStar_EndNodeCheck* EndNodeCheck;

   122

	AyStar_FoundEndNode* FoundEndNode;

   124

   125

	/* These are completely untouched by AyStar, they can be accesed by

   126

	 * the application specific routines to input and output data.

   127

	 * user_path should typically contain data about the resulting path

   128

	 * afterwards, user_target should typically contain information about

   129

	 * what where looking for, and user_data can contain just about

   130

	 * everything */

   131

	void *user_path;

   132

	void *user_target;

   133

	uint user_data[10];

   134

   135

	/* How many loops are there called before AyStarMain_Main gives

   136

	 * control back to the caller. 0 = until done */

   137

	byte loops_per_tick;

   138

	/* If the g-value goes over this number, it stops searching

   139

	 *  0 = infinite */

   140

	uint max_path_cost;

   141

	/* The maximum amount of nodes that will be expanded, 0 = infinite */

   142

	uint max_search_nodes;

   143

   144

	/* These should be filled with the neighbours of a tile by

   145

	 * GetNeighbours */

   146

	AyStarNode neighbours[12];

   147

	byte num_neighbours;

   148

   149

	/* These will contain the methods for manipulating the AyStar. Only

   150

	 * main() should be called externally */

   151

	AyStar_AddStartNode* addstart;

   152

	AyStar_Main* main;

   153

	AyStar_Loop* loop;

   154

	AyStar_Free* free;

   155

	AyStar_Clear* clear;

   156

	AyStar_CheckTile* checktile;

   157

   158

	/* These will contain the open and closed lists */

   159

   160

	/* The actual closed list */

   161

	Hash ClosedListHash;

   162

	/* The open queue */

   163

	Queue OpenListQueue;

   164

	/* An extra hash to speed up the process of looking up an element in

   165

	 * the open list */

   166

	Hash OpenListHash;

   167

};

   168

   169

   170

void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);

   171

int AyStarMain_Main(AyStar *aystar);

   172

int AyStarMain_Loop(AyStar *aystar);

   173

int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);

   174

void AyStarMain_Free(AyStar *aystar);

   175

void AyStarMain_Clear(AyStar *aystar);

   176

   177

/* Initialize an AyStar. You should fill all appropriate fields before

   178

 * callling init_AyStar (see the declaration of AyStar for which fields are

   179

 * internal */

   180

void init_AyStar(AyStar* aystar, Hash_HashProc hash, uint num_buckets);

   181

   182

   183

#endif