JPS Pathfinding

[ChrisClark13 4]

Script Name

JPS Pathfinding v 1.3 

 

Script Link

http://pastebin.com/raw.php?i=rdxSMW5m

Credits

By ChrisClark13

Based off of the Pathfinding script by Jet10985 & Venima

 

Terms of Use

Don't post this under your own name and credit me and the others if used.

 

Introduction

This script allows Events and the Player to use JPS Pathfinding (an extra fast optimization of regular A* Pathfinding) to avoid obstacles while going to a specified point on the map (or within a certain distance if the dist parameter is used).

Features:

• Uses speedy JPS Pathfinding, which is faster than A* by several times in most cases.

• Only recalculates path when it absolutely has to based on if the path is blocked or not (configurable how far down the path it checks).

• The find_path command can be seamlessly inserted into MoveRoutes and Event pages.

• Includes a command (setup_patrol_routes) that will set up a basic patrol route given a list of coordinates inside of a Move Route.

• Can be set up to call bits of code (see Proc objects in the Standard Library/callbacks) when the path either succeeds or fails. Also when a step is taken along the path or when the path gets blocked.

* Has an option to instead path to the closest spot possible

 

To install just put the script under Materials and above Main.

 

Copied from the script's How to section:

 

 

 

 

 

 

 

#===============================================================================
# Basic Options
#===============================================================================
 
To move a player or event, use this in an event "Script..." command or
inside of a Move Route (the Event page version has extra parameters):
 
Move Route version:
  find_path(x, y, dist = 0, lookahead_dist = 1, recalc_if_blocked = true)
  
  x: the target x
  y: the targey y
  All off these parameters are optional and have default values according to
    what's above.
  dist: how close the character needs to get to the target. A value that's 0
    will make them straight to the spot. A value that's less than 0 will make
    them instead get as close as possible.
  lookahead_dist: How far the character will check ahead each step
    to see if the path is blocked. A value of -1 will make them check the
    entire path, other values less then 1 will be set to 1.
  recalc_if_blocked: Whether or not the path will fail outright if the path gets
    blocked. If it's set to true the character will wait RECALC_WAIT frames
    and try to find a new path up to MAX_RECALC times.
  
  Note: If used with in a Move Route that has Skippable set, it'll skip the path
    if it gets blocked at any point (making setting recalc_if_blocked useless).
    Though it'll still call the failure callback.
    
Event Page version:
  find_path(x, y, dist = 0, ev = 0, wait = true,
    lookahead_dist = 1, recalc_if_blocked = true)
 
  Only has a couple more parameters, otherwise is the same as the Move Route
    version.
  ev: Id of the character to be moved. By default it's called on the calling
    event. Use -1 for the player and anything above 0 for a speficic event on
    the map
  wait: whether or not the Event page's processing will stop while the character
    is in motion. Works like the Wait setting on with the Set Move Route
    command.
    
Optional parameters can be defined as far as you like, though if a parameter is
after some others you don't want, you'll have to set those other ones too. (Just
how Ruby works.)
 
Testing if a character is currently following a path:
  You can use following_path? to test whether or not a character is following a
  path like so in a conditional branch.
    get_character(0).following_path?
 
#===============================================================================
# Patrol routes
#===============================================================================
To setup a simple patrol route use this in a script call in a Move Route:
 
setup_patrol_route(*coords)
  
  coords: a list of numbers that are the x and y positions of the patrol
    points like so: x0, y0, x1, y1, x2, y2, x3, y4... and so on.
  
When the character fails to get to a speficic patrol point, they will start
going between the points in reverse order.
(Also, when they reach a point the list is shuffled so the point they just
reached is at the bottom of the list)
 
#===============================================================================
# Advanced options:
#===============================================================================
There are some callbacks that are called at certain points in the code for those
of you who are more programmatically minded.
 
They are all set on a per Game_Character basis via script call like so:
 
$game_player.proc_success = Proc.new {|path|
  puts "Path success!!"
}
 
event = get_character(0)
event.proc_blocked = Proc.new {|path, block_x, block_y|
  #Get mad!
  event.balloon_id = 5
}
 
proc_success(path)
  Called when the character reaches the target for the first time and will not
  be called again until a new path is set.
  The path argument is the JPS_Path that the character is currently using to
  path find.
proc_failure(path)
  Called whenever the path fails, either because the path got blocked and
  recalc_if_blocked is set to false or because the recalucation limit was
  reached. (See below)
  The path argument is the JPS_Path that the character is currently using to
  path find.
proc_step(path, old_x, old_y)
  Called whenever the character takes a step along the path.
  Path is the JPS_Path, old_x and old_y arguments are where the character was
  previously.
proc_blocked(path, block_x, block_y)
  Called whenever it's discovered the path is blocked when looking ahead.
  Path is the JPS_Path, block_x and block_y is where the blockage is.
  
As for the JPS_Path passed in the procs, you can access it's info or do
whatever to it, though try not to break the path. The current goal can be
acessed with path.goal.x and path.goal.y (and the adjusted goal can be accessed
with path.adjusted_goal).
 
If you need to get a move route with find_path in it use:
  character.create_path_route(x, y, dist = 0, lookahead_dist = 1,
    recalc_if_blocked = true)
  It returns a MoveRoute with a find_path command at the top.

 

 

Compatibility Issues

Likely to conflict with other pathfinding scripts and will not work properly with Pixel/Free Movement scripts or other scripts that alter movement. Will likely ignore diagonal movement scripts.

 

Possible Upcoming Features

Proc for when it has to start a new path or recalculates a path, if requested.

 

FAQ

None so far.

 

Changelog

 

v 1.0: Released

v1.3: * Added in convience method for creating a move route with find_path

          in it.

        * Made advanced options (Procs) harder to access as to reduce the long

          method signatures and since only advanced users (ones who know how to

          script) should be using them anyways.

        * Added in Procs that are called whenever a step is taken along the

          path and whenever the path gets blocked.

        * Made it so additional args are passed to the procs.

        * Fixed some weirdness in that if a path was blocked and a new path was

          found immediately, it would go along that new path instantly. Now it

          acts like the normal move route in that it waits until next time to

          move.

        * !!! Reordered arguments since I kept tripping over them in my own

          projects

        * Added in method to test whether or not a character is currently

          following a path.

        * Added in a functionality to instead go to the closest spot possible

          if dist is negative.

        * Bugfix: Made lookahead_dist actually work properly.

 

Edited April 28, 2014 by ChrisClark13

[ChrisClark13 4]

Updated from 1.0 to 1.3!

Change Log:

 

v1.3: * Added in convience method for creating a move route with find_path

in it.

* Made advanced options (Procs) harder to access as to reduce the long

method signatures and since only advanced users (ones who know how to

script) should be using them anyways.

* Added in Procs that are called whenever a step is taken along the

path and whenever the path gets blocked.

* Made it so additional args are passed to the procs.

* Fixed some weirdness in that if a path was blocked and a new path was

found immediately, it would go along that new path instantly. Now it

acts like the normal move route in that it waits until next time to

move.

* !!! Reordered arguments since I kept tripping over them in my own

projects

* Added in method to test whether or not a character is currently

following a path.

* Added in a functionality to instead go to the closest spot possible

if dist is negative.

* Bugfix: Made lookahead_dist actually work properly.

 

[KayDgirl91 99]

So say for instance, with this script would I be able to tell event 1 to move to 15x and 20y and it'll move there in the best way possible, instead of having to go in and tell it every step it should take?

[ChrisClark13 4]

Yes, use the Script command in their custom move route and put in "find_path(15, 20)" or you could put it inside a Script command on their event page (though then you'd need to run the event page).

 

Currently I'm using it to make a semi-intelligent player chasing/encounter system with another script I'm making for player detection with line of sight.

[shaynec1981 32]

Is there a way to have an event that is controlled by your script ignore other events during gameplay? So they essentially walk over events in their path? Problem I'm running into is through narrow, one tile wide paths if I have another event set to below character the event controlled by the script sees the event in the path and the path is essentially blocked and cannot reroute so he stays in place instead of continuing the pursuit of my player.

 

*Edit Nvm. I just set the other events to "through" and it works perfectly.

Edited June 18, 2014 by shaynec1981

[Tommy Gun 19]

Can this be used in commercial projects? If so, is Jet okay with that (I think Jet's was NC)?

[DoomSlinger 0]

I've noticed that this script seems to dissable saving for some reason. I've tried removing each movement related script I have installed (indevidually not all at once), as you said they can conflict sometimes, however I have had no success in fixing this problem. Is there a switch or variable that has an effect on the script? If there is, could you put post the line of code that involves that variable so people can change it?

 

Edit: It's definantly a problem with this script, as you can't save even on a brand new, unedited (except for the addition this script of corse) project.

Edited August 1, 2014 by DoomSlinger

[Firebrand 0]

I have the same problem too. Excluded all other possibilities, with this pathfinding script I cannot save. I only hear an error sound. Anyone has the solution?

[Candacis 0]

Same problem here. But I doubt Chris is still active. Anyone else can solve that problem?

[Sixth 113]

The game can not save Proc objects because Marshal.load/Marshal.dump is not compatible with that class. That is why you can not save the game.

There are 4 instance variables storing a Proc object in Game_Character objects which are saved during the save process. But if a Proc object is present in that class, the save will fail.

It's an automatic prevention process, because even if the engine wouldn't prevent saves, loading a game from a save file like that will instantly crash your game.

 

To fix it, the Proc variables should be cleared before saving and reset them after the save. Troublesome, to say the least. I have no idea what happens if a proc is cleared during a find_path command, and even if it won't cause any errors, they should be re-initialized after the save too to make sure that the pathfinding won't just stand by after the save (or worse, cause the game to crash).

 

I would try other pathfinder scripts, because the chance of someone popping up and fixing this is very slim.

Theo's pathfinder is a good alternative, and uses the same script call for the pathfinder, so even if you have a lot of events already set up, you won't need to change the pathfinder script calls in them.

[♥SOURCE♥ 108]

Theo's pathfinder is a good alternative, and uses the same script call for the pathfinder, so even if you have a lot of events already set up, you won't need to change the pathfinder script calls in them.

 

It isn't a good alternative, that's a bad alternative. It's likely to find clearly suboptimal, dumb-looking paths.

 

Invenio is the best solution.

 

For free alternatives, why not use the pathfinder by Jet and Venima? It's what the OP used as a base:

 

 

 

Credits

By ChrisClark13

Based off of the Pathfinding script by Jet10985 & Venima

[Sixth 113]

I find Jet's pathfinder extremely slow compared to Theo's, my FPS drops significantly if I use pathfinder on multiple characters, that's why I don't use that one.

Theo's will sometimes make some weird paths, that's true, but it's not that bad, and it did not happen often for me, so I settled with that instead of killing my FPS. Personal preferences, I guess.

[♥SOURCE♥ 108]

Jet's script works fine for small maps though. Theo's has some serious problems with object creation (among others) that eventually produces micro-freezes, even after the pathfinding process finished.

[AutumnAbsinthe 153]

Probably a really dumb question, but is there a way to make the target the player?

[Kayzee 4,033]

You just do a find_path to $game_player.x and $game_player.y if you wanna do that. I recommend not using this pathfinding script though, it has some problems.

[AutumnAbsinthe 153]

3 hours ago, Kayzee said:

You just do a find_path to $game_player.x and $game_player.y if you wanna do that. I recommend not using this pathfinding script though, it has some problems.

Which one would you recommend? I find the default pathfinding in VXA to be... Lacking, to say the least. (Come on man, "Approach" doesn't mean "Walk off to the left for no reason".)

EDIT: I just backread. Is the one by Jet and Venima worth the hype?

Edited December 4, 2019 by AutumnAbsinthe

[Kayzee 4,033]

There is no default pathfinding in VXA. Approach shouldn't walk in random directions for no reason though, It should just try to move in whatever direction gets it closest to the player. It isn't smart enough to know how to go around things.

 

i use Jet's myself!

[AutumnAbsinthe 153]

2 hours ago, Kayzee said:

There is no default pathfinding in VXA. Approach shouldn't walk in random directions for no reason though, It should just try to move in whatever direction gets it closest to the player. It isn't smart enough to know how to go around things.

 

i use Jet's myself!

I have this weird problem where I'll have an event chase the player and it will just veer off in a random direction. The map is a straight hallway.

[Kayzee 4,033]

Does that happen without any scripts? Maybe a script is doing something funky.

[AutumnAbsinthe 153]

I'll check it out in a new project. The most likely culprit is the stealth script I have, but I'm gonna replace it soon with a Yanfly one because I suspect it's also stopping me from saving the game properly.

[Kayzee 4,033]

Might be! Hehe... I didn't even know yanfly had a stealth script. I kinda made my own in my game, but it's pretty darn simple. :3

[AutumnAbsinthe 153]

On 12/7/2019 at 7:21 PM, Kayzee said:

Might be! Hehe... I didn't even know yanfly had a stealth script. I kinda made my own in my game, but it's pretty darn simple. :3

It's this one here. It's extremely simple, but it's more or less what I need.

[Kayzee 4,033]

Also: If you are still using this script, it's probobly what is preventing you from saving the game properly.

[PhoenixSoul 1,404]

5 hours ago, AutumnAbsinthe said:

It's this one here. It's extremely simple, but it's more or less what I need.

 

That event chase player script is a bit odd; if the player is not within sight or a certain distance, the event will not move in the way you'd expect.
I noticed this behavior in the Yuri game Luxaren Allure.