Pathfinding on native Gamestudio graphs

Posted By: Saturnus

Pathfinding on native Gamestudio graphs - 09/20/09 21:10

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! : )
Posted By: Felixsg

Re: Pathfinding on native Gamestudio graphs - 09/20/09 21:18

is really useful
thanks
Posted By: darkinferno

Re: Pathfinding on native Gamestudio graphs - 09/20/09 21:19

anything that does AI has definately got a vote in my book, even though i havent tested it yet but i know its a great contribution based on what you said, i'll be playing around with it later for sure wink
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 09/21/09 17:35

Excellent, I was in the middle of doing some Pathfinding, so this will help greatly.
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 09/22/09 03:41

Can you tell me why the compiler is throwing me syntax errors for this? It should be working...

Code:
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
			}
		}
	}
}


Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 09/22/09 11:18

Hello!

Thanks for all your comments.

@Tai
Ok, lets see what we have here.

There's only one syntax error in the code:

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:
Code:
// 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*:
Code:
//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:
Code:
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):
Code:
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.
Posted By: bart_the_13th

Re: Pathfinding on native Gamestudio graphs - 09/22/09 12:34

Impressive!!!

I'm downloading this right now, there's no way I'd miss something this good(for FREE)...
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 09/22/09 14:23

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!

Code:
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);
	}
}


Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 09/22/09 14:50

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.
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 09/22/09 14:54

Code:
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 frown 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.
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 09/22/09 16:08

Ugh, this is bizarre. When I enter in a dest_node like so

var dest_node = ll_pfind_getClosestNode(my, entTarget.x, 1000, NULL);

it gives me that error. It doesn't seem to like my pointer or something... Because if I use player.x it works fine.

(the pointer is defined exactly the same way it is in your scripts, I've checked.)

EDIT: I got it, finally. When defined as void instead of action, pathfinders can find the object pointed to.
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 09/22/09 18:27

Technically it shouldn't matter if you're using void or action.

However, the last time I checked your script, the movement code could invoke random behaviour, as the you pointer (which was not set) and a var instead of a VECTOR were used. Make sure you ar using something like this:
Code:
VECTOR vec_to_target;
vec_diff(&vec_to_target, &node->pos, &my->x);
vec_to_angle(&my->pan, &vec_to_target);
c_move(my, vector(10 * time_step, 0, 0), nullvector, GLIDE);


Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 10/01/09 17:44

Back again, I had the code working, but when I changed the path substantially or added more enemies pathfinding, it just seized up. Are their any rules regarding node placement, etc?
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 10/01/09 17:58

Hello!

I think I don't quite get the point yet.
Could you explain your problem in more detail?
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 12/26/09 06:01

Back from the dead here, but I just implemented this without a hitch. My oh my what wonders a little experience does for you. Thanks alot for your help!
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 12/26/09 20:52

Hey,

this is good news, Tai! : )

On another positive note, the code can now also be used without limitation in the free edition of Gamestudio. Previously this wasn't possible as the free edition was lacking WED (which is needed for building graphs).
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 12/27/09 02:25

I'm at my wit's end here...

It was working; then it stopped.

Code:
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, player.x, 1000, NULL);
	LL_LIST *path = ll_pfind_getPathToTarget(my, start_node, dest_node, ll_pfind_astarCost);
	while(!path)
	{
		beep();
		wait(1);
	}
}



This beeps, which shouldn't be happening.
If I use the full script, I get errors when trying to modify the list; and I get a bit_array error when I compile the full script.
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 12/27/09 16:07

Have you already checked whether the start node and the destination node are valid?

The following line should output their numbers:
printf("start_node: %i | dest_node: %i", (int)start_node, (int)dest_node);

If either of the numbers is equal to zero, the respective node has not been found.

At the moment the pathfinding functions (ll_pfind_getPathTo...) don't check whether the nodes passed as parameters are valid. If both nodes are equal to zero (invalid) the function mistakenly assumes that a path has been found (because current node == destination node). I will fix that, so no list is returned in this case.
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 12/27/09 16:31

I just tested this out with a different method, just making a while loop to check if they were equal to 0. They don't appear to be equal to zero; however when I use the printf the game freezes when I open it.
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 01/05/10 04:30

Hah, I got it working again! I'm not entirely sure what I did though. I reset my level to just a blank square grid with four nodes and it works.
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 01/05/10 19:16

Sorry about the triple post here, but it's still working great. I have a suspicion that you were right; and that the nodes were too far away to find the players position. One quick question though, how would you advise doing a cost function for nodes moving upwards so that the path doesn't calculate a straight line in the air?
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 01/06/10 16:35

Don't mind the triple post!
I just didn't get round to write a reply.

Now let me see whether I understand this correctly:
Do you want (as an example) a path leading up a hill to have higher costs than a regular path? Or something different?
Posted By: Tai

Re: Pathfinding on native Gamestudio graphs - 01/06/10 17:12

Sort of like that. I want the pathfinding to work as if gravity was in effect, so that the entity won't just look up and fly.


EDIT: To clarify further, I just want the pathfinding to consider the z axis. I'm assuming I'll have to implement my own cost function?
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 01/08/10 13:57

Note that the pathfinding code just computes a path - it doesn't control how the entity follows this path.

The pathfinding function should return a path that is actually walkable for the pathfinding entity. If the entity can't swim for example, all edges leading through water should be ruled out in the pathfinding process by the cost function.

This could be done by setting the edge's skill to a specific value indicating that the edge can only be traversed by swimming. This skill value can then be evaluated within the cost function:

Code:
// remark: edge_skill is set by path_getedge()
if ((edge_skill[2] == THROUGH_WATER) && (entity_can_swim == FALSE))
{
	return -1; // edge cannot be traversed by this entity
}



But as said as before the movement code has to take care of how the entity ultimately follows the path. If the entity can't fly, the movement code should steer the entity in a way that it can arrive the nodes with gravity in effect.
Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 02/23/10 14:16

Heloo.. the url for download not found...
Plz plzz .. you can up the file again.
Tnkxs
Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 03/10/10 14:22

somebody can up file again?
Posted By: Saturnus

Re: Pathfinding on native Gamestudio graphs - 03/10/10 14:44

Here is an alternative download link:
pfind_gs.zip

It's the rescent version of the script. German documentation is included. I didn't have time to spare for an English offline documentation (there's still the online doc, though).
Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 03/11/10 13:04

yataaaaaaaaaaaaaaaaaaaaaaaa...
Tnkx man... very tankx...
(^.^) Arigatooooooooo
Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 05/06/10 13:53

exists some forms to make the entity to move itself using (c_move). I tried but I did not have success.
Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 05/06/10 15:05

already I obtained sucess...
its work...
See..
pathfinder.c

Code:
void ent_pathfinder()
{
	entPathfinder = my;
	
	ent_setState(my, STATE_IDLE);
	ent_setPath(my, NULL);
	my->flags &= ~PASSABLE;
	path_set(my, "path_000");
	VECTOR vec_to_target;
	
	while (1)
	{
		
		if (ent_getState(my) == STATE_FOLLOW_PATH)
		{
			ent_drawPath(my, vector(0, 255, 0)); // display path
			
			LL_PFIND_PATH_NODE *node = ent_getFirstPathNode(my);
			
			if (node) // path is not empty
			{
				VECTOR vec_to_node;
				VECTOR *node_pos = ll_pfind_getPathNodePos(node);
				var dist = vec_dist(&my->x, node_pos);
				
				//vec_diff(&vec_to_node, node_pos, &my->x);
				//vec_to_angle(&my->pan, &vec_to_node);

			//	vec_add(&my->x, &vec_to_node);
						
					
vec_diff(&vec_to_target, &node->pos, &my->x);
vec_to_angle(&my->pan, &vec_to_target);
my->tilt=0;

				vec_normalize(&vec_to_target, minv(dist, PATHFINDER_SPEED * time_step));
c_move(my, vector(10 * time_step, 0, -1), nullvector, GLIDE);


				if (dist < 10) // node reached
				{
					ll_pfind_stringPullingFirst(my, ent_getPath(my), 3, ent_isReachable);
					ent_removeFirstPathNode(my);
				}
			}
			else // end of path reached
			{
				ent_setState(my, STATE_IDLE);
				ent_setPath(my, NULL);
			}
		}
		
		wait(1);
	}
}


Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 05/06/10 15:50

now I have another one doubts… Exists a way to make the pontinhos of path to be invisible and Passable? therefore I am colliding in them.
Posted By: NeoNeper

Re: Pathfinding on native Gamestudio graphs - 05/06/10 18:19

ohhhh soryy sory..
it was simply disactivate in main //drawPathfinderGraph();
i post the link for download the "follow path" mode modified, now with the movement using (c_move) and scene made with blocks in wed.

http://www.2shared.com/file/fHUStQ-K/pfind_gs2.html
Posted By: Muhsin

Re: Pathfinding on native Gamestudio graphs - 05/09/10 12:33

sorry, but where can i find the english documents, the link in the first post is dead?


thanks


- Muhsin Kaymak
© 2024 lite-C Forums