About | Rules and Guide
Construction1990’s Internet Montage? No!
Please excuse the site weirdness. Mike is fixing and making things.
Ludum Dare 31 — Coming December 5th-8th 2014!

  • ??? Begins: in 7 days, 13 hours, 55 minutes, 15 seconds
  • October Ends: in 8 days, 14 hours, 7 minutes, 15 seconds
  • Ludum Dare 31 begins: in 43 days, 14 hours, 55 minutes, 15 seconds
  • (FYI: Clock might be off) | Ludum Dare 31: Real World Gatherings (Now Open!)

    [ October Challenge 2014 | Resources | Submit/Edit | View All ]

    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]