[Pokeemerald] Applymovement vs A* Algorithm for Pathfinding

[Doctor Juanjo]

THIS RESEARCH IS UNDER DEVELOPMENT, SO IS NORMAL THAT IS FULL OF BUGS
​

Hi, I am quite new in the world of disassembly but I am working in some research fields:

This is one of my recent ones: The use of Artificial Intelligence to perform the applymovements automatically and online in-game.
It contains an implementation of a Dijkstra algorithm with informed heuristics (A*) that can make easy some Applimovements in the scripts:
https://github.com/J2M2/pokeemerald/tree/path_planner

Adding an obstacle in the map editor changes the trajectory without change the script!

​

Features:

• A new command for scripting moveobjecttopos(ObjectID, X, Y, facing)
• Shortest path computation between the initial and final position
• The NPC's facing at the end of the movement can be chosen
• Obstacle and field objects avoidance
• Works in terrains with different elevations and bridges
• Easy to customize between Uniform Cost Search (Dijkstra), Greedy Best First Search, and A*
• Easy to execute, just a line of code
• Able to solve mazes

Usage:
Instead of use applymovement OBJECT_ID, sequence_of_movement you can just use moveobjecttopos OBJECT_ID, X, Y, FACING
With:
OBJECT_ID: The ID of the object (same as applymovement)
X and Y: the goal position
FACING: The orientation of the ObjectEvent at the end of the movement (0: down, 1: up, 2: left, 3: right)

It finds the shortest path between the current position of the NPC (or player) and the goal position and is able to cross bridges and use elevations

It also can plan the movement of the player​

Known issues:

• It is new research, so the code can be full of bugs and memory errors (use under this warning!!)
• In open worlds may experiment overflow of memory and collapse (working in solution)
• For long movements (far away from the screen) it is possible that doesn't take into account some minisprites
• Maximum path of 200 steps
• Sometimes report problems with waitstate 0 when two consecutive movements are performed

Contributing:

• Help is needed in order to make the algorithm more robust and efficient in-memory consumption (for a detailed explanation of the code see below)
• Feel free to use and find and report bugs. I think is the best way to contribute.
• I am more experienced with C++, MATLAB, Python language code for search algorithms

Spoiler:

The intuition behind the path-planning given solution is the search algorithm based on Graph Search to find the path between an initial and final node.

The best balance between an optimal solution (that warrant always choose the shortest path) and a greedy solution (that prioritize find the best solution available and don't waste time in to find a better one) is the A* algorithm.

This algorithm can be found here https://github.com/J2M2/pokeemerald/blob/path_planner/src/movement_path_planning.c#L42 and follows the following structure:

function searchPath(object, x, y, facing) /* returns a solution or failure */

    node ← a node with State derived from object and path-cost=0
    frontier ← a priority queue by Path-Cost with node as the only element
    explored ← an empty set

    loop do

    if Empty(frontier) then return failure
        node ← Pop(frontier) /* chooses the lowest-cost node in frontier*/

    if problem.Goal-Test(node.State) then return Solution(node)
        add node.State to explored

    for each action in possible_movements(DOWN, UP, LEFT, RIGHT) do

        if not isMoveNotPossible(node, action)
            child ← Child-Node( node, action)

            if child.State is neither in explored nor frontier then
                f(child) ← cost function for the child  / *See below in the f(node) definition */
                frontier ← Insert(child, frontier, f(child))

            else if child.State is in frontier with higher Path-Cost then
                        replace that frontier node with child

The cost is the core of the optimization. Because it gives the priority to choose a new node or another one.

The A* algorithm evaluates nodes by combining the path cost g (NUMBER OF STEPS) and the estimated cost to the goal h heuristic:
f = g + h,
where h has to be admissible. An admissible heuristic is an underestimation, i.e., it has to be less than the actual cost.

For vanilla Dijkstra (UCS) this h heuristic value is 0 and warrants an optimal solution but could do much more calculations and node evaluation than neccesary.
The Greedy Best First Seach, don't use an accumulated path cost of the node g and just use the heuristic to follow the solution.

The heuristic is usually the linear distance between the goal and the current node, this value is decreasing at the same time we are closer and closer to the goal node.
In Pokemon Emerald diagonal movement is not performed by the NPCs so the euclidean distance is not the best option.

However, the Manhattan (L1) distance could be a better alternative:

See https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html for more information about heuristics.

The constant HEUR_WEIGHT can be modified to change the weight that the heuristic is having, allowing you to use UCS when its value is 0, and Greedy Best-First when the value is much greater than 1. For standard, A* just use 1.

The nodes are defined in https://github.com/J2M2/pokeemerald/blob/path_planner/include/movement_path_planning.h#L37 and contain:

state: integer to represent the position of the node in the matrix (flatten into 1D) which use to do comparisons.
coords: coordinates x,y.
cost: integer, cost so far of the node
elevation: integer, current elevation (z coordinate)
path: an array of movements, the path so far until the node.


The https://github.com/J2M2/pokeemerald/blob/path_planner/include/movement_path_planning.h also contains some auxiliary functions to use the priority queue, the set, and the heuristic.

 

[wally-217]

Would this work if the destination was updated dynamically? I.e. An overworld Pokémon chasing a player (à la the wild area), where the player would be changing postion as the NPC navigates.

 

[Doctor Juanjo]

Would this work if the destination was updated dynamically? I.e. An overworld Pokémon chasing a player (à la the wild area), where the player would be changing position as the NPC navigates.

Well, at the moment the system first plans offline (i.e. plans the route at the beginning of the movement) and then executes it (like an applymovement). It could be possible to get the position of the player and make a mapscript that is always moving the minisprite to that square (and play with some options like in follow me). It could be an interesting idea to work with. Although at the moment I am more concerned about solving more the efficiency of the code and the memory usage.

About dynamic changes, when calling the command it takes the current information of the map elements, that is to say, if the NPCs have moved, the code will notice it. However, if during the movement of the overworld something changed (a mini blocks the route that has already been planned during execution) it might not take it into account.

 

[wally-217]

Well, at the moment the system first plans offline (i.e. plans the route at the beginning of the movement) and then executes it (like an applymovement). It could be possible to get the position of the player and make a mapscript that is always moving the minisprite to that square (and play with some options like in follow me). It could be an interesting idea to work with. Although at the moment I am more concerned about solving more the efficiency of the code and the memory usage.

About dynamic changes, when calling the command it takes the current information of the map elements, that is to say, if the NPCs have moved, the code will notice it. However, if during the movement of the overworld something changed (a mini blocks the route that has already been planned during execution) it might not take it into account.

That's amazing. This is actually incredibly useful, especially for open-world stuffs. Thank you!

 

[Blah]

I had used a similar system in a dexnav implementation to determine if the player had a path to the hidden Pokemon. What I found is that, when a path doesn't exist, this causes noticeable FPS lag -- especially if you're evaluating a path frequently (as suggested with dynamic changes). However, when used in a scripted environment (where you know a path exists), this is very useful.

For dynamically evaluating paths, you can run this in a task. Then evaluate until g = C, where C is a small constant. What that would do is cut the processing time and move the object closer to it's target without needing to evaluate the complete path. Again, this is if you know a path exists. If a Path doesn't exist, depending on C, this would cause your NPC to strafe back and forth like a maniac :)

 

[Doctor Juanjo]

I had used a similar system in a dexnav implementation to determine if the player had a path to the hidden Pokemon. What I found is that, when a path doesn't exist, this causes noticeable FPS lag -- especially if you're evaluating a path frequently (as suggested with dynamic changes). However, when used in a scripted environment (where you know a path exists), this is very useful.

For dynamically evaluating paths, you can run this in a task. Then evaluate until g = C, where C is a small constant. What that would do is cut the processing time and move the object closer to its target without needing to evaluate the complete path. Again, this is if you know a path exists. If a path doesn't exist, depending on C, this would cause your NPC to strafe back and forth like a maniac :)

Well the implementation of the A* algorithm just returns a FALSE in case no path is found (it is a finite process) and in this case, the NPC doesn't move and the script continues. However, in really big maps the algorithm could take too much time to realize that there is no feasible path and this can generate that the screen freezes for a few seconds (or even more time) making weirds noises, and then continue the code normally. It won't move weirdly if there is no solution.

 

[Blah]

Well the implementation of the A* algorithm just returns a FALSE in case no path is found (it is a finite process) and in this case, the NPC doesn't move and the script continues. However, in really big maps the algorithm could take too much time to realize that there is no feasible path and this can generate that the screen freezes for a few seconds (or even more time) making weirds noises, and then continue the code normally. It won't move weirdly if there is no solution.

You misunderstood. The suggestions above were ideas of how to avoid the few seconds of lag and their drawbacks, not about the current implementation.