question archive Consider a rectangular grid (width x height) in which it is possible, at each turn, to move from one square to another adjacent square
Consider a rectangular grid (width x height) in which it is possible, at each turn, to move from one square to another adjacent square
Subject:Computer SciencePrice: Bought3
Consider a rectangular grid (width x height) in which it is possible, at each turn, to move from one square to another adjacent square. When KingMode=false, one can move only up, down, left and right, whereas when KingMode=true, one can also move in the four diagonal directions. One wishes to go from the source (start point) to the target (end point) in a minimum number of moves. Obviously, regardless of the value of KingMode, one must stay within the boundaries of the grid. The upper left-hand corner is considered (1,1) and the bottom right-hand corner is considered (w, h) where w is the width and h is the height.
Some of the squares in the grid, however, will already have people in them, and due to "social distancing" concerns, it is forbidden to enter those squares, and one will need to move around them. A list of these squares will be provided as part of the input.
The goal is to compare algorithmic methods for finding a low-cost path between the source and target.
Input:
The numbers shown are just placeholders and actual numbers will vary. Comments denoted by "#" are for illustration purposes.
Width=15 # the width of the rectangular grid
Height=12 # the height of the rectangular grid
Source=7,1 # the x and y coordinates of the start point (1 ≤ x ≤ width; 1 ≤ y ≤ height)
Target=14,11 # the x and y coordinates of the end point (1 ≤ x ≤ width; 1 ≤ y ≤ height)
KingMode=true # whether or not one can also move diagonally - may be true or false
# cells where people are already found and must be avoided
Person=3,5
Person=6,4
Person=8,12
Person=15,2
Person=7,9
Person=14,3
etc.
Methodology:
Implement 2 algorithms to find a "good" solution.
One algorithm must be A*-Search with an appropriate heuristic and Depth First Search. Note that the implied underlying graph is not weighted, as there is no difference in cost between any valid moves.
Output:
Start by drawing the game grid. You can use the following simple text format corresponding to the example above
(Text format PIC at the end)
For play and/or debugging purposes, You want to also print out the grid as your "man" moves from the Source to the Target.
A summary table should include, for each algorithm
- The number of operations
- The path taken from source to target
- The number of moves in the pathf
