[Turtle Navigation] Diagonal route or square?

I've been messing with the GPS api recently and I'm wondering if i want my turtle to go to a specific coordinate.

Should i make it go straight to it (diagonal)? or just in a straight line then turn 90° and proceed again in a straight line (making a half square basicly)?

As I feel going diagonal wouldn't be much more effective at best. Since it has to stop to turn every time.

Each operation (turning, moving, etc…) takes time, so the fewer operations you can do the better. Therefore going in a straight line, then another straight line is faster than any other possibility.

Note, as you're moving block-by-block, you need to think in terms of Manhattan distance - so the diagonal and two straight lines are the same distance!

Certainly straight lines are faster so long as the way is clear, but in a crowded environment you may well find that your turtle is more likely to get snagged in the terrain somewhere. It's a bit of a judgement call.

Personally I have my turtles navigate using a route-node system, wherein I provide a list of "points" and specify which ones are safe to travel between. If a turtle wants to get from one point to another, it checks through all the points in between, determines which set of nodes produces the shortest path, and then follows that. This means I can have them navigate through any complex base layout without ever having them bump into walls - it also means that I can code my turtles to go along the diagonal (to minimise the odds of bumping into things), while still avoiding excess turns (by making sure the path between any two given nodes is a straight line whenever possible).

Bomb Bloke, on 21 May 2017 - 05:31 AM said:

Personally I have my turtles navigate using a route-node system, wherein I provide a list of "points" and specify which ones are safe to travel between. If a turtle wants to get from one point to another, it checks through all the points in between, determines which set of nodes produces the shortest path, and then follows that. This means I can have them navigate through any complex base layout without ever having them bump into walls - it also means that I can code my turtles to go along the diagonal (to minimise the odds of bumping into things), while still avoiding excess turns (by making sure the path between any two given nodes is a straight line whenever possible).

I'm interested in how you do this as it would be useful for Hive.

Bomb Bloke, on 21 May 2017 - 05:31 AM said:

Certainly straight lines are faster so long as the way is clear, but in a crowded environment you may well find that your turtle is more likely to get snagged in the terrain somewhere. It's a bit of a judgement call.

Personally I have my turtles navigate using a route-node system, wherein I provide a list of "points" and specify which ones are safe to travel between. If a turtle wants to get from one point to another, it checks through all the points in between, determines which set of nodes produces the shortest path, and then follows that. This means I can have them navigate through any complex base layout without ever having them bump into walls - it also means that I can code my turtles to go along the diagonal (to minimise the odds of bumping into things), while still avoiding excess turns (by making sure the path between any two given nodes is a straight line whenever possible).

Thanks for the info. Sounds very interesting. Altough I know I'm not able to code such complex things just yet. I'll keep it in mind for the future!

Lupus590, on 21 May 2017 - 02:51 PM said:

I'm interested in how you do this as it would be useful for Hive.

Interested right up until you see the mess that is the code, I'll bet.

This maze-solver is probably the most advanced version of my navigation stuff, written for an old competition.

(Unfortunately the guy running it decided to skip out on making a proper maze and then ripped out random chunks of my code, so things didn't go so well there.)

http://www.youtube.com/watch?v=aDpWlOexY-k

If you can watch that without falling asleep, you'll see that whenever the turtle hits a dead end it's able to navigate back to previous intersections in the maze without bumping into walls anymore. Likewise, loops in the maze can't "capture" it; it doesn't need a "simply-connected maze" in order to escape.

Then there're my base-maintainers, such as this one, which are pre-programmed with nodes and so they don't have to waste time spinning around exploring their environment. In each case, pathToNode() is the important function - it has the turtle build the shortest list of connected nodes that leads to that point, and then simply has it follow them. goToNode(), on the other hand, simply bee-lines the target directly.

I've tackled this problem before with my fractal making program (uses the L system algorithm) so if you would like to see my implementation of using degrees and magnitudes to follow a straight line, here it is. It places a block above the turtle to have a visual straight line as well.