In this homework you will implement several pathfinding algorithms on a grid, and you will visualize the shortest path that you have found.
You are given a game map in the shape of a square grid in the following format:
1 3 3 2 F 5 8
2 F 1 8 3 1 2
1 2 2 5 2 1 3
where every number represents the terrain of the respective grid cell. F means impassable. 1 means easily passable; 9 means nearly impossible to pass. These are effectively the weights assigned with stepping on the respective tile.
Limits: the map will be no larger than 10000x10000 cells, and the weights between passable tiles will be between 1 and 9.
Implement an algorithm that finds the shortest path between two tiles on the map optimally. The starting and ending tile are selected by the user by clicking / touching the respective tile. Obviously, display the grid (so the user can select a starting and an ending tile), and denote the tiles your algorithm is exploring as it explores them. When your algorithm is done, there should be three colors on the grid: untouched tiles, explored tiles, and tiles that form the shortest path.
An interesting addition (that you still have to do) involves teleports. Some tiles on the map form direct links with other tiles (weight 0). Those are designated in the following way:
1 3 3 T1 F T2 8
2 F T2 8 3 1 2
T1 2 2 5 2 1 3
where T1 -- T1 is a teleport between the respective tiles, and T2 -- T2 is another such teleport. There will only ever be pairs of teleports linked in this way, but you do not know how many teleports there will be. It is possible, for example, that there are none; it is also possible that every tile on the map is a teleport.
Make sure that your algorithms handle the case with teleports, too.
Submit your sources to the dropbox before the deadline. You will also have to demonstrate your working homework to me within a week after the deadline.