Jump to content


Photo

Pathfinding


  • Please log in to reply
53 replies to this topic

#1 Jet

Jet

    Flying in a sky near you

  • Members
  • 99 posts
  • LocationCalifornia
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 07 July 2012 - 01:48 PM

Pathfinding


by Jet



Introduction

While the title is somewhat self-explanatory, this is a pathfinder. It uses the A* algorithm (http://en.wikipedia....earch_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, 07 October 2013 - 04:24 PM.

  • BigEd781, Vee, ShinGamix and 5 others like this

All my scripts are made under this license:

88x31.png

 

If you need commercial usage of my scripts, or would like to commission me for a script, PM me for details.


#2 SolarGale

SolarGale

    Learning

  • Member+
  • 240 posts
  • LocationUnited Kingdom
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 07 July 2012 - 03:07 PM

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
My Stuff:
Posted Image

I support:
Spoiler

#3 Link

Link

    Hero of Slime

  • Early Adopter
  • 89 posts
  • LocationUnited States of America
  • Primarily UsesRMVX Ace
  • First LanguageEnglish/Engrish

Posted 07 July 2012 - 03:43 PM

0.0 You, sir, have impressed me.

#4 Adon

Adon

    ADONKADONK

  • Members
  • 73 posts
  • LocationMichigan
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 07 July 2012 - 05:33 PM

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

Looking for my script modifications or maker tutorials? Check out http://adonkadonk.blogspot.com to find script demos, modifications/conversions, and all sorts of other stuff!


#5 Tsukihime

Tsukihime

    Advanced Member

  • Members
  • 5,171 posts
  • LocationToronto
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

User's Awards

        

Posted 08 July 2012 - 11:58 AM

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?
My Scripts. Go here for Bugs and Requests.
Want to write a tutorial? Submit a community tutorial!

himeworks011.png

Like on Facebook: HimeWorks
Follow me on Twitter for the latest updates! @HimeWorks

#6 Jet

Jet

    Flying in a sky near you

  • Members
  • 99 posts
  • LocationCalifornia
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 08 July 2012 - 01:41 PM

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.

All my scripts are made under this license:

88x31.png

 

If you need commercial usage of my scripts, or would like to commission me for a script, PM me for details.


#7 Tsukihime

Tsukihime

    Advanced Member

  • Members
  • 5,171 posts
  • LocationToronto
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

User's Awards

        

Posted 08 July 2012 - 01:50 PM

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?)
My Scripts. Go here for Bugs and Requests.
Want to write a tutorial? Submit a community tutorial!

himeworks011.png

Like on Facebook: HimeWorks
Follow me on Twitter for the latest updates! @HimeWorks

#8 Jet

Jet

    Flying in a sky near you

  • Members
  • 99 posts
  • LocationCalifornia
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 08 July 2012 - 02:07 PM

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, 08 July 2012 - 02:07 PM.

All my scripts are made under this license:

88x31.png

 

If you need commercial usage of my scripts, or would like to commission me for a script, PM me for details.


#9 ze1

ze1

    Newbie

  • Members
  • 9 posts
  • Primarily UsesN/A

Posted 10 July 2012 - 04:30 PM

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

#10 Jet

Jet

    Flying in a sky near you

  • Members
  • 99 posts
  • LocationCalifornia
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 10 July 2012 - 08:29 PM

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.

All my scripts are made under this license:

88x31.png

 

If you need commercial usage of my scripts, or would like to commission me for a script, PM me for details.


#11 Tsukihime

Tsukihime

    Advanced Member

  • Members
  • 5,171 posts
  • LocationToronto
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

User's Awards

        

Posted 10 July 2012 - 08:35 PM

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.
My Scripts. Go here for Bugs and Requests.
Want to write a tutorial? Submit a community tutorial!

himeworks011.png

Like on Facebook: HimeWorks
Follow me on Twitter for the latest updates! @HimeWorks

#12 Jet

Jet

    Flying in a sky near you

  • Members
  • 99 posts
  • LocationCalifornia
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 10 July 2012 - 08:41 PM

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.

All my scripts are made under this license:

88x31.png

 

If you need commercial usage of my scripts, or would like to commission me for a script, PM me for details.


#13 Tsukihime

Tsukihime

    Advanced Member

  • Members
  • 5,171 posts
  • LocationToronto
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

User's Awards

        

Posted 10 July 2012 - 08:44 PM

Does it re-compute a new path if someone needs all of those guys to get across the bridge eventually?
My Scripts. Go here for Bugs and Requests.
Want to write a tutorial? Submit a community tutorial!

himeworks011.png

Like on Facebook: HimeWorks
Follow me on Twitter for the latest updates! @HimeWorks

#14 Jet

Jet

    Flying in a sky near you

  • Members
  • 99 posts
  • LocationCalifornia
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 10 July 2012 - 08:46 PM

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.

All my scripts are made under this license:

88x31.png

 

If you need commercial usage of my scripts, or would like to commission me for a script, PM me for details.


#15 VindictivePersonality

VindictivePersonality

    Zombie! Eye Ball Eating Zombie!

  • Members
  • 176 posts
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 24 October 2012 - 01:56 PM

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 don't need your approval, Don't need your praise - Just need your thoughts.


#16 DooMAGE

DooMAGE

    Newbie

  • Members
  • 9 posts
  • Primarily UsesRMVX Ace
  • First LanguagePortuguese

Posted 07 January 2013 - 06:41 PM

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.

#17 djDarkX

djDarkX

    Retro & Remastered Music Guru

  • Member+
  • 655 posts
  • LocationFort Collins, CO
  • Primarily UsesRMVX Ace
  • First LanguageEnglish

Posted 28 January 2013 - 01:38 AM

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, 28 January 2013 - 01:40 AM.

RM & Music Blog: djDarkX's Lair
 
Helpful Links:
Script Call Equivalent of Events (On-Site)
Mack XP Character Generator (Japanese)
RPG Maker VX Ace Master Script List (Off-Site)
RGSS3 Scripts (RMVX Ace) (On-Site)
 
Currently Owned Products:
RPG Maker XP • RPG Maker VX • RPG Maker VX Ace (Standalone & Steam) • IG Maker
Futuristic Tiles • Modern Day Tiles (Steam) • Old School Modern Tiles • RPG Maker DS Resource Pack • RPG Maker DS+ Resource Pack

 

Current Content Projects:

NEW RPG Maker XP Remastered Music [Members+ Only] (wip/semi-acive)

Anime-styled DS+ Emote Bubbles [Members+ Only] (released/hiatus)

 

Current Game Projects:

What Lies Beyond (wip/hiatus)

It's manliest game ever:
SupportPUNCHBEAR.png


#18 BigEd781

BigEd781

    undefined method 'stupid_title' found for nil:NilClass

  • Admin
  • 932 posts
  • LocationSan Diego, CA
  • Primarily UsesOther
  • First LanguageDothraki

Posted 28 January 2013 - 01:40 AM

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.


- Getting offended is a great way to avoid answering questions that make you sound dumb.

While sloppy writing does not invariably mean sloppy thinking, we've generally found the correlation to be strong -- and we have no use for sloppy thinkers. If you can't yet write competently, learn to.



profile for Ed S. on Stack Exchange, a network of free, community-driven Q&A sites

#19 Zeriab

Zeriab

    Huggins!

  • Member+
  • 322 posts
  • Primarily UsesRMXP

Posted 28 January 2013 - 03:34 AM

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.


ZeriabSig.png


#20 BigEd781

BigEd781

    undefined method 'stupid_title' found for nil:NilClass

  • Admin
  • 932 posts
  • LocationSan Diego, CA
  • Primarily UsesOther
  • First LanguageDothraki

Posted 29 January 2013 - 02:04 AM

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.


- Getting offended is a great way to avoid answering questions that make you sound dumb.

While sloppy writing does not invariably mean sloppy thinking, we've generally found the correlation to be strong -- and we have no use for sloppy thinkers. If you can't yet write competently, learn to.



profile for Ed S. on Stack Exchange, a network of free, community-driven Q&A sites




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users