I'm programming Lua for controlling computers and robots in-game in the Minecraft mod ComputerCraft.
ComputerCraft has these robots called Turtles, that are able to move around in the grid based(?) world of Minecraft. They are also equipped with sensors making them able to detect blocks (obstacles) adjacent to them. Turtles execute Lua programs written by a player.
As a hobby project I would like to program a
goto(x, y, z) function for my Turtles. Some Turtles actually have equipment to remove obstacles, but I would like to make them avoid obstacles and thus prevent the destruction of the in-game environment.
I have no prior experience in robotics, but I have a B.Sc. in Computer Science and am now a lead web developer.
I did some research and found some basic strategies, namely grid based and quadtree based. As I have no experience in this area, these strategies might be old school.
Note that Turtles are able to move in three dimensions (even hover in any height). I could share the obstacles as well as obstacle free coordinates in a common database as they are discovered if that would help me out, as most obstacles are stationary once they are placed.
What are my best options in this matter? Are there any easy fixes? Where do I look for additional resources?
Thank you very much in advance! :-)
EDIT: Thank you for your feedback!
I started reading the book Artificial Intelligence: A Modern Approach, 3rd Edition to get up to speed on basic theory as suggested by Ian. Pointers to other educational resources are appreciated.
Also, I started developing a basic navigation algorithm for moving in unexplored areas, similar to what Cube suggested.
The priority for me is as few moves as possible, as it costs time and fuel cells for each additional move (approx. 0.8 seconds and 1 fuel cell per move in either direction). I plan on using the Euclidean heuristics function in a Greedy Best-First Search for computing a path that is expected to be quite optimal in reducing the number of moves to reach the goal, if enough data is available from the shared database from previous exploration.
Each time an obstacle is reached, I plan to use the following very basic algorithm, exploiting the fact that Turtles are able to move vertically:
1. Calculate direct horizontal path to the goal. 2. Turn to the direction of the next step of the path. 3. If an obstacle is detected in front of the Turtle go to 5. If this is the 4th time that an obstacle is detected in front of the Turtle after moving up, go to 6. 4. Move forward, go to 2. 5. If no obstacle is detected above the Turtle, move up and go to 3, else go to 7. 6. Backtrack to the coordinates the Turtle was in before moving upwards. 7. Turn left, go to 3.
When using this algorithm, records are kept of the explored coordinates and uploaded to a shared database. However, there are some cases, that I did not consider:
- When should it move down? - What if the goal is not reachable from a coordinate directly above it? - If no horizontal move in any direction is possible, how long should it backtrack? - How to detect unreachable goals (obstacles can then be removed if requested)
Maybe if enough exploration data of the area is available, a Jump Point Search is performed to calculate an optimal path. However this assumes a 2D map. How can I take the 3rd dimension into account?
Also, what would be a good data structure to store the exploration data?