3 registered members (AndrewAMD, SBGuy, Petra),
801
guests, and 8
spiders. |
Key:
Admin,
Global Mod,
Mod
|
|
|
Tip of the Week #10: New Pathfinding Solution!
#435118
01/03/14 06:27
01/03/14 06:27
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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=PathfindingThe 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:
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.
Last edited by Superku; 08/08/15 08:29.
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#435312
01/06/14 08:27
01/06/14 08:27
|
Joined: May 2009
Posts: 5,370 Caucasus
3run
Senior Expert
|
Senior Expert
Joined: May 2009
Posts: 5,370
Caucasus
|
Thank you very much man! 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
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#435331
01/06/14 12:15
01/06/14 12:15
|
Joined: Dec 2008
Posts: 1,218 Germany
Rackscha
Serious User
|
Serious User
Joined: Dec 2008
Posts: 1,218
Germany
|
Looks nice. But you should really take node distance into account for better heuristic
MY Website with news of my projects: (for example my current Muliplayer Bomberman, GenesisPrecompiler for LiteC and TileMaster, an easy to use Tile editor) Sparetime-Development
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Rackscha]
#435333
01/06/14 12:25
01/06/14 12:25
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
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?
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: rayp]
#435351
01/06/14 16:39
01/06/14 16:39
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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).
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#435383
01/07/14 05:59
01/07/14 05:59
|
Joined: Apr 2005
Posts: 1,988 Canadian, Eh
DLively
Serious User
|
Serious User
Joined: Apr 2005
Posts: 1,988
Canadian, Eh
|
THANK YOU Superku!!! I've been telling my friends how awesome you are Wait till they hear about this lol
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: WretchedSid]
#435388
01/07/14 08:46
01/07/14 08:46
|
Joined: Dec 2008
Posts: 1,218 Germany
Rackscha
Serious User
|
Serious User
Joined: Dec 2008
Posts: 1,218
Germany
|
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 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 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
Last edited by Rackscha; 01/07/14 08:58.
MY Website with news of my projects: (for example my current Muliplayer Bomberman, GenesisPrecompiler for LiteC and TileMaster, an easy to use Tile editor) Sparetime-Development
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Rackscha]
#435412
01/07/14 18:54
01/07/14 18:54
|
Joined: Apr 2007
Posts: 3,751 Canada
WretchedSid
Expert
|
Expert
Joined: Apr 2007
Posts: 3,751
Canada
|
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. PS: @Justsid you have a pending PM from me o.O Yes! I've actually read it I was waiting how long it would take for you to find out that all questions in there are answered in the Rayne thread
Shitlord by trade and passion. Graphics programmer at Laminar Research. I write blog posts at feresignum.com
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: WretchedSid]
#435413
01/07/14 19:05
01/07/14 19:05
|
Joined: Aug 2002
Posts: 3,258 Mainz
oliver2s
Expert
|
Expert
Joined: Aug 2002
Posts: 3,258
Mainz
|
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.
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#435580
01/09/14 10:47
01/09/14 10:47
|
Joined: Feb 2006
Posts: 1,011 Germany
pegamode
Serious User
|
Serious User
Joined: Feb 2006
Posts: 1,011
Germany
|
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.
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: pegamode]
#435592
01/09/14 13:13
01/09/14 13:13
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
@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.
Last edited by Superku; 01/09/14 13:47.
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#437689
02/23/14 05:24
02/23/14 05:24
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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=Pathfindinghttp://www.superku.de/HPF_v1.21.zip (updated) (EDIT: fixed links)
Last edited by Superku; 08/08/15 08:30.
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#437694
02/23/14 10:06
02/23/14 10:06
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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
Last edited by Superku; 02/23/14 14:49.
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#446632
10/23/14 22:24
10/23/14 22:24
|
Joined: Jun 2014
Posts: 97 Lagos, Nigeria
tolu619
Junior Member
|
Junior Member
Joined: Jun 2014
Posts: 97
Lagos, Nigeria
|
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:
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.
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: tolu619]
#446661
10/26/14 10:19
10/26/14 10:19
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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:
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.
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: Superku]
#446684
10/27/14 22:53
10/27/14 22:53
|
Joined: Jun 2014
Posts: 97 Lagos, Nigeria
tolu619
Junior Member
|
Junior Member
Joined: Jun 2014
Posts: 97
Lagos, Nigeria
|
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
var hpf_path_get_target_collision = 1;
in line 63 to
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.
|
|
|
Re: Tip of the Week #10: New Pathfinding Solution!
[Re: tolu619]
#453766
08/11/15 20:07
08/11/15 20:07
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
TotW#10: Pathfinding 1.26
[Re: Reconnoiter]
#463551
12/12/16 12:22
12/12/16 12:22
|
Joined: Sep 2003
Posts: 6,861 Kiel (Germany)
Superku
OP
Senior Expert
|
OP
Senior Expert
Joined: Sep 2003
Posts: 6,861
Kiel (Germany)
|
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
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual Check out my new game: Pogostuck: Rage With Your Friends
|
|
|
|