Original author: Pierre Sarrazin. Public-domain package. Source: http://sarrazip.com/dev/astar-0.1.0.tar.gz Archive SHA-256: acd2d5e2ad709892cb7609f5e53387cbbfe7364e675abb5e4f2a5c806cd0fc7c
73 lines
2.0 KiB
C
73 lines
2.0 KiB
C
#ifndef _astar_h
|
|
#define _astar_h
|
|
|
|
#include <coco.h>
|
|
|
|
|
|
typedef struct AStarNode
|
|
{
|
|
void *userData; // can be used to point to more data about this node
|
|
byte searchSet; // enum SearchSet
|
|
|
|
// These describe the relation of this node with the grid of nodes that it belongs to.
|
|
BOOL canGoEast;
|
|
BOOL canGoSouth;
|
|
|
|
// Used by the A* algorithm.
|
|
word gScore;
|
|
word fScore;
|
|
struct AStarNode *cameFrom; // node that precedes this one in a path
|
|
} AStarNode;
|
|
|
|
|
|
// Represents a grid of nodes to be searched.
|
|
//
|
|
typedef struct AStarGraph
|
|
{
|
|
AStarNode *nodes; // row-major matrix of nodes
|
|
size_t width; // number of matrix columns
|
|
size_t height; // number of matrix rows
|
|
} AStarGraph;
|
|
|
|
|
|
typedef struct AStarPathIterator
|
|
{
|
|
AStarGraph *graph;
|
|
AStarNode *node;
|
|
} AStarPathIterator;
|
|
|
|
|
|
void astar_initNode(AStarNode *node,
|
|
void *userData,
|
|
byte canGoEast, byte canGoSouth);
|
|
|
|
|
|
// Returns non-zero if a path is found from (startX, startY) to (goalX, goalY).
|
|
// In this case, astar_startPathIteration() can be called to obtain this path.
|
|
// Returns zero if no path is found.
|
|
//
|
|
BOOL astar_searchGrid(AStarGraph *graph,
|
|
size_t startX, size_t startY,
|
|
size_t goalX, size_t goalY);
|
|
|
|
|
|
// Starts an iteration through the graph that goes from the specified goal position
|
|
// to the starting node specified to the most recent call to astar_searchGrid().
|
|
//
|
|
// goalX, goalY: Must be the goal position found by a successful call to astar_searchGrid().
|
|
// After calling this, call astar_advancePathIteration() until it returns NULL.
|
|
//
|
|
void astar_startPathIteration(AStarPathIterator *iter,
|
|
AStarGraph *graph,
|
|
size_t goalX, size_t goalY);
|
|
|
|
|
|
// Returns the address of the next node in the iteration,
|
|
// or NULL if the iteration is at the end.
|
|
// *iter must have been initialized by astar_startPathIteration().
|
|
//
|
|
AStarNode *astar_advancePathIteration(AStarPathIterator *iter);
|
|
|
|
|
|
#endif /* _astar_h */
|