Behold Pathfinding!

[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.