BFC5936 Programming Course ,Help With c/c++，Java Programming,PythonHelp With
R Programming| Web
Classification: Private
BFC5936 – Final assessment task
Pathfinding algorithm
Background:
Finding solutions to mazes is usually done as a leisurely activity but finding efficient
solutions to extremely intricate and complicated mazes has been a field that has seem many
uses in the real world. Google maps and Uber are among the many applications that we
interact with on a daily basis using such algorithms. Some famous pathfinding algorithms
include Dijkstra’s algorithm and A*. Whilst knowledge of these algorithms may help you to
understand pathfinding in more detail, you do not need to implement any of these
algorithms to solve this task.
Instructions:
There are three mazes for you to solve:
• easy
• medium
• hard
Each maze is a grid of cells that has been coloured either black, yellow, blue or red. Black
cells are the boundaries or walls of the maze, yellow cells are the path you can follow, the
blue cell is the starting point of the maze and the red cell/s is the finishing point.
Your algorithm will need start at the blue cell (top left hand corner) and move through each
yellow cell (test if the cell colour is yellow) until the red cell/s are found. Each cell you visit,
you must leave behind a sign that you have visited the cell by printing the number of steps it
took you to reach that cell from the starting cell (unless the path ends in a dead end, see
hard maze description). For example, if it is the fifth cell you have visited, you should print
“5” in that cell.
A solved maze is one where your path to the final red cell from the blue cell is laid out by a
series of numbers that denote your path without any jumps, missed yellow cells or any
deviations from the path (printing into black cells). An example of a solved maze is attached
as a screenshot.
A function has been set up and commented for you to complete that should lead to a
solution for the easy maze. Once your function can solve the easy maze, think about how
you can tweak it to accommodate the extra complexities of the medium and hard mazes. An
algorithm that solves the hard maze should be able to solve the medium and easy ones too.
Each maze is equally weighted meaning each is worth 1/3rd of the spreadsheet mark.
Classification: Private
Easy maze:
The yellow path will only go down or to the right. There are no dead ends and only one red
cell.
Medium maze:
The yellow path can go left, down, up, or right. There are no dead ends but multiple red
cells. You must print your path to all the red cells as if each path is considered from the
starting blue cell. This means that any cells that have multiple paths exiting it will have to
have numbers counting equally in each path. A screenshot of a crossroad is attached for
clarity.
Hard maze:
The yellow path can go left, down, up, or right. There are dead ends and multiple red cells.
You must print your path to all the red cells as if each path is considered from the starting
blue cell (just like the medium maze). Additionally, your finished maze should not contain
any numbers in a path that ends in a dead end (no red cell at the end). A screenshot is
attached for clarity. Lastly, this maze is not visible but can be referenced by it’s named
“Hard”.
Tips:
• START WITH A CODE PLAN
o What is the problem?
o How would you solve a maze like this by hand?
o Can you recreate your manual process in code?
• Testing the colour of a cell’s background can be done using the following snippet of
code:
o If range(“a1”).interior.color = RGB(255, 255, 0) then
o RGB stands for Red Green Blue and it is a standard way of reproducing
colours
o The colours relevant to this assessment are:
Blue – RGB(0, 0, 255)
Yellow – RGB(255, 255, 0)
Red – RGB(255, 0, 0)
Black – RGB(0, 0, 0)
• Each maze range can be referenced by its name
o The easy maze can be referenced by range(“Easy”)
o The medium maze can be referenced by range(“Medium”)
o The hard maze can be referenced by range(“Hard”)
If there are any questions,
Classification: Private