Talk:GoTo
- [History↑]
Contents
| Thread title | Replies | Last modified |
|---|---|---|
| Optimum Goto Driver | 1 | 23:11, 16 August 2019 |
Goto code is crucial for goto surfing and melee movement, however the code listed in this page is not optimal, there are cases that all these methods give wired behavior.
I did some numerical analysis on some simplified model of goto driver, and the result indicates some boundary with shape like r = tan(b θ), -π/2 < θ < π/2, 0 < b < 1, where all destinations within this area is best turning with full speed & going with full speed afterwards, and all destination outside this area is best going with full speed from start & turning at the same time. Destinations near the boundary (the margin is narrow, though) is best turning with max speed at first while accelerating at the same time (and reducing turning rate as a result, per robocode physics), being an intermediate of the both extreme.
Edit: As the robot moves, points inside the area should be quickly falling into the boundary region, then being outside of the area. This behavior indicates that for points inside the area, an optimal way is turning with full speed at the start, then starts accelerating, and move with full speed finally. And for points outside, going with full speed at the start is preferred.
The graph shows the relationship between optimal initial turning radius and initial state where d is the distance to destination, θ is the bearing to destination relative to heading. The result is obtained via numerical analysis on a model that ignores velocity changing rules.
I made a goto driver with some approximation of the above result, it does behave much better, but doesn't look optimal as the approximation is rough.
Then I think we may find an optimum goto driver via calculus of variations, any ideas?
A few weeks ago, I began working towards an algorithm for optimal goto movement like you mention, using a calculus-based approach. My first idea was to find the heading/velocity combination that would minimize the distance between the robot and its target destination on the next turn - a simple optimization problem. This doesn't work, however, due to the fact that in Robocode's processing loop, heading changes before velocity. Because of this, the impact that velocity has on the max turn rate on the next turn, then, must be taken into account. I am currently revising my formulas to do so. (The new goal is still to minimize the distance between the robot and the target destination, but effectively looking forward 2 turns in the future, instead of just one.)
Note #1: I am not certain that this method actually minimizes travel time, but "minimizing distance to destination" seems like it should do so implicitly, as long as all factors affecting possible movement options are accounted for in whatever formula is used. The other way to do this that I see would be to devise some algorithm to effectively mathematically generate possible paths to a point, and then minimize travel time. That seems quite... nontrivial, though.
Note #2: My limited testing with the method mentioned above matches your findings above. Max velocity seems to optimal for all but the tightest turns (as one would expect). One thing I have not taken into account in my calculations is reversing. Thus far, for simplicity's sake, I have effectively considered destination points in only one quadrant and velocities between 0 and 8. As I see it, limiting to one quadrant is a nonissue, as the algorithm should not be affected by π/2 rotations. Negative starting velocities, however, will indeed impact the correct solution, so that is definitely something I plan to look into in the future.
Overall, I believe that a calculus-based approach to path generation shows much promise, and could potentially offer a truly optimal solution if done well enough. I rambled a bit here, so feel free to @ me something I have written is unclear. I'll update if/when I make progress with the approach I am currently trying.
