Microproject
Write a prolog rule which determines if a coordinate is within the bounding box of a rectangle. A rectangle will be defined as a list with four components [X, Y, Width, Height] where X and Y specify the upper left point on the rectangle. 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].
There are two ways to approach this problem: generating the list of squares contained within the rectangle, then checking list membership, or simply doing some math to check the bounds of the rectangle. I recommend the latter, though the former is good recursion practice.
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.
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:
|
1 |
[X, Y, Width, Height] |
The above cave, of size [10, 12], is defined by the following list of rectangles:
|
1 2 3 |
[[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. For convenience, we’ll say the square within the rectangle [0, 0, 1, 1] is the square with coordinates [1, 1]. See the microproject for more on this.
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:
|
1 |
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:
|
1 2 3 4 5 6 |
% 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.
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