Optimize flood fill during search

[QuentinTorg]

Right now our flood fill pattern always prefers certain cardinal directions when it is deciding where to go at a junction with two equal length paths to the finish. This means if it is faced with the option to go straight or do a pivot turn to check out a new area of the maze, it may prefer the pivot turn every time. Pivot turns are slow compared to going straight, so we could save significant time during our search if our navigator preferred to go straight instead of pivoting.

[ghost]

This is a direct result of the algorithm in the FloodFillPath constructor. The algorithm starts filling from the finish outwards, moving from block to block, "painting" each block with a number that increments each time. Blocks are always enqueued for processing with precedence east > west > north > south, simply because I don't know a particularly better way to choose that precedence. The shortest path is found by tracing from start to finish, always selecting the adjacent block with the lowest painted number.

It's not immediately clear how to get a "straight" precedence, so this will take some thought.

[amiller27]

It shouldn't be too hard to store the last direction that was added to the queue and then take that into account in the order of the group of if statements that starts on line 828

[ghost]

Unfortunately it's a bit harder than that. It's easy to store the last direction, but that information doesn't help us decide whether to go straight or to turn, because at the referenced line we're unaware of how far either choice will be from the finish.

Basically we need to say, any time that going straight or turning will result in the same path length, choose to go straight. But that would result in recursively tracing to the finish from each junction to determine when the path lengths are equal, which is very expensive and sort of defeats the purpose of flood filling as opposed to using a tree.

I wish there was a way to do it during painting. Maybe there is.

[amiller27]

The painting is done before that. We have the minimum path length at that line, stored as distance. We just need to check if there's a wall in the last direction and if the distance stored in the next cell in that direction is distance. This won't guarantee the path with the fewest turns overall, but will guarantee that we go straight instead of turn when the two paths are the same length.

[QuentinTorg]

Edit: Never mind, I think that's exactly what Aaron said in his first comment

New idea, I don't know if it will work. You said that the flood fill path always prefers one direction because of how the program is written. What if we just use a switch statement to make the preferred direction the direction the robot is facing instead of defaulting to east every time?

[QuentinTorg]

Alternatively, we can just remove the issue of pivot turns. We can perform our search so that we're at a speed that we can stop in a distance of half of a cell. Every time we are halfway between cells we should be able to decide which walls are inside of the cell we are entering, and determine if the end of the motion will be continuing to the next cell, doing a swept turn right or left, or stopping in the center of the oncoming cell and pivoting to turn around. I think we are already very close to being capable of this

[ghost]

@amiller27, the distance at that line is in fact not a real distance to the finish. That's the problem. The "distance" is really just the nth item that was dequeued for painting, where n ranges from 0 to the number of boxes in the maze.

Don't get me wrong, I understand what you guys mean. The problem is identifying when two choices will have the same distance, because no two boxes are painted with the same number. Do you consider two choices the same when their "distances" are one apart? Two apart? Three? It's not clear.

What you guys are trying to do will work, but first we need to figure out how to identify two choices as having the same real distance. This is why I'm saying this requires some thought.

I think the solution is to paint real distances from the finish. That might be done by storing box location and distance to the queue, but I'm not sure yet.

[amiller27]

@QuentinTorg I definitely think it's not as big of an issue once we corner instead of pivoting in the search, but I think we should still do it @ryanpitt My bad, I didn't read all of the code above that. I think we could paint real distances by keeping a variable for the layer size (where the layer is the set of cells at the same distance from the finish), and only executing this line when we've dequeued everything from the same layer. Every time we pull from the queue, we decrement layer_size. Every time we add to the queue, we increment next_layer_size. When layer_size hits 0, we replace it with next_layer_size and set next_layer_size to 0. I might have an off-by-one error in there somewhere, but that's the idea

[ghost]

Brilliant! I tried it on paper and it seems to work perfectly. So that change will give us real distances. Then straight precedence during tracing will be easy to do by storing the last enqueued box like you said. Only three extra bytes of memory and a small bit of processing. Not bad!

[ghost]

Resolved by commits 1762900dce86ea0bf828b4af00b47f34abd0be4e and 620e28e300cb313023fa799c7bc23463e57f488f. Created issue #36 for continuous search.