A Star in algorithms.h

[andydansby]

Having trouble understand how to use this particularly useful function. Are there any coding examples on using it on a tiled array? Also, assuming that this would be called during the enemy placement loop, what is delay and memory usage it would introduce into the game if placed in?

It seems that all of the pathfinding routines I have read about would require reading the screen tiles in a nested loop which would add great delay into the game.

Pathfinding is an interesting, yet complex subject for me to wrap my head around even after reading tutorials on it.

Thanks
Andy

[alvin]

Having trouble understand how to use this particularly useful function. Are there any coding examples on using it on a tiled array?

It has been ages since I wrote that function but there is some information in the classic library wiki:
https://www.z88dk.org/wiki/doku.php?id= ... :algorithm

This is a very general implementation that requires you to set up a number of functions pointed at by function pointers to describe a specific problem.

Also, assuming that this would be called during the enemy placement loop, what is delay and memory usage it would introduce into the game if placed in?

Memory is set aside statically at compile time so it never grows. You're setting a maximum memory use that the algorithm will not exceed.
Delay is harder to say as it depends on the complexity of the graph. A heuristic is not implemented to favour certain directions to explore so the algorithm is pursuing the currently lowest path first. It does this by maintaining a priority queue containing paths from which it can extract the currently lowest cost path and try to take a step from there. The resulting paths are pushed back into the priority queue which maintains itself in sorted order. And then the next path is extracted from the queue, which will again be the lowest cost one.

Pathfinding is an interesting, yet complex subject for me to wrap my head around even after reading tutorials on it.

There is another option written by Einar:
http://www.worldofspectrum.org/infoseek ... id=0028178

This one may be simpler to use. IIRC it uses a "stink" algorithm to find the lowest cost path. This works by starting at the goal with cost=0 and then taking a step away in each direction not yet visited, adding 1 to the cost as it does so. Eventually the whole map is covered and each move has a cost to the goal associated with it.

If you want to pursue A* I can maybe try to come up with an example but it may take a bit of time as I've quite short of that atm.