Search

Thursday, September 11, 2008

Designer for my path finding boards

I'm writing a small application (or rather a screen saver) that animates and demonstrates A* search algorithm. The idea is simple. On screen you see a start and end point and some random obstacles in between them. Then you see animation on how A* algorithm is used to navigate around the board to find a path (close to the shortest possible) between the two.

All of this is fairly standard. However, I got hit by a simple issue. I wanted to have the ability to design this board visually and also let my potential million users do the same. Obviously I don't have time to code up a designer and hence choose the all time manager's favorite technique. Re-use :)

So the final solution I took was to use Microsoft Office Excel as the WYSIWYG editor. I created a xlsx file with the following conditional formatting which colors cells based on the value of the cells.

Excel Conditional Formatting screen shot for blog

So in this case

  1. w = Wall marking the end of the table
  2. b = blocks/bricks/obstacle
  3. s = start
  4. e = end

Using this I can easily design the board. The designer in action looks as follows

Excel Designer For A* blog screenshot

Since the excel sheet has conditional formatting the user just types in s, e, b, w in the cells and they all light up visually. At the end he/she just saves the file using File => Save As and uses CSV format. This saves the file shown above as

w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,b,,,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,s,,,,,,,,b,b,b,b,b,b,,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,b,b,b,b,,b,b,b,b,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,b,,,,,,b,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,,b,b,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,b,b,,,,,,,b,b,,,,,b,,,,,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,b,b,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,b,b,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,b,b,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,b,b,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,e,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,b,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,,,,,,,,,,,,,,,,,,,,,,,,,,,b,,,,,,,,,,,,,,w
w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w,w

As you see the format is simply a row per line and every column separated by a comma. My simulator reads this file and renders using whatever renderer is configured (console or WPF).

More about the A* simulator to come soon...

No comments: