Mercurial > hg > openttd

annotate src/aystar.h @ 6316:8ecb7b1dea16 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
(svn r9259) -Codechange: NUM_CARGO isn't a valid cargo type...
author peter1138 <peter1138@openttd.org>
date Fri, 16 Mar 2007 21:42:11 +0000
parents 0789677a15a0
children 60ea0f95de91
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
5475
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
1 /* $Id$ */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
2
6117
6def6ecb1bf7 (svn r8853) -Cleanup: doxygen changes. Correct forgotten c files to cpp files with the @file tag as well as a few general comments style
belugas <belugas@openttd.org>
parents: 5587
diff changeset
3 /** @file aystar.h
5475
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
4 * This file has the header for AyStar
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
5 * AyStar is a fast pathfinding routine and is used for things like
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
6 * AI_pathfinding and Train_pathfinding.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
7 * For more information about AyStar (A* Algorithm), you can look at
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
8 * http://en.wikipedia.org/wiki/A-star_search_algorithm
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
9 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
10
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
11 #ifndef AYSTAR_H
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
12 #define AYSTAR_H
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
13
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
14 #include "queue.h"
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
15
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
16 //#define AYSTAR_DEBUG
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
17 enum {
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
18 AYSTAR_FOUND_END_NODE,
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
19 AYSTAR_EMPTY_OPENLIST,
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
20 AYSTAR_STILL_BUSY,
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
21 AYSTAR_NO_PATH,
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
22 AYSTAR_LIMIT_REACHED,
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
23 AYSTAR_DONE
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
24 };
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
25
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
26 enum{
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
27 AYSTAR_INVALID_NODE = -1,
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
28 };
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
29
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
30 struct AyStarNode {
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
31 TileIndex tile;
5587
c44c070c5032 (svn r8038) -Merge: the cpp branch. Effort of KUDr, Celestar, glx, Smoovius, stillunknown and pv2b.
rubidium <rubidium@openttd.org>
parents: 5475
diff changeset
32 int direction;
5475
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
33 uint user_data[2];
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
34 };
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
35
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
36 // The resulting path has nodes looking like this.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
37 struct PathNode {
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
38 AyStarNode node;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
39 // The parent of this item
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
40 PathNode *parent;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
41 };
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
42
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
43 // For internal use only
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
44 // We do not save the h-value, because it is only needed to calculate the f-value.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
45 // h-value should _always_ be the distance left to the end-tile.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
46 struct OpenListNode {
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
47 int g;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
48 PathNode path;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
49 };
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
50
6248
0789677a15a0 (svn r9051) -Codechange: typedef [enum|struct] Y {} X; -> [enum|struct] X {};
rubidium <rubidium@openttd.org>
parents: 6117
diff changeset
51 struct AyStar;
5475
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
52 /*
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
53 * This function is called to check if the end-tile is found
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
54 * return values can be:
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
55 * AYSTAR_FOUND_END_NODE : indicates this is the end tile
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
56 * AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
57 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
58 /*
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
59 * The 2nd parameter should be OpenListNode, and NOT AyStarNode. AyStarNode is
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
60 * part of OpenListNode and so it could be accessed without any problems.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
61 * The good part about OpenListNode is, and how AIs use it, that you can
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
62 * access the parent of the current node, and so check if you, for example
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
63 * don't try to enter the file tile with a 90-degree curve. So please, leave
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
64 * this an OpenListNode, it works just fine -- TrueLight
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
65 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
66 typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
67
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
68 /*
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
69 * This function is called to calculate the G-value for AyStar Algorithm.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
70 * return values can be:
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
71 * AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
72 * Any value >= 0 : the g-value for this tile
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
73 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
74 typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
75
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
76 /*
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
77 * This function is called to calculate the H-value for AyStar Algorithm.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
78 * Mostly, this must result the distance (Manhattan way) between the
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
79 * current point and the end point
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
80 * return values can be:
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
81 * Any value >= 0 : the h-value for this tile
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
82 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
83 typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
84
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
85 /*
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
86 * This function request the tiles around the current tile and put them in tiles_around
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
87 * tiles_around is never resetted, so if you are not using directions, just leave it alone.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
88 * Warning: never add more tiles_around than memory allocated for it.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
89 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
90 typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
91
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
92 /*
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
93 * If the End Node is found, this function is called.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
94 * It can do, for example, calculate the route and put that in an array
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
95 */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
96 typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
97
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
98 // For internal use, see aystar.c
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
99 typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
100 typedef int AyStar_Main(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
101 typedef int AyStar_Loop(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
102 typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
103 typedef void AyStar_Free(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
104 typedef void AyStar_Clear(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
105
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
106 struct AyStar {
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
107 /* These fields should be filled before initting the AyStar, but not changed
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
108 * afterwards (except for user_data and user_path)! (free and init again to change them) */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
109
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
110 /* These should point to the application specific routines that do the
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
111 * actual work */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
112 AyStar_CalculateG *CalculateG;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
113 AyStar_CalculateH *CalculateH;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
114 AyStar_GetNeighbours *GetNeighbours;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
115 AyStar_EndNodeCheck *EndNodeCheck;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
116 AyStar_FoundEndNode *FoundEndNode;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
117
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
118 /* These are completely untouched by AyStar, they can be accesed by
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
119 * the application specific routines to input and output data.
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
120 * user_path should typically contain data about the resulting path
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
121 * afterwards, user_target should typically contain information about
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
122 * what where looking for, and user_data can contain just about
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
123 * everything */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
124 void *user_path;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
125 void *user_target;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
126 uint user_data[10];
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
127
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
128 /* How many loops are there called before AyStarMain_Main gives
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
129 * control back to the caller. 0 = until done */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
130 byte loops_per_tick;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
131 /* If the g-value goes over this number, it stops searching
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
132 * 0 = infinite */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
133 uint max_path_cost;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
134 /* The maximum amount of nodes that will be expanded, 0 = infinite */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
135 uint max_search_nodes;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
136
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
137 /* These should be filled with the neighbours of a tile by
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
138 * GetNeighbours */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
139 AyStarNode neighbours[12];
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
140 byte num_neighbours;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
141
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
142 /* These will contain the methods for manipulating the AyStar. Only
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
143 * main() should be called externally */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
144 AyStar_AddStartNode *addstart;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
145 AyStar_Main *main;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
146 AyStar_Loop *loop;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
147 AyStar_Free *free;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
148 AyStar_Clear *clear;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
149 AyStar_CheckTile *checktile;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
150
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
151 /* These will contain the open and closed lists */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
152
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
153 /* The actual closed list */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
154 Hash ClosedListHash;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
155 /* The open queue */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
156 Queue OpenListQueue;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
157 /* An extra hash to speed up the process of looking up an element in
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
158 * the open list */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
159 Hash OpenListHash;
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
160 };
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
161
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
162
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
163 void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
164 int AyStarMain_Main(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
165 int AyStarMain_Loop(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
166 int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
167 void AyStarMain_Free(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
168 void AyStarMain_Clear(AyStar *aystar);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
169
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
170 /* Initialize an AyStar. You should fill all appropriate fields before
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
171 * callling init_AyStar (see the declaration of AyStar for which fields are
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
172 * internal */
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
173 void init_AyStar(AyStar *aystar, Hash_HashProc hash, uint num_buckets);
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
174
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
175
eabf4b86aed6 (svn r7759) -Merge: makefile rewrite. This merge features:
rubidium <rubidium@openttd.org>
parents:
diff changeset
176 #endif /* AYSTAR_H */