Jump to content


Photo

Karanum's Pathfinding Script


  • Please log in to reply
12 replies to this topic

#1 Karanum

Karanum

    Advanced Member

  • Ace Member
  • 30 posts
  • LocationNetherlands
  • RM Skill - Coder

Posted 31 May 2012 - 09:48 AM

Pathfinding v1.0
by Karanum


Introduction
Pathfinding is an important part of video games nowadays. Even in RPG Maker, where it forms an important part of
tactical battle systems, or even events with variable starting points. This script offers an easy and reliable way to get
your events from A to B in the least time possible.

Features
- 4 different pathfinding methods
- Based on Dijkstra's algorithm
- Minimal lag (increases for large maps though)

Planned
- Upgrade to A* algorithm (it's faster!)
- Include diagonal movement option
- Add collision checking with events

Instructions
Place the script in the Materials section, above Main.
In an event, use the Script command and simply enter the method you want to use.
Further instructions are found in the header of the script.

Demo
Download
The demo was made with the Japanese version of Ace. I might translate the menus if people have problems with it.

Script
Spoiler


FAQ
Q: How can I decrease the lag when using pathfinding?
A: Use a smaller map if possible, otherwise use the walk_to_straight method. It's less flexible, but lighter.

Q: How to increase the amount of steps without walk_to_long's processing time?
A: Use the following script call instead, replacing id, x, y and steps with the numbers you want:
character = get_character(id)
character.walk_to(x, y, steps)

Giving Credit
When using this in your game, give credit to Karanum.
If you want to use this script in a commercial game, contact me first.

Author's Notes
I found out there's another pathfinding script out there by Khas. I must admit, I haven't checked it out yet, and I don't
know exactly what functions Khas' script has. However, I urge everyone to check that one out as well and see which
of the scripts works best for you.

#2 omoney

omoney

    Newbie

  • Ace Member
  • 4 posts

Posted 01 June 2012 - 11:19 AM

This script is awesome and exactly what I've been looking for! The one issue I have with it though is that if i choose to execute path finding on several events they don't collide with each other or the player which is weird visually. I was wondering if future updates will include the option of path finding that take moving events or other path finding events or the player into considerations.


Note: I have tried Khas' script which does collide with other events but if it does it would end the path which is an undesirable result.

#3 Tsukihime

Tsukihime

    Advanced Member

  • Ace Member
  • 6,241 posts
  • LocationToronto
  • RM Skill - Coder

Awards Bar:

Users Awards

Posted 01 June 2012 - 11:44 AM

Q: How can I decrease the lag when using pathfinding?
A: Use a smaller map if possible, otherwise use the walk_to_straight method. It's less flexible, but lighter.


So there's no way to avoid checking the entire map for the shortest valid path?

Edited by Tsukihime, 01 June 2012 - 11:45 AM.

My Scripts. Go here for Bugs and Requests.

himeworks011.png

Like on Facebook: HimeWorks
Follow on Twitter: @HimeWorks

#4 omoney

omoney

    Newbie

  • Ace Member
  • 4 posts

Posted 01 June 2012 - 12:49 PM

okay nevermind, finally figured out that through? represented the event passability. Then I discovered that if something moves into an event's decided path it will wait until it moves out of the way before continuing. Is there a way to make it so that if something blocks it, it will recalculate?

#5 Tsukihime

Tsukihime

    Advanced Member

  • Ace Member
  • 6,241 posts
  • LocationToronto
  • RM Skill - Coder

Awards Bar:

Users Awards

Posted 01 June 2012 - 12:54 PM

I would not re-calculate because you run the risk of going into an infinite loop.
Or if code is written to prevent that (eg: memoization, no-backtrack, etc) at least you're definitely doing a lot of unnecessary calculations for no real reason.

For example, suppose you had a bridge where only one person can cross at a time.
One guy will step forward, and the others would find that there's no path to the destination anymore upon recalculation. Then, whenever the guy in front moves, will you tell them to recalculate the path? There still is no path, so they wait again.

Once the guy reaches the end of the bridge, you tell them to recalculate and the finally one of them will get through. But that means you've potentially ran a couple dozen extra pathfinding only to realize there was no path in the end.

And this repeats for every event that's supposed to be moving. So if you had 5 events trying to cross the bridge, with a bridge length of 5 squares, the first guy would move across, and tell the other 4 (idle) events to recalculate for a total of 20 recalculations.

The second guy goes through, and tells the remaining 3 to re-calculate, for another 15 calculations.

I don't know how long it takes to calculate a single path once, but if you're doing more than even one of these every time you move...that's pretty bad.

Just wait until the coast is clear like usual.

Edited by Tsukihime, 01 June 2012 - 01:03 PM.

My Scripts. Go here for Bugs and Requests.

himeworks011.png

Like on Facebook: HimeWorks
Follow on Twitter: @HimeWorks

#6 omoney

omoney

    Newbie

  • Ace Member
  • 4 posts

Posted 01 June 2012 - 12:59 PM

Hm. The thing is I have seven sprites moving. Sometimes so sometimes they block each other when one has reached it's desitnation first preventing the other sprite from getting to it's destination ever.



And another thing it seems the path calculation doesn't take into account actors or other events. If the player stands still BEFORE the path finding the sprite still attempts to run into the player until the player moves out of the way. This could be problematic during a scene.



Edit: I see. What about like a script that only moves one tile at a time? If something wants to get from point A to point B it would choose the "best" adjacent tile move there than repeat until destination is reached.

or what about after X frames if pathfinding? == true than it recalculates. If there is no point than pathfinding? = false.

Edited by omoney, 01 June 2012 - 02:16 PM.


#7 Karanum

Karanum

    Advanced Member

  • Ace Member
  • 30 posts
  • LocationNetherlands
  • RM Skill - Coder

Posted 04 June 2012 - 04:44 AM

First of all, sorry for the late reply. I'll be able to answer questions more actively from now on.

And another thing it seems the path calculation doesn't take into account actors or other events. If the player stands still BEFORE the path finding the sprite still attempts to run into the player until the player moves out of the way. This could be problematic during a scene.

Edit: I see. What about like a script that only moves one tile at a time? If something wants to get from point A to point B it would choose the "best" adjacent tile move there than repeat until destination is reached.

or what about after X frames if pathfinding? == true than it recalculates. If there is no point than pathfinding? = false.

Better collision checking against other events is something that's planned. It should include options to stop pathfinding after event collision. I'm still wondering whether checking for events when deciding the path is feasible, since events do have the tendency to move around while your event is doing his pathfinding.

Recalculating the path frequently is possible, but expect a lot of lag. Maybe when I change it to use A*, but pathfinding is quite heavy overall. I advise using pathfinding mainly for events, and especially events that are fully coordinated so you know where every event is at what time.

Q: How can I decrease the lag when using pathfinding?
A: Use a smaller map if possible, otherwise use the walk_to_straight method. It's less flexible, but lighter.


So there's no way to avoid checking the entire map for the shortest valid path?

Currently, walk_to_straight does that, sort of, but it's a bit inflexible at the moment. If I can get A* in at the next update, that algorithm checks the map for tiles that have the highest possibility of leading an event to its endpoint, so it only checks the parts of the map that are possibly relevant.
If I can't get A* functional, I'll add an optional parameter to walk_to_straight that allows you to decide how much it will check. Right now it's defaulted to 2 tiles around the event-to-endpoint rectangle.

This script is awesome and exactly what I've been looking for! The one issue I have with it though is that if i choose to execute path finding on several events they don't collide with each other or the player which is weird visually. I was wondering if future updates will include the option of path finding that take moving events or other path finding events or the player into considerations.

Taking moving events into consideration means the pathfinding event must know at all times where the other events on the map are, and recalculate its path every time something gets in its way. As stated above, that would require too much calculations right now.

Edited by Karanum, 04 June 2012 - 04:45 AM.


#8 omoney

omoney

    Newbie

  • Ace Member
  • 4 posts

Posted 04 June 2012 - 10:41 AM

Thanks for the response. I can't wait for the next version :)

#9 Tsukihime

Tsukihime

    Advanced Member

  • Ace Member
  • 6,241 posts
  • LocationToronto
  • RM Skill - Coder

Awards Bar:

Users Awards

Posted 04 June 2012 - 10:47 AM

I see. What about like a script that only moves one tile at a time? If something wants to get from point A to point B it would choose the "best" adjacent tile move there than repeat until destination is reached.


Yes, we can consider subpaths and the recursive nature of a path.

Suppose you've calculated your path from A to D by traveling A -> B -> C -> D, where each arrow is exactly one tile. This means you're basically moving 3 tiles to get to your destination.

If going from A->B->C doesn't work, because there's someone in the middle, then perhaps we can replace B with a path X = {x1, x2, ...} such that A->X->C would work.

If you can get to C, and C is the last step before you reach D, then you only need to figure out how to get to C (because there's no way you CAN'T get to D if you manage to get to C). Unless, of course, someone is standing at D. LOL then you're screwed.

And the pathfinding to go from A to C should in theory be much shorter because the distance you must travel is much, much smaller.

Of course, if we find that there is no path to C like on my bridge, same issue occurs, but at least you're not re-calculating the entire map.

Edited by Tsukihime, 04 June 2012 - 11:16 AM.

My Scripts. Go here for Bugs and Requests.

himeworks011.png

Like on Facebook: HimeWorks
Follow on Twitter: @HimeWorks

#10 Cupcake

Cupcake

    Wallflower

  • Ace Member
  • 17 posts
  • LocationUS
  • RM Skill - Writer

Posted 08 November 2013 - 12:27 PM

[Edited] problem no longer occurring 


Edited by Cupcake, 08 November 2013 - 01:02 PM.


#11 Karanum

Karanum

    Advanced Member

  • Ace Member
  • 30 posts
  • LocationNetherlands
  • RM Skill - Coder

Posted 08 November 2013 - 12:57 PM

I can't find anything in the script itself that might be causing it. I'm going to need a few things to get an idea of what's going on:

  • Open the script editor and tell me the line that's on line 180 of Game_Character
  • Do you have any other scripts installed besides this one?
  • If you're calling pathfinding from anywhere, please show me what script call you've used to call it


#12 orathan

orathan

    Carnifex Malum

  • Ace Member
  • 187 posts
  • LocationIn front of a computer.
  • RM Skill - Jack of All Trades

Posted 06 December 2013 - 01:53 AM

When will the next version be released?  The one with...

 

- Upgrade to A* algorithm (it's faster!)

- Include diagonal movement option
- Add collision checking with events


#13 Rave

Rave

    Dragon Agent

  • Ace Member
  • 138 posts
  • RM Skill - Jack of All Trades

Posted 08 March 2014 - 04:57 PM

Could you make it so if precise spot event is supposed to move to isn't passable, it'd try to go to closest passable tile? Here's use case: I am trying to make enemies go after my player. However I don't know if spots at left, right, top and bottom will be passable when enemies will spot player, so best thing would be just to try to make script find a path to ($game_player.x,$game_player.y) and make it go to closest available spot instead.

 

There's is also bug I found regarding finding path with turned off through? (so enemies won't pass through player and other events as if they're ghosts), making it so that events can block path and even if another path exists, but is longer, event will stupidly use shorter and get stuck. I guess it's because script doesn't account for events' passability, only tilemap's. You should fix that.

 

Please fix that. I don't know shit about pathfinding (otherwise I'd write my own instead of using script), so addition mentioned in first paragraph and fix for issue mentioned in second would be welcome.

 

If you don't understand issue mentioned in second paragraph (I'm not native English speaker so it is possible that I wrote this in non-clear manner), I can make short demo presenting it.


If knowledge is power, then why all powerplants are running on coal, uranium, wind and sun and none on knowledge?

 

There are no impossible things, there is only lack of skills.





0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users