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

Ludum Dare 29 — April 25th-28th Weekend [9 PM EST] — Theme: ??? (Theme Voting!)
  • Ludum Dare 29 Compo (48 Hour+Solo+Scratch+Src) Begins: in 20 hours, 24 minutes, 50 seconds
  • Ludum Dare 29 Jam (72 Hour+Teams OK+Relaxed) Begins: in 20 hours, 24 minutes, 51 seconds
  • [ MiniLD 50 | Warmup Weekend | Real World Gatherings | Ludum Deals | Wallpaper ]


    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]