Hello everybody,

here is a code for doing pathfinding on native Gamestudio graphs (the so-called paths).

The pathfinding functions can be used by any entity that has a Gamestudio graph assigned to it. It can either be searched for a path between two specific nodes or for a path between a specific node and the closest node that matches given criteria. A path is returned as a list of path nodes and path edges. Paths can be post-processed by using string-pulling or similar algorithms.

Cost functions, node evaluation functions and reachability functions can all be set externally. So you can greatly influence the solution yielded by the pathfinding algorithm.

Note that this code is NOT a non-programming solution. Basically it's a pure Dijkstra/A* algorithm that has to be implemented in your own movement code. It was written with the intention that programmers can easily customize it without changing the source code.

Some technical details:
* an indexed binary heap is used as open list
* a bit array is used as closed list
* doubly linked lists are used for the paths
* as a side note: all these data structures can also be used as stand-alone
* compatible with PRAGMA_POINTER

A demo can be downloaded here. It looks like this:


The demo is simple and just shows one way to implement the pathfinding. The pathfinding functions are wrapped in some easy-to-use functions.

There are two different main scripts you can run from SED:
* demo_navigate.c: An entity can be navigated through the level via the mouse.
* demo_follow.c: Same as demo_navigate.c but the navigated entity is chased by another enity.

The full documentation for the pathfinding can be found here. It is written in a language similar to English (I hope). ; )

The code is licensed under the Do What The Fuck You Want To Public License, so it's free for personal as well as for commercial use.

Please note: As I use lite-C free I was not able to test this code on other graphs. It would be very kind if somebody could provide more complex graphs I could test this with!

If you have any questions about or problems with this code I am happy to help you.

Happy programming! : )