ICFP /
Problem Analysis
A page for problem analysis.
I think at first glance we need
- track2trace trackfile[.TRK] (the optimizer)
- outputs: tracefile.TRC (the trace)
- outputs: trackfile.TRR (track plus resulting trace)
- track2img trackfile[.TRK] (tool for visualization, speed represented by color)
- outputs: trackfile.img (which format, should be compressed, jpg?)
- img2track image[.TIF] (tool to use a graphic software as track designer)
- (maybe we don't need this, there should be a PNG2TRK? somewhere)
- input: which format? must be lossless
- ...
I think we should vectorize both sides of track (inner and outer). Then we can have position on the track described by two parameters:
t - from 0 to 1, the position along track with 0 being start, and 1 being finish s - from 0 to 1, the position across the track with 0 being inner border and 1 being outer borderThen we can recognize turns with this logic:
if for corresponding dt the path of inner border is smaller then outer one, the it is left turn if for corresponding dt the path of inner border is biger then outer one, the it is right turn otherwise it is straight line.The we can produce optimal path (something that takes turns in account) and then try to produce optimal control command to follow that path.
-- BurtonRadons
But the problem doesn't seem easy: it is 2-parametric optimization problem since we have to minimize path and maximize velocity in order to minimize time. Comments? -- NicTiger?
Burton, I think your solution may lead to local minima (is it right, minimum -> minima?) obscuring the real minimum. If we're doing this kind of derivative process we should do it in another time to drop the local minima.
-- DanielYokomiso?
I looked through all maps. and my idea doesn't apply to every map. I will concentrate on doing optimal path for maps without obstacles, and someone should work out conception for pathfinding algorithms. Comments? -- NicTiger?
I worked out another solution. Instead of real pathfinding (which is rather difficult) we can manually modify map to remove obstacles from the road. This will make some initial roads not-passable so it should be edited with caution. Do you realize idea? Then we have 'alreday solved problem' -- NicTiger?
How can this work out? We're supposed to give them the commands they'll run in their maps. We can change the maps. -- DanielYokomiso?
alternative strategy
I suggested a totally different strategy but Burton didn't want to discuss it:
- manual hinting of path (doesn't take long, maybe 3-5 alternatives)
- rubber-banding (some call this path straightening, shortening)
- splining/bezier to minimize direction changes
- random genetic optimization
Hmmm, from the top of my head I think that manually calculating the path will take longer than 72 hours. If we had equations describing the geometry of the maps then we could calculate them faster.
-- DanielYokomiso?
- No, not manually calculated paths. Good God! Just adding enough hint points (perhaps 5-20) so that the path needn't be searched but constructed unambiguously more or less from straight lines. You can do this in a few minutes per track. -- HelmutLeitner
YAAS (yet another alternative strategy)
As the straight line is the minimal distance between any two points we just need to find the correct jacobian transform to straighten the maps, marking along the field corresponding to the turns needed (kind of gravity) and solve it using classical physics. I think this may be possible, so I'll try to sort that out with a friend of mine (a real physicist, not a dropt-out like me). If we had the equations describing the geometry of the map it would be simpler, but as we only had the sets of points it may not be feasible.
-- DanielYokomiso?
yet some (useless?) ideas
there are 2 usual ways to pass a turn: to the outer side, then turn early, or forward then turn late. the latter one though probably easier to implement, has a danger of not being able to break early enough. this could be corrected by backtraking? Please add any thoughts.if there is a way to eliminate all track prts one doesn't want to visit, it may make sense to assign every tile a "quality" which would be its (minimal) distance from the border. looking at this "quality" of adjacent tiles may give a hint of whether to turn left or right. preferance to going forward may be given. this may be complete nosense, i don't know.
isn't vectorization quite a painful thing which always gets wrong?
-- IlyaMinkov?
Path curve Optimization strategy
I vectorize borders (inner and outer) supposing that road area doesnot contain obstacles and is counter-clockwise passed. Then I take mean line as the 0-th approximation and iteratevly straighten this curve thus minimizing path lenght. One thing to do is to make final point "free", because when we finishing it doesn't matter at what point we cross finish line, but this can dramatically change finishing path. We should also parametrize average speed when turning around the corner as the function of R and take it into account (on the last step we can modify optimal curve).
-- Nic Tiger