Behold Pathfinding!

[Soul-Blade]

Alrighty, I was working on pathfinding. I haven't touched this script up, so it is a direct integration of A* pathfinding...or in other words, I haven't optimized the script to the best of my abilities yet, mainly because of the errors I am going to tell you about soon.

Anyway, I am posting this because 1) If not a scripter, be amazed by pathfinding and 2) If a scripter, and want to help make a pathfinding function for people to use, then you have a chance.

I've done all the hard parts (I think) on this pathfinding script, but I ran into a few problems I will outline here.

The biggest problem, as you will see in the script, is that the while loops are not functioning correctly. If I do not place a sleep 0.05 after the while, then the while loops oddly end early, among other strange effects. But if I put a sleep 0.05 after the while, the script obviously takes ages to complete calculation (about 3 minutes on average, actually). It is tricky, and if you have a solution please tell me.

Another error, though not nearly as large as the above, is moving the Start location around. I haven't found a pattern yet, but if you move it to the right of the level is skips most of the loops, and well, it is just weird. Have a look yourself.

Another error, though not so much a error as a little glitch, is the "diagnal movement" stuff. You'll see...it is caused by the script when going backwards from the end point choosing a random direction of a smaller number, when it choose there are usually about 3 possible choices, usually 1 of which being straight up and done, and 2 of which being diagnal. Anyway, you'll see.

This pathfinding script is currently far from usable, but we could all learn a thing of turn making it work (and would make me very happy =P).

Well, I actually do need to get it to work for my own projects of course, but the reason I've posted this rather then using my sources on AIM, is so people can use this. After working on this pathfinding, I have discovered it to be a rather complicated script to complete, and I doubt many people wanted this could do it. So as a benefit to graal, here it is...(though I am warning once again, it is needing to be completed so it works 100% nicely).

Thats about it...though I know I forgot something. Be patient, in its current state it will take a few minutes to calculate as I said before.

[Snakeandy7]

I don t really understand it sorry.. Some nice scripting tho
Sorry, i'm not good at scripting so i carnt help

[marcoR]

I can't open this zip folder... Im not a scripter but im still interested...

[Soul-Blade]

Originally posted by marcoR
I can't open this zip folder... Im not a scripter but im still interested...

Eh...thats odd. I can open it fine.

[TribulationStaff]

The biggest problem, as you will see in the script, is that the while loops are not functioning correctly. If I do not place a sleep 0.05 after the while, then the while loops oddly end early, among other strange effects. But if I put a sleep 0.05 after the while, the script obviously takes ages to complete calculation (about 3 minutes on average, actually). It is tricky, and if you have a solution please tell me.

Have you considered an if that sleeps it every, say, ten iterations?


Also, why didn't I think to look for open source pathfinding code? C'est la vie. Well, my little lost newbie script will certainly work well enough for marketplaces and such.

Lastly, if you can do this, I am surprised you needed to call on my services at all for SA, good work.

[edit] What the? n 0 0 b is censored? [/edit]

[Thought]

This would work well if we could get Stefan to implement it serverside and clientside (for speed reasons).

[Spark910]

I couldnt see anything, whats it doing.

[Thought]

At the beginning it's calculating the path, because Graal Script is very slow (and the 0.05 delay), it takes about 5 minutes before the NPC starts walking.

[tlf288]

I hate you Soul-Blade .

[Thought]

The diagonal pathing bug really shows

[Kaimetsu]

Originally posted by Thought
This would work well if we could get Stefan to implement it serverside and clientside (for speed reasons).

Hehe, we tried that back when I was on NW. Stefan didn't seem too keen. I wrote a similar algorithm over two years ago - one of the sample scripts the NW guys required involved an NPC with a daily schedule, so I invented and wrote a full pathfinding algorithm for him (at that point, I had never even heard of A*). Overkill, I know, but that's my style

In any case, tile-by-tile methods are horribly inefficient when navigating over any large distance. Predefined nodes are the way to go.

[TribulationStaff]

In any case, tile-by-tile methods are horribly inefficient when navigating over any large distance. Predefined nodes are the way to go.

Hooray! My little lost newbie isn't so bad after all!

[Projectshifter]

I'm about to take a look, and judging by that screenie and what people are saying, it sounds really good. I'm very impressed to say the least. Konidias asked me how to make one, and it was like 3 am in the morning so I didn't have time nor the will to do it then
Nice work m8.
---SHifter

[adam]

:-/ this is pretty dang hard.

Mine will sometimes find the path, but he keeps blocking himself in, becouse I made it so he can't go back on tiles he already crossed.

[adam]

Behold! if you don't move them it works.


(Yes I know I used the other fella's start and end graphics)

[Soul-Blade]

Originally posted by TribulationStaff

Lastly, if you can do this, I am surprised you needed to call on my services at all for SA, good work.

-_- I told you I was a good scripter to start. I just need help on special effects occasionally, because I don't want average, I want amazing. And I lack in being able to make good special effects (though lately, I have been surprising myself x-x)

btw, A* is a concept for pathfinding, just do a little research. It is the most popular one, but not the most efficient. I've read up alot of it in the past, and I never really gave a shot of making one up...lately with all the pathfinding talk I decided to try.

Originally posted by adam

Behold! if you don't move them it works.

Read my original post again. I said the start NPC is a little odd, but the end NPC works perfect. Leave start alone and move end anywhere on the maze and the NPC will always find a way if there is a way.

Originally posted by Kaimetsu

In any case, tile-by-tile methods are horribly inefficient when navigating over any large distance. Predefined nodes are the way to go.

Agreed. Which is why I am going to finish this tile-by-tile method after I make the node web system we discussed.

I was thinking of the concept of it, and I think I got it all figured out. It will work similiar to the A* technique, except instead of thousands of indexes in multiple arrays, it will only be about 20 or so, and would work instantly. My plan is this: First the NPC detects any nodes seen from the start point, and from that start (assigned number 0) it assigns every seen node number 2. From there, the nodes assign every unassigned node a number increasingly, and once a node has line of sight of the target, the node cost script will be terminated. At that point, it will work backwords from the target, saving the x/y coord of the nodes. Each time it selects a new node, it will decrease the value, and eventually it will get to the start point. From there, pathing is complete and all you must do is reverse the targets trip for the start, and so on more easy stuff.
Heh, I suppose it is still a form of A*, but it must be agreed that it is a superior form as far as efficiency goes. It is also the only smart way to do long distance travel for serverside pathfinding (I was trying to tell Konidias the horrid lag which would occur using A* over a gmap, but I don't know for sure, so maybe I am wrong. I think it would lag tremendously though).

Oh also, I am thinking to solve the problem with this path finding, I should seperate the loops so each loop will stay under 10,000. I need to figure everything though...maybe Giltwists plan of using sleep would work. I was thinking of assigning a sleep every 9999 runs of a loop, but it might be better to find ways to reduce the number of loops it requires.

Heh, I really should bother Stefan about making a built in pathfinding function -_-.

[Soul-Blade]

Originally posted by Thought
The diagonal pathing bug really shows

lol, yes. That will be the last thing I fix when I decide to work on this script some more...mainly because there are funner things needing to be integrated first, such as Mr.Findit occasionally plotting the wrong course (I mean, who could find something in their first try?! Not even Mr.Findit should be able to do that :P).

[Kaimetsu]

The loop limit shouldn't be a huge problem (I'm still not entirely sure how it works, I need to ask Stefan about it) if you segment the overworld. One set of nodes per town, a few other sets for areas of wilderness etc.

[adam]

Originally posted by Soul-Blade


Read my original post again. I said the start NPC is a little odd, but the end NPC works perfect. Leave start alone and move end anywhere on the maze and the NPC will always find a way if there is a way.

lol, I forgot to attach what I did, that must have been confusing.

[Projectshifter]

I took a look at the scripting, quite nice, but it does takea long time, I'm sure we can find a way to fix this though.
Can either one of you explain how the nodes would work? I understand WHAT a node is, but I'm not sure how you would implement is so?
---Shifter

[adam]

Originally posted by Projectshifter
I took a look at the scripting, quite nice, but it does takea long time, I'm sure we can find a way to fix this though.
Can either one of you explain how the nodes would work? I understand WHAT a node is, but I'm not sure how you would implement is so?
---Shifter

I believe they mean instead of having to check all 4096 tiles. they can check like 96 nodes. scattered arround the level in places where they can all see eachother directly. Positioned around major obstacles.

Here this one seems ot work all the time now! remove the sleep to make it fast.

[Soul-Blade]

Originally posted by Kaimetsu
The loop limit shouldn't be a huge problem (I'm still not entirely sure how it works, I need to ask Stefan about it) if you segment the overworld. One set of nodes per town, a few other sets for areas of wilderness etc.

Oh, of course. The loop stands no problem what-so-ever for node system, but for completing the pure A* one it could. I have not really worked on it since I posted this, but I will soon, so I will see how well I can get it to work avoiding the limit.

Originally posted by Projectshifter

I took a look at the scripting, quite nice, but it does takea long time, I'm sure we can find a way to fix this though.
Can either one of you explain how the nodes would work? I understand WHAT a node is, but I'm not sure how you would implement is so?
---Shifter

The solution to fixing it is clear, I just haven't got around to it lately. Reduce the number of loops, or add a sleep occasionally (or ask Stefan a better way) and it will work. The reason and only reason it takes long is because of the sleep 0.05 every loop, in each while, in the caculation. The sleep in the plotting course area near the bottom can be removed though, I thought it was just a nice effect.

Now on to the node system
My implementation includes using cool little node graphics for NPCs. Basicly rather then checking tiles, I will check to see if the NPCs graphic is set to the node graphic (or possibly use a save[index] variable, in addition). There will be less then 5 or maybe even less nodes per level, but it doesn't really matter the number because the nodes themselves will most likely have no script at all, other then hide.

I will post it when I am finished with it, which could be in about a week as I am most likely leaving for that long. The major thing needed to know is that it is essentialy for efficient serverside pathing.

Originally posted by adam

I believe they mean instead of having to check all 4096 tiles. they can check like 96 nodes. scattered arround the level in places where they can all see eachother directly. Positioned around major obstacles.

Here this one seems ot work all the time now! remove the sleep to make it fast.

ROFLOL that was cool. He made like a maze of showpoly. I wonder how well that pathfinding would work in Mr.Findits maze hehe.

[Dach]

I got it to be a little less spastic when it comes to diagonal movement, it just needed to check the cardinal dirs first. But if you want it to not do that at all it would need to be able to move diagonaly in smaller increments (.5ish)

[Kaimetsu]

Originally posted by Soul-Blade
Now on to the node system
My implementation includes using cool little node graphics for NPCs. Basicly rather then checking tiles, I will check to see if the NPCs graphic is set to the node graphic (or possibly use a save[index] variable, in addition). There will be less then 5 or maybe even less nodes per level, but it doesn't really matter the number because the nodes themselves will most likely have no script at all, other then hide.

Making one NPC per node is not necessarily the best way. My system holds them all in an array.

[adam]

Originally posted by Soul-Blade

ROFLOL that was cool. He made like a maze of showpoly. I wonder how well that pathfinding would work in Mr.Findits maze hehe.

I tried it in your maze, It dislikes moving backwords too much. It tracked and re-tracked everything so many times, it just concked out eventually. And it stops working faster if you don't use sleep.

[Projectshifter]

I still don't get all the mathmatical crap here... I need to sit down and read up on HOW it goes through it all... been too busy as of late, I guess it's time to check the entire script and figure it out now.
---Shifter

[adam]

Originally posted by Projectshifter
I still don't get all the mathmatical crap here... I need to sit down and read up on HOW it goes through it all... been too busy as of late, I guess it's time to check the entire script and figure it out now.
---Shifter

Here is the site I found to describe it.

http://www.policyalmanac.org/games/aStarTutorial.htm

It even has a download with a really cool pac-man-ish example of pathfinding.

It's cool and very very fast. and always works! wow!

[Androk]

Originally posted by adam


Here is the site I found to describe it.

http://www.policyalmanac.org/games/aStarTutorial.htm

It even has a download with a really cool pac-man-ish example of pathfinding.

It's cool and very very fast. and always works! wow!

Wow nice little tutorial, my head hurts, but I'll now try to make a small path finding script of my own o.0 hopefully it'll work.

[Dach]

This is fun actually, well when it works, otherwise it would seem more fun to bash the computer to bits... bleh, I got that same loop bug, but atleast it works. Now if only I could get the binary heap to work, if anyone can take a look and tell me whats wrong or atleast explain it to me better it would be greatly appreciated.

Dunno why, but my script says that the player is blocking. I don't like it.

[adam]

Originally posted by Dach
This is fun actually, well when it works, otherwise it would seem more fun to bash the computer to bits... bleh, I got that same loop bug, but atleast it works. Now if only I could get the binary heap to work, if anyone can take a look and tell me whats wrong or atleast explain it to me better it would be greatly appreciated.

Dunno why, but my script says that the player is blocking. I don't like it.

Excellent.

I like it.

Actually I take that back, It's more than Excellent.


I really don't see where your going with that binary heap thing. But hey that's just me, I didn't read up on it. Just heard about it.

[Soul-Blade]

Originally posted by Kaimetsu


Making one NPC per node is not necessarily the best way. My system holds them all in an array.

Using a array could get enourmously annoying, I think a NPC would be the best way personally. I mean, graal handles NPCs with no script rather nicely.

[Kaimetsu]

Originally posted by Soul-Blade
Using a array could get enourmously annoying, I think a NPC would be the best way personally. I mean, graal handles NPCs with no script rather nicely.

Okay, let's say you use independent NPCs to represent the nodes. How are you going to pathfind through them? Before you start applying the algorithm, you need to know the positions of every node in the web, and details on how they interlink. How will you represent that?

[Angel]

Do what G2k1 did for railroad tracks lol. and whatever Soul Blade said is false graal wont handle a npc with nothing in it. It will just go bye bye when you come to execute it on a server. You need to define something like a string (setstring this.realnpc,true then use say save[] and then the pathfinding npc can easy find each of the nodes in order.

[Kaimetsu]

It will not work, I tell you.

[Soul-Blade]

Originally posted by Kaimetsu
It will not work, I tell you.

Well, when I get back from camping next week, I will show what I am working on.

It will work, I can promise you that...you'll see. The way I plan on making it work, it would probably be easy to use an array as well as NPCs.

No time to explain, need to sleep.

[adam]

I'm thinking, positiong the path nodes with npc's and use another npc to store them in an array and gather info on which one's are connected to which.

[Dach]

Um, whether you like it or not, the easiest thing to do would be what Kai is saying

[adam]

Originally posted by Dach
Um, whether you like it or not, the easiest thing to do would be what Kai is saying

Depends on if you want lazy people who can't even write a sign script to be able to set the nodes in a level or not?

[Projectshifter]

Originally posted by Soul-Blade
Using a array could get enourmously annoying, I think a NPC would be the best way personally. I mean, graal handles NPCs with no script rather nicely.

Arrays are generally the best way to store strings of numbers. It is not practical for HUGE amounts of data that YOU input, but as long as the NPC is handling it, then arrays are generally the best way. You can always do a simple 'for' loop and have it do something such as:

NPC Code:

---

for (i=0; i<arraylen(var); i++)

---

Have it check all the coords, for example this.x and this.y as arrays. I still don't understand HOW the nodes are supposed to work, perhaps if it was explained in depth then I could be more helpful.
---Shifter

[Kaimetsu]

Originally posted by Projectshifter
I still don't understand HOW the nodes are supposed to work, perhaps if it was explained in depth then I could be more helpful.
---Shifter

Define nodes.
Define links between the nodes.
Let the NPC figure out the way from A to B, following the desired links.

See diagram.