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

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19930
  • LV: 642
  • 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.23
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 protected by the following license:
Quote
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.

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

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

  • Blizzard

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: January 02, 2017, 07:28:27 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: 19930
  • LV: 642
  • 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: 3045
  • LV: 372
  • Gender: Male
  • Bringer of Salt
    • 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!


NNID: KK20-CP
Discord: KK20 Tyler#8901
Join the CP Discord Server

Offline Ryex

  • Arctic Bird of Programming
  • Global Moderator
  • Chaos Ultimate
  • ****
  • Posts: 5131
  • LV: 197
  • Gender: Male
  • 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: 1511
  • 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: 19930
  • LV: 642
  • 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: 6585
  • 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: 19930
  • LV: 642
  • 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: 3045
  • LV: 372
  • Gender: Male
  • Bringer of Salt
    • 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!


NNID: KK20-CP
Discord: KK20 Tyler#8901
Join the CP Discord Server

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19930
  • LV: 642
  • 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: 19930
  • LV: 642
  • 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: 77
  • 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: 19930
  • LV: 642
  • 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: 3045
  • LV: 372
  • Gender: Male
  • Bringer of Salt
    • 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!


NNID: KK20-CP
Discord: KK20 Tyler#8901
Join the CP Discord Server

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19930
  • LV: 642
  • 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: 741
  • LV: 29
    • 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: 77
  • 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: 19930
  • LV: 642
  • 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.