Search

Tuesday, September 16, 2008

A* Pathfinding algorithm animation screen saver

I'm trying to learn WPF and IMO it is not a simple task. Previously whenever I upgraded my UI technology knowledge it had been easy as it build on a lot of pre-existing concepts. However, WPF is more of a disruptive change.

I decided to write some simple fun application in the effort to learn WPF. Since I cannot write a BabySmash application as Scott Hanselman has already done a awesome job out of it, I decided to code up a simulation of A* path finding algorithm and push it out as a screen saver. The final product looks as follows.

AStar

What it does is that it shows a source, a destination with blockages (wall, mountain?) in between and then uses A* algorithm to find a path in between them. This is the same kind of algorithm that is used in say games like Age of the Empires as workers move around collecting wood and other resources. The algorithm is documented here.

Features

  1. It supports plugging in your own scenes with help of the awesome screen/board designer I blogged about
  2. Comes with a WPF and a console client to show the animation
  3. Algorithm can be played with easily to change or tweak it.
  4. Shows full animation including start, end, obstacle, closed cells, current path being probed and the final path
  5. Multi-screen support. Each screen shows a different board being solved.

Limitations:

Obviously this was more of a quick dirty hobby project and there remains a ton to work on. E.g.

  1. Screen saver preview doesn't work.
  2. Setting dialog is a sham.
  3. The boards do not flip for vertically aligned screens
  4. The XAML data binding is primitive and needs some work
  5. The path can choose diagonally across cell even if it seems to cross over diagonal wall of obstacle.
  6. Mouse move alone doesn't shut down the screen saver. You need to hit a
  7. Many more :)

Download:

Download the final binaries from here. Unzip to a folder, right click on the *.scr and choose Install

Download sources (including VS 2008 sln) from here.

Enjoy.

1 comment:

Anonymous said...

Cool screensaver project. Hope learning WPF gets easier as you go along.

I noticed that you were in India, so I thought this blog post that I wrote might be of interest to you.
http://jaxtr.blogspot.com/2008/09/jaxtr-gets-local-numbers-for-mumbai.html
Take care.