GMS 2 [SOLVED] Trouble With Coding AI Pathfinding With Wormholes/Teleporters

Discussion in 'Advanced Programming Discussion' started by NanoSharkProductions, Jul 19, 2018.

  1. NanoSharkProductions

    NanoSharkProductions Member

    Joined:
    Dec 11, 2017
    Posts:
    11
    I am currently developing a Turn-Based Tactical RPG project with help from SergeantIndie's TBS 101 tutorial on YouTube and have decided to use wormholes in my game to make movement more interesting. However, I am having an issue with implementing/choosing the right algorithm for considering ALL paths that AI units can take to move towards its destination AND choosing the shortest path to get there while considering all wormholes. Before reaching out for help, I have tried a few different coding solutions to solve the problem, but could not find a solid solution. Listed below are the main things I want to accomplish in this AI pathfinding problem.

    1. Enemies starting out at a particular node in the grid can measure its distance from the start node to the goal node using a script I programmed called movement_heuristic(). Movement_heuristic() calculates the G score of the goal from its origin node (which is currently the hero's start position). If the goal cannot be reached (or the heuristic is larger than its movement range) in one turn and there are no wormholes, the AI unit charges towards its destination, but does not reach it and has to wait for its next turn(s).

    2. If the goal node cannot be reached and there is at least 1 pair of wormhole nodes in the map, movement_heuristic() is also run from the origin node to the wormhole node and movement_heuristic() is run again from the wormhole node's paired node to the goal node. The two heuristics are added together. Of the paths in #2 and #1, the lowest distance one is followed. HOWEVER, if there is more than 1 pair of wormhole nodes in the map, that is where I am stuck, especially if there is more than one wormhole node in range of the AI's start node.

    3. The most difficult part is figuring out how to store sequences of wormhole nodes and points (like a hierarchy) and determining when wormholes should stop being considered for pathfinding. The search should stop when ALL paths have been considered and the path with the lowest distance in between them should be grabbed and that's the path that the AI unit should follow.

    Should I come up with a wormhole parenting system like for A*? Should I add a closed list for wormhole nodes that have already been calculated?

    I hope that someone sheds some light on the subject and can help me in determining a solution for the problem because I have been at this for at least 2 weeks now. Thank you all for reading this.

    - NanoSharkProductions.
     
  2. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,864
    Well, A* would be able to figure the shortest path even with teleports / wormholes present. It sees the map as a graph, being a collection of nodes (grid cells) that are connected by edges (valid paths from one grid cell to another, most commonly by virtue of being next to each other). A wormhole connection is simply an edge that connects two nodes that are visually not next to each other. In terms of A* mechanics, it is just another item on the neighbours list. How the nodes are visually rendered has no meaning to its operation, it just runs across the graph to figure the shortest route. The built-in mp_grid commands won't help you here. As their name implies, the graph is expected to be a perfect grid with no extra frills; you'll have to code your own A* which naturally will be somewhat slower (the loops are the killers so they need to be optimized the most).

    Edit - should have expanded that you're needlessly complicating things by running multiple checks. You just need to run a pathfinder once from start to goal, and follow the route it figured out.
     
    Last edited: Jul 20, 2018
  3. NanoSharkProductions

    NanoSharkProductions Member

    Joined:
    Dec 11, 2017
    Posts:
    11
    Thank you for the quick reply.

    What I forgot to mention is that enemies have a normal movement range and a wormhole exit range. Once an enemy exits out a wormhole, their movement range is reset to the wormhole exit range and its new origin for range checking is the exited wormhole. However, a melee attacker's destination is decided by how close it is to a hero. I have a system that calculates the path between where it is currently standing and its preferred destination. But, the destination might be out of range, so its ACTUAL destination backtracks by assigning the destination to its parent until the destination is in the enemy's movement range.

    Also, could you provide a more clear explanation about how I should implement A* and about looping optimizations. Thank you.
     
    Last edited: Jul 20, 2018
  4. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,864
    Oh, the range reset at wormhole exists might complicate things. I suppose when using A* you'd have to reset the range metric at wormhole node so all paths from there will start counting from zero up again. But on the other hand, if you let A* run until it has reached the destination node, it is the shortest path no matter actual movement ranges, and should be followed to reach the destination in least amount of action turns. I've throught the article at redblobgames is a good intro to A* and related pathfinders (it goes through breadth-first, Djikstra and A*). At the end, it links to an implementation guide in C++/C#, but it is worth a read anyway to understand the general logic. I'm sure there's GML-specific implementation guides out there if you google for them.
     
  5. NanoSharkProductions

    NanoSharkProductions Member

    Joined:
    Dec 11, 2017
    Posts:
    11
    I already had a pathfinding system in place for players. When a player wants to move, it calculates the movement range from where it is currently standing and G scores are assigned based on a variation of Djikstra's algorithm. The appropriate path is created from the start position to the node that the cursor is currently hovering over based on parents and G scores. If any wormhole node has a G score greater than 0 and the player clicks on it, that path segment is created and a new movement range is calculated from the other wormhole, for which a new path segment is created. The process repeats until a valid move node is clicked. With that, the player goes through as many wormholes as it wants as long as they are in the current movement/exit range AND they have not already been selected. Implementing the same strategy for AI units is significantly harder because they have different ranges for normal movement and wormhole exit movement. The A* algorithm ignores distant neighbors of nodes that it currently examines if it calculates a path directly from the start node to the goal node. That's a problem for me, though, because a wormhole node might be out of the enemy's way to get to its destination without using a wormhole. But, that wormhole node's paired wormhole is the closest to the destination. Fundamentally adding the paired wormhole node to its wormhole node's neighbor list is a problem on my end, because of the different range resets. Also, there could be more than one wormhole on a map in a single range check. So, that is something to consider.

    My path creation system in my project is a bit different than normal due to the fact that once you enter a wormhole, a path ends and another one begins by exiting out the other wormhole. Every time you either start from your current position or an exited wormhole, a new path segment is created and added to a ds_list called movement_path. Enemies have the same functionality in terms of path creation. If an enemy starts from the current position, it needs to find every wormhole with a G score greater than 0. It picks one from the list and creates a path and adds it to the list. Once it pathfinds from the exited wormhole, if there are no other wormholes in range and the destination cannot be reached, that particular path is listed as a "dead end" and I want to make it to where the pathfinder no longer examines that particular path sequence. All of the solutions I have coded either end up in an infinite loop or hang for a few seconds then move because I used a ds_list_shuffle() script for the wormhole list and reset the list every time an enemy examines a path leading to a dead end.

    Hopefully this sheds some light on the situation and a better understanding of my game can be made.
     
  6. NanoSharkProductions

    NanoSharkProductions Member

    Joined:
    Dec 11, 2017
    Posts:
    11
    I have solved the problem.

    NightFrost suggested that I add each wormhole node to their correspoding wormhole's neighbor list as their visual placement on the map does not change pathfinding's operation. I ran a pathfinder that checks in all directions (Dijkstra's algorithm) from the origin node and once a wormhole node is examined, the paired wormhole is considered next and, from there, the range metric (G score) is reset to 0. The exited wormhole's parent is essentially the entered wormhole and the parent assignment continues as usual. The pathfinder does not stop until the destination has been examined in which the loop terminates.

    To make a melee attacker charge towards the optimal destination, the parent-to-parent (from start to finish) chain is reversed to a child-to-child (finish to start) chain. I reset the parent variable of ALL nodes and keep the child variable of the nodes. I make another loop, which determines the nearest cell to the destination that the enemy is capable of moving to. This considers both normal movement range and wormhole exit range. Before the loop starts, the origin node is stuffed into the variable "nearestNode" Example code of the solution is below:

    Code:
    do {
    
          nearestNode.child.parent = nearestNode;
    
          nearestNode = nearestNode.child;
    
          if (nearestNode == goal) {
                 break;
          }
    
          if (nearestCell.type == "wormhole") {
    
                 //Step from parent to parent based on G score to add path points.
                 create_path(char, nearestCell);
    
                 with (objNode) {
                         parent = noone;
                 }
    
                 //Skip to the wormhole's paired wormhole node.
                 nearestNode = nearestNode.child;
    
                 range = char.wormholeExitRange;
    
    } while (nearestNode.G <= range);
    
    create_path(char, nearestNode);
    
    
    That seemed to fix my issue and I hope wormhole pathfinding can be easier for future users of GameMaker.
     
    Last edited: Aug 11, 2018
    atmobeat and 00.Archer like this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice