Now for the Pathfinding

03.22.2015

The A-star is not too complicated, I found the following video series the most helpful in understanding how the algorithm works, thank you Dooobs (3part video) https://www.youtube.com/watch?v=Kw8AMmyc6vg.

This video was pretty useful too, https://www.youtube.com/watch?v=KNXfSOx4eEE

But I personally liked the wiki page on a-star. It was quite comprehensive and detailed. http://en.wikipedia.org/wiki/A*_search_algorithm

I came up with the following psudo code for my a-star pathfinding.

Get open list and closed list

Get the start and end positions

Get the map information.

Put the start position into the open list

While loops while open list is not empty

                Set the current node to the tile with the lowest f in the open list

                Add the current node to the closed list

                Remove the current node from the open list

                If closed list contains neighbour node do nothing

                                If neighbour is walkable               

                                                If neighbour is in open list

                                                                Add parant info for that neighbour

                                                If neighbour is not in open list

                                                                Calculate f,h,g and parant info and add that neighbour to open list

End while loop

But before jumping into the pathfinding code I need to make sure that I can display what I have. To start, I want to keep the map generation separate. This way we can attach different maps, or later if we come up with a better way for generating the 2d matrix we can use that. For this I wrote a simple matlab function.

function [ a] = testmap ()

a=[ 2 -1 0 0 0;

    0 -1 0 -1 0;

    0 -1 0 -1 0;

    0 -1 0 -1 0;

    0  0 0 -1 3];

end

so now whenever I call testmap(), I will get this matrix. I can also tinker with this map without worry as its separate from the rest of the code. Currently its very simplistic but we can build it us as we progress. For now we need a way to display what we are looking at. For that too I will have a function that is modular.it can be replaced and or modified without messing with the other pieces of the code.

Of the many plot/ draw functions in matlab, ‘pcolor’ seems to be the best suited for this, but it does not draw the last column and last row. For this I am going to fix it by adding a dummy column and dummy row.

function [  ] = DrawMap( matrix )

%Draw the grid using pcolor function

%   since the function pcolor does not draw the last row and column

%   i create a dummy row and column just to draw and display on the screen

matrix(6,6)=0;

pcolor(matrix)

end

At this point I know that I would like to use animations and I have yet to find any for the pcolor function, but I think we can change the way we draw it later.

Now we need a main function that will put all the functions together. In this we will need to have a set current pos and set destination functions.

function [  ] = MainFunc( )

%Main function, all other functions will be executed from here

%   Detailed explanation goes here

MapGrid=testmap();

%set current position

MapGrid(1,1)=-2;

%set destination

MapGrid(5,5)=2;

MapGrid

end

and a screenshot of what I get

its small here but we can always make it a larger grid