Geohashing

Today, I solved a speed problem, related to coloring the tiles based on visibility.

My first, crude solution was this:

• We have an incoming list of visible tiles, named visibleTiles.
• We have a list of all tiles, named allTiles.
• All tiles in allTiles is set to dark
• For each visibleTile in visibleTiles:
• for each tile in allTiles
• if tile.coordinate == visibleTile.coordinate 
• tile is set to bright

So if we have 'n' tiles and 'm' is visible of them, this will use 'n' times 'm' comparisons. Clearly not an effective method. It took half a minute to update a map containing 60 tiles, with about half of them visible.

So I thought maybe I should just hash the coordinates, and use them as an index key. Then, when I want to look for a tile with a specific coordinate, I'll hash that coordinate, and look for that hash in the list. (This requires of course, that each time I hash the same number, it will give the same result.)

Well, in C# there are two data containers for that: Hashtable and Dictionary. What is the difference?

You will declare a Hashtable this way:

Hashtable ht = new Hashtable();

That's all. No types, no anything. Dictionary is different:

Dictionary<Key, Value> dict = new Dictionary<Key, Value>();

So you can have type safety with Dictionary. But that's not all. Let's look at this example:

HexCoord hc1 = .new HexCoord(1, 1);
HexCoord hc2 = .new HexCoord(1, 1);

gameObject tile1 = new Tile(...);

// hc1 and hc2 are the same coordinate, but not the same
// object

Dictionary<HexCoord, GameObject> dict = new  Dictionary<HexCoord, GameObject();
dict.Add(hc1,  tile1);

// Now, if you just check if it is indeed in the list:
dict.ContainsKey(hc1); // True
// ...you will get true. But:
dict.Containskey(hc2); // False
// ...this is strange. What is the problem?

The problem is that internally, Dictionary uses ReferenceEqual for equality check. ReferenceEqual(o1, o2) only returns true, when o1 and o2 are pointing to the same location in memory. So in this case an IEqualityComparer class is needed. I won't go into details, google is your friend, and also I wanna go to sleep soon, have no energy to dive into this topic.

Point is, when you create a dictionary, you can feed it an IEqualityComparer, like this:

Dictionary<Key, Value> dict =
  new Dictionary<Key, Value>(new KeyComparer());

Also, if you would have used Hashtable instead of Dictionary, you would receive an error if you wrote:

Hashtable ht = new Hashtable(new KeyComparer());

...saying that the compiler couldn't typecast IEqualityComparer to int. I don't know why this happens, but it cost me at least half an hour thinking and googleing to realize that Dictionary doesn't have this porblem.

Now it works much faster then originally, in under a second for 60 tiles.