3 ms·
I'd discretize it into squares and get all four orientations. You are then looking for a set of directions (forward ,turn left, turn right) where forwards are m
by crb002 8y ago
I'd discretize it into squares and get all four orientations. You are then looking for a set of directions (forward ,turn left, turn right) where forwards are minimized that works on every square in all four orientations.
We have grammars over the alphabet {F,L,R} where "escape" accepts a word. We want the smallest accepted word contained in all grammars (only counting Forwards).
Brute force enumeration works but is exponential.
Faster is taking every place/orientation grammar where the finite state automata is the grid labeled with transitions. Then recursively merge them in pairs like mergesort. The resulting big automata you then want the shortest path to an escape state (only counting Forwards).
- crb002 8y agoSecond optimization I would apply would be quadtrees. Start with huge squares subdivide them after solving at that level down to your specified tollerence.
- crb002 8y agoIf you need even more precision either tiled hexagon automata or subdivide into K instead of four compass orientations. There is also probably some Pressburger arithmetic formulation treating it as vectors in 2D you could whack with an SMT solver? I'd have to sleep on that. Might be easier to code than all the finite state automata merging.
- caf 8y agoThere aren't four (or any finite) number of orientations. You start off facing an arbitrary bearing.
- crb002 8y agoMentioned below. You can increase from 4 orientations to K and use quad trees to drill down distance of steps taken.