Author Topic: [XP] Lagless Path Finder  (Read 20241 times)

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
[XP] Lagless Path Finder
« on: February 09, 2013, 04:22:06 PM »
Lagless Path Finder
Authors: Blizzard
Version: 1.3
Type: Path Finding System
Key Term: Environment Add-on

Introduction

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.

This work is licensed under BSD License 2.0:
Quote
Copyright (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:
Quote
Lagless 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:
Quote
Lagless 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


Screenshots

N/A

Demo

Lagless Path Finder

Script

Just make a new script above main and paste this code into it.
Script Download

Instructions

Inside the script in the first comment.

Compatibility

99% compatible with SDK v1.x. 90% compatible with SDK v2.x. May cause incompatibility issues with exotic map systems.

Credits and Thanks

  • Boris "Blizzard" Mikić

Author's Notes

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.

If you find any bugs, please report them here:
http://forum.chaos-project.com

That's it! Enjoy! =D
« Last Edit: March 23, 2019, 06:26:21 PM by Blizzard »
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline Terv

  • Awakened Visionist
  • **
  • Posts: 83
  • LV: 14
    • View Profile
Re: Lagless Path Finder
« Reply #1 on: February 09, 2013, 04:35:30 PM »
Best pathfinder in RPG maker history. Full stop! :D
5 approaching events, Ruby 1.9.2: 57fps. Beautiful.
« Last Edit: February 09, 2013, 04:48:32 PM by Terv »

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: Lagless Path Finder
« Reply #2 on: February 09, 2013, 04:50:31 PM »
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.
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline KK20

  • Master Scripter Fixer
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3197
  • LV: 385
  • Gender: Male
  • Choco Octo <3
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #3 on: February 09, 2013, 07:30:35 PM »
Eeyup, this moves much better than F0's. Looks like I wasted my night.

Level++



Other Projects
RPG Maker XP AceUpgrade RMXP to RMVXA performance!
XPA TilemapTilemap rewrite with many features, including custom resolution!


Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Offline Ryex

  • Arctic Bird of Programming
  • Global Moderator
  • Chaos Ultimate
  • ****
  • Posts: 5135
  • LV: 198
  • Gender: Female
  • Wants to write a compiler for fun
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #4 on: February 09, 2013, 07:40:38 PM »
your script download link links to your easy overdrve system :P
I no longer keep up with posts in the forum very well. If you have a question or comment, about my work, or in general I welcome PM's. if you make a post in one of my threads and I don't reply with in a day or two feel free to PM me and point it out to me.

DropBox, the best free file syncing service there is.
(click to show/hide)

Offline Zexion

  • Addicted to LoL
  • Chaos User
  • ******
  • Posts: 1519
  • LV: 69
  • Gender: Male
  • My anaconda don't...jk it does
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #5 on: February 09, 2013, 08:28:38 PM »
your script download link links to your easy overdrve system :P

Subliminal messaging much ?  :naughty:

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #6 on: February 09, 2013, 09:08:13 PM »
@gameus: Thanks for fixing the link. <3 I copy-pasted the topic template from the EOS and forgot the script link.
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline G_G

  • Green Gmod Game_Guy AKA G4 AKA hyper-G AKA G-force
  • Global Moderator
  • Chaos Ultimate
  • ****
  • Posts: 6591
  • LV: 407
  • Gender: Male
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #7 on: February 09, 2013, 09:19:16 PM »
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.

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #8 on: February 09, 2013, 10:14:22 PM »
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.
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline KK20

  • Master Scripter Fixer
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3197
  • LV: 385
  • Gender: Male
  • Choco Octo <3
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #9 on: February 14, 2013, 02:26:19 AM »
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."



Other Projects
RPG Maker XP AceUpgrade RMXP to RMVXA performance!
XPA TilemapTilemap rewrite with many features, including custom resolution!


Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #10 on: February 14, 2013, 05:03:54 AM »
Whoops. :)
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline Terv

  • Awakened Visionist
  • **
  • Posts: 83
  • LV: 14
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #11 on: March 07, 2013, 07:54:49 PM »
Btw there's a tiny mistake in the dyn_request method:

Code: [Select]
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
« Last Edit: March 07, 2013, 09:48:03 PM by Terv »

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #12 on: March 07, 2013, 09:34:35 PM »
Actually that line is correct. There's a line missing after def self.dyn_request.

Code: [Select]
   tx, ty = x, y
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.
« Last Edit: March 07, 2013, 09:36:03 PM by Blizzard »
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline finalholylight

  • Awakened Visionist
  • **
  • Posts: 78
  • LV: 0
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #13 on: March 27, 2013, 07:27:00 PM »
I have small problem with this script, my picture will explain:

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #14 on: March 27, 2013, 08:05:41 PM »
I don't think your map is set up right. Can you walk over that path yourself?
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline KK20

  • Master Scripter Fixer
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3197
  • LV: 385
  • Gender: Male
  • Choco Octo <3
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #15 on: March 27, 2013, 08:21:55 PM »
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
Code: [Select]
if request.range == 0 && kx == request.tx && ky == request.ty && char.passable?(key[0], key[1], dir[2])
« Last Edit: March 27, 2013, 08:44:24 PM by KK20 »



Other Projects
RPG Maker XP AceUpgrade RMXP to RMVXA performance!
XPA TilemapTilemap rewrite with many features, including custom resolution!


Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #16 on: March 27, 2013, 09:21:12 PM »
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.
« Last Edit: March 27, 2013, 09:22:33 PM by Blizzard »
Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.

Offline Heretic86

  • Astral Trancist
  • *****
  • Posts: 775
  • LV: 33
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #17 on: March 27, 2013, 11:17:53 PM »
Level Up for maintaining your scripts.  The better we support our scripts, the more useful they are to the people that use them.
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

Offline finalholylight

  • Awakened Visionist
  • **
  • Posts: 78
  • LV: 0
    • View Profile
Re: [XP] Lagless Path Finder
« Reply #18 on: March 28, 2013, 05:59:29 AM »
Yes,I can walk over that path myself. Also, I already test with Near Fantastica's path finding, and it walk correctly

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 20013
  • LV: 651
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Lagless Path Finder
« Reply #19 on: March 28, 2013, 10:12:41 AM »
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?

Check out Daygames and our games:

King of Booze      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


Quote from: winkio
I do not speak to bricks, either as individuals or in wall form.

Quote from: Barney Stinson
When I get sad, I stop being sad and be awesome instead. True story.