diff options
| -rw-r--r-- | npf.c | 12 | ||||
| -rw-r--r-- | npf.h | 7 | ||||
| -rw-r--r-- | queue.c | 49 | ||||
| -rw-r--r-- | queue.h | 6 |
4 files changed, 69 insertions, 5 deletions
@@ -102,9 +102,19 @@ static const uint _trackdir_length[14] = { uint NTPHash(uint key1, uint key2) { + /* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */ return PATHFIND_HASH_TILE(key1); } +uint NPFHash(uint key1, uint key2) +{ + /* TODO: think of a better hash? */ + uint part1 = TileX(key1) & NPF_HASH_HALFMASK; + uint part2 = TileY(key1) & NPF_HASH_HALFMASK; + /* The value of 14 below is based on the maximum value of key2 (13) */ + return ((((part1 << NPF_HASH_HALFBITS) | part2)) + (NPF_HASH_SIZE * key2 / 14)) % NPF_HASH_SIZE; +} + int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) { return 0; } @@ -809,7 +819,7 @@ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, Tran void InitializeNPF(void) { - init_AyStar(&_npf_aystar, NTPHash, 1024); + init_AyStar(&_npf_aystar, NPFHash, NPF_HASH_SIZE); _npf_aystar.loops_per_tick = 0; _npf_aystar.max_path_cost = 0; _npf_aystar.max_search_nodes = 0; @@ -8,6 +8,13 @@ //#define NPF_DEBUG //#define NPF_MARKROUTE //Mark the routes considered by the pathfinder by //mowing grass +enum { + NPF_HASH_BITS = 12, /* The size of the hash used in pathfinding. Just changing this value should be sufficient to change the hash size. Should be an even value. */ + /* Do no change below values */ + NPF_HASH_SIZE = 1 << NPF_HASH_BITS, + NPF_HASH_HALFBITS = NPF_HASH_BITS / 2, + NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1 +}; typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */ TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */ @@ -443,9 +443,10 @@ Queue* new_BinaryHeap(uint max_size) { * Hash */ -void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets) { +void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets) { /* Allocate space for the Hash, the buckets and the bucket flags */ - int i; + uint i; + uint max_hash; assert(h); #ifdef HASH_DEBUG debug("Allocated hash: %p", h); @@ -502,10 +503,54 @@ void delete_Hash(Hash* h, bool free_values) { free(h); } +void stat_Hash(Hash* h) +{ + uint used_buckets = 0; + uint max_collision = 0; + uint max_usage = 0; + uint usage[200]; + uint i,j; + uint collision; + HashNode* node; + + for (i=0;i<200;i++) usage[i] = 0; + for (i=0;i<h->num_buckets;i++) { + collision = 0; + if (h->buckets_in_use[i]) { + used_buckets++; + node = &h->buckets[i]; + while (node != NULL) { + collision++; + node = node->next; + } + if (collision > max_collision) max_collision = collision; + } + if (collision > 199) collision = 199; + usage[collision]++; + if (collision >0 && usage[collision] >= max_usage) max_usage = usage[collision]; + } + printf("---\nHash size: %d\nNodes used: %d\nNon empty buckets: %d\nMax collision: %d\n", h->num_buckets, h->size, used_buckets, max_collision); + printf("{ "); + for (i=0;i<=max_collision;i++) + if (usage[i]) { + printf("%d:%d ", i, usage[i]); + /*if (i>0) + for (j=0;j<(usage[i] * 160 / 800);j++) + printf("#"); + printf("\n"); + */ + } + printf ("}\n"); +} + void clear_Hash(Hash* h, bool free_values) { uint i; HashNode* node; +#ifdef HASH_STATS + if (h->size > 2000) + stat_Hash(h); +#endif /* Iterate all buckets */ for (i=0;i<h->num_buckets;i++) { @@ -4,6 +4,7 @@ //#define NOFREE //#define QUEUE_DEBUG //#define HASH_DEBUG +//#define HASH_STATS typedef struct Queue Queue; @@ -142,7 +143,8 @@ struct HashNode { void* value; HashNode* next; }; -/* Generates a hash code from the given key pair. You should make sure that +/** + * Generates a hash code from the given key pair. You should make sure that * the resulting range is clearly defined. */ typedef uint Hash_HashProc(uint key1, uint key2); @@ -184,7 +186,7 @@ void* Hash_Get(Hash* h, uint key1, uint key2); Hash* new_Hash(Hash_HashProc* hash, int num_buckets); /* Builds a new hash in an existing struct. Make sure that hash() always * returns a hash less than num_buckets! Call delete_hash after use */ -void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets); +void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets); /* * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash * & friends. If free is true, it will call free() on all the values that |