Home | Rules and Guide | Sign In/Create Account | Write a Post | Reddit | #LD48 | #ludumdare on irc.afternet.org (Info)

Ludum Dare 31 — Coming December 5th-8th 2014! — Join the Mailing List!
Also check out the Ludum Dare 30 results!
  • Ludum Dare 31 begins: in 74 days, 8 hours, 44 minutes, 14 seconds
  • (Time might be off, we’ll have it right soon) | Real World Gatherings (Now Open!)

    Tileshift – Updated A* implementation and query size.

    Posted by (twitter: @OrionTransfer)
    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.

    Leave a Reply

    You must be logged in to post a comment.

    All posts, images, and comments are owned by their creators.

    [cache: storing page]