NanoSharkGames
Member
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.
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.