Tip of the Week #10: New Pathfinding Solution!

Posted By: Superku

Tip of the Week #10: New Pathfinding Solution! - 01/03/14 06:27

A new tip of the week has arrived which is basically just a contribution. It's a new pathfinding solution written from scratch - although similar to my last one from the goodies.zip archive it has many advantages such that it does not need to pre-calculate all paths in a level (and store all those nasty text files in your game folder), that those paths can be changed dynamically (for example when a gate opens), that you don't have to attach a path manually to the entity and that it is in general much more flexible.

See here, TotW #10 (fixed link): http://opserver.de/swik10/index.php?title=Pathfinding

Originally Posted By: TotW #10
The idea behind this pathfinding script is to use regions (optional but highly recommended!) and WED paths and to divide the level into small logical segments. Those segments can be corridors, houses, hangars and so on. See the following screenshot:




The usage is as simple as follows:

Code:
action enemy()
{
	while(1)
	{
		VECTOR temp;
		hpf_region_get_target(temp,my,player.x,HPF_XYZ);
		turn to temp;
		move to temp;
		wait(1);
	}
}



It is just the first version of the script completed minutes ago so please notify me of any bugs that you may find.

There is a newer version/ update which you can find below.
Posted By: 3run

Re: Tip of the Week #10: New Pathfinding Solution! - 01/06/14 08:27

Thank you very much man! laugh I'll test this, as soon as I'll have a chance!
Your "Tip of the Week" series are the most useful I've seen on this forum!

Greets
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 01/06/14 09:13

Thank you, please tell me what you think!
The part where the entity leaves a region definitely needs to be smoothed but it's not so easy because of mutual dependencies. I will try to update and improve it soon.
Posted By: Rackscha

Re: Tip of the Week #10: New Pathfinding Solution! - 01/06/14 12:15

Looks nice.
But you should really take node distance into account for better heuristic wink
Posted By: WretchedSid

Re: Tip of the Week #10: New Pathfinding Solution! - 01/06/14 12:25

Not trying to be an ass, but do it yourself? It's open source code and I'm sure Superku would be glad if other people with knowledge would get behind it as well.

Also, where are all the people who were crying about missing pathfinding solutions? There you have one that's easy to use, shouldn't you rejoice and kiss Superkus feet now or something?
Posted By: rayp

Re: Tip of the Week #10: New Pathfinding Solution! - 01/06/14 14:25

W O W ! Thank you very much my old friend. Felix, if u want i * your * grin
Asap ill look into that great contribution.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 01/06/14 16:39

blush You are welcome!

I've thought about using real node distances, I may do that in the future, too, at least optionally, but it does not really add much. It may get more intuitive this way and more accurate by a few quants but the algorithm will rather get slower, not faster this way (because of additional calculations/ sorting, right now it does at most n/2 iterations with a total of 2n node checks).
Posted By: DLively

Re: Tip of the Week #10: New Pathfinding Solution! - 01/07/14 05:59

THANK YOU Superku!!!

I've been telling my friends how awesome you are laugh
Wait till they hear about this lol
Posted By: Rackscha

Re: Tip of the Week #10: New Pathfinding Solution! - 01/07/14 08:46

Originally Posted By: JustSid
Not trying to be an ass, but do it yourself? It's open source code and I'm sure Superku would be glad if other people with knowledge would get behind it as well.


1) i wrote my own systems for pathfinding wink
Some years ago i presented a demo of an AI which chases the player through a level.
EDIT to 1: Whoops, sorry JustSid, thought you accused me for being a potential parasite. But you meant it the way that i should help if i know how it works. Need more coffe!

2) currently i have no time to contribute to anything
3) I am a Softwaredeveloper, and to avoid later complications, my boss likes to know before i publish something in my sparetime. I know, the german law only restricts to direct concurrent actions, which is mostly not the case. But that job feeds me, so better be on the safe side wink

I wrote a sheetpaper with some points, as i want to discuss which types of projects i can release without asking before.
But that'll need some time.

PS: @Justsid you have a pending PM from me o.O

Greetings
Rackscha
Posted By: WretchedSid

Re: Tip of the Week #10: New Pathfinding Solution! - 01/07/14 18:54

Originally Posted By: Rackscha
3) I am a Softwaredeveloper, and to avoid later complications, my boss likes to know before i publish something in my sparetime.

WHAT?! Dude, seriously, find a new job! (Yes, strap on your job helmet and jump into the job cannon etc. blahblah). Your boss has NO say whatsoever over your free time and what you do with it, unless it involves selling company secrets to the competition. If you employer thinks he has a say over what projects you publish and which not, there is something seriously wrong with your relationship with them.

Originally Posted By: Rackscha
PS: @Justsid you have a pending PM from me o.O

Yes! I've actually read it laugh
I was waiting how long it would take for you to find out that all questions in there are answered in the Rayne thread tongue
Posted By: oliver2s

Re: Tip of the Week #10: New Pathfinding Solution! - 01/07/14 19:05

Originally Posted By: JustSid
Originally Posted By: Rackscha
3) I am a Softwaredeveloper, and to avoid later complications, my boss likes to know before i publish something in my sparetime.

Your boss has NO say whatsoever over your free time and what you do with it, unless it involves selling company secrets to the competition.


That's not true. At least in Germany the boss can claim that, related to employee laws.
Posted By: Quad

Re: Tip of the Week #10: New Pathfinding Solution! - 01/07/14 22:20

THEN MOVE TO ANOTHER COUNTRY, QUICK!
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 09:49

Updated the code, fixed some (partly major) bugs. Entities now leave regions much smoother and more natural, too. Just keep the region borders close to the outer path nodes.
Posted By: pegamode

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 10:14

Hey Superku,

thanks for this contribution. It's great that still some people share their knowledge and code with the community though they're working on their own projects. Unfortunately I wasn't able to share some code for a while :-(

About 2 years ago I struggled with a code I wasn't able to solve the problem due to lack of time. As it was related to pathfinding I thought it might fit to this thread and could be resolved and build in with united forces:

In our Meteor Mess project we use WED paths and a A-star algorithm for moving the characters through the mansion. By clicking left on the screen we search for the nearest node and calculate the path from the current node to the target node. The issue we have is that we have to set quite a lot of nodes (and maintain them) to achieve a smooth movement.
Therefore I thought it might be good to have a code that makes it possible to let the player walk to a point between two nodes (still on the path, but not exactly to the calculated target node). This point would be the nearest point to the click point on the given path instead to the nearest node.
Some of the problems I ran into was that this point might be behind or before the nearest node and to exactly calculate this point (some vector math).
So sometimes the player has to just stop somewhat earlier and sometimes he has to move some further on.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 10:25

Hm I'm not sure if I got your problem correctly. Have you tested my (preferably new) code? Does it have the same problem(s)?
Posted By: pegamode

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 10:47

Yes, I just tried.

The problem is that I want to tie the moving character onto the path. In your version the player first walks to the first node, then follows the calculated path and then walks to the clicked point by leaving the path.

Take a look at this picture:



The blue dot is the clicked point and the red dot is the target I want the player to move to as it's on the path between node 3 and 2.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 11:44

I see. Find the/ some closest nodes (A,B) to the target which are connected via an edge. Then calculate the projection of node A to pos on the vector A->B. This is now your target position.
Posted By: alibaba

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 11:52

Where can i find that updated code? The one in the Wiki is still the same.
Posted By: pegamode

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 11:55

Yes, exactly. With that technique and a character tied to the path one can get rid of many, many nodes. Especially for adventure games this would be great to have.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 01/09/14 13:13

@alibaba: It is the new code on the wiki, I've just replaced the old zip file on my webspace with the new one. I forgot to link it here, though: http://www.superku.de/HPF.zip

@pegamode: Once you find the correct nodes the rest should not be difficult. I've posted such a vector projection some time ago on the forum or have a look at my one region function which calculates the projection onto the region bounding box.

EDIT: Btw. you can use my/ your pathfinding code for this and simply ignore the last node. When the entity reaches the second last node, calculate said projection, "abort" the regular pathfinding and move the entity to the newly calculated target.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 02/23/14 05:24

A simple function set for Bézier curve "interpolation" has been added as well as integrated directly into the pathfinding. It's not perfect (only 1 node gets interpolated/ smoothed at a time for stability reasons in the pathfinding algorithm) but the entity follows a much smoother path now and it's pretty fast, too:

http://opserver.de/swik10/index.php?title=Pathfinding
http://www.superku.de/HPF_v1.21.zip (updated)



(EDIT: fixed links)
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 02/23/14 10:06

Fixed a few pretty big bugs in the function that calculates the projection of the target position onto the region bounding box (green dot in upper screen), the pathfinding barely/ never worked on bigger areas.
Please download the new version here: http://www.superku.de/HPF_v1.21.zip
Posted By: alibaba

Re: Tip of the Week #10: New Pathfinding Solution! - 02/23/14 14:06

Thanks! May come in very handy! laugh
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 10/10/14 07:10

Thanks man! I've just downloaded it. It will save me the trouble of waiting for the current AI series on AUM to be completed before I can learn to add the AI to my racing game laugh
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 10/21/14 16:53

I'm having problems getting the algorithm to work 100% of the time. I wanted to go through the wiki before posting questions which might have been answered there already. However, whenever I try to go there, it redirects to http://unendliches.net/english/
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 10/21/14 17:06

Here is the fixed/ new link: http://opserver.de/qwik8/index.php?title=Pathfinding

What kind of errors/ problems are you experiencing? What is the scale of your level/ game, i.e. your characters, choke points and entity speed per tick?
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 10/23/14 22:24

This error "HPF_PATH_GET: Invalid start/ target node(s)!". How do I check the entity speed per tick? I built a level that's slightly smaller than the "test" level I downloaded with your code and I'm calling up the level from the menu in my game as if it were one of my game's levels. It only has 2 regions and a total of 18 nodes between the 2 paths, and only one AI character. So it's a small level.
My game loads the player into the level, but before now, I hadn't included any NPC in the game. So I put one NPC in my test level and tried to make it so that he finds his way to whatever spot the player was standing when the "t" key was pressed. He should go to that spot even if the player has moved away from the placw. This is the code the AI is running:
Code:
action FollowPlayer()
{
	while(!player)
	wait(-1);
	
	vec_for_min(AIfeet, me); //assigning the lowest position of the model to the vector named "AIfeet"
	
	c_setminmax(my);
	vec_fill(my.min_x,-24);
	vec_fill(my.max_x,24);
	vec_set(PlayerTarget,my.x);
			
	my.skill10 = hpf_path_get_max_nodes(my);
	my.group = 2; // ignore other enemy units when doing pathfinding and visibility calculations (with IGNORE_PUSH)
	
	while(1)
	{
		if(key_t)
		vec_set(PlayerTarget, vector(player.x, player.y, player.z));
		
		my.red = 0;
	 	my.ambient = 0;
	 	my.lightrange = 0;
		
		if(!key_ins) hpf_region_get_target(temp,my,PlayerTarget,HPF_XYZ); //using insert key for dummy if statement
		else vec_set(temp, PlayerTarget);
		hpf_path_draw(my,COLOR_GREEN);
		temp.z = my.z;
		if(vec_dist(temp,my.x) > 16)
		{
			my.red = 100;
	 		my.ambient = 100;
	 		my.lightrange = 100;
	 		
			vec_diff(temp2,temp,my.x);
			vec_to_angle(temp,temp2);
			my.pan += ang(temp.x-my.pan)*0.25*time_step;
			result = c_move(me,vector(maxv(10-0.1*abs(ang(temp.x-my.pan)),0)*time_step,0,0), vector(0, 0, -AIdistancedown),IGNORE_PASSABLE | GLIDE);
			my.skill1 += result;
			my.skill1 %= 100;
			ent_animate(me,"run",my.skill1,ANM_CYCLE);
			
				
	 		//gravity codes		
	 		if(c_trace(my.x, vector(my.x,my.y,my.z-10000), IGNORE_ME|IGNORE_PASSABLE |USE_BOX) > 0)
	   	    AIdistancedown = my.z + AIfeet.z - target.z;
	     	else
	    	AIdistancedown = 0;
	   	
	    	if(AIdistancedown > 0)
	    	AIdistancedown = clamp(AIdistancedown, 0, accelerate(mygravity, 9.8, 0.1)); //0.1 is friction, accelerate "mygravity" by 9.8
	    	//clamp limits distance down to lower limit 0 and upper limit accelerate(mygravity, 9.8, 0.1)
	    	else
	    	{mygravity = 0; vec_set(AILastSolidGround,vector(my.x,my.y,my.z));}
	    	//if Mon is on ground, set gravity to zero and store position of mon on ground
		}
		
		var i;
		for(i = 1; i <= my.skill10; i++)
		{
			path_getnode(my,i,temp,NULL);
			if(vec_to_screen(temp,camera))
			{
				draw_text(str_for_num(NULL,i),temp.x-9,temp.y-9,vector(50,50,50));
				draw_text(str_for_num(NULL,i),temp.x-10,temp.y-10,COLOR_RED);
			}
		}
	
		
		wait(1);
	}
}



Sometimes it works perfectly. At random times, it gives this error "HPF_PATH_GET: Invalid start/ target node(s)!"
On the last few attempts, the whole game would hang without an error message. I can't find any pattern to the problem because the AI finds its way to certain spots perfectly sometimes, then crashes or gives an error at other times when asked to find its way to the same spot.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 10/24/14 09:21

Ok. I will get back to you in the next let's say 24 hours.
What I meant with "how big is your level" was not the actual content or size in terms of complexity but the actual quant size because it has only been thoroughly tested in the scale that you see in the demo level (or in my sidescroller where I use the pathfinding all the time and haven't had a single error since).
First guess:
Do you have multiples paths in the level which have the same name?
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 10/25/14 01:08

No, just path_000 and path_001. I even tested to see whether I could use names like Tpath_000 and Treg_000 but adding any other characters to the path and region names doesn't work with your code. Can you point out what line of code I can go edit so that I can use custom names for my paths and regions?
In WED, quants are represented by the smallest, indivisible cubes when the view is zoomed into 16x8 right? Then my level is about 176 quants wide and 128 quants high. Thanks a lot
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 10/26/14 10:19

hpf_region_get_target()
uses region_find() and some string manipulation to determine the appropriate path name. Have a look at line 529 and following:

Code:
str_clip(str_tmp,3);
str_printf(str_tmp,"path%s",_chr(str_tmp));
if(!path_set(ent,str_tmp)) error("HPF_REGION_GET_TARGET: Path to region does not exist!");



Apparently when you want to use Treg_ and Tpath_ as names you will have to adapt the number in str_clip (change it to 4).


Your enemy/ NPC code looks fine to me. hpf_region_get_target() calls hpf_path_get_target() which calculates corresponding start and target nodes which are then used by a subsequent hpf_path_get() call. You could add a
printf("Start: %d, Target: %d, Max_nodes: %d",(int)start_node,(int)target_node,(int)max_nodes);
before the error() instruction in line 216.

Try disabling hpf_path_get_target_collision (in the *.h file) temporarily, too.
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 10/27/14 22:53

Changing the number in str_clip to 4 (or 5 for that matter) didn't allow me to use Treg_ and Tpath_, but it's cool because I can still use custom names. reg_tee and path_tee work perfectly without any need to edit your code at all. Curiously, the code block that contains "draw_text(str_for_num(NULL,i),temp.x-10,temp.y-10,COLOR_RED);"
doesn't seem to work with my custom names. I know it's merely for debugging purposes to let us see the nodes' locations during run time, but I thought it might be worth pointing out.

How do I disable hpf_path_get_target_collision? Would changing
Code:
var hpf_path_get_target_collision = 1;

in line 63 to
Code:
var hpf_path_get_target_collision = 0;

do the trick?

The values I got after replacing the error code with the printf you suggested were
"Start: -1, Target: 1, Max_nodes: 12" (got this a few times)
"Start: 7, Target: -1, Max_nodes: 10" (same path as above after I deleted 2 unnecessary nodes. They weren't connected to the rest of the nodes)
"Start: -1, Target: 1, Max_Nodes: 6"
"Start: 6, Target: -1, Max_nodes: 10"
I still haven't found a way of reproducing the error 100% of the time. Sometimes, I'll try about 8 times and the AI will make his way to the target perfectly each time. The only pattern I've been able to notice is that the error pops up ONLY when the AI (and hence, the start node) is in a different region from the target/the player's position when I press "t" to trigger the function.
The error usually doesn't pop up as soon as I hit "t", but when the NPC has already traveled about halfway to his target, sometimes when he's just about to reach the target. Sometimes, the game still hangs without any error message.
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 10/29/14 09:30

I assume the project is not that big yet? Can you send it to me please for debugging purposes?
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 10/30/14 11:30

Will send you a direct message. Thanks.
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 11/06/14 14:16

Sorry, I couldn't find a way to add this thread to my watched topics without posting a reply so consider this reply an empty string laugh
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 11/06/14 14:35

I've had a look at my code and the corresponding functions twice and tried to force an error by using two different regions (and paths) for start and target nodes but I couldn't find anything or reproduce the error yet.
I sadly don't have an idea right now what could be the cause of the error but I will keep on thinking about it.
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 11/08/14 14:48

Ok, thanks. When you run my own game on your computer, does it crash like I said it does on my computer? I noticed that if the AI is in another region and I call the function to make him come over to the player's position, he starts coming and the game doesn't crash until the second he steps into the player's region. And the crashes only seem to happen 1 out of 8 times.
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 11/20/14 13:06

So I was wondering...what's the advantage of breaking the level into small sections, each with its own path and region? As it is, even though we're not yet sure what it is about my code/level structures that causes the occasional crash, your code won't crash in my game if I used only one region and one path. For relatively small levels, why don't I just use one big region with one path?
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 11/20/14 13:35

As I am using the same pathfinding code in my sidescroller game I hope to find the cause for the error some time soon but I didn't have much time for Gamestudio the last couple of weeks.
Until then it's fine to use just a single region and path for your enemies and objects.
The advantage of multiple regions and corresponding paths is not only ease of usability (in terms of level creation) and performance but the movement in non-regions is more flexible and smoother because the entity will not try to follow a path but move directly to the (potentially dynamic) target.
Posted By: tolu619

Re: Tip of the Week #10: New Pathfinding Solution! - 11/22/14 09:07

Your game is almost complete and the code has given you no problems. It probably has something to do with tracking in 3 dimensions. Anyway, thanks. I'll use a single large region in the mean time
Posted By: Superku

Re: Tip of the Week #10: New Pathfinding Solution! - 08/11/15 20:07

There is a new and improved version available!
Major new feature is debugging function which you can call each frame:
void hpf_debug(ENTITY* ent, var mode, COLOR* color);

This should help with debugging and isolating problems. There are some other features and more customizability so make sure you check the "hpf_pathfinding.h" configurable stuff area.

Download: http://superku.de/HPF_v1.25.zip

Posted By: Reconnoiter

Re: Tip of the Week #10: New Pathfinding Solution! - 08/11/15 20:14

Thanks, I soon want to implement pathing in a new project so this will come in handy for ideas.
Posted By: Superku

TotW#10: Pathfinding 1.26 - 12/12/16 12:22

There is a new and improved version available!
It mostly consists of bug fixes, some of which quite severe (including an infinite loop and, even more importantly, the pathfinding not working when entities moved across multiple regions!).

There is an (unused) new function which lets you project a position in world space onto a WED path, for example to put a camera on a path with the player's position in mind.

Download: http://superku.de/HPF_v1.26.zip
Posted By: alibaba

Re: TotW#10: Pathfinding 1.26 - 12/12/16 13:32

Woot! Thanks! Gonna try it now
© 2024 lite-C Forums