Most genetic algorithms (GAs) require some kind of fitness function. Essentially the algorithms can be very simple. As input we have some initial state (in the case of Tileshift, a 2D tile map). Then, we have some mutation function which makes changes to the tile map. Each of these candidates is processed by a fitness function which in turn produces a single number that rates how good the candidate is. The candidate with the best rating is then used for the next iteration.

Tileshift uses the A* algorithm for path planning and the fitness function. Each candidate tilemap is ranked based on how it helps the player get to the end goal. By selecting a tile map that assist the user, eventually a path to the goal is formed. We hope to add additional challenges to the generation function along with keys, doors, monsters and movable blocks. These will enhance the gameplay and engage the user.

You can visualise part of the A* search by checking the visualise checkbox at the lower left side of the demo page. This shows the cost for the path search. The blue number is the best guess by the search algorithm, and ultimately represents the fitness of the current candidate. Red number means explored and green number means open. Candidates are evaluated as the user moves through the map (which you can’t see) and the best candidate is used to update the game state.

Check out our next blog post.

Hi,

Just having a bit of fun with my visualisation. Here is Manhattan distance as the cost function:

Here is Euclidean distance as the cost function:

I also found a bug, my estimate was not admissible. I’m still trying out various combinations of cost function weights to get a good result… its complicated =)

So, I’ve been working on A* heuristics.

It is interesting so I wrote a visualisation tool for looking at the costs and paths.

This is a relatively large number of iterations using Manhattan Distance. The large search space is quite costly since we use the search algorithm as a fitness function to the genetic selection algorithm:

To improve the efficiency of the GA, I reduced the size of the search, and we get a similar short term prediction which is good enough:

In particular, the shorter search allows for the users location to have more of an effect on the genetic algorithm since the best possible destination will be more local.

Finally, I was interested to compare the results with Euclidean distance. We see a larger diagonal component (which is to be expected) heading towards the goal (in this case towards the lower right).

I actually found that the directionality of this cost function didn’t give as good results as the Manhattan distance allows the user to try out both horizontal and vertical paths which effectively have the same cost, where-as the Euclidian cost tends to build paths directly towards the goal diagonally.

It has been interesting to play with the parameters of the A* algorithm and visualise the results, and generally it has been very helpful. You can try out some of the visualisations in the first level here.

So, after developing the tile engine and the underlying genetic algorithm, I started working on the story and Steven continued work on the procedural generation.

I also implemented a basic monster bug using A* path finding for AI. The turned out to be quite fun =)

I also tried to make the game resolution independent, so if you resize your browser window the game will scale correctly so you can see the entire map.

Try it out, have fun, and give us some feedback =).