Author Topic: [XP] Advanced Pathfinding  (Read 21687 times)

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
[XP] Advanced Pathfinding
« on: May 30, 2011, 10:00:31 PM »
Advanced Pathfinding
Authors: ForeverZer0
Version: 1.1
Type: Autonomous Character Movement
Key Term: Custom Movement System

Introduction

This is an advanced an highly intelligent pathfinding system. It allows for the user to either through script or script call quickly and easily have events or the game player automatically walk a path to a given set of coordinates. The system is smart enough to quickly find paths through relatively complex areas, and adjust on the fly for any obstacle that moves to block its path. I used the A* algorithm, basic search algorithm used often for robotics. More on this algorithm can be read about here: A* Search Algorithm

Features

  • Fast and intelligent pathfinding
  • Easy to use script calls
  • Optional "range" parameter can have character find alternate locations if the preferred one is blocked and they are within the given range.
  • Optional callbacks can be given to have something execute if when the character reaches its goal, or when it fails to do so.

Screenshots

Can quickly and easily navigate a maps like these, lag-free:
(click to show/hide)
(click to show/hide)

Demo

Demo Link

Script

Here's the script.
(click to show/hide)

Instructions

Place script below default scripts and above "Main".
Further instructions are within the script and demo.

Compatibility

Highly compatible. Only issue may be with other custom movement scripts.

Credits and Thanks

  • ForeverZer0, for the script
  • Special thanks to Jragyn for help making the big maze for the demo and help testing.
  • Credit goes to the Peter Hart, Nils Nilsson and Bertram Raphael for the original search algorithm that was implemented

Author's Notes

Please report any bugs/issues you may encounter so they can be resolved.
Enjoy!end
 
« Last Edit: February 02, 2012, 04:22:20 AM by ForeverZer0 »
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

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] Advanced Pathfinding
« Reply #1 on: May 30, 2011, 10:05:55 PM »
You're an ass. >:U I seriously was going to create this using that same algorithm.

Nice job! :)

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #2 on: May 30, 2011, 10:07:55 PM »
Its the least complicated I could find. There are some straight-up confusing ones out there...
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19917
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Advanced Pathfinding
« Reply #3 on: May 30, 2011, 11:21:55 PM »
I beat you all to it. :V: *points to Blizz-ABS*
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 ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #4 on: May 30, 2011, 11:24:35 PM »
Yes, I noticed that. :P

Its still nice to have a system not dependent on another for those who don't use Blizz-ABS.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19917
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Advanced Pathfinding
« Reply #5 on: May 30, 2011, 11:32:51 PM »
Actually it shouldn't be very much dependent on Blizz-ABS. The only part is the interpretation of the movement commands.
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 Vexus

  • Ethereal Devastator
  • ****
  • Posts: 365
  • LV: 9
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #6 on: February 01, 2012, 08:23:32 PM »
Sorry for the kind of necro post but I getting an error with this script when I make a set move route event that walks near the edge and tries to walk again (Which in theory it should just make the event stay in the same spot).

The error is:

Line 469

Undefined method 'failure proc' for nil:NilClass

Now this error I don't understand why it's happening as I'm not using this script on this particular event (Testing some ways to do some puzzles into the map with move rocks).

So if you could reply with a way to fix it it would be great else I'll probably have to switch to something else sadly. (This one is currently the best one I found when dealing with fps drop)
Current Project/s:

Offline Poe

  • Awakened Visionist
  • **
  • Posts: 55
  • LV: 2
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #7 on: February 01, 2012, 10:23:47 PM »
it's because you haven't set a failure proc for your event, yet the script is expecting there to be one because you haven't turned on "ignore if can't move" in the custom route window. turning this on will fix the problem.

Offline Vexus

  • Ethereal Devastator
  • ****
  • Posts: 365
  • LV: 9
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #8 on: February 02, 2012, 12:07:26 AM »
But I don't want it to pass through unpassable tiles.

Also when I tried making the part of the failure only it was keeping on giving me errors.

Still I can't understand why I'm having the error when I'm not even calling the script.
Current Project/s:

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #9 on: February 02, 2012, 12:11:31 AM »
There is a little bug I need to fix. Its pretty simple, so I'll fix it in a bit and re-upload.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Offline Vexus

  • Ethereal Devastator
  • ****
  • Posts: 365
  • LV: 9
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #10 on: February 02, 2012, 12:24:23 AM »
Great thanks :)
Current Project/s:

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #11 on: February 02, 2012, 04:22:41 AM »
Fixed.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Offline Poe

  • Awakened Visionist
  • **
  • Posts: 55
  • LV: 2
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #12 on: February 02, 2012, 11:51:57 AM »
But I don't want it to pass through unpassable tiles.
just to be clear on this, "ignore if can't move" will make it skip movement that would go through unpassable tiles, it doesn't make your event pass through them.


i see the slight delay in starting custom movement is gone now too. might i ask what the bug was?

Offline Vexus

  • Ethereal Devastator
  • ****
  • Posts: 365
  • LV: 9
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #13 on: February 02, 2012, 04:01:30 PM »
Thanks it worked.
Current Project/s:

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #14 on: February 03, 2012, 07:36:16 AM »
I just fixed a condition, the same one that mad.array mentioned in his edit to the script. I had made a "else" statement, when it should have been an "elsif" statement when determining if the failure proc should execute.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Offline Vexus

  • Ethereal Devastator
  • ****
  • Posts: 365
  • LV: 9
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #15 on: March 09, 2012, 04:24:00 AM »
Hi again.

I'm not sure if it's a problem on my end but I'm trying to make your script working with your event range condition but am getting an error.

I'm making events that will chase your player when they are x range away and it works and when the event comes near the battle starts. Now obviously after the fight the event has to disappear no? so I ticked the can escape button and put an erase event in both win or escape.

I tried it only with escape but probably the same error would be given if I won.

The error is:

 'Path Finding' line 178: SystemStackError occurred.
stack level too deep.

Does not happen often but it happened twice now.

Any idea why?

Thanks.
Current Project/s:

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #16 on: March 09, 2012, 04:56:34 AM »
I'm not really sure why that would happen. Those errors are thrown when a method ends up calling itself, either directly or indirectly through other methods. I don't really see how erasing the event would cause that, since all erasing really does is creates a blank new page of the event and sets it as the current page for the event.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19917
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: [XP] Advanced Pathfinding
« Reply #17 on: March 09, 2012, 09:19:20 AM »
It's possible that you did a mistake in your script where you check tiles that have already been checked earlier. If a path could not be found (e.g. the target tile is cut off from the start tiles completely), then an infinite loop would happen which could cause this.
Another thing would be that RGSS does not support recursion. If you call a function from within itself, (YO DAWG style) even if it has not been called immediately, then this can happen as well. Your path finder should not calculate the path recursively. You have to implement it using a loop.
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 Vexus

  • Ethereal Devastator
  • ****
  • Posts: 365
  • LV: 9
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #18 on: March 09, 2012, 01:49:02 PM »
This is what I placed in the event:



The pathfind shouldn't loop as I made it go back to position if I manage to outrun the monster.

Strangely enough I tried several scripts for enemies behaviours but using this as method is the least on lagging the game.

Ps. would having a big map (240x200) affect the event's pathfinding? I get several fps issues when an event uses pathfinding to go in a location and the only solution I have is adding like 400 wait after the pathfind in the event (Same for this event even if the event has to go back 4 tiles only the fps goes down to 20 from 40).
Current Project/s:

Offline ForeverZer0

  • CP's Pedophile
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3248
  • LV: 294
  • Gender: Male
  • Remember you are unique, just like everyone else.
    • View Profile
Re: [XP] Advanced Pathfinding
« Reply #19 on: March 10, 2012, 08:39:54 PM »
I double-checked, and I cannot for the life of me see anywhere in the script that would cause recursion.

I factored in the path being blocked during the movement, but after it was already calculated, and set a max number of tries it is allowed to do it. The "recalculating" method basically just clears the current data and restarts the whole process from the current location, even calling the same method. I know that it can successfully recalculate (see pig map in demo), so that should not be it, otherwise it would not work at all, it would fail in the first retry.

I imagine the reason for your lag is in the event above, the pathfind call is being made every frame that the event is on the screen and not within 4 tiles of the player. Calculating a path is not a simple call, and not meant to be called every frame.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.