Microproject
Grab a logic puzzle from here and solve it with Prolog! Use our example from class as a guide!
Main Project: I Drone’t Know Where I’m Going!
You’ve recently been hired on a team of advance drone scouts. Your task is to fly a drone through a dark cave, recording your path so that future drones can fly through at high rates of speed while avoiding obstacles. Of course, being a computer scientist you aim to automate this path finding. You are writing a program (in Prolog) which flies the drone, slowly, through the cave, maneuvering around obstacles, and recording the path taken.

To make this easier, a cave will be defined by its height and width, along with a series of rectangles which indicate unsafe spaces to fly. Each rectangle is a 4-tuple, with X and Y coordinates of the top left corner, and a width and height. These will be of the form:
[X, Y, Width, Height]
The above cave, of size width=12, height=10, is defined by the following list of rectangles:
[[0, 0, 2, 3], [2, 0, 1, 2], [3, 0, 3, 1], [6, 0, 1, 2], [7, 0, 1, 3], [8, 0, 4, 4], [9, 4, 3, 1], [10, 5, 2, 1], [0, 4, 6, 6], [3, 3, 3, 1], [4, 2, 1, 1], [6, 5, 1, 5], [7, 8, 1, 2], [8, 9, 3, 1], [11, 8, 1, 2]]
Rectangle coordinates bound squares on the grid. Coordinates are 1-indexed, so within the rectangle [0, 0, 2, 3] are the squares [1, 1], [2, 1], [1, 2], [2, 2], [1, 3], and [2, 3], and within the rectangle [0, 0, 1, 1] is the square with coordinates [1, 1]. The effect of treating everything as rectangles means our cave looks more like the below.

Your drone can only move up, down, forward, or backward. It cannot move diagonally. You can assume your drone occupies one square. Once your drone has completed a path through the cave (it has reached a coordinate whose X matches the width of the cave), you should return a list of coordinates which were flown through.
The main entry point to your program should be a predicate, fly, of four arguments:
fly(Cave, [CaveWidth, CaveHeight], StartY, Path)
where Cave is a set of rectangles like those defined earlier. The call to fly, and solution above, could appear as:
% Definition of cave, in your source file. cave([[0, 0, 2, 3], [2, 0, 1, 2], [3, 0, 3, 1], [6, 0, 1, 2], [7, 0, 1, 3], [8, 0, 4, 4], [9, 4, 3, 1], [10, 5, 2, 1], [0, 4, 6, 6], [3, 3, 3, 1], [4, 2, 1, 1], [6, 5, 1, 5], [7, 8, 1, 2], [8, 9, 3, 1], [11, 8, 1, 2]]). % Resolve X to the cave definition, and use it in fly. cave(X), fly(X, [12, 10], 4, Path). Path = [[1, 4], [2, 4], [3, 4], [3, 3], [4, 3], [4, 2], [5, 2], [6, 2], [6, 3], [7, 3], [7, 4], [7, 5], [8, 5], [9, 5], [9, 6], [9, 7], [9, 8], [10, 8], [11, 8], [12, 8]]
Remember this is only one of several solutions to this problem. Pressing the semicolon should result in more solutions. If you use a slightly different rule definition for fly, that is ok, but be prepared to explain your changes.
Hints and Limitations
- The cave will never curve back on itself in a way such that the drone needs to move backward to find its way to the end of the cave. There can, however, be areas where the drone gets “trapped” and can’t move forward, and therefore will need to backtrack. This case should be handled by Prolog automatically.
- Avoid the temptation to represent the grid explicitly, or to assert knowledge about the current state into the knowledge base. Instead, use a state-space finding approach as in the example from class (consider, in any given position, what are the next possible positions? Are they safe? etc…).
- You may want to perform your testing with simple caves at first, and then increase the difficulty.
Credit: Drone icon