Entries

 TileshiftLudum Dare 24

Gameplay and Story

Posted by (twitter: @OrionTransfer)
Monday, August 27th, 2012 8:47 am

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.

Sound effects with BFXR =)

Posted by (twitter: @OrionTransfer)
Sunday, August 26th, 2012 2:40 pm

I was just adding sound effects to my game and came across this great site where you can generate and download WAV files which suit typical games very well. I had a lot of fun making various sounds for our game Tileshift.

Now when you get the chest or stars, you have a nice rewarding sound.. well I guess it might be subjective =)

Let me know if you use it too!

Posted by (twitter: @OrionTransfer)
Sunday, August 26th, 2012 10:47 am

I have to say I found this result very interesting. A* heuristic can be inadmissible which means that it might sometimes find the non-optimal path. However, it is also more efficient. By biasing the estimate, you can choose between path cost and search cost.

Firstly, here is a heuristic estimate that underestimates the actual cost (admissible). Estimate = Manhattan Distance * 0.95

Wow! Look at that search space, it is pretty massive… Secondly here is a heuristic estimate that is exactly the actual cost (still admissible). Estimate = Manhattan Distance * 1.0

That is looking a bit better. Path is still good too, but it still explored quite a bit area. Finally, here is a slightly inadmissible heuristic, which means that sometimes the path might be slightly longer than the best possible. Estimate = Manhattan Distance * 1.2

Wow! Look at that super small search space. By sacrificing some path efficiency, we can reduce our search space by quite a bit! I was surprised, but I guess its a logical result.

Tileshift – A* Manhattan Distance vs Euclidean Distance

Posted by (twitter: @OrionTransfer)
Sunday, August 26th, 2012 8:26 am

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 =)

Tileshift – Updated A* implementation and query size.

Posted by (twitter: @OrionTransfer)
Sunday, August 26th, 2012 7:52 am

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.

Tileshift – Using the A* algorithm as a fitness function.

Posted by (twitter: @OrionTransfer)
Saturday, August 25th, 2012 8:07 am

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.

Tileshift – A game that evolves around you.

Posted by (twitter: @OrionTransfer)
Saturday, August 25th, 2012 6:48 am

This is my first LD, I’m from New Zealand and I enjoy making games in my spare time. We are working in a team of two people (myself and Steven) at Canterbury University, so I guess that means we are entering the Jam =).

Rather than build a game where evolution is intrinsically part of the player personification, we decided to reverse this and build a tile based game where the mechanics of the world evolve around you based on how you interact with the world.

The implementation uses a evolutionary algorithm with a fitness function based on the A* algorithm. As the player move through the map, the world changes to both assist and challenge the player. Right now most of the basics are working and we will be looking to develop the core gameplay over the next few days. Please give us feedback and check out the initial release.

[cache: storing page]