Turtle path-finding following roads?

Hello,

Inspired by the recent news of how Google is working on a driver-less car, I decided I wanted to replicate that in Minecraft, using turtles as little delivery men who can carry resources to pre-set locations, following player built roads. :)/>

However, after an hour or two of searching the web, I did find some algorithms to path-find, such as A*, but I didn't understand how:

1. I could replicate this in CC, Lua.
2. I could manage to only let the turtles drive on roads (and, optionally but preferred, without having to predefine long lists of information about the roads, junctions, direction of north/south or east/west.)

I haven't used Computer Craft for some time, as I've been playing Vanilla Survival on some servers, however I thought this would be really cool to setup a small automated village with turtles roaming around doing jobs. :lol:/>

My main questions: :wacko:/>

• How can I create a path-finding program for my turtles to drive around on roads, and stop at requested pre-set locations (given the co-ordinates of the locations by a central computer, which can be edited to store new locations)
• I also want to have two lanes on each road.

Extra Information:

Here is a little map of the village I setup to test my new autonomous turtles, completed with co-ordinates of each junction for both lanes, and the co-ordinates for both lanes at destinations, along with the co-ordinates for the 'parking lot':

With co-ordinate labels:

Spoiler

Without co-ordinate labels (easier to see layout)

Spoiler

Notes:
The orange, blue and green boxes are example buildings, with each red square (red wool) being a 'parking lot' and the dark-grey being 'drive-ways' (dark-grey wool). The dark green squares are grass blocks, light grey is pavement (stone slabs, level with the road), and dark grey is the road (stone).

I have also setup a GPS System with 4 Computers in the vicinity of this 'town', so you can use the co-ordinates. I would also like the Turtles to drive on the left (I'm British :P/> ).


Thanks in advance! :D/>

• How can I create a path-finding program for my turtles to drive around on roads, and stop at requested pre-set locations (given the co-ordinates of the locations by a central computer, which can be edited to store new locations)
• I also want to have two lanes on each road.

How to make a path finder… I would suggest a forward loop only if the block below the turtle was comparable to the block assigned for "TO" travel or "FROM" travel. If it hit a block that wasn't comparable, back up, turn right, continue the loop if comparable, else, turn right, etc etc.

Stop locations could be saved as blocks as well

Take wool for example. You could have a while rail for travel one-way, black rail for other-way travel. Then at places on the rail have a color stop the turtle and do specific functions according to the color.

That's my idea and I may do something with it. Feel free to try yourself as well :)/>

BlockSmith, on 29 May 2014 - 11:31 AM said:

• How can I create a path-finding program for my turtles to drive around on roads, and stop at requested pre-set locations (given the co-ordinates of the locations by a central computer, which can be edited to store new locations)
• I also want to have two lanes on each road.

How to make a path finder… I would suggest a forward loop only if the block below the turtle was comparable to the block assigned for "TO" travel or "FROM" travel. If it hit a block that wasn't comparable, back up, turn right, continue the loop if comparable, else, turn right, etc etc.

Stop locations could be saved as blocks as well

Take wool for example. You could have a while rail for travel one-way, black rail for other-way travel. Then at places on the rail have a color stop the turtle and do specific functions according to the color.

That's my idea and I may do something with it. Feel free to try yourself as well :)/>

Thanks for the reply!

I never thought of using blocks to tell the Turtle where to go, that's a good idea. However, I would also like the road to still… look like a road. I will definitely try this out, but I'm still open to new ideas which don't need lots of different blocks placed down, but instead a nice clean looking road.

An extra thought:

OK, so this probably won't help here, but how does Google map all the roads in the entire world? I'm sure that they don't have people manually filling in information, but instead it's automated by some supercomputer somewhere. Just an idea… Maybe, a Turtle could map the area of the town and work out where roads are, maybe read signs on the roads to get their name, and send the data it found to a server PC? Then the data could be used to calculate junctions, and later be used to pathfind.

Google mostly pulls the data from pre-existing maps, manual work, or by where its photography cars can drive.

This is more or less what I did with my first ComputerCraft script; I wanted to have a turtle running my base, but unfortunately I encountered a CC (server-stalling) bug which kinda shut that idea down.

Then I tried it again later and encountered a different CC (server-stalling) bug which also stopped me in my tracks.

But this is the guts of the latest copy of my navigation code; the turtle I fed it to wandered around between the nodes defined in its "nodes" table, collecting resources then dropping them off into machines or crafting them into new items.

Basically you'd build your own nodes table with all the co-ords on your map, along with the data as to which nodes the turtle is allowed to travel to from which other nodes. This on its own would probably not be enough to guarantee no collisions between turtles but with two lanes of traffic and the minor bit of "let's go around things" code already in there it'd probably work with little alteration.

Bomb Bloke, on 29 May 2014 - 11:43 AM said:

Google mostly pulls the data from pre-existing maps, manual work, or by where its photography cars can drive.

This is more or less what I did with my first ComputerCraft script; I wanted to have a turtle running my base, but unfortunately I encountered a CC (server-stalling) bug which kinda shut that idea down.

Then I tried it again later and encountered a different CC (server-stalling) bug which also stopped me in my tracks.

But this is the guts of the latest copy of my navigation code; the turtle I fed it to wandered around between the nodes defined in its "nodes" table, collecting resources then dropping them off into machines or crafting them into new items.

Basically you'd build your own nodes table with all the co-ords on your map, along with the data as to which nodes the turtle is allowed to travel to from which other nodes. This on its own would probably not be enough to guarantee no collisions between turtles but with two lanes of traffic and the minor bit of "let's go around things" code already in there it'd probably work with little alteration.

Thanks for the reply :)/>

I have decided to start off with a 1-lane system, but make it so that the Turtle check's it has moved whenever it tries to move forward in-case someone stands in-front of it etc, and it will also be able to go in either direction on roads.

I will start off by creating a script where I type in a road name, the directions (n/s or w/e), and the two end points, and it will store all of the co-ordinates for that road in a file. I will do this for each road, and then work on a system using this to work out which road is closest to the destination, and work backwards from there.

Thanks again! :)/>