Pathfinding

[Jet]

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.

 

[SolarGale]

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!

 

[Link]

0.0 You, sir, have impressed me.

 

[Adon]

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

 

[Tsukihime]

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?

 

[Jet]

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.

 

[Tsukihime]

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?)

 

[Jet]

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.

 

[ze1]

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)?

 

[Jet]

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.

 

[Tsukihime]

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.

 

[Jet]

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.

 

[Tsukihime]

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

 

[Jet]

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.

 

[VindictivePersonality]

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.

 

[DooMAGE]

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.

 

[djDarkX]

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!

 

[BigEd781]

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.

 

[Zeriab]

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.

 

[BigEd781]

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.