Pathfinding

Jet

Flying in a sky near you
Veteran
Joined
Mar 19, 2012
Messages
172
Reaction score
103
First Language
English
Primarily Uses
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.
 
Last edited by a moderator:

SolarGale

Learning
Veteran
Joined
Jun 8, 2012
Messages
479
Reaction score
37
First Language
English
Primarily Uses
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
 

Link

Hero of Slime
Veteran
Joined
Mar 13, 2012
Messages
227
Reaction score
11
First Language
English/Engrish
Primarily Uses
0.0 You, sir, have impressed me.
 

Adon

ADONKADONK
Veteran
Joined
Mar 24, 2012
Messages
93
Reaction score
15
First Language
English
Primarily Uses
Odd, I was just thinking about this earlier. Pretty cool, plan do something like it in VX?
 

Tsukihime

Veteran
Veteran
Joined
Jun 30, 2012
Messages
8,564
Reaction score
3,846
First Language
English
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

Flying in a sky near you
Veteran
Joined
Mar 19, 2012
Messages
172
Reaction score
103
First Language
English
Primarily Uses
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

Veteran
Veteran
Joined
Jun 30, 2012
Messages
8,564
Reaction score
3,846
First Language
English
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

Flying in a sky near you
Veteran
Joined
Mar 19, 2012
Messages
172
Reaction score
103
First Language
English
Primarily Uses
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.
 
Last edited by a moderator:

ze1

Veteran
Veteran
Joined
Apr 19, 2012
Messages
32
Reaction score
4
Primarily Uses
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

Flying in a sky near you
Veteran
Joined
Mar 19, 2012
Messages
172
Reaction score
103
First Language
English
Primarily Uses
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

Veteran
Veteran
Joined
Jun 30, 2012
Messages
8,564
Reaction score
3,846
First Language
English
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

Flying in a sky near you
Veteran
Joined
Mar 19, 2012
Messages
172
Reaction score
103
First Language
English
Primarily Uses
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

Veteran
Veteran
Joined
Jun 30, 2012
Messages
8,564
Reaction score
3,846
First Language
English
Does it re-compute a new path if someone needs all of those guys to get across the bridge eventually?
 

Jet

Flying in a sky near you
Veteran
Joined
Mar 19, 2012
Messages
172
Reaction score
103
First Language
English
Primarily Uses
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

Zombie! Eye Ball Eating Zombie!
Veteran
Joined
Oct 14, 2012
Messages
176
Reaction score
4
First Language
English
Primarily Uses
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

Villager
Member
Joined
Jan 6, 2013
Messages
9
Reaction score
0
First Language
Portuguese
Primarily Uses
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

Retro & Remastered Music Guru
Veteran
Joined
Jan 17, 2013
Messages
2,700
Reaction score
1,901
First Language
Music
Primarily Uses
RMMV
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!
 
Last edited by a moderator:

BigEd781

undefined method 'stupid_title' found for nil:NilC
Veteran
Joined
Mar 1, 2012
Messages
940
Reaction score
304
First Language
Dothraki
Primarily Uses
N/A
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

Huggins!
Veteran
Joined
Mar 20, 2012
Messages
1,268
Reaction score
1,422
First Language
English
Primarily Uses
RMXP
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

undefined method 'stupid_title' found for nil:NilC
Veteran
Joined
Mar 1, 2012
Messages
940
Reaction score
304
First Language
Dothraki
Primarily Uses
N/A
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.
 
Last edited by a moderator:

Users Who Are Viewing This Thread (Users: 0, Guests: 2)

Latest Threads

Latest Posts

Latest Profile Posts

People3_5 and People3_8 added!

so hopefully tomorrow i get to go home from the hospital i've been here for 5 days already and it's driving me mad. I miss my family like crazy but at least I get to use my own toiletries and my own clothes. My mom is coming to visit soon i can't wait to see her cause i miss her the most. :kaojoy:
Couple hours of work. Might use in my game as a secret find or something. Not sure. Fancy though no? :D
Holy stink, where have I been? Well, I started my temporary job this week. So less time to spend on game design... :(
Cartoonier cloud cover that better fits the art style, as well as (slightly) improved blending/fading... fading clouds when there are larger patterns is still somewhat abrupt for some reason.

Forum statistics

Threads
105,868
Messages
1,017,093
Members
137,587
Latest member
Usagiis
Top