diff --git a/src/landscape.cpp b/src/landscape.cpp
--- a/src/landscape.cpp
+++ b/src/landscape.cpp
@@ -1286,7 +1286,7 @@ static const uint RIVER_HASH_SIZE = 8; /
  * @param dir The unused direction.
  * @return The hash for the tile.
  */
-static uint River_Hash(uint tile, uint dir)
+static uint River_Hash(TileIndex tile, Trackdir dir)
 {
 	return GB(TileHash(TileX(tile), TileY(tile)), 0, RIVER_HASH_SIZE);
 }
diff --git a/src/pathfinder/npf/npf.cpp b/src/pathfinder/npf/npf.cpp
--- a/src/pathfinder/npf/npf.cpp
+++ b/src/pathfinder/npf/npf.cpp
@@ -132,20 +132,20 @@ static uint NPFDistanceTrack(TileIndex t
 
 /**
  * Calculates a hash value for use in the NPF.
- * @param key1 The TileIndex of the tile to hash
- * @param key2 The Trackdir of the track on the tile.
+ * @param tile The TileIndex of the tile to hash
+ * @param dir The Trackdir of the track on the tile.
  *
  * @todo Think of a better hash.
  */
-static uint NPFHash(uint key1, uint key2)
+static uint NPFHash(TileIndex tile, Trackdir dir)
 {
 	/* TODO: think of a better hash? */
-	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;
-	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;
+	uint part1 = TileX(tile) & NPF_HASH_HALFMASK;
+	uint part2 = TileY(tile) & NPF_HASH_HALFMASK;
 
-	assert(IsValidTrackdir((Trackdir)key2));
-	assert(IsValidTile((TileIndex)key1));
-	return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE;
+	assert(IsValidTrackdir(dir));
+	assert(IsValidTile(tile));
+	return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * dir / TRACKDIR_END)) % NPF_HASH_SIZE;
 }
 
 static int32_t NPFCalcZero(AyStar *as, AyStarNode *current, OpenListNode *parent)
diff --git a/src/pathfinder/npf/queue.cpp b/src/pathfinder/npf/queue.cpp
--- a/src/pathfinder/npf/queue.cpp
+++ b/src/pathfinder/npf/queue.cpp
@@ -366,9 +366,9 @@ void Hash::Clear(bool free_values)
  * bucket, or nullptr if it is empty. prev can also be nullptr, in which case it is
  * not used for output.
  */
-HashNode *Hash::FindNode(uint key1, uint key2, HashNode** prev_out) const
+HashNode *Hash::FindNode(TileIndex tile, Trackdir dir, HashNode** prev_out) const
 {
-	uint hash = this->hash(key1, key2);
+	uint hash = this->hash(tile, dir);
 	HashNode *result = nullptr;
 
 	/* Check if the bucket is empty */
@@ -376,7 +376,7 @@ HashNode *Hash::FindNode(uint key1, uint
 		if (prev_out != nullptr) *prev_out = nullptr;
 		result = nullptr;
 	/* Check the first node specially */
-	} else if (this->buckets[hash].key1 == key1 && this->buckets[hash].key2 == key2) {
+	} else if (this->buckets[hash].tile == tile && this->buckets[hash].dir == dir) {
 		/* Save the value */
 		result = this->buckets + hash;
 		if (prev_out != nullptr) *prev_out = nullptr;
@@ -386,7 +386,7 @@ HashNode *Hash::FindNode(uint key1, uint
 		HashNode *node;
 
 		for (node = prev->next; node != nullptr; node = node->next) {
-			if (node->key1 == key1 && node->key2 == key2) {
+			if (node->tile == tile && node->dir == dir) {
 				/* Found it */
 				result = node;
 				break;
@@ -403,11 +403,11 @@ HashNode *Hash::FindNode(uint key1, uint
  * that value. Returns nullptr when the value was not present. The value returned
  * is _not_ free()'d!
  */
-void *Hash::DeleteValue(uint key1, uint key2)
+void *Hash::DeleteValue(TileIndex tile, Trackdir dir)
 {
 	void *result;
 	HashNode *prev; // Used as output var for below function call
-	HashNode *node = this->FindNode(key1, key2, &prev);
+	HashNode *node = this->FindNode(tile, dir, &prev);
 
 	if (node == nullptr) {
 		/* not found */
@@ -426,7 +426,7 @@ void *Hash::DeleteValue(uint key1, uint 
 		} else {
 			/* This was the last in this bucket
 			 * Mark it as empty */
-			uint hash = this->hash(key1, key2);
+			uint hash = this->hash(tile, dir);
 			this->buckets_in_use[hash] = false;
 		}
 	} else {
@@ -446,10 +446,10 @@ void *Hash::DeleteValue(uint key1, uint 
  * Sets the value associated with the given key pair to the given value.
  * Returns the old value if the value was replaced, nullptr when it was not yet present.
  */
-void *Hash::Set(uint key1, uint key2, void *value)
+void *Hash::Set(TileIndex tile, Trackdir dir, void *value)
 {
 	HashNode *prev;
-	HashNode *node = this->FindNode(key1, key2, &prev);
+	HashNode *node = this->FindNode(tile, dir, &prev);
 
 	if (node != nullptr) {
 		/* Found it */
@@ -461,7 +461,7 @@ void *Hash::Set(uint key1, uint key2, vo
 	/* It is not yet present, let's add it */
 	if (prev == nullptr) {
 		/* The bucket is still empty */
-		uint hash = this->hash(key1, key2);
+		uint hash = this->hash(tile, dir);
 		this->buckets_in_use[hash] = true;
 		node = this->buckets + hash;
 	} else {
@@ -470,8 +470,8 @@ void *Hash::Set(uint key1, uint key2, vo
 		prev->next = node;
 	}
 	node->next = nullptr;
-	node->key1 = key1;
-	node->key2 = key2;
+	node->tile = tile;
+	node->dir = dir;
 	node->value = value;
 	this->size++;
 	return nullptr;
@@ -481,9 +481,9 @@ void *Hash::Set(uint key1, uint key2, vo
  * Gets the value associated with the given key pair, or nullptr when it is not
  * present.
  */
-void *Hash::Get(uint key1, uint key2) const
+void *Hash::Get(TileIndex tile, Trackdir dir) const
 {
-	HashNode *node = this->FindNode(key1, key2, nullptr);
+	HashNode *node = this->FindNode(tile, dir, nullptr);
 
 	return (node != nullptr) ? node->value : nullptr;
 }
diff --git a/src/pathfinder/npf/queue.h b/src/pathfinder/npf/queue.h
--- a/src/pathfinder/npf/queue.h
+++ b/src/pathfinder/npf/queue.h
@@ -10,6 +10,9 @@
 #ifndef QUEUE_H
 #define QUEUE_H
 
+#include "../../tile_type.h"
+#include "../../track_type.h"
+
 //#define HASH_STATS
 
 
@@ -58,8 +61,8 @@ struct BinaryHeap {
  * Hash
  */
 struct HashNode {
-	uint key1;
-	uint key2;
+	TileIndex tile;
+	Trackdir dir;
 	void *value;
 	HashNode *next;
 };
@@ -67,7 +70,7 @@ struct HashNode {
  * 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);
+typedef uint Hash_HashProc(TileIndex tile, Trackdir dir);
 struct Hash {
 	/* The hash function used */
 	Hash_HashProc *hash;
@@ -83,10 +86,10 @@ struct Hash {
 
 	void Init(Hash_HashProc *hash, uint num_buckets);
 
-	void *Get(uint key1, uint key2) const;
-	void *Set(uint key1, uint key2, void *value);
+	void *Get(TileIndex tile, Trackdir dir) const;
+	void *Set(TileIndex tile, Trackdir dir, void *value);
 
-	void *DeleteValue(uint key1, uint key2);
+	void *DeleteValue(TileIndex tile, Trackdir dir);
 
 	void Clear(bool free_values);
 	void Delete(bool free_values);
@@ -103,7 +106,7 @@ protected:
 #ifdef HASH_STATS
 	void PrintStatistics() const;
 #endif
-	HashNode *FindNode(uint key1, uint key2, HashNode** prev_out) const;
+	HashNode *FindNode(TileIndex tile, Trackdir dir, HashNode** prev_out) const;
 };
 
 #endif /* QUEUE_H */