Lagless Path Finder
Authors: Blizzard
Version: 1.3
Type: Path Finding System
Key Term: Environment Add-on
IntroductionThis script will allow your characters to walk from point A to point B, navigating by themselves, finding the shortest path and all that without you having to manually specify their moving route. They can also navigate through dynamically changing environments or track a dynamically moving target.
This work is licensed under BSD License 2.0:
QuoteCopyright (c) Boris "Blizzard" Mikić
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. Neither the name of the copyright holder nor the names of its contributors
may be used to endorse or promote products derived from this software
without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.
You may use this script for both non-commercial and commercial products without limitations as long as you fulfill the conditions presented by the above license. The "complete" way to give credit is to include the license somewhere in your product (e.g. in the credits screen), but a "simple" way is also acceptable. The "simple" way to give credit is as follows:
QuoteLagless Path Finder licensed under BSD License 2.0, Copyright (c) Boris "Blizzard" Mikić
Alternatively, if your font doesn't support diacritic characters, you may use this variant:
QuoteLagless Path Finder licensed under BSD License 2.0, Copyright (c) Boris "Blizzard" Mikic
In general other similar variants are allowed as long as it is clear who the creator is (e.g. "Lagless Path Finder created by Blizzard" is acceptable). But if possible, prefer to use one of the two variants listed above.
If you fail to give credit and/or claim that this work was created by you, this may result in legal action and/or payment of damages even though this work is free of charge to use normally.
Features- calculates path from point A to point B on the map
- allows immediate calculation as well as path calculation requests that are done over the course of a few frames in order to reduce lag
- supports dynamic calculation that is done every step to ensure the character reaches its targets
- can assign other characters as targets so dynamic calculation with a moving will cause the character to find the target regardless of his changed position
v1.01- fixed attempted optimizations to work properly
v1.1- added PASSABLE parameter for all path finder functions to determine how to behave when using the RANGE parameter
v1.2- added waypoints
- Game_Character#has_path_target? now returns true as well when using target coordinates instead of a target character
v1.21- added option for loose movement when target cannot be reached
- added separate option for debug messages
v1.22- fixed a problem with waypoints when using range
v1.22- fixed a problem when DIRECTIONS_8_WAY is turned on
v1.3- added new license
- added usage and crediting instructions
ScreenshotsN/A
DemoLagless Path Finder (https://downloads.chaos-project.com/scripts/Lagless Path Finder.zip)
ScriptJust make a new script above main and paste this code into it.
Script Download (https://downloads.chaos-project.com/scripts/Lagless%20Path%20Finder.txt)
InstructionsInside the script in the first comment.
Compatibility99% compatible with SDK v1.x. 90% compatible with SDK v2.x. May cause incompatibility issues with exotic map systems.
Credits and Thanks
Author's NotesThis Path Finder is a derived version of Blizz-ABS's original Path Finder. If you are using Blizz-ABS, please remove this script. Blizz-ABS has a Path Finder already built-in.
If you find any bugs, please report them here:
http://forum.chaos-project.com
That's it! Enjoy! =D
Best pathfinder in RPG maker history. Full stop! :D
5 approaching events, Ruby 1.9.2: 57fps. Beautiful.
When I realized that I could easily let it calculate 200+ nodes per frame, I set the calculation limit to 100 just to be one the safe side. Since Blizz-ABS requires a lot of processing power, it only uses 5 nodes per frame in Blizz-ABS. This is quite a difference.
Eeyup, this moves much better than F0's. Looks like I wasted my night.
Level++
your script download link links to your easy overdrve system :P
Quote from: Ryex on February 09, 2013, 12:40:38 pm
your script download link links to your easy overdrve system :P
Subliminal messaging much ? :naughty:
@gameus: Thanks for fixing the link. <3 I copy-pasted the topic template from the EOS and forgot the script link.
Judging from the name of the demo, it wasn't all that hard to find the script.
http://downloads.chaos-project.com/scripts/Lagless%20Path%20Finder.txt
No problem Blizzard! Nice job on this, wasn't expecting to see another script release from you when I logged in. xD Haven't had a full Saturday off for awhile. Gonna hang around the forums for a bit today.
It's good that my OCD likes all stuff named properly.
I wasn't going to make it at first, but I was too lazy to first understand the whole design of F0's script and then have to redesign it. It was easier to pull out Blizz-ABS's one, tweak it a bit and release it separately.
Hah, I was trying to find this script in the database to study it some more but couldn't find it.
Then I saw 'Custom Environment Add-on'. And then I was like "Oh you."
Whoops. :)
Btw there's a tiny mistake in the dyn_request method:
def self.dyn_request(char, x, y = nil, range = 0)
char, x, y, range = self.check_args(char, x, y, range)
self._request(char, x, y, range, true)
char.set_path_target(tx, ty, range, false)
return true
end
Actually that line is correct. There's a line missing after def self.dyn_request.
I updated the script.
The thing is that tx and ty would be the original arguments passed into the method. This ensures that character tracking works right. Otherwise, the character would only to to the position where the character was when the call was made.
I have small problem with this script, my picture will explain:
(http://i663.photobucket.com/albums/uu358/finalholylight/PathFinding_zpsde7e0cc5.jpg)
I don't think your map is set up right. Can you walk over that path yourself?
I tried it out for myself. At first I thought it had to do something with it walking onto an event, but that's not it. I set a tile to not be passable to the left and had the target location and moving event on the same x-axis. I can't walk over the tile. I get the same error.
If you move the target location so that it looks like [target, empty_space, wall, empty_spaces..., event] the event will walk around the wall.
EDIT: I think I figured it out. Line 317 should be this
if request.range == 0 && kx == request.tx && ky == request.ty && char.passable?(key[0], key[1], dir[2])
Yeah, I thought it might be this line since I remember adding an optimization to skip the last check if the adjacent tile was the target. But I forgot that in RMXP you can make that connection impassable. That's why I asked if he could walk from that last tile to the other.
If this is really it, I'll fix it ASAP.
Level Up for maintaining your scripts. The better we support our scripts, the more useful they are to the people that use them.
Yes,I can walk over that path myself. Also, I already test with Near Fantastica's path finding, and it walk correctly
(http://i663.photobucket.com/albums/uu358/finalholylight/PathFingNP_zps3402bcab.jpg)
Actually both these paths are correct. Near Fantastica's and the one you posted which it should use. There is even one more combination that is also valid.
So in this is the path it walks and then it gets stuck, am I right?
(http://i663.photobucket.com/albums/uu358/finalholylight/PathFinding_zpsde7e0cc5.jpg)
Yes, you're right, it gets stuck when move to location next to the stair, I can not move after that.
Alright, then it's most probably what KK20 mentioned. I'll fix it later today, it's a quick fix.
Ow, Blizzard, you forgot fixing the script ~.~
When I saw this in the list of unread topics, I totally realized that. I can't remember why this topic wasn't in an open tab anymore so I remember to fix this. I'll do it tomorrow when I get home from work.
EDIT: Fixed.
Any chance you'll add a success/failure proc so you can give the event further intructions if it has reached its destination or split a path up in several waypoints, like in F0's script? Looks kind of wierd if NPCs in a city wall-hug all the time instead of using the sidewalk :^_^':
Also they would be able to sideline vexatious heroes blocking their path.
Of course this could be done by constantly checking x/y or if the event is still moving, but I guess that'd be rather performance heavy to do for 3+ events, especially if fps is a precious resource.
I didn't like F0's implementation, especially since it was bound to scripting and not events. Use this in a parallel process instead:
# In order to check if a character has a dynamic path calculation for a
# target, use following script call:
#
# character.has_path_target?
#
# Example:
#
# if $game_map.events[23].has_path_target?
Is it possible to determine whether a character has a non-dynamic calculation as well? I.e. hasn't made it to the destination yet.
You could use this:
But there is no distinction between a character moving by normal events and through the path finder.
Yup I decided to use moving? combined with a range check to be sure it's not the player or another NPC causing the character not to move anymore. Thanks for your time :up:
Edit: Could you explain what exactly clear_path_target does? Is it supposed to stop a character while pathfinding, or just stop updating the target coords?
I forgot. I'll go check. xD
EDIT: It will abort the path finding and moving completely.
I've found this command to stop pathfinding, however the event will still finish its way to the last coordinates. In order to stop movement too you have to use an empty Set Move Route event command (just in case someone else stumbles upon this).
Is there a way to call this script from inside another script instead of from an event? I'd love to add it to the custom controls to allow for movement by mouse, but I'm not sure how to set it up.
Yes, you can simply use the same script calls from the instructions within another script.
I tried adding this script call at the end of the updates module of the custom commands area in "Tons of Add-ons":
if @game_map = true
if key == 'Mouse Left'
PathFinder.dyn_request(0, x, y)
end
end
When I try to play test I get an error message: Script 'Path Finder' line 422:SystemStackError occurred. stack level too deep
Am I just completely wrong in how to do the script call or is there something else I have to change as well?
Tried it both ways, still got the error, then realized I had two copies of the path finder installed.... *reminds self not to do scripting at 3am*
Still can't get the pathfinder to work with the mouse, but no error message, so not sure how to fix it. Would the script order matter? Or where exactly in the custom commands script I added the script call? If you have any pointers I'd appreciate it.
The mouse enhancement for this script should definitely be under it. You could use my Mouse Controller script in conjunction with the $game_map.display_x and $game_map.display.y variables and the click position to get some sort of mouse-to-map translation and then (after some more calculation) you can pass the coordinates to the path finder.
Appears what I'm trying to do is too far above my scripting ability. Thanks for trying to help.
Found them bugs:
- dynamic calls behave oddly. I made sure I'm calling them only once. dyn_request: the pathfinding event is swaying like after a dozen glasses Scotch as soon as there's an obstacle to be circumvented. dyn_find: way to target is fine but the event doesn't stop there (range 1) but keeps circling around it (this is also true for dyn_request).
Call used:
PathFinder._____(@event_id, $game_player, 1)A screen from a new map in your demo (dyn_request):
(http://img.tikky.tk/dyn_request_bug.gif)
Lagless Path Finder Bugs.zip (http://cdn.tikky.tk/Lagless%20Path%20Finder%20Bugs.zip)
I'll take a look at it. But keep in mind that the moving is used as movement route so naturally when you change the page, it's gone.
EDIT: Fixed it. Nvm about the page changing, the character should still continue on its path because either way with dyn_request the path is recalculated after every step.
EDIT: Actually wait, dyn_find seems broken.
EDIT: Alright, I fixed it all. One of the problems was caused by the recent "fix" due to passability, but now it doesn't work in the opposite scenario when you want to get closer to a non-passable position so I have included an optional parameter after RANGE to determine whether the next neighbor has to be passable or not when using RANGE.
Where would I start editing if I want certain events' dyn_request update only, say, once per 40 frames? Because I have loads of NPCs that I do not need to find around new obstacles quickly. Having them stop for a second when the player blocks their path is even desirable so he can easily talk to them.
PathFinder#update, but it's simpler if you just change MAX_NODES_PER_FRAME. As a matter of fact, that should be enough since you can limit how many nodes are calculated every frame so there is no lag.
The problem with the max nodes is that the events will wait after every step instead of keeping walking. Basically they wait for their updated path and don't follow their old one until a new path is available. I guess so at least :^_^':
I'm currently using a loop with .find, followed by a wait of 40 frames. Does the job and costs around 0.5-1 fps per event in my usual use cases. Yet I'd like to know if there's a way with dyn_request.
Then no, at least not easily. That's not how they were intended to be used. You will have to modify the code yourself.
Keep in mind that the dyn_* variants are meant for targets that move and/or environments that keep changing.
Quote from: Blizzard on August 20, 2013, 05:44:57 amor environments that keep changing.
Good point, my towns aren't really ever-changing, at all. The loop now only issues a new find call if the event hasn't moved for a second. dynamic pathfinding or continuos updates in general is overkill for my scenario. Thanks for pointing that out.
If i enable 8-Dir he stuck on the wall and can find the path and without 8-dir works im alone with this bug? when no please fix it :(
8-dir is not path finding using 8 directions, it's just used to cut corners in an 8-dir manner. It should actually work, though.
Minor edit:
I'm trying a change to module PathFinder def self.update:
code removed, did not work as expected
Allows pathfind to a spot, wait, pathfind to next waypoint, wait, etc
---
I have an Event that changes pages, then tries to pathfind using Loose to a spot, but when it gets to the spot, it just goes back and forth on that spot but does not stop moving. The pathfind is called in an Automated Move Route Script.
PathFinder.dyn_request(@id, [49,40], 2, true)
The spot is triggered when the player moves to that location so its occupied at the time of trigger. There are terrain tiles in the way so it needs to pathfind to that spot, but once there, the NPC just moves back and forth and is stuck. Anyone know what I'm doing wrong?
maybe you need to add one more condition to stop the character when the character is already arrived at destination
something like :
if (last = characters.last) && last.x != @x && last.y != @y
or
if (last = characters.last) && (last.x - @x).abs < 1 && (last.y - @y).abs < 1
It's not just your edit; it's the script. Putting a RANGE of anything greater than 1 will cause this frantic walking of back and forth.
I made this change to Game_Character#update
def update
update_lagless_path_finder_later
return if self.moving? || !self.has_path_target?
if (@x - @path_targets[0].x).abs + (@y - @path_targets[0].y).abs <= @path_targets[0].range #<===== THIS RIGHT HERE
self.next_path_target
check = true
else
check = @path_targets[0].dynamic
end
if check && self.has_path_target?
if @path_targets[0].immediate
PathFinder._find(self, @path_targets[0])
else
PathFinder._request(self, @path_targets[0])
end
end
end
And that stopped it. The script was failing to remove the current path request and kept requesting paths constantly since the character will never reach the coordinates of the target location (and effectively call next_path_target). Not sure if confirmed, but just throwing this out there.
It's possible that I messed up during the refactor when I added waypoints. Let me know if this fixes the problem completely so that I can add it to the main script. Try both "passable" and "impassable" mode when you test this.
Alright. Further testing of checking for @wait_count didnt quite work, but lets see if this edit does anything.
Thank you guys.
---
After some decent testing, KK20's update appears to do the trick. As a nice little benefit, this appears to also cause putting a wait command between pathfinding waypoints to work properly.
I did add in
in
also.
Updated.
Please except my apologies for seeming like a complete newb, but I have no idea how scripts work. I am trying to create better pathfinding for the enemies in my game (abs style) so that when you come within a certain range of them, they automatically come at you to attack, or if you get a certain distance away, they stop.
I copied the script over into the proper spot, copied the following PathFinder.request(C_ID, TARGET[, RANGE[, PASSABLE]]) and pasted it into a script call in one of my events movements that is set to custom. I have tried plugging in multiple things within C_ID and Target etc... Nothing is working as it just keeps giving me a Syntax Error.
Basically, how exactly should PathFinder.request(C_ID, TARGET[, RANGE[, PASSABLE]]) be set up? I read through the script and read the tutorial but I find the technical terms used to be a bit confusing of what each of those 4 things mean.
C_ID,
TARGET,
RANGE and
PASSABLE are the parameters of the call. This is standard call syntax notation and it means you can call it with either
C_ID and
TARGET or
C_ID,
TARGET and
RANGE or with all 4 parameters. You are supposed to put actual values instead of literally
PathFinder.request(C_ID, TARGET[, RANGE[, PASSABLE]]). I suggest that you download the demo and take a look how it's done there and it should become clear then.
All possible calls are:
PathFinder.request(C_ID, TARGET)
PathFinder.request(C_ID, TARGET, RANGE)
PathFinder.request(C_ID, TARGET, RANGE, PASSABLE)
C_ID is the "character ID". That means that if you put a
5 there, it will do path finding for the event with ID 5. TARGET is an array with the x and y coordinates like
[10, 20]. RANGE is used if the character isn't supposed to go to an actual position, but just come into range of that position. e.g. if you put a
2 there, the character will move towards the target position and stop once he's 2 squares away. And PASSABLE is used for checking whether the target position has to be passable. e.g. You could gather characters around a tower with a certain range, but the tower is not passable so you have to use
false in order to make the character stop when he's in range.
Quote from: Blizzard on December 01, 2013, 03:48:07 am
C_ID, TARGET, RANGE and PASSABLE are the parameters of the call. This is standard call syntax notation and it means you can call it with either C_ID and TARGET or C_ID, TARGET and RANGE or with all 4 parameters. You are supposed to put actual values instead of literally PathFinder.request(C_ID, TARGET[, RANGE[, PASSABLE]]). I suggest that you download the demo and take a look how it's done there and it should become clear then.
All possible calls are:
PathFinder.request(C_ID, TARGET)
PathFinder.request(C_ID, TARGET, RANGE)
PathFinder.request(C_ID, TARGET, RANGE, PASSABLE)
C_ID is the "character ID". That means that if you put a 5 there, it will do path finding for the event with ID 5. TARGET is an array with the x and y coordinates like [10, 20]. RANGE is used if the character isn't supposed to go to an actual position, but just come into range of that position. e.g. if you put a 2 there, the character will move towards the target position and stop once he's 2 squares away. And PASSABLE is used for checking whether the target position has to be passable. e.g. You could gather characters around a tower with a certain range, but the tower is not passable so you have to use false in order to make the character stop when he's in range.
Thanks for the quick reply. I will download the demo and test out what you said.
Quote from: Blizzard on December 01, 2013, 03:48:07 am
Tried out the demo, finally got it working. But I have one small issue :facepalm:
I am trying to make an event follow me or even just walk to my location by putting a 0 in the TARGET value (Which 0 is the player). Does this work because it just gives me a 359 error (Nil can't be forced into fixnum). The reason I got this pathfinder is so I could use it to give my evented enemies better AI when it comes to pathfinding when they chase you down to finally attack you. It works sending me or an event to locations I specify such as [11, 12] or whatever but it doesn't work trying to put a 0 in the TARGET value.
So basically, can this be used to send events my way or is the TARGET specifically for X and Y coordinates?
Thanks for you help.
EDIT: If it is possible, what exactly should I put in the TARGET value?
Use $game_player for TARGET, it should work.
Quote from: Blizzard on December 04, 2013, 02:34:21 am
Use $game_player for TARGET, it should work.
Works perfectly.
I am getting a few bugs however. I decided to go ahead with using dynfind since I will have multiple events moving about the map targeting you. The odd thing is that I noticed using "set move route" for any of the events and adding in a "wait" will mess up the script. Also I am currently getting strange things happening, such as the events will sometimes completely freeze or stop running certain variables or commands.
I am using PathFinder.dyn_find(7, $game_player, 1, false)
I have tried putting $game_map.events[7].clear_path_target in at several spots in an event page to stop the script to see if it would fix them from bugging but it does not.
I have my events set for custom move route "Move towards player" and have tried putting it on fixed but they end up just stopping at you or bugging worse.
Sorry to unload issues but I would like for this to work. Your script is almost to much of what I needed lol. It is an awesome script. All I am trying to obtain is for when the page is flipped in an event, they pursue you intelligently, and when I turned the switch off to flip the page back, they stop. =\
I will mess around with it some more because it might just be my own ignorance messing this up.
Can you make a demo?
Also, please check if the wait commands works when you don't use the path finder. Because the wait command is buggy in some RMXP editions.
Quote from: Blizzard on December 05, 2013, 01:54:58 am
Can you make a demo?
Also, please check if the wait commands works when you don't use the path finder. Because the wait command is buggy in some RMXP editions.
I decided to keep messing around with it so you wouldn't have to waste your time lol.
My waits work perfectly in whatever edition I have. I kept messing around with when the game calls your lagless pathfinding script and stops it from running using $game_map.events[ID].clear_path_target. <--- after plugging that into the right spot and setting the range of it calling the script to 0 instead of 1, it works now.
Hopefully things will run smoothly now or I will have to upload a demo as you said.
I was wondering though, is this script messing around with the X and Y cords of my character and events that are calling it? I know it prolly is obviously, but is it changing there X and Y positions to things that are false? Such as if the main character has an X and Y of 12/24 is it changing his X and Y to something not true. Because I have variables using X and Y of the main character and events other than your pathfinder script...and that may be messing with my variables.
No, it doesn't change the X and Y coordinates. But it does add custom movement commands so technically the coordinates get altered afterward.
Quote from: hirasu on November 03, 2013, 12:04:32 am
If i enable 8-Dir he stuck on the wall and can find the path and without 8-dir works im alone with this bug? when no please fix it :(
lmao Blizz, you totally misinterpreted this guy's question xD
Zex mentioned this bug to me. If you enable DIRECTIONS_8_WAY and make an event path find from say 3,3 to 0,0, the event never actually makes it.
The problem was in set_found_path:
# each move command code equals direction / 2
path.reverse.each {|dir| route.list.unshift(RPG::MoveCommand.new(dir / 2))}
Now this works fine for 4 directions (2,4,6,8) because
# During move command (from move down to jump)
if command.code <= 14
# Branch by command code
case command.code
when 1 # Move down
move_down
when 2 # Move left
move_left
when 3 # Move right
move_right
when 4 # Move up
move_up
But when you add in the diagonal movement:
when PathFinder::DIR_DOWN_LEFT, PathFinder::DIR_LEFT_DOWN
result[i], result[i + 1] = 1, nil
when PathFinder::DIR_DOWN_RIGHT, PathFinder::DIR_RIGHT_DOWN
result[i], result[i + 1] = 3, nil
when PathFinder::DIR_LEFT_UP, PathFinder::DIR_UP_LEFT
result[i], result[i + 1] = 7, nil
when PathFinder::DIR_RIGHT_UP, PathFinder::DIR_UP_RIGHT
result[i], result[i + 1] = 9, nil
end
Those values get divided by 2 as well! xD
EDIT: Realized I could have just replaced the diagonal values with 10,12,14,16 but oh wellI updated to v1.23. Feel free to replace the first post with this:
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
# Lagless Path Finder by Blizzard
# Version: 1.23
# Type: Pathfinding System
# Date: 9.2.2013
# Date v1.01: 11.4.2013
# Date v1.1: 29.7.2013
# Date v1.2: 7.10.2013
# Date v1.21: 8.10.2013
# Date v1.22: 11.11.2013
# Date v1.23: 28.12.2016 (fix by KK20)
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
#
# This work is protected by the following license:
# #----------------------------------------------------------------------------
# #
# # Creative Commons - Attribution-NonCommercial-ShareAlike 3.0 Unported
# # ( http://creativecommons.org/licenses/by-nc-sa/3.0/ )
# #
# # You are free:
# #
# # to Share - to copy, distribute and transmit the work
# # to Remix - to adapt the work
# #
# # Under the following conditions:
# #
# # Attribution. You must attribute the work in the manner specified by the
# # author or licensor (but not in any way that suggests that they endorse you
# # or your use of the work).
# #
# # Noncommercial. You may not use this work for commercial purposes.
# #
# # Share alike. If you alter, transform, or build upon this work, you may
# # distribute the resulting work only under the same or similar license to
# # this one.
# #
# # - For any reuse or distribution, you must make clear to others the license
# # terms of this work. The best way to do this is with a link to this web
# # page.
# #
# # - Any of the above conditions can be waived if you get permission from the
# # copyright holder.
# #
# # - Nothing in this license impairs or restricts the author's moral rights.
# #
# #----------------------------------------------------------------------------
#
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
#
# IMPORTANT NOTE:
#
# This Path Finder is a derived version of Blizz-ABS's original Path Finder.
# If you are using Blizz-ABS, please remove this script. Blizz-ABS has a
# Path Finder already built-in.
#
#
# Compatibility:
#
# 99% compatible with SDK v1.x. 90% compatible with SDK v2.x. May cause
# incompatibility issues with exotic map systems.
#
#
# Features:
#
# - calculates path from point A to point B on the map
# - allows immediate calculation as well as path calculation requests that
# are done over the course of a few frames in order to reduce lag
# - supports dynamic calculation that is done every step to ensure the
# character reaches its targets
# - can assign other characters as targets so dynamic calculation with a
# moving will cause the character to find the target regardless of his
# changed position
#
# new in v1.01:
# - fixed attempted optimizations to work properly
#
# new in v1.1:
# - fixed a problem with how dyn_request is handled
# - added PASSABLE parameter for all path finder functions to determine
# how to behave when using the RANGE parameter
#
# new in v1.2:
# - added waypoints
# - Game_Character#has_path_target? now returns true as well when using
# target coordinates instead of a target character
#
# new in v1.21:
# - added option for loose movement when target cannot be reached
# - added separate option for debug messages
#
# new in v1.22:
# - fixed a problem with waypoints when using range
#
# new in v1.23:
# - fixed a problem when DIRECTIONS_8_WAY is turned on
#
# Instructions:
#
# - Explanation:
#
# This script will allow your characters to walk from point A to point B,
# navigating by themselves, finding the shortest path and all that without
# you having to manually specify their moving route. They can also navigate
# through dynamically changing environments or track a dynamically moving
# target.
#
# - Configuration:
#
# MAX_NODES_PER_FRAME - maximum number of node calculation per frame when
# using path requests instead of immediate calculations
# DIRECTIONS_8_WAY - if set to true, it will smooth out corner movement
# and use a diagonal movement step wherever possible
# (this does NOT mean that the path finder will do
# 8-directional path finding!)
# LOOSE_MOVEMENT - if set to true, it will cause characters to continue
# moving when the target cannot be reached for some
# reason, following its last movement path (works only
# with "dyn" variants)
# DEBUG_MESSAGES - if set to true, it will display messages when paths
# can't be found
#
#
# - Script calls:
#
# This path finder offers you several script calls in order to designate path
# finding to characters on the map. Following script calls are at your
# disposal:
#
# PathFinder.find(C_ID, TARGET[, RANGE[, PASSABLE]])
# PathFinder.request(C_ID, TARGET[, RANGE[, PASSABLE]])
# PathFinder.dyn_find(C_ID, TARGET[, RANGE[, PASSABLE]])
# PathFinder.dyn_request(C_ID, TARGET[, RANGE[, PASSABLE]])
#
# C_ID - either an event ID, 0 for the player character or an actual
# character (e.g. $game_map.events[ID])
# TARGET - an array with X,Y coordinates, an actual target character,
# an array with arrays of X,Y waypoints or an array of actual
# character waypoins
# RANGE - range within which the target should be located (greater than 0)
# PASSABLE - when using a range, this is used to determine if the next tile
# must be passable as well, false by default, used usually when
# passability between 2 tiles isn't used
#
# This is how the 8 different script calls behave:
#
# - The "find" variants always calculate the path immediately.
# - The "request" variants always request a path calculation to be done over
# the course of several frames in order to avoid lag. Requesting paths for
# multiple characters will cause the calculation to take longer as each
# frame only a certain number of nodes is calculated (can be configured).
# So if there are more characters requesting a path, naturally each one
# will consume a part of the allowed node calculations every frame.
# - The "dyn" variants (dynamic) will recalculate/request a calculation every
# step in order to keep a path up to date with an ever-changing
# environment. You won't need to use these calls if there are no moving
# events on the map or if there are no environmental passability changes.
# - When using a "dyn" variant, if actual coordinates (X, Y) are used, the
# character will find its path to these fixed coordinates. If an actual
# target character is being used, the path finder will track the character
# instead of fixed coordinates. If the character changes its position, the
# path calculation will attempt to find a path to the new position of the
# target.
# - Using "dyn_find" a lot, with many characters at the same time and/or for
# long paths may cause performance issue and lag. Use it wisely.
# - Using "dyn_request" is much more performance-friendly, but it will also
# cause characters to "stop and think". This can also cause problems in a
# constantly changing environment as the environment may change during the
# few frames while the calculation is being done. Use it wisely.
# - In order to queue multiple targets like waypoints, simply call any of the
# functions as many times as you need.
#
# In order to cancel dynamic path calculation for a character, use following
# script call:
#
# character.clear_path_target
#
# Example:
#
# $game_map.events[23].clear_path_target
#
# In order to check if a character has a dynamic path calculation for a
# target, use following script call:
#
# character.has_path_target?
#
# Example:
#
# if $game_map.events[23].has_path_target?
#
#
# Notes:
#
# - This path finder is an implementation fo the A* Search Algorithm.
# - The PathFinder module is being updated during the call of
# $game_system.update. Keep this in mind if you are using specific exotic
# scripts.
# - When using the option LOOSE_MOVEMENT, keep in mind that it doesn't work
# accurately with dyn_request, because request calculations aren't done
# immediately like with dyn_find.
#
#
# If you find any bugs, please report them here:
# http://forum.chaos-project.com
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
# START Configuration
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
module BlizzCFG
MAX_NODES_PER_FRAME = 50
DIRECTIONS_8_WAY = false
LOOSE_MOVEMENT = false
DEBUG_MESSAGES = false
end
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
# END Configuration
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
$lagless_path_finder = 1.22
#==============================================================================
# module PathFinder
#==============================================================================
module Math
def self.hypot_squared(x, y)
return (x * x + y * y)
end
end
#==============================================================================
# module PathFinder
#==============================================================================
module PathFinder
PATH_DIRS = [[0, 1, 1], [-1, 0, 2], [1, 0, 3], [0, -1, 4]]
DIR_DOWN_LEFT = [1, 2]
DIR_LEFT_DOWN = [2, 1]
DIR_DOWN_RIGHT = [1, 3]
DIR_RIGHT_DOWN = [3, 1]
DIR_LEFT_UP = [2, 4]
DIR_UP_LEFT = [4, 2]
DIR_RIGHT_UP = [3, 4]
DIR_UP_RIGHT = [4, 3]
DIR_OFFSETS = [[ 0, 0], [0, 1], [-1, 0], [1, 0], [0,-1],
[-1, 1], [1, 1], [-1,-1], [1,-1]]
@requests = {}
def self.clear
@requests = {}
end
def self.find(char, target, range = 0, pass = false)
char, target = self.check_args(char, target, range, pass, false, true)
self._find(char, target, true)
return true
end
def self.dyn_find(char, target, range = 0, pass = false)
char, target = self.check_args(char, target, range, pass, true, true)
self._find(char, target, true)
return true
end
def self.request(char, target, range = 0, pass = false)
char, target = self.check_args(char, target, range, pass, false, false)
self._request(char, target, true)
return true
end
def self.dyn_request(char, target, range = 0, pass = false)
char, target = self.check_args(char, target, range, pass, true, false)
self._request(char, target, true)
return true
end
def self.check_args(char, target, range, pass, dynamic, immediate)
range = 0 if range == nil || range < 0
if char.is_a?(Numeric)
char = (char > 0 ? $game_map.events[char] : $game_player)
end
target = PathTarget.new(target, range, pass, dynamic, immediate)
if $DEBUG && BlizzCFG::DEBUG_MESSAGES && char == nil
p "Warning! Character to move does not exist!"
end
return [char, target]
end
def self._find(char, target, new = false)
if @requests[char] == nil && (!char.has_path_target? || !new)
@requests[char] = PathRequest.new(char.x, char.y, target)
result = nil
result = self.calc_node(char) while result == nil
if $DEBUG && BlizzCFG::DEBUG_MESSAGES && result.size == 0
p "Warning! Path Finder could not find path for character at (#{target.x},#{target.y})!"
end
if !BlizzCFG::LOOSE_MOVEMENT && target.dynamic
char.set_found_step(result)
else
char.set_found_path(result)
end
end
char.add_path_target(target) if new
end
def self._request(char, target, new = false)
if @requests[char] == nil
@requests[char] = PathRequest.new(char.x, char.y, target)
end
char.add_path_target(target) if new
end
def self.update
@requests = {} if @requests == nil
characters = @requests.keys
count = BlizzCFG::MAX_NODES_PER_FRAME
while characters.size > 0 && count > 0
char = characters.shift
dynamic = @requests[char].target.dynamic
result = self.calc_node(char)
if result != nil
if !BlizzCFG::LOOSE_MOVEMENT && dynamic
char.set_found_step(result)
else
char.set_found_path(result)
end
else
characters.push(char)
end
count -= 1
end
end
def self.calc_node(char)
request = @requests[char]
if request.open.size == 0
@requests.delete(char)
return []
end
found = false
key = request.open.keys.min {|a, b|
a[2] > b[2] ? 1 : (a[2] < b[2] ? -1 :
(Math.hypot_squared(a[0] - request.target.x, a[1] - request.target.y) <=>
Math.hypot_squared(b[0] - request.target.x, b[1] - request.target.y)))}
request.closed[key[0], key[1]] = request.open[key]
request.open.delete(key)
kx, ky = 0, 0
passable = false
passable_checked = false
PATH_DIRS.each {|dir|
kx, ky = key[0] + dir[0], key[1] + dir[1]
passable = false
passable_checked = false
if (kx - request.target.x).abs + (ky - request.target.y).abs <= request.target.range
if request.target.pass
passable = char.passable?(key[0], key[1], dir[2]*2)
passable_checked = true
else
passable = true
end
if passable
request.closed[kx, ky] = dir[2]
found = true
break
end
end
if request.closed[kx, ky] == 0
passable = char.passable?(key[0], key[1], dir[2]*2) if !passable_checked
if passable
request.open[[kx, ky, key[2] + 1]] = dir[2]
end
end}
return nil if !found
result = request.backtrack(kx, ky)
@requests.delete(char)
return result
end
end
#==============================================================================
# PathTarget
#==============================================================================
class PathTarget
attr_reader :range
attr_reader :pass
attr_reader :dynamic
attr_reader :immediate
def initialize(target, range, pass, dynamic, immediate)
if target.is_a?(Game_Character)
@char = target
else
@x, @y = target
end
@range = range
@pass = pass
@dynamic = dynamic
@immediate = immediate
end
def x
return (@char != nil ? @char.x : @x)
end
def y
return (@char != nil ? @char.y : @y)
end
end
#==============================================================================
# PathRequest
#==============================================================================
class PathRequest
attr_reader :open
attr_reader :closed
attr_reader :sx
attr_reader :sy
attr_reader :target
def initialize(sx, sy, target)
@sx, @sy, @target = sx, sy, target
@open = {[@sx, @sy, 0] => -1}
@closed = Table.new($game_map.width, $game_map.height)
end
def backtrack(tx, ty)
cx, cy, x, y, result = tx, ty, 0, 0, []
loop do
cx, cy = cx - x, cy - y
break if cx == @sx && cy == @sy
result.unshift(@closed[cx, cy])
x, y = PathFinder::DIR_OFFSETS[@closed[cx, cy]]
end
return self.modify_8_way(result)
end
def modify_8_way(result)
if BlizzCFG::DIRECTIONS_8_WAY
result.each_index {|i|
if result[i] != nil && result[i + 1] != nil
case [result[i], result[i + 1]]
when PathFinder::DIR_DOWN_LEFT, PathFinder::DIR_LEFT_DOWN
result[i], result[i + 1] = 5, nil
when PathFinder::DIR_DOWN_RIGHT, PathFinder::DIR_RIGHT_DOWN
result[i], result[i + 1] = 6, nil
when PathFinder::DIR_LEFT_UP, PathFinder::DIR_UP_LEFT
result[i], result[i + 1] = 7, nil
when PathFinder::DIR_RIGHT_UP, PathFinder::DIR_UP_RIGHT
result[i], result[i + 1] = 8, nil
end
end}
result.compact!
end
return result
end
end
#==============================================================================
# Game_System
#==============================================================================
class Game_System
alias update_lagless_path_finder_later update
def update
PathFinder.update
update_lagless_path_finder_later
end
end
#==============================================================================
# Game_Map
#==============================================================================
class Game_Map
alias setup_lagless_path_finder_later setup
def setup(map_id)
PathFinder.clear
setup_lagless_path_finder_later(map_id)
end
end
#==============================================================================
# Game_Character
#==============================================================================
class Game_Character
def add_path_target(target)
@path_targets = [] if @path_targets == nil
@path_targets.push(target)
end
def clear_path_target
@path_targets = nil
end
def next_path_target
if @path_targets.size <= 1
self.clear_path_target
else
@path_targets.shift
end
end
def has_path_target?
return (@path_targets != nil && @path_targets.size > 0)
end
def set_found_path(path)
return if path.size == 0
route = RPG::MoveRoute.new
route.repeat = false
path.reverse.each {|dir| route.list.unshift(RPG::MoveCommand.new(dir))}
self.force_move_route(route)
end
def set_found_step(path)
return if path.size == 0
route = RPG::MoveRoute.new
route.repeat = false
route.list.unshift(RPG::MoveCommand.new(path[0]))
self.force_move_route(route)
end
alias update_lagless_path_finder_later update
def update
update_lagless_path_finder_later
return if self.moving? || !self.has_path_target? || self.jumping?
if (@x - @path_targets[0].x).abs + (@y - @path_targets[0].y).abs <=
@path_targets[0].range
self.next_path_target
check = true
else
check = @path_targets[0].dynamic
end
if check && self.has_path_target?
if @path_targets[0].immediate
PathFinder._find(self, @path_targets[0])
else
PathFinder._request(self, @path_targets[0])
end
end
end
end
Oh lol! xD I'll upload the fix today when I get home.
Hi! :D
I use the google-translator, sorry for my bad english :<
Can "if $game_map.events[23].has_path_target?" used in a conditional branch?
So it is important to me that the event can run several waypoints and a variable is changed at each point as soon as it is reached. :<
Then I have the following problem:
Where and how would I have to install, that also a terrain tag should be considered (so an event can only move on a certain TT)? Please do not always, but only at certain events. So best in the pathfind call, where coordinates X and Y is determined. So if no TT is determined, the event can move freely, if a TT is determined in the pathfind-call (in brackets), the event can only move on a specific TT.
Is that somehow and if so how? :D
Thanks in advance! :D
Josey~
(This english is so cruel XD
I hope you understand me... _._)
Remove the "if" in your statement and it can be used in a Conditional Branch.
The Terrain Tag feature is not built into the script. It would need to be manually added by a scripter.
Thank you for your answear! : D
Should I create a new topic for the Terrain Tag Feature?
You could, but no one is going to fulfill that request.
I've found a problem with this script. It works amazingly in most cases, however if you have a tile that is passable in at least one direction, but not all four, sometimes when pathfinding it's possible for events to get stuck trying to move into a tile that is not passable in a certain direction.
I've got a lot of these types of tiles, mainly for decoration (bar stools you can move behind but but not through them, for example) and a lot of my NPCs get stuck.
There even seems to be a check in place for this, as the script DOES account for direction. (See lines 395 and 407.)
passable = char.passable?(key[0], key[1], dir[0]*2)
I don't really understand how this script works, so I have no idea how to fix this...
If you could provide a visible example, I'd take a look at it.
Thanks!
Here's just a quick thing I whipped up in a default project to demonstrate.
In this setup the player will get stuck trying to navigate through the plant.
(Edit: No idea why the images won't display properly. Here they are anyway.)
https://imgur.com/a/leRSyFe
https://imgur.com/a/Gw4GljV
(https://imgur.com/a/leRSyFe)
(https://imgur.com/a/Gw4GljV)
Yeah, it has to do with the PASSABLE parameter in the script call. You should be setting that to true in these cases.
PathFinder.find(0, [19, 13], 0, true)
I feel like true should have been the default, or at the very least be the default if the range is 0.
def self.check_args(char, target, range, pass, dynamic, immediate)
range = 0 if range == nil || range < 0
pass = true if range == 0
Tysm! I didn't realize that passable did that. :^_^':
I think I did this because of performance reasons. But it's been a such long time ago, I really don't remember.