Pathfinder

[manglemix]

Historically, we have always just done A* Pathfinding since there are many resources about it. Boiling it down, we just need a pathfinding algorithm that only needs to work on a discrete grid of safe and unsafe cells that can easily be modified to add limitations on the specific kinds of paths that the robot can take. For example, if the robot is facing forwards, it cannot take a path directly to the right of it without first turning, and the time taken for the turn must be included in the calculations.

The pathfinder does not need to consider the radius of the robot. If the cell is unoccupied, then it is safe for the robot to be there. The pathfinder should not return a new vector. It should be provided a vector to append to. How exactly the pathfinder receives the safe and unsafe cells is up for debate. It could be provided the whole map as a slice or some other representation, or it could be provided a closure that can determine if a given position is safe.

[manglemix]

There was one minor mistake where a successor was still considered even if it was already in the parents map. There were also some coordinate space confusion (y axis is the vertical axis), and step_size can be negative to accommodate for mirrored arenas, however that last fact was not well expressed to you so that's fine. We may want to come up with a better way for the pathfinding library to allow for arenas that may be transformed in different ways. Currently, the decimate portion of the pathfinder is too lax, probably because the obstacles have not been expanded yet. After all, the pathfinder is currently provided with a gradient map instead of an obstacle map, so paths hug obstacles, which will allow the decimator to see shorter paths when they are not actually safe. A CPU approach would be to iterate over the gradient map and add each point with a gradient above the threshold to a quadmap and then querying the quadmap. However, this would force the robot to always have a square profile that is aligned with the map, but it should be efficient. The GPU approach is still being worked on by troy, and it would be much more flexible.