Monday, February 16, 2009

A* algorithm bug fixes

It's been a while since I checked the issues page on my A* algorithm google code project. So it turns out there's a possible memory leak and the Manhattan distance calculation in the findpath.cpp is wrong. I've investigated both of these and uploaded a fixed version.

In the case of the memory leak, there is some code in my "fast simple allocator" which allocates some memory, assigns it to a temporary pointer, then converts it and stores it in a member variable. Apparently, this shows up in memory tracking software as a leak, even though the memory is released in the destructor, so I've changed the code so that the allocation and free is done with the same variable.

The Manhattan distance refers to a simple heuristic for finding a path when you can only move horizontally and vertically through a grid. Like calculating how far you would have to walk in a city on a grid system, like NY, you simple count how many blocks along and how many blocks up you need to walk. Well I implemented this carelessly and forgot to make sure that I take the absolute value when calculating the difference between 'streets'. That's done now.

You can download the latest version of the A* algorithm here...

http://code.google.com/p/a-star-algorithm-implementation/downloads/list

3 comments:

Rezkizuka said...

thank you very much.

Juan Pablo Folco said...

Hey, how are you?
I tested the implementation and i liked it but i had the problem that it performed Breadth-first search..
(it was then evaluating wayy more nodes than it needed). Maybe this is not an issue but im dropping the code here just in case.
In SearchStep:
after: "m_OpenList.push_back( (*successor) );"

if (m_OpenList[0]->f == m_OpenList[m_OpenList.size()-1]->f)
{
Node *aux = m_OpenList[0];
m_OpenList[0] = m_OpenList[m_OpenList.size()-1];
m_OpenList[m_OpenList.size()-1] = aux;
}

Thank you, great work! :)

Anonymous said...
This comment has been removed by a blog administrator.