On Better Hiding Keys

When I first wrote the code to place the items (exit, key, gate), I used this process:

1. pick a random location
2. find the farthest place away from it - put the player there
3. find the farthest place away from the player - put the exit there
4. find a spot about 70% of the way from the player to the exit, put the gate there
5. find a spot about 50% of the way from the player to the gate, put the key there

And this works, in the sense that the key and the exit are guaranteed to be on the correct sides of the gate. It also does a good job of forcing the player to travel the furthest, guarding against degenerate mazes.

I recognized one thing that it didn't do was to allow the player to reach the gate without first having reached the key. And, if you're guaranteed to pick up the key before you reach the gate, one or both of them isn't really fulfilling its purpose.

So, I've put a new build up here: http://bigdicegames.com/RatMaze/maze.html The big difference here is that the key is now placed differently. I've got a modified version of the "farthest place away" code that generates a table of locations indexed by distance from the start location and another table of locations indexed by distance from the gate. I then walk through one of these lists and cross reference with the other list, and I can find out the distances for each location to the start location and to the gate location. I find a hex that has the maximum sum of these two values, and that's going to be a place far away from both, and probably off in some dead end; a good place to hide a key.

One thing I'm pleased about, even though the code is a little gross, that whole thing is running in O(n) in the number of walkable spaces inside the gate. A somewhat simpler algorithm would have been O(n2)

So, the game is pretty much doing what it needs to - you get a maze, you have to find the key, the gate, and the exit, and visit them in that order.

Some things that aren't working correctly:

• pinch to zoom on mobile - the mobile experience isn't really something I've looked at recently.
• mobile viewers of the webpage can't click - I haven't really been optimizing for this case, but it's totally broken. May stay totally broken, depending on how excited I am about fixing it.
• dialogs when finding an item - this may be pretty simple, and the text is going to be trivial to write, something like "You have found a key! Now find a gate to unlock!"
• sound effects - footsteps, picking up a key, opening a gate
• main menu, about, credits screens - I'll probably reuse much of earlier projects, that's what I'm here for. 
• HUD? - maybe I should provide an indicator that you've picked up a key and are looking for a gate. Almost like a mini quest log thing. Or a simple inventory. Or maybe I don't need it for this game.
• smoother movement - blinking from hex to hex isn't what I wanted. I like the Lair of the Rat King implementation where the guy would move by using a spline, hopping from location to location, like a piece on a board.