Jet

Pathfinding

94 posts in this topic

Pathfinding


by Jet



Introduction

While the title is somewhat self-explanatory, this is a pathfinder. It uses the A* algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm). It has been adapted to work with Ace's directional passability as well. This will allow you to send characters off to specific parts of the map automatically without having to manually program their move route, which can be handy for obvious reasons.

Features

- Quick, flexible pathfinding, via A*
- Usable within a move route
- And more...

Script

Original (Unsupported): http://pastebin.com/raw.php?i=DwZSakKB
As edited by Venima: http://pastebin.com/raw.php?i=ctt8RfdK

Credit

Jet

Note

I have a license, it's in my signature. Edited by Jet

Share this post


Link to post
Share on other sites

Wow, sounds incredible, I was actually looking for something like this and was planning to learn some ruby to implement it, seems like it's not necessary now great work Jet! :D

QuizicalGin likes this

Share this post


Link to post
Share on other sites

0.0 You, sir, have impressed me.

QuizicalGin likes this

Share this post


Link to post
Share on other sites

Odd, I was just thinking about this earlier. Pretty cool, plan do something like it in VX?

Share this post


Link to post
Share on other sites

Apparently A* algorithm is supposed to run at log* time.

How long does it take to find a path on a map that's 100x100 and you're going from one corner to the other?

Share this post


Link to post
Share on other sites

Apparently A* algorithm is supposed to run at log* time.

How long does it take to find a path on a map that's 100x100 and you're going from one corner to the other?

If it's a clear path, only a couple of frames.

If it's a randomly generated dungeon via the default system, it actually takes about a full half second or so.

But it is impractical to do such a thing anyways.

Share this post


Link to post
Share on other sites

What makes a pre-made map different from a randomly generated one?

For a randomly generated dungeon, does that half-second apply to every pathfinding call or just the first time (presumably to set-up the graph?)

cygnus flamel likes this

Share this post


Link to post
Share on other sites

What makes a pre-made map different from a randomly generated one?

For a randomly generated dungeon, does that half-second apply to every pathfinding call or just the first time (presumably to set-up the graph?)

By randomly generated i mean that it's more of a maze. By 100x100 clear path, i meant a blank map with all passable tiles.

I don't setup a graph actually at all. It's all done over again every call. I do this so that events are incorporated into the passability of the map.

You'll see that setting up a graph is somewhat silly for A* anyways considering how it goes about what it does anyways.

Dijkstra on the other hand, oh man.

Edited by Jet

Share this post


Link to post
Share on other sites

I'm not home, so I can't try this out. =(

I have two questions:

1) what happens if I try to find a path between two events which have no path between them? Does an error occur, like the other pathfinding scripts around, or does it give some kind of response (like returning nil or something)?

2) maybe you can't answer me this, but how efficient is your script compared to other pathfinding scripts for VXA, such as Khas's (http://arcthunder.site40.net/en-khas-pathfinder/) or modern algebra's (http://rmrk.net/index.php?topic=44740.0)?

Share this post


Link to post
Share on other sites

I'm not home, so I can't try this out. =(

I have two questions:

1) what happens if I try to find a path between two events which have no path between them? Does an error occur, like the other pathfinding scripts around, or does it give some kind of response (like returning nil or something)?

2) maybe you can't answer me this, but how efficient is your script compared to other pathfinding scripts for VXA, such as Khas's (http://arcthunder.si...has-pathfinder/) or modern algebra's (http://rmrk.net/inde...p?topic=44740.0)?

1.) Nothing. The event just won't do anything.

2.) I don't know. It's probably pretty equivalent with modern algebra's, if not faster. As for Khas's, I have no idea how his works, as I can't seem to access his site, but if i recall his doesn't use A* (Correct me if i'm wrong), but I wouldn't know.

Share this post


Link to post
Share on other sites

How does the script handle cases where the selected path is suddenly blocked off?

For example, when multiple events are moving simultaneously.

Or when you have a large party and they're trying to cross a bridge that is wide enough to support only one event.

I think these are the kinds of things a lot of scripts seem to be having issues with.

Share this post


Link to post
Share on other sites

How does the script handle cases where the selected path is suddenly blocked off?

For example, when multiple events are moving simultaneously.

Or when you have a large party and they're trying to cross a bridge that is wide enough to support only one event.

I think these are the kinds of things a lot of scripts seem to be having issues with.

If you're using the script call outside a move route, and the path suddenly becomes blocked, it will skip the rest of the route.

If you're using it inside a move route, it depends if you have "Skippable" checked in the move route.

Share this post


Link to post
Share on other sites

Does it re-compute a new path if someone needs all of those guys to get across the bridge eventually?

Share this post


Link to post
Share on other sites

Does it re-compute a new path if someone needs all of those guys to get across the bridge eventually?

No. That can easily be evented with x and y variable setting, and checking until all the events are in their proper places.

Share this post


Link to post
Share on other sites

Issue - I think. I have an event that should walk (on a 17x17 map) from 08 x 05 to 08 x014 so I set up the events and set the move script in the movement route for that event:

find_path(8, 14)

How ever - the event does not move. the path is walk able, there is NOTHING blocking its way.

Share this post


Link to post
Share on other sites

Issue - I think. I have an event that should walk (on a 17x17 map) from 08 x 05 to 08 x014 so I set up the events and set the move script in the movement route for that event:

find_path(8, 14)

How ever - the event does not move. the path is walk able, there is NOTHING blocking its way.

Same problem here.

Share this post


Link to post
Share on other sites

Did you guys set the event to activate upon player touch?  Also, if it's for the player, I found that setting up a Move Route for the player and using the "Script..." button in there works wonderfully.  So, your event should look similar to this:
 
@>Set Move Route: Player

: $>Script: find_path(8,14)


Thanks for this Jet!  Works beautifully with Lemony's Follower Move Routes in the same fashion I just posted.  Needed this for various conversations with NPCs!

Edited by djDarkX

Share this post


Link to post
Share on other sites

Apparently A* algorithm is supposed to run at log* time.

How long does it take to find a path on a map that's 100x100 and you're going from one corner to the other?

 

Algorithmic complexity is a measure of worst case time, not an average or something similar.  It all depends on the input and what sort of input is most common.

Share this post


Link to post
Share on other sites

Algorithmic complexity is a measure of worst case time, not an average or something similar.  It all depends on the input and what sort of input is most common.

 

Worst case time is but one measure of algorithm complexity.

It is indeed usually implied if another measurement is not specified explicitly, exception randomized algorithms where average running time is usually implied.

Share this post


Link to post
Share on other sites

Worst case time is but one measure of algorithm complexity.

It is indeed usually implied if another measurement is not specified explicitly, exception randomized algorithms where average running time is usually implied.

 

Sure, but the *vast* majority of the time your algorithms are not random and you state the worst case complexity and, later, state the average (at least, average for a given use case).  I really just wanted to make it clear that the input is what mattered, i.e., a question like "how long does it take to get from one corner to another" can't be answered without context.

 

On a side note, I always enjoy your comments when a CS subject comes up.

Share this post


Link to post
Share on other sites

Issue - I think. I have an event that should walk (on a 17x17 map) from 08 x 05 to 08 x014 so I set up the events and set the move script in the movement route for that event:

find_path(8, 14)

How ever - the event does not move. the path is walk able, there is NOTHING blocking its way.

I have this too. However, I found that when I hold the control button (you know, the one that makes the player pass inpassable tiles), the event starts moving...

Seems there is a bug somewhere in the passability checks?

The path I'm trying to send the event along is a 3 tile wide dirt road, completely passable in all directions, the event only has to go in a straight line and the road is completely free of obstacles.

 

Edit:

Judging by the FPS, it also doesn't seem to process reaching it's destination. If I hold the control key and wait for the event to get to it's destination, it does stop walking but the FPS seems to suggest the script is still running.

I hope you can fix the script, I prefer it above the other pathfinding scripts I found for Ace.

Edited by gpgekko

Share this post


Link to post
Share on other sites

Sure, but the *vast* majority of the time your algorithms are not random and you state the worst case complexity and, later, state the average (at least, average for a given use case).  I really just wanted to make it clear that the input is what mattered, i.e., a question like "how long does it take to get from one corner to another" can't be answered without context.

I was considering whether to make a comment as it was clearly a case of... for the lack of a better expression teaching by lying.

You know, usually by expressing the world or models less complex than they really are. Later when the simplified world is understood it can more easily be expanded.

Anyway you are quite right except that it hasn't been a vast majority for me, though you know >_>

 

More than context is needed to answer that. As you know the golden rule of performance is to measure it before starting to do analysis and optimizations and to properly answer the question of how long it takes.

 

On a side note, I always enjoy your comments when a CS subject comes up.

The feeling is quite mutual as I enjoy yours on CS related matters.

I quite love CS ^^

Edited by Zeriab

Share this post


Link to post
Share on other sites

Hey guys. Really sorry for the necropost, however, I've made a few fixes and additions to this pathfinder to give it extra functionality (am I excused?). 

 

This modified version should work with anything the previous version worked with.

 

Modifications:

I noticed some of you were complaining about your event not moving, I believe this was because your goal location was impassable. This issue is fixed: Goal location may now be impassable, pathfinder will still reach it.
I also noticed the pathfinder behaves strangely if the event's custom move route is set to repeat. It would repeat the steps of the originally determined path, which is pointless. This is improved: If the move route is set to repeat, the pathfinder will revalidate path each step. You can now specify the x and y to be variables or continuously changing values such as the player's x and y, and it will follow them. (Note, this is a bit more processor heavy, but for repeat only, the normal move route hasn't been modified)
Added parameter: Distance. So I wanted to use the pathfinder for an event to follow the player, but I wanted it to follow up to a certain distance from the player and then stop. By specifying the (optional) distance parameter, you can do just that. This is effectively an alternative to party following, except not limited to the party.

 

Jet, feel free to change the comments, though I made some additions to explain the modifications and also label the code I've modified.

 

Modified script: http://pastebin.com/raw.php?i=ctt8RfdK

 

One final thing with the movement repeat behaviour that I'll mention: When applying your find_path script to your event's custom move route with a distance of say 3, that will continue running until it has reached a distance of 3 from its target (including moving targets), you can then add a random move step after it, and it will move randomly as long as it is within the specified distance from the target. You could use the change frequency moves to set the find_path frequency to highest, and random to normal (it hurries to the target, then wanders slowly).

Edited by Venima

Share this post


Link to post
Share on other sites

Hello Venima,

My license openly allows modification and redistribution, as long as it's attributed and distributed with the same license.

I appreciate you taking time to make the script better, I do not have as much time to keep up new features and such on all my scripts.

I put a link to your modified version in the first post, but feel free to start your own thread with the script if you plan to make further modifications.

Share this post


Link to post
Share on other sites

Awesome script! Thank you Jet and Venima! :D

I have only a slight Problem with the documentation, I can't get the event to move to a position and the player has to wait til the event arrives.

 

I don't get 100% how to make the wait (and I know it's in the script... sorry, for the slightly dump question :( ).

 

Edit: Is it possible to move the followers, too?

I use Victors Follower Script but I think, this is not possible?

Edited by Marcio

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.