[Sub] Pathfinding

Posted By: Wade_Adams

[Sub] Pathfinding - 11/17/04 12:34

This part I of a pathfinding tutorial I am working on. Please indicate suggestion and interest.

http://home.comcast.net/~wadams73/Pathfinding1.zip
Posted By: A.Russell

Re: [Sub] Pathfinding - 11/18/04 02:06



Looks good.

I didn't know 3dgs had pathfinding. When did that happen?

I always thought you could only make paths for actors to follow around like they were on rails. Can you actually use them to get to any position in your level?

I'm not sure why you included that note about setting the video driver. How is that related to this tutorial?
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 11/18/04 02:26

I think it is new to 6.31.x I think. The new instructions are in the update63.txt. and yes the driver part is very important because you can'y edit the paths in WED without changing it. In my experiance the new stuff didn't work at all until I did so for the newbs that aren't going to read the update file I added that to keep from getting ask the question a couple hundred times. I am working on some mode advanced use of the pathfind in terms of a usable AI. That is going to be Part II. I am thinking of some more thoughtful maze alogorthims in PartIII. I trying to bring it up gradually not to loose the newbie that may want to try this too.
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 11/19/04 03:02

Not much comment on Part I. Part I was a necessary evil to make sure everyone understood, before diving into part to. Part II is about 80% complete. It will involve an enemy that chases the player via a web of path nodes. Pretty cool if I say so myself.
Posted By: Grimber

Re: [Sub] Pathfinding - 11/19/04 05:00

part 1 looks good, can't wait to see part 2
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 11/20/04 10:52

Ok part II is up comments welcome.

http://home.comcast.net/~wadams73/Path_Finding_Part_II.zip
Posted By: Grimber

Re: [Sub] Pathfinding - 11/21/04 15:21

looks very good wade. havn't tried it yet but reads well and easy to understand.
Posted By: Locoweed

Re: [Sub] Pathfinding - 11/21/04 18:44

Very interesting. I learned quite a bit about the new path commands and it will be interesting to see how far you get with this.

I played around with it a bit and got it so whenever the player got in view it would quit path and also had it go to the farthest visible node on the path first instead of just the closest. But unless you have the paths set up like you do, it won't always take the shortest path, for instance, if you set the nodes up like you would for router pathfinding. Of, course this makes sense, and could probably be made to work.

Anyway, good job. I will keep an eye on this thread.

Loco
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 11/22/04 00:16

Yes there a all sorts of things with node theory. It is true that you may not get the shortest path with this alogrithim, This can be minimize with carful design of the path. I was wondering if anyone would catch that. The advantage is that it is fast. If you have to compute all of the node between point A and point B every frame for 50 AI characters would kill my computer.
Posted By: William

Re: [Sub] Pathfinding - 11/27/04 17:48

Thanks Wade! Always intrested in reading pathfinding/node tutorials.
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 11/28/04 12:57

Thanks, still a work in progress. Let me know what you think. The holiday has put a kink in my time table. Hopefully I will get something new up soon...

I would have thought there would be more interest than there has been. Maybe when it is done.
Posted By: A.Russell

Re: [Sub] Pathfinding - 11/28/04 15:06


I think you'llfind there is more interest in this than your number of replies on this thread suggests. I, for one, am looking forward to it.
Posted By: Locoweed

Re: [Sub] Pathfinding - 11/28/04 15:20

I am anxiously awaiting Part III.
Posted By: Grimber

Re: [Sub] Pathfinding - 11/28/04 15:42

Im definatly reading it so far. put part 1 and 2 on my site this week ( just have to add teh links is all.)
Posted By: Alkai

Re: [Sub] Pathfinding - 11/30/04 00:55

Definitely continue!
Posted By: A.Russell

Re: [Sub] Pathfinding - 12/26/04 12:47



How is this coming along, anyway?
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 12/27/04 01:05

I have been a bit distracted with other stuff recently. Also the algorithm I was using in part II doesn't work for complicated paths. One could alway break out Dijkstra's Algorithm, but it seems a bit too terminator like. I want something a bit more fuzzy. Honestly with work I haven't had much of a chance other that to see that something a bit more complicated in order.
Posted By: A.Russell

Re: [Sub] Pathfinding - 12/27/04 23:46

What is "Dijkstra's Algorithm"? I was under the impression a simple A* was what most people went with.

Edit> I just checked it out on the internet. I'd go with A*, it is a little more efficient and flexible. A pain to write in c-script though (you'll have to use single dimension arrays to store all that data). Perhaps you could do that side of it in the SDK and include it as a plugin with the tutorial? Dijkstra's Algorithm doesn't appear to be much less data intensive.








Posted By: Rhuarc

Re: [Sub] Pathfinding - 12/28/04 02:21

Dijkstra's algorythm was used in router paths if I remember right (dear god, my memory scares me). A* is the best to use for games because it is very accurate and also very fast compared to the other options. Precalculated paths using A* can increase performance by not doing the calculations in-game (which leaves you with a static, unchanging path table). Another option is to go with D* (Dynamic A*), it's a touch slower but allows much more dynamics.

-Rhuarc
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 12/28/04 03:02

I may just do that and add a fudge factor to force AI to not take the optimal path.
Posted By: abetrader

Re: [Sub] Pathfinding - 03/22/05 04:40

Your tutorial is great.
I am trying to implement it into my game which is a hovercraft game.
If I place a node high up in a room how do I program the enemy craft to rotate upward and go up.

Thanks
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 03/23/05 11:03

What is stoping that is the my.tilt=0; in there. Also I wanted to add I've had personal issues keeping me out the loop recently. I hope to be back before too long.
Posted By: mk_1

Re: [Sub] Pathfinding - 03/23/05 22:10

Where's the problem with one dimensional arrays? As long as you use a binary heap there should be no problems.
Posted By: abetrader

Re: [Sub] Pathfinding - 03/24/05 04:46

The code you have in totorial1 is:
action patrol_path
{
var node_pos[3]; // temp storage for node position in AI
var node; // current node
var dist; // distance to node

// attach entity to nearest path
node = path_scan(me,my.x,my.pan,vector(360,180,1000));
if (node == 0) { beep();return; } // no path found

// find first waypoint
path_getnode(my,node,node_pos.x,null);


while (1)
{
// find distance
dist = vec_dist(node_pos.x,my.x);

// near target? Find next waypoint of the path
if (dist < 25) {
beep(); // you can comment this out is is nice for test though
node = path_nextnode(my,node,1);
path_getnode(my,node,node_pos.x,NULL);
}
vec_set(temp, node_pos.x);
vec_sub(temp, my.x);
vec_to_angle(my.pan, temp);

my.tilt = 0; // I'm a maniac
temp.x = 5 * time;
temp.y = 0;
temp.z = 0;

c_move (my, temp, nullvector, IGNORE_YOU + IGNORE_PASSABLE + IGNORE_PUSH + ACTIVATE_TRIGGER + GLIDE);

wait(1);
}
}

The code I marked in red is the movement code. How do I change it that if I set the node high up the enemey ship gos up? (I tried deleting my.tilt = 0; but it did not work.)
Also the line of code that turns the enemey towards the player(vec_to_angle(my.pan, temp)) makes the enemey ship snap into place, how do I make it rotate smoothly.

Thank you.
Posted By: jumpman

Re: [Sub] Pathfinding - 03/26/05 07:26

I dont think this has anything to do with pathfinding, but how about trying this for your tilt problem:

// create a vector skill beforehand

define target_angle,skill1;
define target_angle,skill2;
define target_angle,skill3;

// apply the target angle to the skills, not the entity itself

vec_set(temp, node_pos.x);
vec_sub(temp, my.x);
vec_to_angle(target_angle, temp);

//then apply the hover craft the new angles:

my.pan=target_angle.pan;
my.tilt=target_angle.tilt;

I think that should work.

(although this isnt helping to get off the tangent )
Posted By: abetrader

Re: [Sub] Pathfinding - 03/28/05 01:15

I had to use "var target_angle;" instead of the defines.

Besides for that it works great

Thank you.
Posted By: FeiHongJr

Re: [Sub] Pathfinding - 03/29/05 01:43

if you want to use them as defines instead then use my.target_angle and so on in the functions instead of calling them like target_angle im not positive but a var might conflict if you have more then one ship in the level unless you declared them in the function then i dont think it would matter. this is just to my understanding of variables and their scope. so using them as defines is probally the best bet so that you can use them in as many functions as you want since it will point to that entitys skill instead of a global var. hope that makes sense
Posted By: Vfx

Re: [Sub] Pathfinding - 03/29/05 20:54

Off-topic
Posted By: abetrader

Re: [Sub] Pathfinding - 03/30/05 11:42

I tried using skills but I am getting errors in lines:
my.pan =my.target_angle.pan;
my.tilt = my.target_angle.tilt;
Posted By: Locoweed

Re: [Sub] Pathfinding - 04/05/05 15:19

action patrol_path
{
var node_pos[3]; // temp storage for node position in AI
var node; // current node
var dist; // distance to node
var temp_angle[3];
var target_angle[3];
var temp_pan[3];
var rotation_speed = 6;
.
// get direction to target
vec_set(temp, node_pos.x);
vec_sub(temp, my.x);
vec_to_angle(temp_angle, temp);
.
// get difference of current angle to desired angle
target_angle.pan = ang(temp_angle.pan - my.pan);
target_angle.tilt = ang(temp_angle.tilt - my.tilt);
// move towards desired angle over time
temp_pan.pan = target_angle.pan * rotation_speed * time;
temp_pan.tilt = target_angle.tilt * rotation_speed * time;
temp_pan.roll = 0;
// must use c_rotate() to turn if using c_move()
c_rotate(my,temp_pan,IGNORE_YOU + IGNORE_PASSABLE + IGNORE_PUSH + ACTIVATE_TRIGGER + GLIDE);
// move the entity
c_move (my, temp, nullvector, IGNORE_YOU + IGNORE_PASSABLE + IGNORE_PUSH + ACTIVATE_TRIGGER + GLIDE);
.

That should be closer methinks.
Loco
Posted By: FeiHongJr

Re: [Sub] Pathfinding - 04/06/05 19:36

try deleteing the my. in front of target_angle.tilt and .pan hope that helps
Posted By: SandGroper

Re: [Sub] Pathfinding - 04/21/05 21:12

cheers i shall checkout your finder!
Posted By: Wade_Adams

Re: [Sub] Pathfinding - 04/26/05 22:39

Well I am trying to creep back into 3DGS. Hopefully I can get a look at part 3 and figure out what's going on with it. I am almost positive the bug is in how I am storing the data I will keep everyone posted.
Posted By: william_123

Re: [Sub] Pathfinding - 05/05/05 05:15

Part 1 and part 2 both looks very good, can't wait to see part 3.
Posted By: Wade_Adams

Re: [Sub] Pathfinding Part 3 - 05/14/05 00:13

It isn't a tutorial yet, but check the code and let me know what you think.

http://home.comcast.net/~wadams73/Pathfinding3.zip
Posted By: Wade_Adams

Re: [Sub] Pathfinding Part 3 - 05/29/05 02:12

well it seems my script works along as you don't have any dead ends in the path, but it seem to frequently seems to pick the longest path which is not good. I am going to have to tweak the algorithm to guess better which path is best. I will also I to be a bit more elaborate with which edges have been checked already because as of now the ai will always check down edge one and if a path exist down edge one then that is the one it will take even if the path is bad. So, what I think I will do is search the edges and use bitwise operations to pull which edges have been visited yet.
Posted By: Wade_Adams

Re: [Sub] Pathfinding Part 3 - 05/29/05 15:18

Well, I made the above changes, and they seem to work well I will test them futher with a move complicated level. If any one want to give some feedback so far it is welcome. ALso space bar currently toggles the camera from player to the enemy AI. If all goes well, I will develop a tutorial level and the tutorial soon. Again, sorry for the delay on this... I hate to promise something and not deliver; so, hopefully I can correct that soon.
© 2024 lite-C Forums