summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authormatthijs <matthijs@openttd.org>2005-04-07 19:19:16 +0000
committermatthijs <matthijs@openttd.org>2005-04-07 19:19:16 +0000
commitda3621c1804e6da9cefd712da9d0dd48fff61add (patch)
tree034da873c7ef2d41762a674839ff36339133a41e
parent9c3813e21374c71da7c1c49cf52d68546815c1b0 (diff)
downloadopenttd-da3621c1804e6da9cefd712da9d0dd48fff61add.tar.xz
(svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is easily changable now.
- Codechange: [NPF] Improved the NPF hash calculation slightly. - Codechange: [NPF] Increased hash size, should speed up somewhat.
-rw-r--r--npf.c12
-rw-r--r--npf.h7
-rw-r--r--queue.c49
-rw-r--r--queue.h6
4 files changed, 69 insertions, 5 deletions
diff --git a/npf.c b/npf.c
index 15f11dfcb..66061d1ae 100644
--- a/npf.c
+++ b/npf.c
@@ -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;
diff --git a/npf.h b/npf.h
index be2fb95c1..6f665ec7e 100644
--- a/npf.h
+++ b/npf.h
@@ -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 */
diff --git a/queue.c b/queue.c
index 21c163688..8602bb673 100644
--- a/queue.c
+++ b/queue.c
@@ -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++)
{
diff --git a/queue.h b/queue.h
index 56ecd2a3e..c4a1bf0ee 100644
--- a/queue.h
+++ b/queue.h
@@ -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