Pathfinding

[gpgekko]

Issue - I think. I have an event that should walk (on a 17x17 map) from 08 x 05 to 08 x014 so I set up the events and set the move script in the movement route for that event:

find_path(8, 14)

How ever - the event does not move. the path is walk able, there is NOTHING blocking its way.

I have this too. However, I found that when I hold the control button (you know, the one that makes the player pass inpassable tiles), the event starts moving...

Seems there is a bug somewhere in the passability checks?

The path I'm trying to send the event along is a 3 tile wide dirt road, completely passable in all directions, the event only has to go in a straight line and the road is completely free of obstacles.

Edit:

Judging by the FPS, it also doesn't seem to process reaching it's destination. If I hold the control key and wait for the event to get to it's destination, it does stop walking but the FPS seems to suggest the script is still running.

I hope you can fix the script, I prefer it above the other pathfinding scripts I found for Ace.

 

[Zeriab]

Sure, but the *vast* majority of the time your algorithms are not random and you state the worst case complexity and, later, state the average (at least, average for a given use case).  I really just wanted to make it clear that the input is what mattered, i.e., a question like "how long does it take to get from one corner to another" can't be answered without context.

I was considering whether to make a comment as it was clearly a case of... for the lack of a better expression teaching by lying.

You know, usually by expressing the world or models less complex than they really are. Later when the simplified world is understood it can more easily be expanded.

Anyway you are quite right except that it hasn't been a vast majority for me, though you know

More than context is needed to answer that. As you know the golden rule of performance is to measure it before starting to do analysis and optimizations and to properly answer the question of how long it takes.

On a side note, I always enjoy your comments when a CS subject comes up.

The feeling is quite mutual as I enjoy yours on CS related matters.

I quite love CS ^^

 

[Venima]

Hey guys. Really sorry for the necropost, however, I've made a few fixes and additions to this pathfinder to give it extra functionality (am I excused?). 

This modified version should work with anything the previous version worked with.

Modifications:

I noticed some of you were complaining about your event not moving, I believe this was because your goal location was impassable. This issue is fixed: Goal location may now be impassable, pathfinder will still reach it.

I also noticed the pathfinder behaves strangely if the event's custom move route is set to repeat. It would repeat the steps of the originally determined path, which is pointless. This is improved: If the move route is set to repeat, the pathfinder will revalidate path each step. You can now specify the x and y to be variables or continuously changing values such as the player's x and y, and it will follow them. (Note, this is a bit more processor heavy, but for repeat only, the normal move route hasn't been modified)

Added parameter: Distance. So I wanted to use the pathfinder for an event to follow the player, but I wanted it to follow up to a certain distance from the player and then stop. By specifying the (optional) distance parameter, you can do just that. This is effectively an alternative to party following, except not limited to the party.

Jet, feel free to change the comments, though I made some additions to explain the modifications and also label the code I've modified.

Modified script: http://pastebin.com/raw.php?i=ctt8RfdK

One final thing with the movement repeat behaviour that I'll mention: When applying your find_path script to your event's custom move route with a distance of say 3, that will continue running until it has reached a distance of 3 from its target (including moving targets), you can then add a random move step after it, and it will move randomly as long as it is within the specified distance from the target. You could use the change frequency moves to set the find_path frequency to highest, and random to normal (it hurries to the target, then wanders slowly).

 

[Jet]

Hello Venima,


My license openly allows modification and redistribution, as long as it's attributed and distributed with the same license.


I appreciate you taking time to make the script better, I do not have as much time to keep up new features and such on all my scripts.


I put a link to your modified version in the first post, but feel free to start your own thread with the script if you plan to make further modifications.

 

[Marcio]

Awesome script! Thank you Jet and Venima!

I have only a slight Problem with the documentation, I can't get the event to move to a position and the player has to wait til the event arrives.

I don't get 100% how to make the wait (and I know it's in the script... sorry, for the slightly dump question ).

Edit: Is it possible to move the followers, too?

I use Victors Follower Script but I think, this is not possible?

 

[Marcio]

Can someone help me out?

I can't get wait til movement is done to work.

 

[Venima]

I can't get the event to move to a position and the player has to wait til the event arrives.

Edit: Is it possible to move the followers, too?

I use Victors Follower Script but I think, this is not possible?

 

In terms of waiting, the normal rules apply. If you set a move route for your event in a separate event which triggers using "Autorun", this will force the player to wait (remember to erase or change the autorunning event's conditions so that it doesn't keep executing. Alternatively, before moving the event, you can set the player's move route to wait indefinitely, then below your "find_path" script command, add a call common event command, in the common event you set the player's move route to blank allowing him to move again. An even better alternative if this works: modify a blank common event to activate by Autorun when a switch is active, and set the switch on before find_path and off again afterwards.

In terms of controlling followers, there shouldn't be any problems with that, just set a move route as normal. See my latest demo here for an example (FormationDemo.zip, you don't have to use the formations function): http://forums.rpgmakerweb.com/index.php?/topic/19053-change-formation-followers/.

 

[Marcio]

Okay I feel stupid now, but I didn't made a scriptcall within the "Moveroute eventer"... I honestly forget about it *lol*

So I just have to make my autorun event (Cutscene) and when I need a pathfinding I flip a swich on to trigger another autorun with the "moveroute" scriptcall for finding x and y coordinates and make it wait til movement is done. Afterwards I flip over the autoswitch a to on, make a new blank page and my 1st Autorun Event (Cutscene) will move accordingly after I flipped the switch?

To be clear: It's not possible to make a Event where I just make a moveroute and make the scriptcall in there and put the wait til movement is done?

Thank you for the answer.

Edit:

I tried it and I feel so stupid *lol*

Just used a normal event and made "set move route" with scriptcall and "wait til end" and bam!

 

[Verilian]

So I'm having an issue in that the event cannot go around the player.  Basically, player walks up to event, then the event walks around the player to the other side, but that doesn't work.  If I approach the event from a direction where I'm not blocking it's path it works fine, but if I'm in its way then it doesn't work.  Anybody know a way to make it work right?

 

[Venima]

Odd, try setting the move to repeat. That will re-find a path per movement. I may need to update a script to detect blocking events, though I thought this was already done.

 

[Marcio]

In terms of controlling followers, there shouldn't be any problems with that, just set a move route as normal. See my latest demo here for an example (FormationDemo.zip, you don't have to use the formations function): http://forums.rpgmakerweb.com/index.php?/topic/19053-change-formation-followers/.

Ok I made a trigger NPC which have normal comments and pathfinding scriptcall within a "Set move Route" for my 7nd actor. My Actor #7 goes to the destination and after it arrives it goes to another destination (no problem here).

After that I gatther my Followers with the Gather Follower Event and after that, if I talk to the same trigger NPC, the pathfinding is weird. It doesn't go to the specified destination, altough it functions every 1st time correctly.

I put a little Demo togheter.

I tried with the updated pathfinder from this post and all 3 alternate scripts you made from the change formation follower you mentioned, but none works.

http://forums.rpgmakerweb.com/index.php?/topic/19053-change-formation-followers/

You have any Idea why this is so?

Pathfinding Test.rar

 

[Venima]

Yes that's because once the path is calculated once, the actual path remains that way. So unless that follower is in the exact same position as last time, it will appear to behave strangely. I don't actually know how to fix this, I've tried to use the path restore functions in RGSS, but they don't seem to do anything.

You can find a way around this by making your move route repeating and using auto-run common events like in the following demo:

Pathfinding Test.zip

I'm sorry I don't have a better solution for this, but I don't know enough about the move route system to fix this bug.

 

[Marcio]

Well at least it's a working Solution!

Thank you ^^

 

[Soveliss]

I'm fairly new to RMVX Ace and I'm attempting to use this script to have a NPC walk out of a building. I am using basic Move Route calls to have the NPC walk in, then the player talks to the NPC and she is supposed to walk out after the player speaks to her (this is where I'm using the script); however, for some reason, despite the fact that I have Walking Animations on and a graphic selected for the NPC, when the event reaches the script call (which is inside a Set Move Route call) instead of walking out the NPC's graphic simply disappears. Does anyone have any idea why this could be?

 

[Venima]

No idea without some screenshots. Would you mind sending me a shot of your event code where it's called, so I know you're using it correctly. Also, what other scripts are you using?

 

[mordor3]

I tested this for my project and it works very well.  I use the XAS hero system so the events are enemies.  I tested this script to control their movement.  It locks onto the player using move routes on the event.  It gives enemies a decent AI pathing.

However, other move routes will not work because this does not move 1 space per input.

find_path($game_player.x, $game_player.y, 0)

If I can control this to only move 1 step toward the player using the path it would work great.

Ideally a move route script would look something like this

find_path($game_player.x, $game_player.y, 0)

find_path($game_player.x, $game_player.y, 0)

find_path($game_player.x, $game_player.y, 0)

find_path($game_player.x, $game_player.y, 0)

find_path($game_player.x, $game_player.y, 0)

find_path($game_player.x, $game_player.y, 0)

wait 75

shoot(80)

se

change graphic

it would chase the player 6 steps in this case and then perform other actions, spell casting, change form, sound effect etc.

-------------------------------------------------------------------------------------------------

I was testing this from Galv's script

move_toward_xy($game_player.x, $game_player.y)

This does move the event (enemy) 1 space toward the player.  However, it lacks the algorith to make a smooth AI pathing.  It's noticable in some situations.

-------------------------------------------------------------------------------------------------

 

[Venima]

The difficulty with this is running the algorithm 6 times is a lot of wasted processing. It would be much better to modify the script to specify how many steps to take. Unfortunately I don't have the time at the moment to do this so I will propose an alternative:

If you can find out how many frames one step of your event is then you can give it a move route with find_path (don't wait for completion), immediately place a wait command of step-time x6 and then a second move route with wait(1) to clear the previous move route. I'm sure with a bit of playing around you can get this to work.

 

[mordor3]

I belive the XAS action battle system changes the requirements for this.

Only the right hand side of events is activated.  Meaning the Event's move routes are the only ones in use.

I do not code very well, but I have been able to succesfully modify a lot of code for specific needs.  This one I have not been able to accomplish yet.

It may not be very optimized, but it would create a strong AI pathing for the game.  I have tested the Iterations at about 15-20 and it seems to reduce any lag.  I do not need this for it's original purpose of moving an object from point A - B, it's being used as an AI pathing system.

I was trying to modify the code to falsely give it the impression it had reached it destination after 1 step or cheating the variables or blocking the move routes after a single move.

The path might need to be recalculated a lot anyway.  It's following a moving object (the player) not a sec location.

The amount of momements is random depending on each mob.  It might move 2 steps and cast or 9.  There are a lot of other options besides movement.

The current problem is once that pathing route is set, it will bypass other commands until it reaches it's destination.

-------------------------------------------------------------------------------------------------------------

I did a few tests which may explain part of the problem also.

When repeat is not checked after the mob reaches the player it accepts additional movements.

find_path($game_player.x, $game_player.y, 0)

shoot(80)

find_path($game_player.x, $game_player.y, 0)

shoot(80)

This will catch up the player and then shoot (projectile: tool #80 on the XAS tool map) it will then chase the player again and then shoot.

When this same sequence is on repeat it will continually follow the player never shooting.  Unless you move into an area that the pathing can not locate, then it will shoot.

 

[mordor3]

I may have found a compromise.  I was testing a few blending techniques with various pathing methods.

I'm testing how the pathing works with a distance set of 3.  At that point the normal commands would take over and it would appear the enemies only use special attacks when they get close to the player.

--------------------------------------------------------------------------------------------------------------------

Current Testing Setup:

find_path($game_player.x, $game_player.y, 3)

move_toward_xy($game_player.x, $game_player.y)

move_toward_xy($game_player.x, $game_player.y)

move_toward_xy($game_player.x, $game_player.y)

move toward player

--------------------------------------------------------------------------------------------------------------------

This hybrid is doing well during testing.  When it cycles through the commands Jet's path finding will direct the enemy toward the player.  When the range becomes less than 3 Gavl's movement takes over and helps force the event toward the player.  (This force is necessary because a non passable projectile is moving toward the enemy which normal movement would try to avoid causing poor pathing).  The final move forward command helps move the enemy into a few locations Galv's script does not handle well such as enemies stacked behind each other.

If you get far away from the enemy, but still in aggro range the Jet pathing will take over again and find a smart AI path back to the player.

--------------------------------------------------------------------------------------------------------------------

From the players perspective it looks fairly smooth

A link to the game (This IS NOT an updated version with the hybrid pathing)

http://forums.rpgmakerweb.com/index.php?/topic/14218-mordor-3/

 

[Venima]

When repeat is not checked after the mob reaches the player it accepts additional movements.

find_path($game_player.x, $game_player.y, 0)

shoot(80)

find_path($game_player.x, $game_player.y, 0)

shoot(80)

When this same sequence is on repeat it will continually follow the player never shooting.  Unless you move into an area that the pathing can not locate, then it will shoot.

That is because you've told the event to shoot once it's on top of the player (distance 0), which it never is. You want the distance to be whatever your event's shoot range is, or maybe 1 less than that.

When it comes to AI, it's always about compromises unless you write it all yourself

When the range becomes less than 3 Gavl's movement takes over and helps force the event toward the player.  (This force is necessary because a non passable projectile is moving toward the enemy which normal movement would try to avoid causing poor pathing).

Non-passable projectile? Now I understand your dilemma. Besides your compromise, the only other fix for this I can think of is some way of identifying the projectile as passable by the pathfinder. Well done for your solution though.