1

/* $Id$ */

     2

     3

/*

     4

 * This file has the header for AyStar

     5

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

     6

 *  AI_pathfinding and Train_pathfinding.

     7

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

     8

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

     9

 */

    10

    11

#ifndef AYSTAR_H

    12

#define AYSTAR_H

    13

    14

#include "queue.h"

    15

    16

//#define AYSTAR_DEBUG

    17

enum {

    18

	AYSTAR_FOUND_END_NODE,

    19

	AYSTAR_EMPTY_OPENLIST,

    20

	AYSTAR_STILL_BUSY,

    21

	AYSTAR_NO_PATH,

    22

	AYSTAR_LIMIT_REACHED,

    23

	AYSTAR_DONE

    24

};

    25

    26

enum{

    27

	AYSTAR_INVALID_NODE = -1,

    28

};

    29

    30

typedef struct AyStarNode AyStarNode;

    31

struct AyStarNode {

    32

	TileIndex tile;

    33

	uint direction;

    34

	uint user_data[2];

    35

};

    36

    37

// The resulting path has nodes looking like this.

    38

typedef struct PathNode PathNode;

    39

struct PathNode {

    40

	AyStarNode node;

    41

	// The parent of this item

    42

	PathNode *parent;

    43

};

    44

    45

// For internal use only

    46

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

    47

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

    48

typedef struct OpenListNode OpenListNode;

    49

struct OpenListNode {

    50

	int g;

    51

	PathNode path;

    52

};

    53

    54

typedef struct AyStar AyStar;

    55

/*

    56

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

    57

 *  return values can be:

    58

 *	AYSTAR_FOUND_END_NODE : indicates this is the end tile

    59

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

    60

 */

    61

/*

    62

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

    63

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

    64

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

    65

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

    66

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

    67

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

    68

 */

    69

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

    70

    71

/*

    72

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

    73

 *  return values can be:

    74

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

    75

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

    76

 */

    77

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

    78

    79

/*

    80

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

    81

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

    82

 *   current point and the end point

    83

 *  return values can be:

    84

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

    85

 */

    86

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

    87

    88

/*

    89

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

    90

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

    91

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

    92

 */

    93

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

    94

    95

/*

    96

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

    97

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

    98

 */

    99

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

   100

   101

// For internal use, see aystar.c

   102

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

   103

typedef int AyStar_Main(AyStar *aystar);

   104

typedef int AyStar_Loop(AyStar *aystar);

   105

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

   106

typedef void AyStar_Free(AyStar *aystar);

   107

typedef void AyStar_Clear(AyStar *aystar);

   108

   109

struct AyStar {

   110

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

   111

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

   112

   113

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

   114

	 * actual work */

   115

	AyStar_CalculateG* CalculateG;

   116

	AyStar_CalculateH* CalculateH;

   117

	AyStar_GetNeighbours* GetNeighbours;

   118

	AyStar_EndNodeCheck* EndNodeCheck;

   119

	AyStar_FoundEndNode* FoundEndNode;

   120

   121

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

   122

	 * the application specific routines to input and output data.

   123

	 * user_path should typically contain data about the resulting path

   124

	 * afterwards, user_target should typically contain information about

   125

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

   126

	 * everything */

   127

	void *user_path;

   128

	void *user_target;

   129

	uint user_data[10];

   130

   131

	/* How many loops are there called before AyStarMain_Main gives

   132

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

   133

	byte loops_per_tick;

   134

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

   135

	 *  0 = infinite */

   136

	uint max_path_cost;

   137

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

   138

	uint max_search_nodes;

   139

   140

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

   141

	 * GetNeighbours */

   142

	AyStarNode neighbours[12];

   143

	byte num_neighbours;

   144

   145

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

   146

	 * main() should be called externally */

   147

	AyStar_AddStartNode* addstart;

   148

	AyStar_Main* main;

   149

	AyStar_Loop* loop;

   150

	AyStar_Free* free;

   151

	AyStar_Clear* clear;

   152

	AyStar_CheckTile* checktile;

   153

   154

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

   155

   156

	/* The actual closed list */

   157

	Hash ClosedListHash;

   158

	/* The open queue */

   159

	Queue OpenListQueue;

   160

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

   161

	 * the open list */

   162

	Hash OpenListHash;

   163

};

   164

   165

   166

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

   167

int AyStarMain_Main(AyStar *aystar);

   168

int AyStarMain_Loop(AyStar *aystar);

   169

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

   170

void AyStarMain_Free(AyStar *aystar);

   171

void AyStarMain_Clear(AyStar *aystar);

   172

   173

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

   174

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

   175

 * internal */

   176

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

   177

   178

   179

#endif /* AYSTAR_H */