代写Redbeard Treasure Hunt游戏，需要用A*算法寻找地图上的最短路径。
Learning Objectives
By the end of this assignment you should have:
- become fluent with the mechanics of class definitions in Python, including constructors and other special methods
- practised implementing a class, given its interface
- practised identifying suitable classes, given the description of a problem in English
- faced decisions about which classes should be responsible for what, and made reasonable choices
- faced decisions about what data structure to use to implement a class, weighed some options, and made reasonable choices
- implement and use an ADT to solve a problem
The Redbeard Treasure Hunt Game
The famous pirate Redbeard master ship sunk in 17-th century in the Sea Of 1000 Islands after a fierce battle with Bluebeard’s ship. The sunken ship contains a large bounty. You are navigating the Sea Of 1000 Islands in your ship provided with modern technology. The Sea Of 1000 Islands has been mapped into a grid where a navigable square is denoted by a dot (“.”), and a square that belongs to one of many islands is denoted by a “+”.
You have a number of sonar devices. If you drop a sonar device from your ship, if the treasure is in the range of sonar, the device will give you the grid coordinates of the treasure. Once you have the coordinates, your AI engine will run a clever algorithm, called A-star search algorithm, that is capable of plotting the shortest way from the current position of your ship to the detected treasure avoiding the obstacles (in this case, the obstacles are the numerous islands).
If the sonar device detects nothing, you can navigate in any direction you like (north, south, east, west, north-east, north-west, south-east, south-west) one navigable square at a time. You can move as many squares as you like (one square at a time). Whenever you feel like it, you drop another sonar. And so on until the treasure has been found, or you run out of the sonars. Please note once a sonar has been dropped, it is not recoverable. The goal of the game is to find the treasure and plot the navigation route to the treasure. If you run out of the sonar devices before finding the treasure, you lose the game.
A copy of the map, including the plotted trip to the treasure, is shown below. The dots indicate navigable squares, the “+” signs indicate obstacles, the letter “B” indicates the position of the ship, the letter “T” indicates the position of the treasure. The sequence of “*“ signs indicates the path plotted by the A-star search algorithm. The jagged red line just follows the “*“ symbols to emphasize the path.
The A-star path search algorithm
The A-star path search adjoins next cell to the path by chosing a cell that is “open” (see the links below) and satisfies the following condition: the sum of distances of that cell from the origin and the destination must be minimal. The details of the algorithm including the pseudocode can be found on the internet. Here is a couple of recommended links:
- http://web.mit.edu/eranki/www/tutorials/search/
- http://www.policyalmanac.org/games/aStarTutorial.htm
The next image shows how the actual sum of distances is computed. Please note if we assume one cell has side length one unit, a vertical or horizontal distance from one cell to next is one unit, whereas a diagonal distance (for example from current cell to the cell loacted north-east) is 2 or approx. 1.4 units. In order to avoid decimals from or computation, we will multiply everything by 10, so for instance the distance of the cell painted in red is computed as follows: the red cell is one (diagonal) square far from cell labelled “A”, that is 14 unit, and two (diagonal) squares from cell labelled “B” therefore 28 units, so its total distance (or, as it is called in the A-star algorithm, its f-cost) is 14+28=42 units (as shown).
Please note on each iteration we need the open cell with minimal f-cost (please see the pseudocode in the MIT weblink above). To avoid a costly search on each iteration, we will maintain the list of the open cells using a data structure called priority queue. In fact, this is not very efficient. We will learn later that the best structure use for this purpoise is a heap.
Priority Queue
In the A-star path search algorithm, you need to maintain a set of open cells and chose the one with minimum f-cost. While we could use a Python list, it has no way to give us items in order according to our priority (f-cost).
Instead we will use something called a PriorityQueue. It is a kind of container that allows you to add and remove items. But a PriorityQueue removes items in a very specific order: it always removes the item with the highest priority. We define what the priority is to be when we construct the PriorityQueue.
A PriorityQueue supports the following actions: determine whether the priority queue is empty insert an item with a given priority remove the item with the highest priority Look at container.py, which contains the Container class, as well as a new, partially-complete PriorityQueue class. PriorityQueue is a child class of Container, which means that it inherits attributes and methods from Container.
You must complete the required methods according to the provide docstring. (Notice that we’re using a sorted list to implement this class; in later courses, you’ll learn about a much more efficient implementation called heaps.)
The Node, Grid, and TreasureHunt
Please study the starter code carefully. It contains a lot of comments explaining many aspects of your coding work.
The Node class is used to represent grid node. Each cell of the grid will be represented by a Node object. A Node object has grid coordinates, and also can be navigable or not (that is can be an obstacle or not), it has a parent (that is a prior cell in the A-star path) and can be a member of the A-star path or not, as determined by the A-star algorithm.
The Grid class represents the game world: it has a map and the main paremeters needed to maintain the game - width, height, the position of the boat, and the position of the treasure. Make sure to use a priority queue object to maintain the set of open cells in the find_path method.
The TreasureHunt class sets up the game. Each game can have the status “STARTED”, “WON” or “OVER”.
The game can be played from keyboard if you build a user interface for it, however for the purpose of this assignment, we will allow commands of a play session to be read from a text file. Sample test files and some test code will be provided a few days after the Assignment has been published, so you can test.
Please note we have NOT prepared a user interface (and we won’t). If you prefer to play your game, you may consider to build a user interface. In case you do, please do not submit it.
Make sure to test your work carefuly before submitting! Submit the completed code in container.py, grid.py and treasurehunt.py.