[XP] Lagless Path Finder

Started by Blizzard, February 09, 2013, 09:22:06 am

Previous topic - Next topic

Blizzard

February 09, 2013, 09:22:06 am Last Edit: October 07, 2021, 10:37:32 am by Blizzard
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:
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


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
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

Terv

February 09, 2013, 09:35:30 am #1 Last Edit: February 09, 2013, 09:48:32 am by Terv
Best pathfinder in RPG maker history. Full stop! :D
5 approaching events, Ruby 1.9.2: 57fps. Beautiful.

Blizzard

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 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

KK20

Eeyup, this moves much better than F0's. Looks like I wasted my night.

Level++

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

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

Join the CP Discord Server!

Ryex

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.<br /><br />DropBox, the best free file syncing service there is.<br />

Zexion

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:

Blizzard

@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 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

G_G

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.

Blizzard

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 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

KK20

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 Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

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

Join the CP Discord Server!

Blizzard

Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

Terv

March 07, 2013, 12:54:49 pm #11 Last Edit: March 07, 2013, 02:48:03 pm by Terv
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

Blizzard

March 07, 2013, 02:34:35 pm #12 Last Edit: March 07, 2013, 02:36:03 pm by Blizzard
Actually that line is correct. There's a line missing after def self.dyn_request.

    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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

finalholylight

I have small problem with this script, my picture will explain:

Blizzard

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 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

KK20

March 27, 2013, 01:21:55 pm #15 Last Edit: March 27, 2013, 01:44:24 pm by KK20
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])

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

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

Join the CP Discord Server!

Blizzard

March 27, 2013, 02:21:12 pm #16 Last Edit: March 27, 2013, 02:22:33 pm by Blizzard
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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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

Heretic86

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

finalholylight

Yes,I can walk over that path myself. Also, I already test with Near Fantastica's path finding, and it walk correctly

Blizzard

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 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


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

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