VBA – A* search algorithm with Excel – Really?

Today, some hours ago I saw the implementation of the A* search algorithm with Java, made by a classmate (or colleague) of mine. It looks like this:

12032621_893074144075352_8225843988882803031_o

 

Thus, I have thought that for the reading of the Python Algorithm book, it may be a good idea to remember how algorithms were made 🙂 Thus, instead of using Python, which makes a lot of things easy, provides outstanding and easy to use lists, dictionaries and anything a VBA programmer may dream of, I have decided to make a tribute to the good old VBA.

Before continuing, I remember that I have not mentioned the Hack Bulgaria Conference in Sofia, so I have to fix this bug a little. If by any chance you are going to Sofia on 18.09.2015 then this is a must-see! 🙂

Back to the VBA. So, what did I do? At first I have started to go around the net to see whether someone has something similar. Nothing similar with VBA was found at the first page of the Google results, thus I have decided to dedicate my evening for this. (Actually two evenings, as far as at the end I have somehow deleted the code).

So, I have been able at the end to provide the following beautiful picture of the A* path finding:

hb

So, how does it work? You “create” the obstacles in the path finder with simply selecting the cells, which you want to be obstacles. Then you start the macro, and it sets automatically the start and end points on the two corners (red is start, green is end). In order to set different dimensions for the labyrinth, you may adjust the two constant values for C_COLUMNS and C_ROWS.

I have decided not to use arrays, because I do not like the way Excel treats them (true story), thus the whole data for the “cost” of the possible achieving of the result, plus the “parent” cell were simply written in the excel file within the cell.

Thus, the visualization was better. 🙂 At the end, once the path was found, I simply went back, coloring the “parents” of the cell.

The code has really plenty of points for improvement:

  • Its size can be really made 2-3 times less;
  • I have to make the font colors in the same color as the background colors
  • The A* implementation can be improved. It does not select the best path always, I am aware of it. This is because I am ignoring the rule, that the diagonal cells cost 14 units and the straight cells cost just 10. When I have time, I will fix it. Or not.

Pretty much that is it. And the funny moment now – as far as I was really tired yesterday, when I was writing this article, somehow I have forgotten to save the Excel as *.xlsm and I have lost the code. Thus, I have decided to recode it today 🙂 Yup, the only more insane thing than writing A* algorithm with Excel is writing it twice.

But now I have the code, plus 2-3 nice pictures. Here they are:

The start (walls are simply selection in Excel – you know, press control)

start

The A* is running

working

The End

end

 

So, pretty much that is all. Here comes the code of the app and the app itself (I would not download  a script file from any internet site, thus think twice before doing so)  and the GitHub code.

Enjoy it! 🙂

About

VBA Developer

Tagged with: , , ,