In Java
Introduction Valentines Day is fast approaching, and the hero of our story, Cupid, is trying his best to spread some platonic love and friendship in these gloomy times. If you didn't know. Cupid is an archer, and archers often prefer staying still and spending their time taking good shots with their bow. Cupid is no different in this regard, but he's heard you've been learning about stacks and algorithm design and was wondering if you could help him simulate some scenarios so that he's in tip-top shape (He hasn't been getting out much with the pandemic). He also understands that your assignment isn't due until the 4" of March, but he's happy to have it for future years anyways. You are given a map that describes Cupid and the targets for his arrows, which is divided into rectangular cells to simplify the task of computing the required path. There are different types of map cells: The starting point that Cupid wants to use Map cells where the target is located Map cells indicating roadblocks or other barriers Map cells containing pathways. There are 3 types of pathways: Cross paths. A cross path located in cellL can be used to interconnect all the neighbouring map cells of L. A cell L has at most 4 neighbouring cells that we denote as the north, south, east, and west neighbours. The cross path can be used to interconnect all neighbours of L, Vertical paths. A vertical path can be used to connect the north and south neighbours of a map cell; and Horizontal paths. A horizontal path can be used to connect the east and west neighbours of a map cell Figure 1 shows an example of a map divided into cells. Each map cell has up to 4 neighbouring cells indexed from 0 to 3. Given a cell the north neighbouring cell has index 0 and the remaining neighbouring cells are indexed in clockwise order. For example, in Figure 1 the neighbouring cells of cell 8 are indexed from 0 to 3 as follows: neighbour with index O is cell 1, neighbour with index 1 is cell 9. neighbour with index 2 is cell 13, and neighbour with index 3 is cell 7. Some cells have fewer than 4 neighbours and the indices of these neighbours might not be consecutive numbers, for example, cell 4 in Figure 1 has 2 neighbours indexed 1 and 2 (no 0 or 3 neighbours). A path from Cupid (cell number 12 in the figure) to a target (cell number 0) is the following: 12, 7, 2, 1, 0. A path from Cupid to another target (cell number 4) is the following: 12. 7. 2. 3. 4. Note that in some other maps, cells will be inaccessible because they are walls, or because the path is horizontal and the only way is vertical, or vice versa. Valid Paths When looking for a path the program must satisfy the following conditions: The path can go from Cupid, a cross path cell or a target cell to the following neighbouring cells: A target cell . A cross path cell The north cell or the south cell, if such a cell is a vertical path or The east cell or the west cell, if such a cell is a horizontal path. The path can go from a vertical path cell to the following neighbouring cells: The north cell or the south cell, if such a celi is either Cupid, a cross path cell, a target cellor a vertical path cell. The path can go from a horizontal path cell to the following neighbouring cells: The east cell or the west cell, if such a cell is either Cupid, a cross path cell, a target cell, or a horizontal path cell Map 3 2 LO 6 7 O +++ Figure 1. A sample of one of Cupid's maps represented as a grid of cells Limitation: If while looking for a path the program finds that from the current cell there are several choices as to which adjacent cell to use to continue the path your program must select the next cell for the path in the following manner An object in motion in motion will stay in motion unless acted on by an unbalanced force. The arrows will continue in the same direction they were heading if the path is available. . The program prefers a target cell over the other cells. If there is no target cell adjacent to the current cell, then the program must prefer the cross path cell over the other cells, and If there is no cross-path cell then the program chooses the smallest indexed cell that satisfies the conditions described above. While Cupid's arrows are magic, they are only so magical. The arrows Cupid uses can backtrack up to 3 times before they are unable to do so again. Cupid's arrows can only turn so much as well. Keep track of the inertia of the arrow by tracking how many times it has traveled in the same direction. After it has taken 3 steps in the same direction, it can no longer turn. For simplicity, it may take 2 steps and turn as many times as needed for the pathfinding. Note: The initial step required to pick a direction does not count for inertia. Importantly, Cupid will only shoot an arrow down the same path once. Cupid's arrows should stop when they hit a target and the stack should be popped until empty The distance Cupid can shoot an arrow is configurable and provided as an argument to the program Lastly, Cupid fires arrows one at a time. StartSearch.java This class will have the following private instance variable o Map targetMap This variable will reference the object representing the map where Cupid and the targets are located. This variable must be initialized in the constructor for the class, as described below. oint numArrows, for how many arrows Cupid has fired so far. Compare this to the quiversize from the Map. int inertia, which is used for tracking how many times an arrow has travelled in the same direction. It should start at 0 and increase everytime an arrow moves in the same direction. Int direction, which is used for tracking the direction of the arrow. O is north, 1 is east, 2 is south, 3 is west. (Or Up, Right Down, Left, respectively) It should import: import java.io.FileNotFoundException; & import java.0.10Exception; You must implement the following methods in this class: StartSearch(String filename) This is the constructor for the class. It receives as input the name of the file containing the description of the map. In this method you must create an object of the class Map (described in the provided files) passing as parameter the given Input file; this will display the map on the screen. Read them if you want to know the format of the input files, static void main(String[] args). This method will first create an object of the class StartSearch using the constuctor StartSearch(args[0]). Argstop will be the name of a map file, args[1] will be the number of cells that the arrow can travel before it falls to the ground. if and only if a size argument is provided, your algorithm should count how many targets can be found in a path that is at most args[1] long with the number of arrows determined by the map. When you run the program, you will pass as command line arguments the name of the input file (see following section after Java classes), and the number of cells that Cupid can hit from his starting point to find target along with the number of arrows. Your main method then will try to find a path from Cupid to the targets according to the restrictions specified above. The algorithm that looks for a path from the initial cell to the destinations must use a stack and it cannot be recursive. Suggestions on how to look for this path are given in the next section. The code provided to you will show the path selected by the algorithm as it tries to reach the target cells, so you can visually verify if your program works. The main method should exit by printing out the number of targets found given the restrictions above (maximum arrow length, maximum number of arrows, Cupid won't shoot down the same path twice. MapCell nextCell/MapCell cell). The parameter is the current cell. This method returns the best cell to continue the path from the current one, as specified early in the limitations. Refer to those priorities when coding this section. of several unmarked cells are adjacent to the current one and can be selected as part of the path (remember the arrow will stay on the same path first), then this method must return one of them in the following order: - A target cell A cross path cell . If there are several possible cross path cells, then the one with the smallest index is returned. . A vertical path cell or a horizontal path cell with smallest index . Read the description of the class MapCell below to learn how to get the Index of a neighbouring cell . If there are no unmarked cells adjacent to the current one that can be used to continue the path, this method returns null Your program must catch any exceptions that are thrown by the provided code. For each exception caught, an appropriate message must be printed. . The message must explain what caused the exception to be thrown. You can write more methods in this class but they must be declared as private Introduction Valentines Day is fast approaching, and the hero of our story, Cupid, is trying his best to spread some platonic love and friendship in these gloomy times. If you didn't know. Cupid is an archer, and archers often prefer staying still and spending their time taking good shots with their bow. Cupid is no different in this regard, but he's heard you've been learning about stacks and algorithm design and was wondering if you could help him simulate some scenarios so that he's in tip-top shape (He hasn't been getting out much with the pandemic). He also understands that your assignment isn't due until the 4" of March, but he's happy to have it for future years anyways. You are given a map that describes Cupid and the targets for his arrows, which is divided into rectangular cells to simplify the task of computing the required path. There are different types of map cells: The starting point that Cupid wants to use Map cells where the target is located Map cells indicating roadblocks or other barriers Map cells containing pathways. There are 3 types of pathways: Cross paths. A cross path located in cellL can be used to interconnect all the neighbouring map cells of L. A cell L has at most 4 neighbouring cells that we denote as the north, south, east, and west neighbours. The cross path can be used to interconnect all neighbours of L, Vertical paths. A vertical path can be used to connect the north and south neighbours of a map cell; and Horizontal paths. A horizontal path can be used to connect the east and west neighbours of a map cell Figure 1 shows an example of a map divided into cells. Each map cell has up to 4 neighbouring cells indexed from 0 to 3. Given a cell the north neighbouring cell has index 0 and the remaining neighbouring cells are indexed in clockwise order. For example, in Figure 1 the neighbouring cells of cell 8 are indexed from 0 to 3 as follows: neighbour with index O is cell 1, neighbour with index 1 is cell 9. neighbour with index 2 is cell 13, and neighbour with index 3 is cell 7. Some cells have fewer than 4 neighbours and the indices of these neighbours might not be consecutive numbers, for example, cell 4 in Figure 1 has 2 neighbours indexed 1 and 2 (no 0 or 3 neighbours). A path from Cupid (cell number 12 in the figure) to a target (cell number 0) is the following: 12, 7, 2, 1, 0. A path from Cupid to another target (cell number 4) is the following: 12. 7. 2. 3. 4. Note that in some other maps, cells will be inaccessible because they are walls, or because the path is horizontal and the only way is vertical, or vice versa. Valid Paths When looking for a path the program must satisfy the following conditions: The path can go from Cupid, a cross path cell or a target cell to the following neighbouring cells: A target cell . A cross path cell The north cell or the south cell, if such a cell is a vertical path or The east cell or the west cell, if such a cell is a horizontal path. The path can go from a vertical path cell to the following neighbouring cells: The north cell or the south cell, if such a celi is either Cupid, a cross path cell, a target cellor a vertical path cell. The path can go from a horizontal path cell to the following neighbouring cells: The east cell or the west cell, if such a cell is either Cupid, a cross path cell, a target cell, or a horizontal path cell Map 3 2 LO 6 7 O +++ Figure 1. A sample of one of Cupid's maps represented as a grid of cells Limitation: If while looking for a path the program finds that from the current cell there are several choices as to which adjacent cell to use to continue the path your program must select the next cell for the path in the following manner An object in motion in motion will stay in motion unless acted on by an unbalanced force. The arrows will continue in the same direction they were heading if the path is available. . The program prefers a target cell over the other cells. If there is no target cell adjacent to the current cell, then the program must prefer the cross path cell over the other cells, and If there is no cross-path cell then the program chooses the smallest indexed cell that satisfies the conditions described above. While Cupid's arrows are magic, they are only so magical. The arrows Cupid uses can backtrack up to 3 times before they are unable to do so again. Cupid's arrows can only turn so much as well. Keep track of the inertia of the arrow by tracking how many times it has traveled in the same direction. After it has taken 3 steps in the same direction, it can no longer turn. For simplicity, it may take 2 steps and turn as many times as needed for the pathfinding. Note: The initial step required to pick a direction does not count for inertia. Importantly, Cupid will only shoot an arrow down the same path once. Cupid's arrows should stop when they hit a target and the stack should be popped until empty The distance Cupid can shoot an arrow is configurable and provided as an argument to the program Lastly, Cupid fires arrows one at a time. StartSearch.java This class will have the following private instance variable o Map targetMap This variable will reference the object representing the map where Cupid and the targets are located. This variable must be initialized in the constructor for the class, as described below. oint numArrows, for how many arrows Cupid has fired so far. Compare this to the quiversize from the Map. int inertia, which is used for tracking how many times an arrow has travelled in the same direction. It should start at 0 and increase everytime an arrow moves in the same direction. Int direction, which is used for tracking the direction of the arrow. O is north, 1 is east, 2 is south, 3 is west. (Or Up, Right Down, Left, respectively) It should import: import java.io.FileNotFoundException; & import java.0.10Exception; You must implement the following methods in this class: StartSearch(String filename) This is the constructor for the class. It receives as input the name of the file containing the description of the map. In this method you must create an object of the class Map (described in the provided files) passing as parameter the given Input file; this will display the map on the screen. Read them if you want to know the format of the input files, static void main(String[] args). This method will first create an object of the class StartSearch using the constuctor StartSearch(args[0]). Argstop will be the name of a map file, args[1] will be the number of cells that the arrow can travel before it falls to the ground. if and only if a size argument is provided, your algorithm should count how many targets can be found in a path that is at most args[1] long with the number of arrows determined by the map. When you run the program, you will pass as command line arguments the name of the input file (see following section after Java classes), and the number of cells that Cupid can hit from his starting point to find target along with the number of arrows. Your main method then will try to find a path from Cupid to the targets according to the restrictions specified above. The algorithm that looks for a path from the initial cell to the destinations must use a stack and it cannot be recursive. Suggestions on how to look for this path are given in the next section. The code provided to you will show the path selected by the algorithm as it tries to reach the target cells, so you can visually verify if your program works. The main method should exit by printing out the number of targets found given the restrictions above (maximum arrow length, maximum number of arrows, Cupid won't shoot down the same path twice. MapCell nextCell/MapCell cell). The parameter is the current cell. This method returns the best cell to continue the path from the current one, as specified early in the limitations. Refer to those priorities when coding this section. of several unmarked cells are adjacent to the current one and can be selected as part of the path (remember the arrow will stay on the same path first), then this method must return one of them in the following order: - A target cell A cross path cell . If there are several possible cross path cells, then the one with the smallest index is returned. . A vertical path cell or a horizontal path cell with smallest index . Read the description of the class MapCell below to learn how to get the Index of a neighbouring cell . If there are no unmarked cells adjacent to the current one that can be used to continue the path, this method returns null Your program must catch any exceptions that are thrown by the provided code. For each exception caught, an appropriate message must be printed. . The message must explain what caused the exception to be thrown. You can write more methods in this class but they must be declared as private
