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

#include "tile_type.h"

    16

    17

//#define AYSTAR_DEBUG

    18

enum {

    19

	AYSTAR_FOUND_END_NODE,

    20

	AYSTAR_EMPTY_OPENLIST,

    21

	AYSTAR_STILL_BUSY,

    22

	AYSTAR_NO_PATH,

    23

	AYSTAR_LIMIT_REACHED,

    24

	AYSTAR_DONE

    25

};

    26

    27

enum{

    28

	AYSTAR_INVALID_NODE = -1,

    29

};

    30

    31

struct AyStarNode {

    32

	TileIndex tile;

    33

	int direction;

    34

	uint user_data[2];

    35

};

    36

    37

// The resulting path has nodes looking like this.

    38

struct PathNode {

    39

	AyStarNode node;

    40

	// The parent of this item

    41

	PathNode *parent;

    42

};

    43

    44

// For internal use only

    45

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

    46

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

    47

struct OpenListNode {

    48

	int g;

    49

	PathNode path;

    50

};

    51

    52

struct 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

    99

// For internal use, see aystar.c

   100

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

   101

typedef int AyStar_Main(AyStar *aystar);

   102

typedef int AyStar_Loop(AyStar *aystar);

   103

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

   104

typedef void AyStar_Free(AyStar *aystar);

   105

typedef void AyStar_Clear(AyStar *aystar);

   106

   107

struct AyStar {

   108

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

   109

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

   110

   111

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

   112

	 * actual work */

   113

	AyStar_CalculateG *CalculateG;

   114

	AyStar_CalculateH *CalculateH;

   115

	AyStar_GetNeighbours *GetNeighbours;

   116

	AyStar_EndNodeCheck *EndNodeCheck;

   117

	AyStar_FoundEndNode *FoundEndNode;

   118

   119

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

   120

	 * the application specific routines to input and output data.

   121

	 * user_path should typically contain data about the resulting path

   122

	 * afterwards, user_target should typically contain information about

   123

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

   124

	 * everything */

   125

	void *user_path;

   126

	void *user_target;

   127

	uint user_data[10];

   128

   129

	/* How many loops are there called before AyStarMain_Main gives

   130

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

   131

	byte loops_per_tick;

   132

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

   133

	 *  0 = infinite */

   134

	uint max_path_cost;

   135

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

   136

	uint max_search_nodes;

   137

   138

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

   139

	 * GetNeighbours */

   140

	AyStarNode neighbours[12];

   141

	byte num_neighbours;

   142

   143

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

   144

	 * main() should be called externally */

   145

	AyStar_AddStartNode *addstart;

   146

	AyStar_Main *main;

   147

	AyStar_Loop *loop;

   148

	AyStar_Free *free;

   149

	AyStar_Clear *clear;

   150

	AyStar_CheckTile *checktile;

   151

   152

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

   153

   154

	/* The actual closed list */

   155

	Hash ClosedListHash;

   156

	/* The open queue */

   157

	Queue OpenListQueue;

   158

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

   159

	 * the open list */

   160

	Hash OpenListHash;

   161

};

   162

   163

   164

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

   165

int AyStarMain_Main(AyStar *aystar);

   166

int AyStarMain_Loop(AyStar *aystar);

   167

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

   168

void AyStarMain_Free(AyStar *aystar);

   169

void AyStarMain_Clear(AyStar *aystar);

   170

   171

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

   172

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

   173

 * internal */

   174

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

   175

   176

   177

#endif /* AYSTAR_H */