I'm the creator of an autonomous bot referred to as SwarmBot for Minecraft. One of SwarmBot's core features is its parkouring ability. Despite being relatively effective, there are instances where the current algorithm (block-discretized A*) fails to ensure that the bot operates as intended. For certain complex jumps, such as the neo-jump that is shown below, the bot lacks the required finesse to pull off.
Neo jumps pose a unique hurdle as the jumping sequence does not entail the bot looking towards the next target block. Instead, it requires the bot to jump around a block by facing away from the next intended block before changing directions.
Now, I am trying another approach—discretizing based on game ticks, with consequent nodes based on the player-pressed keys. The image below shows A* without a heuristic trying to find a path over a course where the bot can turn/jump when it is on the ground. Each green circle is a block, and each black pixel is an expanded node.
Clearly, this is not feasible. Turns are tried at lowest g-scores (since there is no heuristic), and I cannot think of a good consistent & admissible heuristic to try turning furthest down the chain. Perhaps I do not need a consistent nor admissible heuristic. I am only trying to find good paths, not optimal ones. I have also tried negative costs for certain nodes instead of a heuristic, which seems better, but this could cause issues as I could get a path of infinite length if conditions are just right.
What are some recommendations for this problem? It looks like I want to do something like is demonstrated in this Udacity video on A* for their cars, but I have a hard time finding why theirs looks much more like a sparse tree than mine. Perhaps they are using something more akin to Rapidly exploring random tree. Is this a path that makes sense to go down? Would you recommend any other papers?
