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

	uint 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

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

    60

    61

/*

    62

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

    63

 *  return values can be:

    64

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

    65

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

    66

 */

    67

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

    68

    69

/*

    70

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

    71

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

    72

 *   current point and the end point

    73

 *  return values can be:

    74

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

    75

 */

    76

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

    77

    78

/*

    79

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

    80

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

    81

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

    82

 */

    83

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

    84

    85

/*

    86

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

    87

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

    88

 */

    89

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

    90

    91

// For internal use, see aystar.c

    92

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

    93

typedef int AyStar_Main(AyStar *aystar);

    94

typedef int AyStar_Loop(AyStar *aystar);

    95

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

    96

typedef void AyStar_Free(AyStar *aystar);

    97

typedef void AyStar_Clear(AyStar *aystar);

    98

    99

struct AyStar {

   100

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

   101

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

   102

   103

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

   104

	 * actual work */

   105

	AyStar_CalculateG* CalculateG;

   106

	AyStar_CalculateH* CalculateH;

   107

	AyStar_GetNeighbours* GetNeighbours;

   108

	AyStar_EndNodeCheck* EndNodeCheck;

   109

	AyStar_FoundEndNode* FoundEndNode;

   111

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

   112

	 * the application specific routines to input and output data.

   113

	 * user_path should typically contain data about the resulting path

   114

	 * afterwards, user_target should typically contain information about

   115

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

   116

	 * everything */

   117

	void *user_path;

   118

	void *user_target;

   119

	uint user_data[10];

   121

	/* How many loops are there called before AyStarMain_Main gives

   122

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

   123

	byte loops_per_tick;

   124

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

   125

	 *  0 = infinite */

   126

	uint max_path_cost;

   127

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

   129

   130

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

   131

	 * GetNeighbours */

   132

	AyStarNode neighbours[12];

   133

	byte num_neighbours;

   134

   135

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

   136

	 * main() should be called externally */

   137

	AyStar_AddStartNode* addstart;

   138

	AyStar_Main* main;

   139

	AyStar_Loop* loop;

   140

	AyStar_Free* free;

   141

	AyStar_Clear* clear;

   142

	AyStar_CheckTile* checktile;

   144

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

   145

   146

	/* The actual closed list */

   147

	Hash ClosedListHash;

   148

	/* The open queue */

   149

	Queue OpenListQueue;

   150

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

   151

	 * the open list */

   152

	Hash OpenListHash;

   153

};

   154

   155

   156

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

   157

int AyStarMain_Main(AyStar *aystar);

   158

int AyStarMain_Loop(AyStar *aystar);

   159

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

   160

void AyStarMain_Free(AyStar *aystar);

   161

void AyStarMain_Clear(AyStar *aystar);

   162

   163

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

   164

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

   165

 * internal */

   166

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

   168

   169

#endif