Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create function to calculate fastest path #30

Open
QuentinTorg opened this issue Mar 13, 2016 · 1 comment
Open

Create function to calculate fastest path #30

QuentinTorg opened this issue Mar 13, 2016 · 1 comment
Labels

Comments

@QuentinTorg
Copy link
Collaborator

Right now our flood fill during search only calculates the shortest path from start to finish. This works well during search to find a potential path to the finish, but this is not ideal for chaos mode, as the shortest path isn't always the fastest.

After the search mode is done finding one of the shortest paths, we should run calculation to make sure that it is also the fastest path assuming that all unknown cells have no walls. If the shortest path is also found to be faster than traveling through empty space, then the robot does not need to search through those cells because there is no chance for them to provide a faster route.

Calculating the fastest path will require navigator to create the shortest path, and then ask the driver how long each of the path will take. The navigator will continue to request how long the next shortest path will take until it runs out of paths to check. The shortest possibility will then be used as the path for the speed run.

Alternatively, if calculating longest paths takes too long, the navigator could stop requesting path durations when the pathLength/maxLinearVelocity results in a longer time than the fastest path that has been calculated so far. This says that if the robot were to travel in a straight line at top velocity through the designated number of cells, then it would still take longer than if it would have just taken the fastest path that has been calculated so far.

We will probably need to add functions to motion.cpp that return how long a move is projected to take given a set of input parameters. The driver can request the duration for each move of a path from motion.cpp, and then pass it back to the Navigator

@ghost
Copy link

ghost commented Apr 6, 2016

This is probably an issue that won't be solved before competition. However:

Solution is for our robot to simulate itself. :-) Make a new Driver that inherits from the existing one, swapping out each call to motion_x() for motion_x_time() and incrementing a simulation time variable with the result. After the simulation is finished, just read the time variable to see how long it took. This approach makes motion decision logic completely independent from time calculation, so that we might chain together very different movements in the robot driver without invalidating time calculation (and then having to rewrite it). Also makes time calculation dead simple, given we already have the motion_x_time() functions. And one of my favorite parts is that it makes time calculation for move(Compass8 dir, int distance) no different than for move(Path<x, y> path), makes transitions between moving and not moving irrelevant, and so on.

Some code in the robot driver will have to be pulled out into additional methods (to be overridden) for the inheritance mechanism to work.

@ghost ghost added the feature label Jan 13, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant