#ifndef _ALGORITHM_H #define _ALGORITHM_H ////////////////////////////////////////////////////////////////// // // // ALGORITHMS // // // // A home for interesting and useful algorithm implementations. // // Link to -lalgorithm when using functions from this library. // // // // Contents: // // // // 1. A* Search Algorithm, 01.2007 aralbrec // // // ////////////////////////////////////////////////////////////////// #include #include /*****************************************************************/ // 1. A* Search Algorithm, 01.2007 aralbrec // See http://en.wikipedia.org/wiki/A%2A_search_algorithm // Program must also be linked with -ladt to access priority queue /*****************************************************************/ // // The A* Search Algorithm finds the shortest path between any // two nodes. It is a best-search-first algorithm, meaning it // pursues paths of lowest cost first. This implementation of A* // uses the heap implementation from the Abstract Data Types // library as a priority queue. Each path is stored as an 8-byte // block, which is dynamically allocated by A* functions through // the usual u_malloc() and u_free() functions (see the wiki topic // on memory allocation for details if you are unfamiliar with // how z88dk libraries implicitly allocate dynamic memory). // // To use A*, you must provide functions with the following // signatures: // // a. void [[]] astar_TestAndClose(uint node); // // Mark the node as 'closed' and return carry flag set // if the node was already closed previously. C functions // should make use of the special z88dk keywords return_c() // and return_nc() to exit with known carry flag state. // // b. void astar_Successor(uint *node, uint *cost); // // This function enumerates all the neighbours of node, one // after the other on successive calls. With node not -1, a // new start node is indicated. If node is -1, the next // neighbour of the last valid node supplied should be returned. // This function indicates to the algorithm the connectivity // of the map. // // If node is not -1, write into node its first neighbour // and the cost of moving from that node to this neighbour // into cost. // // If node is -1, write the next neighbour into node and the // cost of moving from the last valid node to this neighbour // into cost. // // Return with carry flag set when there are no more neighbours // and reset if the neighbour returned is valid. C functions // should use the z88dk keywords return_c() and return_c() // to exit with known carry flag state. // // c. uint [[]] astar_DestCost(uint node) // // (optional) Estimate the cost from the node indicated to // the destination node. These nodes may be widely separated // so a cartesian distance metric is probably simplest. // // This function is only called by astar_EstimateBestPath(). // If astar_EstimateBestPath() is not used, this function need // not be defined. // // Prior to calling the A* search algorithm, function pointers // must be declared globally and assigned to point at the above // function implementations: // // void *astar_TestAndClose, *astar_Successor, *astar_DestCost; // // Additionally a number of variables A* uses must be declared // globally and initialized: // // uint astar_startNode; /* init to starting node */ // uint astar_destNode; /* init to finish node */ // // void **astar_queue; /* address of array of 2-byte entries */ // uint astar_queueSize; /* max num entries available in array */ // uint astar_queueN; /* no init necessary */ // // A* uses the Abstract Data Type library's heap data type to // implement the priority queue. The latter three variables // indicate the location of a static array to use for the heap, // the max size of the heap, and the current number of entries // in the heap. See the ADT library documentation for more // details. // struct astar_path { // 7 bytes uint node; // +0 last node of this path uchar ref_count; // +2 reference count for this path struct astar_path *prefix; // +3 path leading to this node uint cost; // +5 cost of this path 0-65535 }; extern struct astar_path __LIB__ *astar_Search(void); extern struct astar_path __LIB__ *astar_SearchResume(struct astar_path *p) __z88dk_fastcall; extern struct astar_path __LIB__ *astar_EstimateBestPath(struct astar_path *p) __z88dk_fastcall; extern uint __LIB__ astar_PathLength(struct astar_path *p) __z88dk_fastcall; extern uint __LIB__ *astar_WalkPath(struct astar_path *p, uint *node_arr, uint n) __smallc; extern uint __LIB__ *astar_WalkPath_callee(struct astar_path *p, uint *node_arr, uint n) __smallc __z88dk_callee; extern void __LIB__ astar_DeletePath(struct astar_path *p) __z88dk_fastcall; extern void __LIB__ astar_CleanUp(struct astar_path *p) __z88dk_fastcall; #define astar_WalkPath(a,b,c) astar_WalkPath_callee(a,b,c) #endif