C代写:COMS327 Path Finding

用Dijkstras算法代写作业,实现迷宫路径的最优寻址。

Requirement

So far, weve got this lovely dungeon. And we can save and restore it.

And, you know look at it. And thats about it. Nice for moms fridge, but otherwise kind of boring.

Once you have monsters (next week), they (at least the smart ones) will need to find a path to the player through the dungeon. To find that path, youll need to implement a path-finding algorithm. Were going to have some monsters that can tunnel through walls and others that can only move through open space, so well actually need two slightly different pathfinding algorithms. In both cases well use Dijkstras Algorithm, treating each cell in the dungeon as a node in a graph with (up to) 8-way connectivity. For the non-tunneling monsters, well give a weight of 1 for floor and ignore wall cells (i.e., dont try to find paths through walls; this actually degenerates to BFS, and youre welcome to use that, but we will not require you to implement two different-if very similar-algorithms for this assignment). For the tunnelers, well have to use weights based on the hardness; cells with a hardness of 0 have a weight of 1, and cells with hardnesses in the ranges [1, 254] have weights of hardness / 85. A hardness of 255 has infinite weight. We dont have to assign a value to this. Instead, we simply do not put it in the queue.

A naive implementation will call pathfinding for every monster in the dungeon, but in practice, every monster is trying to get to the same place, so rather than calculating paths from the monsters to the player character (PC), we can instead calculate the distance from the PC to every point in the dungeon, and this only needs to be updated when the PC moves or the dungeon changes. Each monster will choose to move to the neighboring cell with the lowest distance to PC. This is gradient descent; the monsters move downhill. Unless the monster is already collocated with the PC, there is always at least one cell with a shorter distance than its current cell. In the case of multiple downhill cells having the same distance, the monster may choose any one of them.

Dijkstras Algorithm is described here: http://en.wikipedia.org/wiki/Dijkstra%27s algorithm Scroll down to find the pseudocode under Using a priority queue. Obviously, youll need a priority queue, one with a decrease priority operation. You may use the Fibonacci queue that I provided with my solution to 1.01, or you may implement (or use a properly-attributed third party implementation of) any other priority queue you like.

My corridor building code uses Dijkstras algorithm, so you may start with that (it wont require much modification) or start from scratch.

To test your code, select a random floor point in the dungeon for your PC, which you will render with an @. Render your dungeon with the PC. Then render your non-tunneling monster distance map, still marking the PC with @ and marking distances using the last digit of the distance from the PC as calculated by your pathfinding algorithm (see image). Repeat for the tunneling monster distance map. Note that your distance maps will be integers from zero to some max value. We are only displaying them using the values above, not storing them that way. It is recommended that you add a switch to place your PC at a specified (y, x) in the dungeon; this will allow you to easily compare your output with mine on the test dungeons that were released for 1.02.

Your submission, when run, should generate a dungeon, calculate all distance maps, render all three views of the dungeon, and exit.

All code is to be written in C.

Here is an example distance map for non-tunneling monsters. The PC is near the lower right corner. Only the last digit of the distance is shown. You can get actual distances by counting the zeros along a path (sort of like reading elevations on a topographical map). Keep in mind that if you follow a non-optimal path in a circuit, you may have to count backwards! Pay attention to the gradients. Note that I dont have a solution for our dungeons, yet, so Ive produced this map manually. Its highly possible Ive made an error in here somewhere, but I believe its correct.

]]>

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注