HW11. Virtual world and projects (2nd of Dec, 23.59)
Your task in this homework is to play games in a virtual block world! A virtual world can be represented as an image (e.g. Figure 1) where each pixel is either white (means vacant) or has a color. Colored pixels have special meaning, e.g. pink pixels belong to impenetrable obstacles. Also, each possible virtual world has a start pixel (A) and end pixel (B), that are defined by circles.
Goal: find the shortest path from pixel A to pixel B. The final path is measured as a sum of lengths of each step in the path. The length of a step is an Euclidean distance between its start and end pixels.
Rules: You need to avoid the obstacles (pink areas and no crossing the pink line!) and honoring the slow-down factors in the swamp and in the sea (by making Euclidean distance 2x and 4x times “longer” in those areas).
Things to consider before you start:
- Think about how to programmatically represent the block world as a graph.
- What are the nodes?
- What are the edges? Given a node, where can you move to?
- What is the distance between any two nodes?
EX1. Getting started with pathfinding in the small virtual world. The first task is to implement Dijkstra algorithm to find the shortest path from A (blue) to B (red) on the following small scale world (250x250). Pink is a block, you can not go through it! Report the shortest distance from A to B and the time it took to run the algorithm. Visualize the final path and pixels that were visited by the algorithm at any time. Comment on your results.
To generate the image for the world use the following web tool. Set the world size to 250x250 at the top and use the following object instructons to get the small world:
circle 10 10 3 blue circle 240 240 3 red text "A" 15 20 20 black text "B" 225 235 20 black rectangle 0 110 50 125 pink rectangle 70 110 250 125 pink
Figure 1: a small virtual block world for EX1 and EX2
After you’ve added objects (and path) to the world under Objects, you can click “Save as png” to save the image to your computer. This image can then be used as an input to your search algorithm.
In order to visualize the path using the webtool, save your algorithm’s output into a “.txt” file in the following format
X1 Y1 X2 Y2 X3 Y3 ….
Here, each pair of X and Y represents a pixel that is included into the final path from A to B (including A and B). For example, consider the following .txt file (URL). Select this file by clicking “Choose file” under “Path file” section in the web tool. You should get the following result:
Figure 2: an example path in the small virtual block world.
You can also use the web tool to highlight pixels that were visited by the algorithm. For this, store the visited pixels/nodes in a text file, in a similar to path file format:
X1 Y1 X2 Y2 …
For example, if your search algorithm visited every possible node (which is inefficient!) then you would get the following output, defined by the coverage file (URL):
Figure 3: an example visited area in the small virtual block world.
NB! “Save as png” does not save the visited pixels, therefore if you want to use the webtool for this, you need to separately screenshot it.)
EX2. Implement A* search algorithm on the small world (the same as above). Similarly to the previous exercise report: execution time and the shortest distance. Visualize the visited area and the final path. Comment on the differences between Dijkstra and A*!
EX3. Now let’s consider the bigger version of the virtual world (1000x1000), which is provided below (Figure 4). The goal is still the same - find the path from A (BLUE) to B (RED). But now with some additional obstacles: SWAMP and SEA. SWAMP in light green, is 2 times slower compared to usual. SEA in light blue and is 4 times slower than the usual (taking one step in a sea, is equal to taking 4 steps on normal land). Measure and report the search time and the shortest distance. Visualize the visited area and the final path. How sea and swamp affect the final trajectory?
Hint: make sure to use efficient data structures for keeping visited/discovered nodes, e.g. consider the priority queue for A*. Using inefficient data structures can end up your search running for a really long time!. Another way to speed up your search is by making steps longer. So, instead of considering every immediate nearest neighbor as a potential next step, consider only nodes that are 2-3 pixels away (or even 10-20 pixels).
Hint II: for the slower regions like the sea or swamp decide the distance or time spent on each step based on the slow-down in the location of the target pixel.
The instructions to build a bigger version of the virtual world are provided in the file (URL). Feel free to either ignore or remove the “text” lines. The world size is 1000x1000. The same instructions are given as an example on the web tool page.
Figure 4: the bigger version of the virtual world (1000x1000) for EX3 and EX6.
EX4 & EX5: The course ends with the project to be completed usually by a small team of 2-3 people. Your task is to come up with one project proposal all by yourself (this is an individual task, you will have time to share) - taking ideas from project ideas file, from previous homeworks, or your imagination + google. E.g. you may attempt to extend some of the past exercises. Note - this is a proposal that you may use to attract other students to join; and this is at the same time a proposal that you do not need to start executing necessarily. So. it's more a planning exercise, not execution exercise.
Your project proposal should have:
- Title
- 2-5 sentences of a short description
- Briefly described the motivation and the main challenge of this project
- Division of tasks, the estimated number of work hours per task, and deadline (aim at our poster session!)
- Allocation of the 2-3 people to tasks and hours.
- Recommended: create a GANTT chart to cover the previous two points.
- Description of the envisioned end results that would go to the project report/poster.
We will discuss these in the practice session.
EX6 (Bonus up to 3p). Experiment with the virtual world, add more different terrains (ice, lava, forest etc.), add surprising things (e.g. portals, magnets, black holes etc.). Also, you may try to improve visualization by perhaps doing it yourself. How your algorithm behaves? Can you tweak the algorithm to outperform standard A* in this specific setting? Try to show this advantage with some empirical results. The number of points granted for this exercise will depend on the number of things considered and on the level of their implementation.