Derek says the search strategy is "Flood Fill", but I looked and could only find that used in reference to flooding algorithms -- like for bucket fill in paint programs.
On the other hand, I thought what he describes sounds a lot like A-star. Does anyone know what algorithm is used (if, indeed, as he says, everyone's converged on using the same algorithm). Is it straight A-star, some sort of incremental A-star, or something like D-star-lite (which is apparently quite popular for path planning)?
I don't think there's any heuristic involved that would make it A-star other than having an initial guess of Manhattan distance. The bot also does not consider all active paths; it only considers the shortest possible from the current state. This makes it not A* since A* considers all open.
To me, this looks like running multiple iterations of Dijkstra's. You start with Manhattan distance between nodes and finish. As you go through the maze, you update the dynamics of the current node, run dijkstra's, go to shortest path from here.
This also sounds a bit like IDA*, where you are also updating the heuristic as you go, but without the iterative deepening part.
Many of us have tried A* but because the maze is so "small" (16x16 or 32x32), the "just solve it every time" using Dijkstra's or a flood fill or similar algorithm wins out.
In particular, in A*, the "to be explored" queue has to be kept sorted. This sorting dominates the compute time.
For example, using the "flood fill" method on an 8-bit processor, depending on the state of the maze, it took less than 3milliseconds (hand optimized assembly) to solve a maze. On a Cortex M4, with decently thought through maze representation, but not optimized beyond that, it takes under 1.5milliseconds. This is in the "don't need to bother" category.
What we have done is extended it to be time based rather than distance based i.e. we take into account the motion parameters - acceleration, maximum speed on the straight and through different turns, distance and use that together to generate a cost table and then use the cost table to generate the fastest path.
This is so cool! I'd love to get into it! Many thanks for the thoughtful reply!
Question; with A*, I assumed the issue was that you needed to backtrack to a promising node which could be very far from current position. But that is based on the assumption that A* is rooted in the start of the maze. The way you described this makes the backtracking seem like a non issue. I assume it is because you were changing the root to be the current node each time. Is this correct?
On the other hand, I thought what he describes sounds a lot like A-star. Does anyone know what algorithm is used (if, indeed, as he says, everyone's converged on using the same algorithm). Is it straight A-star, some sort of incremental A-star, or something like D-star-lite (which is apparently quite popular for path planning)?