1

/* $Id$ */

     2

     3

/** @file aystar.h

     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

struct AyStarNode {

    31

	TileIndex tile;

    32

	int direction;

    33

	uint user_data[2];

    34

};

    35

    36

// The resulting path has nodes looking like this.

    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

struct OpenListNode {

    47

	int g;

    48

	PathNode path;

    49

};

    50

    51

struct AyStar;

    52

/*

    53

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

    54

 *  return values can be:

    55

 *   AYSTAR_FOUND_END_NODE : indicates this is the end tile

    56

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

    57

 */

    58

/*

    59

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

    60

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

    61

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

    62

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

    63

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

    64

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

    65

 */

    66

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

    67

    68

/*

    69

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

    70

 *  return values can be:

    71

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

    72

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

    73

 */

    74

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

    75

    76

/*

    77

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

    78

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

    79

 *   current point and the end point

    80

 *  return values can be:

    81

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

    82

 */

    83

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

    84

    85

/*

    86

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

    87

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

    88

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

    89

 */

    90

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

    91

    92

/*

    93

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

    94

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

    95

 */

    96

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

    97

    98

// For internal use, see aystar.c

    99

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

   100

typedef int AyStar_Main(AyStar *aystar);

   101

typedef int AyStar_Loop(AyStar *aystar);

   102

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

   103

typedef void AyStar_Free(AyStar *aystar);

   104

typedef void AyStar_Clear(AyStar *aystar);

   105

   106

struct AyStar {

   107

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

   108

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

   109

   110

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

   111

	 * actual work */

   112

	AyStar_CalculateG *CalculateG;

   113

	AyStar_CalculateH *CalculateH;

   114

	AyStar_GetNeighbours *GetNeighbours;

   115

	AyStar_EndNodeCheck *EndNodeCheck;

   116

	AyStar_FoundEndNode *FoundEndNode;

   117

   118

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

   119

	 * the application specific routines to input and output data.

   120

	 * user_path should typically contain data about the resulting path

   121

	 * afterwards, user_target should typically contain information about

   122

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

   123

	 * everything */

   124

	void *user_path;

   125

	void *user_target;

   126

	uint user_data[10];

   127

   128

	/* How many loops are there called before AyStarMain_Main gives

   129

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

   130

	byte loops_per_tick;

   131

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

   132

	 *  0 = infinite */

   133

	uint max_path_cost;

   134

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

   135

	uint max_search_nodes;

   136

   137

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

   138

	 * GetNeighbours */

   139

	AyStarNode neighbours[12];

   140

	byte num_neighbours;

   141

   142

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

   143

	 * main() should be called externally */

   144

	AyStar_AddStartNode *addstart;

   145

	AyStar_Main *main;

   146

	AyStar_Loop *loop;

   147

	AyStar_Free *free;

   148

	AyStar_Clear *clear;

   149

	AyStar_CheckTile *checktile;

   150

   151

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

   152

   153

	/* The actual closed list */

   154

	Hash ClosedListHash;

   155

	/* The open queue */

   156

	Queue OpenListQueue;

   157

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

   158

	 * the open list */

   159

	Hash OpenListHash;

   160

};

   161

   162

   163

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

   164

int AyStarMain_Main(AyStar *aystar);

   165

int AyStarMain_Loop(AyStar *aystar);

   166

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

   167

void AyStarMain_Free(AyStar *aystar);

   168

void AyStarMain_Clear(AyStar *aystar);

   169

   170

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

   171

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

   172

 * internal */

   173

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

   174

   175

   176

#endif /* AYSTAR_H */