[Pokeemerald] Applymovement vs A* Algorithm for Pathfinding

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

​

• 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

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​

• 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

• 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:

Code:

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 http://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 said:

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.

Click to expand...

Doctor Juanjo said:

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.

Click to expand...

FBI said:

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 :)

Click to expand...

Doctor Juanjo said:

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.

Click to expand...