Turtle Movement Routine - ComputerCraft Forums (archive)

BlankWolf #1

BlankWolf's profile picture

51 posts

Posted 01 August 2013 - 03:36 AM

Hello every one.

I have a 2 dimensional table wich saves all coordinates for (in that case) a circle with Ø5.

Spoiler


-3 : -1
-3 : 0
-3 : 1
-2 : -2
-2 : -1
-2 : 0
-2 : 1
-2 : 2
-1 : -3
-1 : -2
-1 : -1
-1 : 0
-1 : 1
-1 : 2
-1 : 3
0 : -3
0 : -2
0 : -1
0 : 0
0 : 1
0 : 2
0 : 3
1 : -3
1 : -2
1 : -1
1 : 0
1 : 1
1 : 2
1 : 3
2 : -2
2 : -1
2 : 0
2 : 1
2 : 2
3 : -1
3 : 0
3 : 1

I can't get a good solution for a turtle movement routine, to pass each coordiante with less fuelcost as possibile.

conditions:

the turtle will stay in the center (0:0)
I don't want that the turtle move outside the coordiantes
the coordinates can be from a square to
it must also works for a bigger object like:

circle with Ø21

Spoiler


-10 : -3
-10 : -2
-10 : -1
-10 : 0
-10 : 1
-10 : 2
-10 : 3
-9 : -5
-9 : -4
-9 : -3
-9 : -2
-9 : -1
-9 : 0
-9 : 1
-9 : 2
-9 : 3
-9 : 4
-9 : 5
-8 : -6
-8 : -5
-8 : -4
-8 : -3
-8 : -2
-8 : -1
-8 : 0
-8 : 1
-8 : 2
-8 : 3
-8 : 4
-8 : 5
-8 : 6
-7 : -7
-7 : -6
-7 : -5
-7 : -4
-7 : -3
-7 : -2
-7 : -1
-7 : 0
-7 : 1
-7 : 2
-7 : 3
-7 : 4
-7 : 5
-7 : 6
-7 : 7
-6 : -8
-6 : -7
-6 : -6
-6 : -5
-6 : -4
-6 : -3
-6 : -2
-6 : -1
-6 : 0
-6 : 1
-6 : 2
-6 : 3
-6 : 4
-6 : 5
-6 : 6
-6 : 7
-6 : 8
-5 : -9
-5 : -8
-5 : -7
-5 : -6
-5 : -5
-5 : -4
-5 : -3
-5 : -2
-5 : -1
-5 : 0
-5 : 1
-5 : 2
-5 : 3
-5 : 4
-5 : 5
-5 : 6
-5 : 7
-5 : 8
-5 : 9
-4 : -9
-4 : -8
-4 : -7
-4 : -6
-4 : -5
-4 : -4
-4 : -3
-4 : -2
-4 : -1
-4 : 0
-4 : 1
-4 : 2
-4 : 3
-4 : 4
-4 : 5
-4 : 6
-4 : 7
-4 : 8
-4 : 9
-3 : -10
-3 : -9
-3 : -8
-3 : -7
-3 : -6
-3 : -5
-3 : -4
-3 : -3
-3 : -2
-3 : -1
-3 : 0
-3 : 1
-3 : 2
-3 : 3
-3 : 4
-3 : 5
-3 : 6
-3 : 7
-3 : 8
-3 : 9
-3 : 10
-2 : -10
-2 : -9
-2 : -8
-2 : -7
-2 : -6
-2 : -5
-2 : -4
-2 : -3
-2 : -2
-2 : -1
-2 : 0
-2 : 1
-2 : 2
-2 : 3
-2 : 4
-2 : 5
-2 : 6
-2 : 7
-2 : 8
-2 : 9
-2 : 10
-1 : -10
-1 : -9
-1 : -8
-1 : -7
-1 : -6
-1 : -5
-1 : -4
-1 : -3
-1 : -2
-1 : -1
-1 : 0
-1 : 1
-1 : 2
-1 : 3
-1 : 4
-1 : 5
-1 : 6
-1 : 7
-1 : 8
-1 : 9
-1 : 10
0 : -10
0 : -9
0 : -8
0 : -7
0 : -6
0 : -5
0 : -4
0 : -3
0 : -2
0 : -1
0 : 0
0 : 1
0 : 2
0 : 3
0 : 4
0 : 5
0 : 6
0 : 7
0 : 8
0 : 9
0 : 10
1 : -10
1 : -9
1 : -8
1 : -7
1 : -6
1 : -5
1 : -4
1 : -3
1 : -2
1 : -1
1 : 0
1 : 1
1 : 2
1 : 3
1 : 4
1 : 5
1 : 6
1 : 7
1 : 8
1 : 9
1 : 10
2 : -10
2 : -9
2 : -8
2 : -7
2 : -6
2 : -5
2 : -4
2 : -3
2 : -2
2 : -1
2 : 0
2 : 1
2 : 2
2 : 3
2 : 4
2 : 5
2 : 6
2 : 7
2 : 8
2 : 9
2 : 10
3 : -10
3 : -9
3 : -8
3 : -7
3 : -6
3 : -5
3 : -4
3 : -3
3 : -2
3 : -1
3 : 0
3 : 1
3 : 2
3 : 3
3 : 4
3 : 5
3 : 6
3 : 7
3 : 8
3 : 9
3 : 10
4 : -9
4 : -8
4 : -7
4 : -6
4 : -5
4 : -4
4 : -3
4 : -2
4 : -1
4 : 0
4 : 1
4 : 2
4 : 3
4 : 4
4 : 5
4 : 6
4 : 7
4 : 8
4 : 9
5 : -9
5 : -8
5 : -7
5 : -6
5 : -5
5 : -4
5 : -3
5 : -2
5 : -1
5 : 0
5 : 1
5 : 2
5 : 3
5 : 4
5 : 5
5 : 6
5 : 7
5 : 8
5 : 9
6 : -8
6 : -7
6 : -6
6 : -5
6 : -4
6 : -3
6 : -2
6 : -1
6 : 0
6 : 1
6 : 2
6 : 3
6 : 4
6 : 5
6 : 6
6 : 7
6 : 8
7 : -7
7 : -6
7 : -5
7 : -4
7 : -3
7 : -2
7 : -1
7 : 0
7 : 1
7 : 2
7 : 3
7 : 4
7 : 5
7 : 6
7 : 7
8 : -6
8 : -5
8 : -4
8 : -3
8 : -2
8 : -1
8 : 0
8 : 1
8 : 2
8 : 3
8 : 4
8 : 5
8 : 6
9 : -5
9 : -4
9 : -3
9 : -2
9 : -1
9 : 0
9 : 1
9 : 2
9 : 3
9 : 4
9 : 5
10 : -3
10 : -2
10 : -1
10 : 0
10 : 1
10 : 2
10 : 3

I hope someone can help me along.

TheDawgMiner #2

TheDawgMiner's profile picture

8 posts

Posted 01 August 2013 - 10:13 AM

Not a good answer but the math involved to "Path-find" you require is called "Dijkstra's Algorithm".I haven't found an app that allows set cords. like you provided but maybe your math skills are way above mine(i hope lol)

Saving fuel = least amount of movement = straight lines with minimal turns… GL

BlankWolf #3

BlankWolf's profile picture

51 posts

Posted 01 August 2013 - 10:26 AM

TheDawgMiner, on 01 August 2013 - 10:13 AM said:
Not a good answer but the math involved to "Path-find" you require is called "Dijkstra's Algorithm".I haven't found an app that allows set cords. like you provided but maybe your math skills are way above mine(i hope lol)

Thanks. But I think thats not that what I needed.
Dijkstra's Algorithm found the shortest way from A->F (A->C->F) and ignores the other coordinates (B, D, E)

GopherAtl #4

GopherAtl's profile picture

871 posts

Posted 01 August 2013 - 10:44 AM

this is the classic Traveling Salesman Problem, and writing a generic program to find an optimal solution is non-trivial even in the trivial case of a circle, where the optimal path is obvious to the programmer. Google will give you a massive number of algorithms and implementations for it, of varying quality and efficiency.

TheDawgMiner #5

TheDawgMiner's profile picture

8 posts

Posted 01 August 2013 - 12:49 PM

BlankWolf, on 01 August 2013 - 10:26 AM said:
TheDawgMiner, on 01 August 2013 - 10:13 AM said:
Not a good answer but the math involved to "Path-find" you require is called "Dijkstra's Algorithm".I haven't found an app that allows set cords. like you provided but maybe your math skills are way above mine(i hope lol)

Thanks. But I think thats not that what I needed.
Dijkstra's Algorithm found the shortest way from A->F (A->C->F) and ignores the other coordinates (B, D, E)

You really need to do the Algorithm about 5 times, once for distance and 4 times for fuel economy Vs. faceing of turtle. then average the 5 numbers and run it a 6th time. on your 5x5 circle I found 2 answers(one is basicly op. of the other) I'll paste it as F=Forward, R=turn right, L= turn Left:

F,F,L,F,L,F,F,F,F,L,F,F,L,F,F,F,F,L,L,F,L,F,R,F,F,R,F,F,F,F,R,F,F,R,F,F,R,F of course this will reverse the facing of the turtle when it returns to 0,0 if you graph it you will see the pattern & it should work for larger circles also. fuel wise it is sometimes cheaper to go over a single block more than once then to turn twice then forward.

oops at (1,2) it's cheaper to back up and turn right then L,L,F,L sorry

so: F,F,L,F,L,F,F,F,F,L,F,F,L,F,F,F,F,B,R,F,R,F,F,R,F,F,F,F,R,F,F,R,F,F,R,F = 36 movements

TheDawgMiner #6

TheDawgMiner's profile picture

8 posts

Posted 01 August 2013 - 02:43 PM

I haven't had time to fully run the numbers useing your 21 example but there is a pattern showing up, if you use a spredsheet & change all the boxes to same height & width then colorize the boxes to show the pattern you want & assume the top of the page is the direction the turtle is faceing when it starts, going forward always travel as far as you can without turning(unless that would cover an area twice, then stop short & turn), turn to the lonest direction, if = chose left or right, while doing this plot your return course the exact op. of your first path. though it may not be 100% perfect to you requirements the two paths should never cross each other and meet back at (0,) there will be a few spots where a back up then turn may serve you better on the diag.

how to program the turtle to accept the variable and choose the correct path without having 100's of sub programs for every size you may ever need/want is beyond my lua. Sorry

immibis #7

immibis's profile picture

997 posts

Location Wellington, New Zealand

Posted 01 August 2013 - 07:50 PM

TheDawgMiner, on 01 August 2013 - 12:49 PM said:
fuel wise it is sometimes cheaper to go over a single block more than once then to turn twice then forward.

Turning is free.