Add new path finding command 2001

[ell1e]

This adds a new path finding command with initial code by @MackValentine that I fixed up, and @jetrotal helping out coordinating the whole thing. It's based on the new CheckWay command added in #3120 and #3130 and can be used via event command 2001. It has a few special options which are documented in the doc comment that allow ignoring other events in the pathing (they won't be ignored in the actual collision!). The command is intended to both work for a use case where it's used once and then sets a movement route that is just left to execute, as you would in an autorun event, and for a use case where it's used repeatedly in a parallel event to continuously update the route to a moving target.

Behavior quirks: The current algorithm is a breadth first search, so it's not full A yet. I might update it to an A later if I get around to that, for now it seemed more relevant to get it to work properly with all the options people may want to use. It uses a search cutoff to avoid huge lag even when used constantly in parallel events by multiple moving things. Whenever a target is too far away to be safely located within that cutoff the command will set a guessed, approximate route. This means if the target is too far away the search might get lost and route into wrong sections of the map, this isn't a bug.

Another edit/additional note: I should be available also in the longer term if something with this code breaks to look into it.

[ell1e]

It seems like Debian's presumably old g++ doesn't like the exact way the hash function looks like. I suppose way way to fix it would be to no longer nest it inside the SearchNode definition, but for clarity reasons I actually like that layout. I wonder if there's a different way to appease it? I'm not quite sure I fully understand its error message either. If any C++ expert knows how to get it to work while still keeping the hash function inside the SearchNode struct, lemme know!

[ell1e]

Converting to draft for now since there seems to be a path finding bug remaining where the path isn't found when it should be. jetrotal is helping me debug, should hopefully have a fix in a day or two.

[ell1e]

I suppose way way to fix it would be to no longer nest it inside the SearchNode definition

Nope, didn't fix it. I'm actually clueless why the Debian 10 g++ is unhappy then. If anyone knows, happy for pointers.

[jetrotal]

@Ghabry Since you commented soon you'll have some time to check this one... This one is near completion, only two extra things:

• First one is the Debian compatibility with Search Node.

• Second is related to lag in my end when multiple events use Path Finding. Adding if (!event-IsMoving()) return false; right after event is defined helped me, But Ellie commented about extra issues that would cause:

[ell1e]

Regarding lag, you could alternatively for example add a sleep/wait into your parallel event to not run the path finding every frame. Of course that means sometimes it'll set the route with a slight delay but it shouldn't be too bad. (And it would then still react to doors, albeit also with sometimes a delay.)

As for Debian, the main reason I haven't done anything about it yet is that I'm simply clueless so far what even the problem is. I tried multiple variants to specify the set hash function, debian 10's g++ doesn't like any of them. I'm really not sure why it doesn't like them, the error suggests a wrong type or wrong function signature for the hash function to me, but I can't really figure out why it claims that. Maybe it's a compiler bug? I'm not sure how to address it.

[ell1e]

For what it's worth, @jetrotal suggested some behavioral changes that could make this more intuitive to use and less performance intensive, and there were some pretty good ideas that I still have to test out. But the plan is that I test with the actual 2K3 editor first and compare how other movement route commands behave. Once I got that all checked out and adjusted, I'll undraft this again. (I'm assuming it's better to figure this out now before merging, so that people don't start to use it already and then the behavior suddenly unnecessarily changes with a later update.)

However, there shouldn't be any massive changes upcoming anymore, so if anyone wants to have an initial look at the overall code quality now wouldn't be a bad time.

[jetrotal]

Hi Ellie, thanks for working and improving this 🙏 Reviewing updates is a bit slow right now, since we have a lot of critical stuff on the next version checklist: https://github.com/EasyRPG/Player/milestone/26

But, I'd say your pr is looking good, and I'm willing to keep testing it while its being updated

tnx again!

[Ghabry]

Hey. Please don't feel discouraged when their is no feedback for a while.

We are close to 0.8.1 release and want to get most of the stuff sorted out first before I look at the "lower priority" stuff like your new features.

I like this new command but right now cannot look more at it, sorry.

[ell1e]

No problem, no need to rush. I might also be busy for the next 3-4 weeks or so, so the final changes might also take me a bit. I won't be going anywhere if this still takes a bit, no worries.

[ell1e]

After some discussion I propose a split into two separate commands:

"Smart Move Route" (2001):

/* This is the "Smart Move Route" command:
 * Like "Set Move Route", this command sets a longer route
 * of all the steps necessary to a possibly farther off target.
 * The route is computed to smartly go around any obstacles.
 * This command is best used in "Autorun" blocking events, e.g.
 * in situations where an event or character should be sent on
 * their way with a single command. Don't use it every frame in a
 * "parallel" event because it uses a higher search depth and will
 * cause extreme lag if used so often, use "Smart Step Toward" for
 * parallel events instead.
 *
 * Event command parameters are as follows:
 *
 * Parameter 0, 1: Passed to ValueOrVariable() to get the moving event's ID.
 *
 * Parameter 2, 3: Passed to ValueOrVariable() to get the target X coord.
 *
 * Parameter 4, 5: Passed to ValueOrVariable() to get the target Y coord.
 *
 * Parameter string: Allows free form options, see generic
 * CommandSmartMoveRoute() function prototype for full list.

and this one:

"Smart Step Toward" (2002):

/* This is the "Smart Step Toward" command:
 * Unlike "Set Move Route" that always applies even if the event or
 * character is currently between two tiles and moving, "Smart Step Toward"
 * tries to be economical and doesn't change anything if the event is
 * currently moving, to avoid expensive comptuations.
 * Otherwise, it sets a new one-step move route, computed to smartly move
 * one tile toward a given target. Because of it's economical behavior,
 * this command is useful for "Parallel" event use in every frame to
 * track a moving target continuously.
 * Event command parameters are as follows:
 *
 * Parameter 0, 1: Passed to ValueOrVariable() to get the moving event's ID.
 *
 * Parameter 2, 3: Passed to ValueOrVariable() to get the target X coord.
 *
 * Parameter 4, 5: Passed to ValueOrVariable() to get the target Y coord.
 *
 * Parameter string: Allows free form options, see generic
 * CommandSmartMoveRoute() function prototype for full list.

[ell1e]

Since I saw this pull request mentioned elsewhere, I'm still interested in helping out with getting it across the finish line once there's a good opportunity. It's mostly a draft since I'm hoping for more input.