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.

Visibility

I want this game to be impossible to cheat in without access to the server. (By cheating I mean maphacks and things like that. DDoS & co. are entirely other stories.) So I only send informations to the client that they have access to.

This means the server has to calculate, what can each client see, then - using this list - filter all the units and towns, and send them to each clients. Now, since I have to calculate all the tiles that are visible to a client, why would I choose not to send this info to the clients as well? This way, the client code doesn't need to calculate visible tiles.

So this is what I did. After the client receives the list of visible tiles, it sets their color to white (meaning they will be drawn in their original color), and the rest to grey (meaning they will be darker). The only problem so far is that I can't index the tiles by their coordinates (yet), so it takes half a minute to set each tile to the correct color. But at least now it works.

I've made a quick test to check if the visibility rules are calculated correctly on the server. Here is the result:

For the test, I used the Forest, Grass and Mountain tiles. The empty tile is opaque and invisible, so I didn't need to block out visibility with HighMountain tiles. Okay, let's go through all seven tests:

1. You can't look into a group of forest tiles from another group of forest tiles.
2. However, from a mountain tile, you can see other mountain tiles.
3. You can't see forest or mountain tiles from outside.
4. But you can look outside from mountains...
5. ...and from forests.
6. Mountains will block your vision through forests.
7. Forests will block your vision from mountains.

One might argue that why can't one see the other mountains in test 7. - forests shouldn't block the sight from mountains, even if you can't look into them. While this argument is correct, the solution is not trivial - it would require another visibility type, or some height information, or something else.

Or maybe I just shouldn't allow mountains to be visible from other mountains. But playtests will tell. If it is counter-intuitive, I will change it.

Setting up Haskell with Atom on Windows

1. Install MinGHC from https://github.com/fpco/minghc
2. Install Atom from http://atom.io/
3. Do your Haskell-configurations
1. Open command line, then "cabal update"
2. Modify the cabal config file in AppData\Roaming\cabal - enable profiling libraries and documentation
3. Set up your sandboxes
4. Install ghc-mod (cabal install ghc-mod)
5. In atom, install the Language-haskell package
6. In cmd, run this command: "apm install language-haskell haskell-ghc-mod ide-haskell autocomplete-haskell" (This will install the ide-haskell package.)
7. ???
8. Profit

The end result will be something like this:

The Best Programming Font Ever, and waving goodbye to Notepad++

Yes, it happened. I changed my default text editor from notepad++. Why?

Yesterday I have changed the default font used by npp. What happened after that, is npp had its colors mixed. Most notably, the background color went from a convenient grayish color to some bright orange. I don't know if I did something stupid (maybe pressed some buttons when I thought I'm writing somewhere else, probably in the browser's address bar), or it was npp's mistake, but I don't really care. I decided to look around in the world of not-so-IDE-but-more-advanced-than-notepad-kind-of text editors.

What I found is that there are mainly four contenders: SublimeText, Brackets, LightTable and Atom. SublimeText is propriety, LightTable is Clojure-oriented at the moment, so it leaves Brackets and Atom. Adfter eading this comparison I have decided to try my luck with Atom (which is developed by the devs of GitHub).

First, I saw their trailer video. I have to say I think it is hilariously well done. They seem to have a sense of style, which is good. Next, I have installed it, which wasn't hard (that is, after I finally found the download button on their site). Then I installed the "Language Haskell" package, which gave me syntax highlight.

When I used Notepad++, I had a little script, that ran "ghc -fno-code Main.hs" when I pressed Ctrl-F7. How should I do it in Atom? After reading about a few other packages, I settled at Process Palette, which is a little tool that enables me to create hotkeys and assign commands to them (among other things). The code snippet was easy to write:

{
   "action" : "Typecheck Haskell code",
   "command" : "ghc -fno-code Main.hs",
   "outputTarget" : "void",
   "keystroke" : "ctrl-f7",
   "successMessage" : "{stdout}",
   "errorMessage" : "{stderr}",
   "fatalMessage" : "{stderr}"
}

(I wanted to feed the output to the little message window instead of the panel on the bottom side of the window, because I like style. But that's just my personal thing.)

• EDIT: It seems I don't need this process-palette extension and the code snippet, as ide-haskell also has a code-checking feature. Testing it.
• EDIT 2: Much better. Wrote a new blog post about it.

But there was another problem: when I presset Alt Gr + B (which is the character '{' for me), it didn't write a bracket, but instead jumped to the beginning of the line. This is because Atom has a key binding on Ctrl + Alt + B. So I had to disable this hotkey - to do this, just go to Settings -> Keybindings, select Ctrl + Alt + B, click on copy, open the keymap file, paste the command you have just copied, and delete the string from the command part. This way, you will have an empty action assigned to the key combo, and it lets you write the bracket.

• EDIT: instead of leaving it empty, you should write 'unset!', because otherwise weird things (like cryptic error messages) will happen. So this is the correct snippet:

 'atom-text-editor':
  'ctrl-alt-b': 'unset!'

You might also want to turn off the feature that automatically completes the brackets when you type in the opening part. it can be done by going to Settings -> Packages, searching for "Bracket-matcher", and clicking on Settings - you can turn off this feature there.

I also found The Best Programming Font Ever, namely "Input" - it finally has everything done right - it is readable, it distinguishes the il1O0o characters well, and what's more - it is configurable! You can set a few settings on its webpage (like character strength, line width, character width, the type of the letter 'a', 'g', etc...), and then you can download the customized version.

After I have done everything, it looked like this:

I'm excited about Atom at this moment. It is still a little rough around the edges, but looks very promising.

Units between tiles and attacking

Having the requirement that units travel between tiles for one or two turns is nice, but it poses a problem: when a unit is between two tiles, what happens when someone would arrive to one of those tiles?

Moreover, there is another problem: what if two units of the same owner want to move to the same tile at once? I made it a clear rule that one tile could be occupied by only one unit at a time.

Ok, let's tackle the first problem: say there is a unit (blue circle) trying to go from Tile A to Tile B. It's the start of the turn. Now let's imagine there is another unit (red circle), that is trying to move to Tile A.

Let's say their speed are 0.5. (I should've painted mountains instead of grasses. Whatever.) At the end of the turn, their positions are like this:

I quickly discarded the idea that we should use the border of tiles as places, too, because that would really complicate things - like calculating visibility, calculating speed, and so on.

But which tile should we take into account when a unit is between tiles? The target tile? The starting tile? Both?

If wou would take both into accounts, then the red unit would kill the blue. This is because the target of the red Infantry unit is the same as the origin of the blue Archer. But at the beginning of the turn, there were no overlapping tiles. So this idea is not consistent - it is possible to kill a unit when both of the attacker and defender are moving. Idea scrapped.

Okay, then let's look at the possibility when we use the target tile. Here, blue tries to escape by going to the mountains.

We know that going to the mountain halves a unit's speed. So going by common sense, red should capture blue. Let's see, what happens if we take the target tile into account:

Seems kind of counter-intuitive. Okay, red could capture blue in the next turn, but still, this is plain bad for a perfectionist like me. If we would take into account the original tile the unit was on, everything would work as they should.

The result is that we will take the original tile into account. But what about multiple units going to the same tile?

Since I don't allow more than one unit on any single tile, I would have to kill some units. But which one? It seems I would have to kill all of them. Which is kind of unfortunate if the user only misclicked, or was tired, and didn't think through where they want to place their units. One possibility would be to have the regular "move and attack" command, and there a simple "attack" command as well. The "move and attack" command would tell the unit to attack anything that is on the target tile, and also start moving towards it. The "attack" command would tell the unit to attack the target, but stay on the place.

But in this case, the unit's attacking tile would be one tile forward, but the tile it can be attacked on would be one tile backward (when the unit is between tiles). This is really uncomfortable if an infantry attacks an archer, since I also want every attack to result in exactly one winner. Would that mean that the defender could kill the attacker on a tile it can't even attack?

Also, it would be possible to set up a chain of attacks, where the outcome is not so clear at first glance:

The unit marked with read would die because it is attacked with a unit of the same type, but would also kill the blue unit. Resolving this in game logic would require a two-step system: in the first step, we check all encounters, and mark the dead units, then in the second run, we delete all those marked units.

If the units attaking tile would be the same that they could be attacked on, this wouldn't happen. But this would eliminate the possibility of a command that tells the unit to attack, but not move. (Although I don't really like the idea of attacking without moving, this is a medieval game, not a sniperfest.)

The other solution would be to just simply disable this possibility from the client. This is not a good idea, as I can't be sure that players use the official client, and they can issue commands that would make the gamestate illegal with respect to these rules.

The most likely scenario is that I will just resolve units of the same owner going to the same tile like I would do it if the units were of different teams. I don't want to disable this possibility in the client, because it could be useful in some very rare cases.

There is also the possibility that two units of different teams want to swap places. I don't want them to just swap places, because it would make it really hard to capture a single unit. But by these rules, this is what should happen.

It really needs some serious thoughts.