Behold Pathfinding!

Soul-Blade · #1 07-31-2003, 12:02 PM

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 · #2 07-31-2003, 01:31 PM

I don t really understand it sorry.. Some nice scripting tho

Sorry, i'm not good at scripting so i carnt help

marcoR · #3 07-31-2003, 08:16 PM

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

Soul-Blade · #4 07-31-2003, 09:26 PM

Quote:

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 · #5 07-31-2003, 11:24 PM

Quote:

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 · #6 07-31-2003, 11:45 PM

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

Spark910 · #7 07-31-2003, 11:52 PM

I couldnt see anything, whats it doing.

Thought · #8 07-31-2003, 11:54 PM

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 · #9 07-31-2003, 11:55 PM

I hate you Soul-Blade

.

Thought · #10 08-01-2003, 12:02 AM

The diagonal pathing bug really shows

Kaimetsu · #11 08-01-2003, 12:09 AM

Quote:

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 · #12 08-01-2003, 12:33 AM

Quote:

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 · #13 08-01-2003, 05:36 AM

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 · #14 08-01-2003, 05:44 AM

:-/ 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 · #15 08-01-2003, 08:05 AM

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

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