server/include/micropather.h

/*
Copyright (c) 2000-2003 Lee Thomason (www.grinninglizard.com)
Grinning Lizard Utilities.

This software is provided 'as-is', without any express or implied 
warranty. In no event will the authors be held liable for any 
damages arising from the use of this software.

Permission is granted to anyone to use this software for any 
purpose, including commercial applications, and to alter it and 
redistribute it freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must 
not claim that you wrote the original software. If you use this 
software in a product, an acknowledgment in the product documentation 
would be appreciated but is not required.

2. Altered source versions must be plainly marked as such, and 
must not be misrepresented as being the original software.

3. This notice may not be removed or altered from any source 
distribution.
*/


#ifndef GRINNINGLIZARD_MICROPATHER_INCLUDED
#define GRINNINGLIZARD_MICROPATHER_INCLUDED

/** @mainpage MicroPather
        
        MicroPather is a path finder and A* solver (astar or a-star) written in platform independent 
        C++ that can be easily integrated into existing code. MicroPather focuses on being a path 
        finding engine for video games but is a generic A* solver. MicroPather is open source, with 
        a license suitable for open source or commercial use.

        An overview of using MicroPather is in the <A HREF="../readme.htm">readme</A> or
        on the Grinning Lizard website: http://grinninglizard.com/micropather/
*/

#include <vector>
#include <list>
#include <assert.h>
#include <float.h>

#ifdef _DEBUG
        #ifndef DEBUG
                #define DEBUG
        #endif
#endif

#ifndef GRINLIZ_TYPES_INCLUDED
        #if defined(_MSC_VER) && (_MSC_VER >= 1400 )
                #include <stdlib.h>
                typedef uintptr_t               UPTR;
        #elif defined (__GNUC__) && (__GNUC__ >= 3 )
                #include <stdlib.h>
                typedef uintptr_t               UPTR;
        #else
                // Assume not 64 bit pointers. Get a new compiler.
                typedef unsigned UPTR;
        #endif
#endif

/*  USE_LIST and USE_BINARY_HASH change the some of details the pather algorithms. They
        are set optimally in my experiments, but different applications may benefit
        from a different combination of these #defines.
*/
#define USE_LIST
//#define USE_BINARY_HASH

namespace micropather
{
        const float FLT_BIG = FLT_MAX / 2.0f;   

        /**
                Used to pass the cost of states from the cliet application to MicroPather. This
                structure is copied in a vector.

                @sa AdjacentCost
        */
        struct StateCost
        {
                void* state;                    ///< The state as a void*
                float cost;                             ///< The cost to the state. Use FLT_MAX for infinite cost.
        };


        /**
                A pure abstract class used to define a set of callbacks. 
                The client application inherits from 
                this class, and the methods will be called when MicroPather::Solve() is invoked.

                The notion of a "state" is very important. It must have the following properties:
                - Unique
                - Unchanging (unless MicroPather::Reset() is called)

                If the client application represents states as objects, then the state is usually
                just the object cast to a void*. If the client application sees states as numerical
                values, (x,y) for example, then state is an encoding of these values. MicroPather
                never interprets or modifies the value of state.
        */
        class Graph
        {
          public:
                virtual ~Graph() {}
          
                /**
                        Return the least possible cost between 2 states. For example, if your pathfinding 
                        is based on distance, this is simply the straight distance between 2 points on the 
                        map. If you pathfinding is based on minimum time, it is the minimal travel time 
                        between 2 points given the best possible terrain.
                */
                virtual float LeastCostEstimate( void* stateStart, void* stateEnd ) = 0;

                /** 
                        Return the exact cost from the given state to all its neighboring states. This
                        may be called multiple times, or cached by the solver. It *must* return the same
                        exact values for every call to MicroPather::Solve(). It should generally be a simple,
                        fast function with no callbacks into the pather.
                */
                virtual void AdjacentCost( void* state, std::vector< micropather::StateCost > *adjacent ) = 0;

                /**
                        This function is only used in DEBUG mode - it dumps output to stdout. Since void* 
                        aren't really human readable, normally you print out some concise info (like "(1,2)") 
                        without an ending newline.

                        @note If you are using other grinning lizard utilities, you should use GLOUTPUT for output.
                */
                virtual void  PrintStateInfo( void* state ) = 0;
        };


        class PathNode;

        struct NodeCost
        {
                PathNode* node;
                float cost;
        };


        class PathNode
        {
                friend class none;      // Trashy trick to get rid of compiler warning, because
                                                // this class has a private constructor and destructor -
                                                // it can never be "new" or created on the stack, only
                                                // by special allocators.
          public:
                void Init(      unsigned _frame,
                                        void* _state,
                                        float _costFromStart, 
                                        float _estToGoal, 
                                        PathNode* _parent )
                {
                        state = _state;
                        costFromStart = _costFromStart;
                        estToGoal = _estToGoal;
                        totalCost = _costFromStart + _estToGoal;
                        parent = _parent;
                        frame = _frame;
                        numAdjacent = -1;
                        left = 0;
                        #ifdef USE_BINARY_HASH
                        right = 0;
                        #endif
                        #ifdef USE_LIST
                        next = 0;
                        prev = 0;
                        #endif
                        inOpen = 0;
                        inClosed = 0;
                }

                void Reuse( unsigned _frame, float _costFromStart, float _estToGoal, PathNode* _parent ) 
                {
                        costFromStart = _costFromStart;
                        estToGoal = _estToGoal;
                        parent = _parent;
                        frame = _frame;

                        inOpen = 0;
                        inClosed = 0;
                }

                void *state;                    // the client state
                float costFromStart;    // exact
                float estToGoal;                // estimated
                float totalCost;                // could be a function, but save some math.
                PathNode* parent;               // the parent is used to reconstruct the path
                unsigned frame;                 // unique id for this path, so the solver can distinguish
                                                                // correct from stale values

                enum {
                        /*
                                @enum MAX_CACHE. If you want to optimize "down deep" this is the way
                                to go. MAX_CACHE determines the number of adjacent nodes cached by 
                                MicroPather. If your nodes generally have 8 or 3 neighbors (common cases)
                                changing this may increase performance, sometimes dramatically.
                        */
                        MAX_CACHE = 4
                };
                // If there are 4 or less adjacent states, they will be cached as *nodes*.
                NodeCost adjacent[ MAX_CACHE ];
                int numAdjacent;                                        // -1  is unknown & needs to be queried
                                                                                        // 0-4 adjacent is known & in 'adjacent'
                                                                                        // 5+  known, but has to be queried from Graph

                PathNode* left;                 // Binary tree, where the 'state' is what is being compared.
                                                                // Also used as a "next" pointer for memory layout.
                #ifdef USE_BINARY_HASH
                PathNode* right;
                #endif
                #ifdef USE_LIST
                PathNode *next, *prev;
                #endif

                unsigned inOpen:1;
                unsigned inClosed:1;

                #ifdef USE_LIST
                void Unlink() {
                        next->prev = prev;
                        prev->next = next;
                        next = prev = 0;
                }
                void AddBefore( PathNode* addThis ) {
                        addThis->next = this;
                        addThis->prev = prev;
                        prev->next = addThis;
                        prev = addThis;
                }
                #ifdef DEBUG
                void CheckList()
                {
                        assert( totalCost == FLT_MAX );
                        for( PathNode* it = next; it != this; it=it->next ) {
                                assert( it->prev == this || it->totalCost >= it->prev->totalCost );
                                assert( it->totalCost <= it->next->totalCost );
                        }
                }
                #endif
                #endif

          private:
                PathNode();
                ~PathNode();
                PathNode( const PathNode& );
                void operator=( const PathNode& );
        };


        /**
                Create a MicroPather object to solve for a best path. Detailed usage notes are
                on the main page.
        */
        class MicroPather
        {
                friend class micropather::PathNode;

          public:
                enum
                {
                        SOLVED,
                        NO_SOLUTION,
                        START_END_SAME,
                };

                /**
                        Construct the pather, passing a pointer to the object that implements
                        the Graph callbacks.

                        @param graph            The "map" that implements the Graph callbacks.
                        @param allocate         The block size that the node cache is allocated from. In some
                                                                cases setting this parameter will improve the perfomance of
                                                                the pather.
                                                                - If you have a small map, for example the size of a chessboard, set allocate
                                                                  to be the number of states+1. 65 for a chessboard. This will allow
                                                                  MicroPather to used a fixed amount of memory.
                                                                - If your map is large, something like 1/4 the number of possible
                                                                  states is good. For example, Lilith3D normally has about 16,000 
                                                                  states, so 'allocate' should be about 4000.
                */
                MicroPather( Graph* graph, unsigned allocate = 250 );
                ~MicroPather();

                /**
                        Solve for the path from start to end.

                        @param startState       Input, the starting state for the path.
                        @param endState         Input, the ending state for the path.
                        @param path                     Output, a vector of states that define the path. Empty if not found.
                        @param totalCost        Output, the cost of the path, if found.
                        @return                         Success or failure, expressed as SOLVED, NO_SOLUTION, or START_END_SAME.
                */
                int Solve( void* startState, void* endState, std::vector< void* >* path, float* totalCost );

                /// Should be called whenever the cost between states or the connection between states changes.
                void Reset();

                /*  Deprecated. Too complex for the practical value.
                        @warning It is very easy to "miss" a state that needs to be changed and break the pather.

                        As described on the main page, it is possible to change the costs (but not the connections)
                        of states without calling Reset(). Be sure that all effected states are passed to
                        StateCostChange.
                */
                //void StateCostChange( void* state );

                /**
                        Return the "checksum" of the last path returned by Solve(). Useful for debugging,
                        and a quick way to see if 2 paths are the same.
                */
                UPTR Checksum() { return checksum; }
                
                void DumpHashTable();
                
                // Debugging function to return all states that were used
                // by the last "solve" 
                void StatesInPool( std::vector< void* >* stateVec );

          private:
                MicroPather( const MicroPather& );      // undefined and unsupported
                void operator=( const MicroPather ); // undefined and unsupported
                
                void GoalReached( PathNode* node, void* start, void* end, std::vector< void* > *path );
                void RecPathNodeWalk( PathNode* node, int* count );
                
                // Allocates and returns memory for a new, unititialized node.
                PathNode* AllocatePathNode();

                // Returns a path node that is ready to go. 
                // Strictly speaking, the name is somewhat misleading, as it
                // may be reused from the cache, but it will be ready for use regardless.
                PathNode* NewPathNode( void* state, float costFromStart, float estToEnd, PathNode* parent );

                // Finds the node for state, or returns null. 
                // A node that doesn't have a correct "frame" will never be found.
                PathNode* FindPathNode( void* state, bool findStale = false ); 

                NodeCost* GetNodeNeighbors( PathNode* node, std::vector< StateCost >* neighbor, std::vector< NodeCost >* neighborNode );

                #ifdef DEBUG
                void DumpStats();
                #endif

                enum {
                        #ifdef DEBUG_PATH
                        HASH_SIZE = 16,         // In debug mode, stress the allocators more than in release.
                                                                        // The HASH_SIZE must be a power of 2.
                        #else
                        HASH_SIZE = 256,
                        #endif
                };

        unsigned Hash( void* voidval ) {
                        UPTR val = (UPTR)voidval;
            return (unsigned)((HASH_SIZE-1) & ( val + (val>>8) + (val>>16) + (val>>24) ));
        }    
    
                const unsigned ALLOCATE;                        // how big a block of pathnodes to allocate at once
                const unsigned BLOCKSIZE;                       // how many useable pathnodes are in a block

                Graph* graph;
                PathNode* hashTable[HASH_SIZE];         // a fixed hashtable used to "jumpstart" a binary search
                PathNode* pathNodeMem;                          // pointer to root of PathNode blocks
                unsigned availMem;                                      // # PathNodes available in the current block
                unsigned pathNodeCount;                         // the # of PathNodes in use
                unsigned frame;                                         // incremented with every solve, used to determine
                                                                                        // if cached data needs to be refreshed
                UPTR checksum;                                  // the checksum of the last successful "Solve".

                std::vector< StateCost > neighborVec;   // really local vars to Solve, but put here to reduce memory allocation
                std::vector< NodeCost > neighborNodeVec; // really local vars to Solve, but put here to reduce memory allocation
        };

        inline PathNode* MicroPather::FindPathNode( void* state, bool findStale )
        {
                unsigned key = Hash( state );

                PathNode* root = hashTable[key];
                #ifdef USE_BINARY_HASH
                while ( root ) {
                        if ( root->state == state ) {
                                if ( findStale || root->frame == frame )
                                        return root;
                                else
                                        return 0;
                        }
                        else if ( state > root->state ) {
                                root = root->right;
                        }
                        else {
                                assert( state < root->state );
                                root = root->left;
                        }
                }
                #else
                while( root ) {
                        if ( root->state == state ) {
                                if ( findStale || root->frame == frame )
                                        return root;
                                else
                                        return 0;
                        }
                        else {
                                root = root->left;
                        }
                }
                #endif
                return 0;
        }               
};      // namespace grinliz

#endif

Revision:	1.1
Committed:	Thu May 24 00:24:11 2007 UTC (17 years ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-2_1
Log Message:	I like micropather so much without ever having used it that I included it. This is not to be used directly, it should be integrated into the map management code.
#	User	Rev	Content
1	root	1.1	/*
2			Copyright (c) 2000-2003 Lee Thomason (www.grinninglizard.com)
3			Grinning Lizard Utilities.
4
5			This software is provided 'as-is', without any express or implied
6			warranty. In no event will the authors be held liable for any
7			damages arising from the use of this software.
8
9			Permission is granted to anyone to use this software for any
10			purpose, including commercial applications, and to alter it and
11			redistribute it freely, subject to the following restrictions:
12
13			1. The origin of this software must not be misrepresented; you must
14			not claim that you wrote the original software. If you use this
15			software in a product, an acknowledgment in the product documentation
16			would be appreciated but is not required.
17
18			2. Altered source versions must be plainly marked as such, and
19			must not be misrepresented as being the original software.
20
21			3. This notice may not be removed or altered from any source
22			distribution.
23			*/
24
25
26			#ifndef GRINNINGLIZARD_MICROPATHER_INCLUDED
27			#define GRINNINGLIZARD_MICROPATHER_INCLUDED
28
29			/** @mainpage MicroPather
30
31			MicroPather is a path finder and A* solver (astar or a-star) written in platform independent
32			C++ that can be easily integrated into existing code. MicroPather focuses on being a path
33			finding engine for video games but is a generic A* solver. MicroPather is open source, with
34			a license suitable for open source or commercial use.
35
36			An overview of using MicroPather is in the <A HREF="../readme.htm">readme</A> or
37			on the Grinning Lizard website: http://grinninglizard.com/micropather/
38			*/
39
40			#include <vector>
41			#include <list>
42			#include <assert.h>
43			#include <float.h>
44
45			#ifdef _DEBUG
46			#ifndef DEBUG
47			#define DEBUG
48			#endif
49			#endif
50
51			#ifndef GRINLIZ_TYPES_INCLUDED
52			#if defined(_MSC_VER) && (_MSC_VER >= 1400 )
53			#include <stdlib.h>
54			typedef uintptr_t UPTR;
55			#elif defined (__GNUC__) && (__GNUC__ >= 3 )
56			#include <stdlib.h>
57			typedef uintptr_t UPTR;
58			#else
59			// Assume not 64 bit pointers. Get a new compiler.
60			typedef unsigned UPTR;
61			#endif
62			#endif
63
64			/* USE_LIST and USE_BINARY_HASH change the some of details the pather algorithms. They
65			are set optimally in my experiments, but different applications may benefit
66			from a different combination of these #defines.
67			*/
68			#define USE_LIST
69			//#define USE_BINARY_HASH
70
71			namespace micropather
72			{
73			const float FLT_BIG = FLT_MAX / 2.0f;
74
75			/**
76			Used to pass the cost of states from the cliet application to MicroPather. This
77			structure is copied in a vector.
78
79			@sa AdjacentCost
80			*/
81			struct StateCost
82			{
83			void* state; ///< The state as a void*
84			float cost; ///< The cost to the state. Use FLT_MAX for infinite cost.
85			};
86
87
88			/**
89			A pure abstract class used to define a set of callbacks.
90			The client application inherits from
91			this class, and the methods will be called when MicroPather::Solve() is invoked.
92
93			The notion of a "state" is very important. It must have the following properties:
94			- Unique
95			- Unchanging (unless MicroPather::Reset() is called)
96
97			If the client application represents states as objects, then the state is usually
98			just the object cast to a void*. If the client application sees states as numerical
99			values, (x,y) for example, then state is an encoding of these values. MicroPather
100			never interprets or modifies the value of state.
101			*/
102			class Graph
103			{
104			public:
105			virtual ~Graph() {}
106
107			/**
108			Return the least possible cost between 2 states. For example, if your pathfinding
109			is based on distance, this is simply the straight distance between 2 points on the
110			map. If you pathfinding is based on minimum time, it is the minimal travel time
111			between 2 points given the best possible terrain.
112			*/
113			virtual float LeastCostEstimate( void* stateStart, void* stateEnd ) = 0;
114
115			/**
116			Return the exact cost from the given state to all its neighboring states. This
117			may be called multiple times, or cached by the solver. It must return the same
118			exact values for every call to MicroPather::Solve(). It should generally be a simple,
119			fast function with no callbacks into the pather.
120			*/
121			virtual void AdjacentCost( void* state, std::vector< micropather::StateCost > *adjacent ) = 0;
122
123			/**
124			This function is only used in DEBUG mode - it dumps output to stdout. Since void*
125			aren't really human readable, normally you print out some concise info (like "(1,2)")
126			without an ending newline.
127
128			@note If you are using other grinning lizard utilities, you should use GLOUTPUT for output.
129			*/
130			virtual void PrintStateInfo( void* state ) = 0;
131			};
132
133
134			class PathNode;
135
136			struct NodeCost
137			{
138			PathNode* node;
139			float cost;
140			};
141
142
143			class PathNode
144			{
145			friend class none; // Trashy trick to get rid of compiler warning, because
146			// this class has a private constructor and destructor -
147			// it can never be "new" or created on the stack, only
148			// by special allocators.
149			public:
150			void Init( unsigned _frame,
151			void* _state,
152			float _costFromStart,
153			float _estToGoal,
154			PathNode* _parent )
155			{
156			state = _state;
157			costFromStart = _costFromStart;
158			estToGoal = _estToGoal;
159			totalCost = _costFromStart + _estToGoal;
160			parent = _parent;
161			frame = _frame;
162			numAdjacent = -1;
163			left = 0;
164			#ifdef USE_BINARY_HASH
165			right = 0;
166			#endif
167			#ifdef USE_LIST
168			next = 0;
169			prev = 0;
170			#endif
171			inOpen = 0;
172			inClosed = 0;
173			}
174
175			void Reuse( unsigned _frame, float _costFromStart, float _estToGoal, PathNode* _parent )
176			{
177			costFromStart = _costFromStart;
178			estToGoal = _estToGoal;
179			parent = _parent;
180			frame = _frame;
181
182			inOpen = 0;
183			inClosed = 0;
184			}
185
186			void *state; // the client state
187			float costFromStart; // exact
188			float estToGoal; // estimated
189			float totalCost; // could be a function, but save some math.
190			PathNode* parent; // the parent is used to reconstruct the path
191			unsigned frame; // unique id for this path, so the solver can distinguish
192			// correct from stale values
193
194			enum {
195			/*
196			@enum MAX_CACHE. If you want to optimize "down deep" this is the way
197			to go. MAX_CACHE determines the number of adjacent nodes cached by
198			MicroPather. If your nodes generally have 8 or 3 neighbors (common cases)
199			changing this may increase performance, sometimes dramatically.
200			*/
201			MAX_CACHE = 4
202			};
203			// If there are 4 or less adjacent states, they will be cached as nodes.
204			NodeCost adjacent[ MAX_CACHE ];
205			int numAdjacent; // -1 is unknown & needs to be queried
206			// 0-4 adjacent is known & in 'adjacent'
207			// 5+ known, but has to be queried from Graph
208
209			PathNode* left; // Binary tree, where the 'state' is what is being compared.
210			// Also used as a "next" pointer for memory layout.
211			#ifdef USE_BINARY_HASH
212			PathNode* right;
213			#endif
214			#ifdef USE_LIST
215			PathNode next, prev;
216			#endif
217
218			unsigned inOpen:1;
219			unsigned inClosed:1;
220
221			#ifdef USE_LIST
222			void Unlink() {
223			next->prev = prev;
224			prev->next = next;
225			next = prev = 0;
226			}
227			void AddBefore( PathNode* addThis ) {
228			addThis->next = this;
229			addThis->prev = prev;
230			prev->next = addThis;
231			prev = addThis;
232			}
233			#ifdef DEBUG
234			void CheckList()
235			{
236			assert( totalCost == FLT_MAX );
237			for( PathNode* it = next; it != this; it=it->next ) {
238			assert( it->prev == this \|\| it->totalCost >= it->prev->totalCost );
239			assert( it->totalCost <= it->next->totalCost );
240			}
241			}
242			#endif
243			#endif
244
245			private:
246			PathNode();
247			~PathNode();
248			PathNode( const PathNode& );
249			void operator=( const PathNode& );
250			};
251
252
253			/**
254			Create a MicroPather object to solve for a best path. Detailed usage notes are
255			on the main page.
256			*/
257			class MicroPather
258			{
259			friend class micropather::PathNode;
260
261			public:
262			enum
263			{
264			SOLVED,
265			NO_SOLUTION,
266			START_END_SAME,
267			};
268
269			/**
270			Construct the pather, passing a pointer to the object that implements
271			the Graph callbacks.
272
273			@param graph The "map" that implements the Graph callbacks.
274			@param allocate The block size that the node cache is allocated from. In some
275			cases setting this parameter will improve the perfomance of
276			the pather.
277			- If you have a small map, for example the size of a chessboard, set allocate
278			to be the number of states+1. 65 for a chessboard. This will allow
279			MicroPather to used a fixed amount of memory.
280			- If your map is large, something like 1/4 the number of possible
281			states is good. For example, Lilith3D normally has about 16,000
282			states, so 'allocate' should be about 4000.
283			*/
284			MicroPather( Graph* graph, unsigned allocate = 250 );
285			~MicroPather();
286
287			/**
288			Solve for the path from start to end.
289
290			@param startState Input, the starting state for the path.
291			@param endState Input, the ending state for the path.
292			@param path Output, a vector of states that define the path. Empty if not found.
293			@param totalCost Output, the cost of the path, if found.
294			@return Success or failure, expressed as SOLVED, NO_SOLUTION, or START_END_SAME.
295			*/
296			int Solve( void* startState, void* endState, std::vector< void* >* path, float* totalCost );
297
298			/// Should be called whenever the cost between states or the connection between states changes.
299			void Reset();
300
301			/* Deprecated. Too complex for the practical value.
302			@warning It is very easy to "miss" a state that needs to be changed and break the pather.
303
304			As described on the main page, it is possible to change the costs (but not the connections)
305			of states without calling Reset(). Be sure that all effected states are passed to
306			StateCostChange.
307			*/
308			//void StateCostChange( void* state );
309
310			/**
311			Return the "checksum" of the last path returned by Solve(). Useful for debugging,
312			and a quick way to see if 2 paths are the same.
313			*/
314			UPTR Checksum() { return checksum; }
315
316			void DumpHashTable();
317
318			// Debugging function to return all states that were used
319			// by the last "solve"
320			void StatesInPool( std::vector< void* >* stateVec );
321
322			private:
323			MicroPather( const MicroPather& ); // undefined and unsupported
324			void operator=( const MicroPather ); // undefined and unsupported
325
326			void GoalReached( PathNode* node, void* start, void* end, std::vector< void* > *path );
327			void RecPathNodeWalk( PathNode* node, int* count );
328
329			// Allocates and returns memory for a new, unititialized node.
330			PathNode* AllocatePathNode();
331
332			// Returns a path node that is ready to go.
333			// Strictly speaking, the name is somewhat misleading, as it
334			// may be reused from the cache, but it will be ready for use regardless.
335			PathNode* NewPathNode( void* state, float costFromStart, float estToEnd, PathNode* parent );
336
337			// Finds the node for state, or returns null.
338			// A node that doesn't have a correct "frame" will never be found.
339			PathNode* FindPathNode( void* state, bool findStale = false );
340
341			NodeCost* GetNodeNeighbors( PathNode* node, std::vector< StateCost >* neighbor, std::vector< NodeCost >* neighborNode );
342
343			#ifdef DEBUG
344			void DumpStats();
345			#endif
346
347			enum {
348			#ifdef DEBUG_PATH
349			HASH_SIZE = 16, // In debug mode, stress the allocators more than in release.
350			// The HASH_SIZE must be a power of 2.
351			#else
352			HASH_SIZE = 256,
353			#endif
354			};
355
356			unsigned Hash( void* voidval ) {
357			UPTR val = (UPTR)voidval;
358			return (unsigned)((HASH_SIZE-1) & ( val + (val>>8) + (val>>16) + (val>>24) ));
359			}
360
361			const unsigned ALLOCATE; // how big a block of pathnodes to allocate at once
362			const unsigned BLOCKSIZE; // how many useable pathnodes are in a block
363
364			Graph* graph;
365			PathNode* hashTable[HASH_SIZE]; // a fixed hashtable used to "jumpstart" a binary search
366			PathNode* pathNodeMem; // pointer to root of PathNode blocks
367			unsigned availMem; // # PathNodes available in the current block
368			unsigned pathNodeCount; // the # of PathNodes in use
369			unsigned frame; // incremented with every solve, used to determine
370			// if cached data needs to be refreshed
371			UPTR checksum; // the checksum of the last successful "Solve".
372
373			std::vector< StateCost > neighborVec; // really local vars to Solve, but put here to reduce memory allocation
374			std::vector< NodeCost > neighborNodeVec; // really local vars to Solve, but put here to reduce memory allocation
375			};
376
377			inline PathNode* MicroPather::FindPathNode( void* state, bool findStale )
378			{
379			unsigned key = Hash( state );
380
381			PathNode* root = hashTable[key];
382			#ifdef USE_BINARY_HASH
383			while ( root ) {
384			if ( root->state == state ) {
385			if ( findStale \|\| root->frame == frame )
386			return root;
387			else
388			return 0;
389			}
390			else if ( state > root->state ) {
391			root = root->right;
392			}
393			else {
394			assert( state < root->state );
395			root = root->left;
396			}
397			}
398			#else
399			while( root ) {
400			if ( root->state == state ) {
401			if ( findStale \|\| root->frame == frame )
402			return root;
403			else
404			return 0;
405			}
406			else {
407			root = root->left;
408			}
409			}
410			#endif
411			return 0;
412			}
413			}; // namespace grinliz
414
415			#endif
416