|
|
Pathfinding on native Gamestudio graphs
#290711
09/20/09 21:10
09/20/09 21:10
|
Joined: Dec 2008
Posts: 271
Saturnus
OP
Member
|
OP
Member
Joined: Dec 2008
Posts: 271
|
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! : )
|
|
|
Re: Pathfinding on native Gamestudio graphs
[Re: Tai]
#290875
09/22/09 03:41
09/22/09 03:41
|
Joined: Sep 2008
Posts: 68
Tai
Junior Member
|
Junior Member
Joined: Sep 2008
Posts: 68
|
Can you tell me why the compiler is throwing me syntax errors for this? It should be working...
action test_pather()
{
path_set(my, "path_000");
while(1)
{
var start_node = ll_pfind_getClosestNode(my, my.x, 1000, NULL);
var dest_node = ll_pfind_getClosestNode(my, target_pos.x, 1000, NULL);
LL_LIST *path = ll_pfind_getPathToTarget(my, start_node, dest_node, ll_pfind_astarCost);
LL_PFIND_PATH_NODE *node = (LL_PFIND_PATH_NODE *)path->first->data;
if (path) // path has been found
{
LL_PFIND_PATH_NODE *node;
// insert the start position as first node
node = ll_pfind_createPathNode(start_node);
ll_list_push(path, (void *)node);
// insert the destination as last node
node = ll_pfind_createPathNode(dest_node);
ll_list_add(path, (void *)node);
if (path->count > 0) // path is not empty yet
{
// get the next node of the path
LL_PFIND_PATH_NODE = (LL_PFIND_PATH_NODE *)path->first->data;
// move to the node
// [insert your movement code here]
// [the destination should be: node->pos]
// if the entity has reached the node
if (vec_dist(&my->x, &node) < 50)
{
// remove it from the path
ll_list_remove(path, path->first, ll_pfind_destroyPathNode);
}
}
else // path has been traversed completely
{
ll_list_destroy(path, NULL); // remove it
}
}
}
}
|
|
|
Re: Pathfinding on native Gamestudio graphs
[Re: Tai]
#290913
09/22/09 11:18
09/22/09 11:18
|
Joined: Dec 2008
Posts: 271
Saturnus
OP
Member
|
OP
Member
Joined: Dec 2008
Posts: 271
|
Hello! Thanks for all your comments. @Tai Ok, lets see what we have here. There's only one syntax error in the code:
//LL_PFIND_PATH_NODE = (LL_PFIND_PATH_NODE *)path->first->data; // old
LL_PFIND_PATH_NODE *node= (LL_PFIND_PATH_NODE *)path->first->data; // new
This was not your fault, but a misstatement in the example from the documentation. Sorry for that! Your code compiles fine for me after correcting this (compiled with lite-C 1.7). However, it will probably not quite do what you want it to do, as there are still a few semantic errors. Here we go: 1) ll_pfind_createPathNode() takes a VECTOR* as an argument, but node numbers are passed instead:
// insert the start position as first node
//node = ll_pfind_createPathNode(start_node); // old
node = ll_pfind_createPathNode(&my->x); // new
ll_list_push(path, (void *)node);
// insert the destination as last node
//node = ll_pfind_createPathNode(dest_node); // old
node = ll_pfind_createPathNode(&target_pos); // new
ll_list_add(path, (void *)node);
2) A pointer is passed instead of a VECTOR*:
//if (vec_dist(&my->x, &node) < 50) // old
if (vec_dist(&my->x, &node->pos) < 50) // new
3) The while loop misses a wait(). 4) path should be set to NULL when the path has been traversed or else the condition 'if (path)' is still true, although the path was already freed:
else // path has been traversed completely
{
ll_list_destroy(path, NULL); // remove it
path = NULL; // new
}
This one wasn't that obvious and it isn't mentioned in the examples yet. I'll check if and how I can clarify this. Last but not least also note that in each iteration of your while loop a path from the starting point to the destination point is created. In principle this isn't wrong, but it isn't necessary either and just produces overhead. If the destination point is immovable, it's entirely sufficient to calculate the path only once. Also mind, that all the created lists are never freed in your code (except for the case if a path is traversed completely), so this ultimately leads to a heap overflow. You could shorten your while loop to the following code and do the rest outside of the loop (as an example):
while(1)
{
if (path) // path has been found
{
if (path->count > 0) // path is not empty yet
{
// get the next node of the path
node = (LL_PFIND_PATH_NODE *)path->first->data;
// move to the node
// [insert your movement code here]
// [the destination should be: node->pos]
// if the entity has reached the node
if (vec_dist(&my->x, &node->pos) < 50)
{
// remove it from the path
ll_list_remove(path, path->first, ll_pfind_destroyPathNode);
}
}
else // path has been traversed completely
{
ll_list_destroy(path, NULL); // remove it
path = NULL;
}
}
wait(1);
}
You might also have a look at "pathfinder.c" from the demo which uses the same approach. Hope this helps! If not, you can tell me of course. : ) If you consider the documentation or the examples unclear, please tell me too, so I can improve them.
|
|
|
Re: Pathfinding on native Gamestudio graphs
[Re: bart_the_13th]
#290936
09/22/09 14:23
09/22/09 14:23
|
Joined: Sep 2008
Posts: 68
Tai
Junior Member
|
Junior Member
Joined: Sep 2008
Posts: 68
|
So I took your suggestions, (coicendentally I had actually tried that *node code before, but because I got the following error when I started the game, I thought it was incorrect. With the code you posted I get a crash in ll_bitArray_set. Sorry for the troubles!
action test_pather()
{
path_set(my, "path_000");
var start_node = ll_pfind_getClosestNode(my, my.x, 1000, NULL);
var dest_node = ll_pfind_getClosestNode(my, target_pos.x, 1000, NULL);
LL_LIST *path = ll_pfind_getPathToTarget(my, start_node, dest_node, ll_pfind_astarCost);
LL_PFIND_PATH_NODE *node= (LL_PFIND_PATH_NODE *)path->first->data; // new
while(1)
{
if (path) // path has been found
{
if (path->count > 0) // path is not empty yet
{
// get the next node of the path
node = (LL_PFIND_PATH_NODE *)path->first->data;
// move to the node
// get the direction from the entity MY to the entity YOU
var temp;
vec_set(temp,your.x);
vec_sub(temp,my.x);
vec_to_angle(my.pan,temp); // now MY looks at YOU
c_move(my,node->pos,nullvector,GLIDE);
// [the destination should be: node->pos]
// if the entity has reached the node
if (vec_dist(&my->x, &node->pos) < 50)
{
// remove it from the path
ll_list_remove(path, path->first, ll_pfind_destroyPathNode);
}
}
else // path has been traversed completely
{
ll_list_destroy(path, NULL); // remove it
path = NULL;
}
}
wait(1);
}
}
Last edited by Tai; 09/22/09 14:27.
|
|
|
Re: Pathfinding on native Gamestudio graphs
[Re: Tai]
#290940
09/22/09 14:50
09/22/09 14:50
|
Joined: Dec 2008
Posts: 271
Saturnus
OP
Member
|
OP
Member
Joined: Dec 2008
Posts: 271
|
Have you initialized the pathfinding with ll_pfind_init()?
This has to be done before any pathfinding is performed, or else the open and the closed list are not created.
This is the most probable reason I can think of.
Let me know if this fixes your problem. : )
You can also repost your current code if the problem persists. Edit: Ok, you already have.
Last edited by Kombucha; 09/22/09 14:51.
|
|
|
Re: Pathfinding on native Gamestudio graphs
[Re: Saturnus]
#290943
09/22/09 14:54
09/22/09 14:54
|
Joined: Sep 2008
Posts: 68
Tai
Junior Member
|
Junior Member
Joined: Sep 2008
Posts: 68
|
function main()
{
game_state_game_on = 1;
video_screen = 1; // lite-C: start settings for Fullscreen
level_load ("Mistborn.wmb");
ll_pfind_init();
wait(3);
//ent_create("terrain.hmp",vector(0,0,0),terrain_basic);
normal_movement = 1;
dynamic_movement = 0;
}
No such luck  Your examples compile fine, but it's not working well. I'll mess around a bit. EDIT: Fixed it; changed the target position to the player position, this fixed it.
Last edited by Tai; 09/22/09 14:58.
|
|
|
|
