summaryrefslogtreecommitdiff
path: root/aystar.h
diff options
context:
space:
mode:
authorrubidium <rubidium@openttd.org>2007-01-02 19:19:48 +0000
committerrubidium <rubidium@openttd.org>2007-01-02 19:19:48 +0000
commit66bbf336c6af7353ef0aeed58002c46543b30635 (patch)
treead4a63860df2626b22f77e7dac712e958bea54cb /aystar.h
parentccc0a3f4dbf58c005b22341ac8874252924690cd (diff)
downloadopenttd-66bbf336c6af7353ef0aeed58002c46543b30635.tar.xz
(svn r7759) -Merge: makefile rewrite. This merge features:
- A proper ./configure, so everything needs to be configured only once, not for every make. - Usage of makedepend when available. This greatly reduces the time needed for generating the dependencies. - A generator for all project files. There is a single file with sources, which is used to generate Makefiles and the project files for MSVC. - Proper support for OSX universal binaries. - Object files for non-MSVC compiles are also placed in separate directories, making is faster to switch between debug and release compiles and it does not touch the directory with the source files. - Functionality to make a bundle of all needed files for for example a nightly or distribution of a binary with all needed GRFs and language files. Note: as this merge moves almost all files, it is recommended to make a backup of your working copy before updating your working copy.
Diffstat (limited to 'aystar.h')
-rw-r--r--aystar.h179
1 files changed, 0 insertions, 179 deletions
diff --git a/aystar.h b/aystar.h
deleted file mode 100644
index 4920a37d4..000000000
--- a/aystar.h
+++ /dev/null
@@ -1,179 +0,0 @@
-/* $Id$ */
-
-/*
- * This file has the header for AyStar
- * AyStar is a fast pathfinding routine and is used for things like
- * AI_pathfinding and Train_pathfinding.
- * For more information about AyStar (A* Algorithm), you can look at
- * http://en.wikipedia.org/wiki/A-star_search_algorithm
- */
-
-#ifndef AYSTAR_H
-#define AYSTAR_H
-
-#include "queue.h"
-
-//#define AYSTAR_DEBUG
-enum {
- AYSTAR_FOUND_END_NODE,
- AYSTAR_EMPTY_OPENLIST,
- AYSTAR_STILL_BUSY,
- AYSTAR_NO_PATH,
- AYSTAR_LIMIT_REACHED,
- AYSTAR_DONE
-};
-
-enum{
- AYSTAR_INVALID_NODE = -1,
-};
-
-typedef struct AyStarNode AyStarNode;
-struct AyStarNode {
- TileIndex tile;
- uint direction;
- uint user_data[2];
-};
-
-// The resulting path has nodes looking like this.
-typedef struct PathNode PathNode;
-struct PathNode {
- AyStarNode node;
- // The parent of this item
- PathNode *parent;
-};
-
-// For internal use only
-// We do not save the h-value, because it is only needed to calculate the f-value.
-// h-value should _always_ be the distance left to the end-tile.
-typedef struct OpenListNode OpenListNode;
-struct OpenListNode {
- int g;
- PathNode path;
-};
-
-typedef struct AyStar AyStar;
-/*
- * This function is called to check if the end-tile is found
- * return values can be:
- * AYSTAR_FOUND_END_NODE : indicates this is the end tile
- * AYSTAR_DONE : indicates this is not the end tile (or direction was wrong)
- */
-/*
- * The 2nd parameter should be OpenListNode, and NOT AyStarNode. AyStarNode is
- * part of OpenListNode and so it could be accessed without any problems.
- * The good part about OpenListNode is, and how AIs use it, that you can
- * access the parent of the current node, and so check if you, for example
- * don't try to enter the file tile with a 90-degree curve. So please, leave
- * this an OpenListNode, it works just fine -- TrueLight
- */
-typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current);
-
-/*
- * This function is called to calculate the G-value for AyStar Algorithm.
- * return values can be:
- * AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
- * Any value >= 0 : the g-value for this tile
- */
-typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
-
-/*
- * This function is called to calculate the H-value for AyStar Algorithm.
- * Mostly, this must result the distance (Manhattan way) between the
- * current point and the end point
- * return values can be:
- * Any value >= 0 : the h-value for this tile
- */
-typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
-
-/*
- * This function request the tiles around the current tile and put them in tiles_around
- * tiles_around is never resetted, so if you are not using directions, just leave it alone.
- * Warning: never add more tiles_around than memory allocated for it.
- */
-typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
-
-/*
- * If the End Node is found, this function is called.
- * It can do, for example, calculate the route and put that in an array
- */
-typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
-
-// For internal use, see aystar.c
-typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);
-typedef int AyStar_Main(AyStar *aystar);
-typedef int AyStar_Loop(AyStar *aystar);
-typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
-typedef void AyStar_Free(AyStar *aystar);
-typedef void AyStar_Clear(AyStar *aystar);
-
-struct AyStar {
-/* These fields should be filled before initting the AyStar, but not changed
- * afterwards (except for user_data and user_path)! (free and init again to change them) */
-
- /* These should point to the application specific routines that do the
- * actual work */
- AyStar_CalculateG *CalculateG;
- AyStar_CalculateH *CalculateH;
- AyStar_GetNeighbours *GetNeighbours;
- AyStar_EndNodeCheck *EndNodeCheck;
- AyStar_FoundEndNode *FoundEndNode;
-
- /* These are completely untouched by AyStar, they can be accesed by
- * the application specific routines to input and output data.
- * user_path should typically contain data about the resulting path
- * afterwards, user_target should typically contain information about
- * what where looking for, and user_data can contain just about
- * everything */
- void *user_path;
- void *user_target;
- uint user_data[10];
-
- /* How many loops are there called before AyStarMain_Main gives
- * control back to the caller. 0 = until done */
- byte loops_per_tick;
- /* If the g-value goes over this number, it stops searching
- * 0 = infinite */
- uint max_path_cost;
- /* The maximum amount of nodes that will be expanded, 0 = infinite */
- uint max_search_nodes;
-
- /* These should be filled with the neighbours of a tile by
- * GetNeighbours */
- AyStarNode neighbours[12];
- byte num_neighbours;
-
- /* These will contain the methods for manipulating the AyStar. Only
- * main() should be called externally */
- AyStar_AddStartNode *addstart;
- AyStar_Main *main;
- AyStar_Loop *loop;
- AyStar_Free *free;
- AyStar_Clear *clear;
- AyStar_CheckTile *checktile;
-
- /* These will contain the open and closed lists */
-
- /* The actual closed list */
- Hash ClosedListHash;
- /* The open queue */
- Queue OpenListQueue;
- /* An extra hash to speed up the process of looking up an element in
- * the open list */
- Hash OpenListHash;
-};
-
-
-void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g);
-int AyStarMain_Main(AyStar *aystar);
-int AyStarMain_Loop(AyStar *aystar);
-int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
-void AyStarMain_Free(AyStar *aystar);
-void AyStarMain_Clear(AyStar *aystar);
-
-/* Initialize an AyStar. You should fill all appropriate fields before
- * callling init_AyStar (see the declaration of AyStar for which fields are
- * internal */
-void init_AyStar(AyStar *aystar, Hash_HashProc hash, uint num_buckets);
-
-
-#endif /* AYSTAR_H */