A* search algorithm & navigation grid

November 25, 2010

The A* search algorithm implementation and the navigation grid (previously path grid) have been in the “astar” branch for quite a while… I’ve finally sorted things out and now they’ve been merged into master.

I don’t have any examples yet, but do note one thing – the A* implementation is a generic one, which means that it isn’t bound to any form; it works on a set of nodes, which it considers as fully abstract objects. In other words, it doesn’t care whether the nodes represent a grid, a node graph in a mathematical sense or, indeed, apples and oranges, long as there exists a cost function between two different nodes.

Both the cost and the heuristic (predicted cost, which must be optimistic – that is, lower or equal to the actual cost – in order for the algorithm to work correctly) are passed in as callbacks, which means that the user can provide whatever he wants for the cost. Furthermore, checking whether a node is the goal is also performed via a function, so one can, for example, have multiple goals.

That said, if the user doesn’t provide such functions, the algorithm tries to use decent predictions – the cost between two nodes is assumed to be 1, and the heuristic is assumed to be 0, essentially making this a breadth-first search. Why 0? This prevents cases of the user providing a cost function returning values lower than 1, with the heuristic assuming 1 – it would break the algorithm, which would return a suboptimal (not shortest/lowest cost) path. A similar assumption is made for the goal node – a node is assumed to be the goal if they are the same references, something which is not completely necessarry when “custom” functions are provided (indeed, it completely depends on the function at hand).

Hopefully, I’ll find some time to scribble together a couple of demos.

Posted in SIEGE.

Arcs

November 19, 2010

Minor update this time – the functionality to draw arcs has been added this time – this means that SIEGE can now draw an arbitrary arc (elliptic as well), as opposed to merely circles and ellipses:

Image of drawn arcs in SIEGE

Current circle and ellipse-drawing code has been modified to use this instead.

Indeed, it is a small update, however work is being done on other things (it’s nearing completion) – coming soon – per-pixel collision detection and a generic implementation of the A* search algorithm (also a wrapper over it for grid-based pathfinding).

For the implementation, see the sources on Gitorious – note that the implementation may be done with the help of rational splines once those are added to SIEGE.

Posted in SIEGE.

4 bugs removed

November 19, 2010

Just now, I’ve removed 4 bugs from SIEGE (they were found quickly with a bit of help of Valgrind) – this means that SIEGE now exits with no memory leaks whatsoever (well, none that Valgrind could find with the app I tested with) and that it’s clean on the Valgrind end.

The first two bugs were in the implementation of SGList (linked lists) – in freeing of the list:

if(list->internalFree != NULL;
    list->internalFree(list->internal);

…and an individual node:

if(node->internalFree != NULL;
    node->internalFree(node->internal);

This normally isn’t a problem, however the issue is that neither internalFree was set anywhere – that means that “internalFree” was undefined (could have any value), and as such, the program would segfault on exit.

The other problem was in deinit of viewports and the modules – both had code which was similar to this:

SGListNode* node;
for(node = _sg_viewList->first; node != NULL; node = node->next)
    sgViewportDestroy(node->item);

Look carefully – the viewport at the node is destroyed (which also destroys the node), after which “node = node->next” is ran – by that time, the previous node has been free’d, and its contents are thus undefined. The solution was simple:

SGListNode* node;
SGListNode* next;
for(node = _sg_viewList->first; node != NULL; node = next)
{
    next = node->next;
    sgViewportDestroy(node->item);
}

So there you have it – the problems which were pestering SIEGE’s otherwise clean shutdown are now gone.

Posted in SIEGE.