# ComputerCraft (Minecraft mod) navigation: Collision avoidance and path planning/finding in 2D/3D space

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?

• If I wanted to do this, I would look at some variant of A*... – apnorton Jan 4 '14 at 15:50
• I'm glad my answer helped you, and I would recommend splitting your edit into an entirely new question so we can address it more directly. – Ian Jan 6 '14 at 21:58
• I thought about that too, Ian. I found a lot of useful books on the topics. The questions I need answers for are becoming clearer as I study more theory and think about the features I want the robot agent to have. – Lars Gyrup Brink Nielsen Jan 7 '14 at 0:41

What comes to my mind first is some sort of bug algorithm. That is a path finding algorithm that has only small constant amount of memory and only sees (small) local parts of the world.

You can imagine this as

1. Go directly to the goal
2. If there is an obstacle in a way, pick a direction and start going around it
3. Once there is a free path again, goto 1

Of cause there are some problems with this, I'm not entirely sure that this will work in 3D. Selecting a way around an obstacle will be a little trickier than just saying "always go right". Other than that, this algorithm can select a wrong direction and spend a long time going around the obstacle which it could avoid easily by going other way around it.