COMP10002 Foundations of Algorithms

Semester 1, 2025

Assignment 1: Exploring Spaces

Due: 11:59 pm Friday 02 May 2025

Version: 1.4.2

April 28, 2025

IMPORTANT NOTES:

•  Clarified where to write bonus challenge code (V1.4.2)

•  Please be aware that we have changed the submission location to be on GRADESCOPE, instead of ED. You will need to submit one file a1 . c onto the grade-scope submission tab.

•  Please note that the auto-grader on gradescope will provide sugges- tions on your coding style. that will contribute to the style. mark.

•  The expectations for Task 2 have been further clarified.

•  For the bonus challenge we have made it count for 1 bonus mark

Please see the FAQ for instructions on how to submit the assignment.

At some point in time you may have seen one of these...  You have prob-

ably even encountered them in a variety of video games from Pac-man to Animal Crossing...

Or maybe you have heard the myths of labyrinths with monsters hidden in their depths...

This is because spatial exploration puzzles, like mazes are one of the old- est form. of playful activities we have.

We live a world where we are constantly physically exploring and nav- igating with our bodies.  So it’s almost a no-brainer that we would see this kind of activity show up in our play. Spatial exploration puzzles span many different types of navigation problems, but for today we will focus on one called pathfinding.

Pathfinding is the act of finding a possible path between two locations. Of- ten we are looking for the shortest-path, but sometimes we may look for other types of paths. In modern games, pathfinding is used to tell charac- ters how to move through the world. When people are chasing you in the Untitled Goose Game, or your Sim can’t get out of the pool because you deleted the ladder, those are examples of path finding at work.

For this assessment, we are going to be putting our algorithmic thinking to the test by exploring simple pathfinding.

About the Assignment

Assignment Structure

Like a game, this assignment is divided into levels with different tasks. Like any good game, each subsequent level builds on the skills and tech- niques you used in the previous level. We recommend trying them all in order for this reason.

To help get you started, each level will outline the problem, your require- ments for the level, any information about the problem space that may be useful to you, and an example of output from one of the provided test files.  Occasionally we will also highlight helpful hints and tips in a blue box like so:

Hey! Listen!

This is an example of what a hint/tip will look like.

Bonus Challenge:

At the end of the assignment, there is a skill-testing bonus challenge. The bonus challenge is a slightly more advanced problem that you are invited to try. There is one bonus mark associated with this.

Learning Outcomes

By completing this assessment you will demonstrate your understanding of the following coding concepts:

•  Input processing,

•  Control structures (conditionals and loops), •  Functions, and

•  Arrays.

You will also be demonstrating your algorithmic problem solving skills, particularly showing how you understand searching problems and recur- sion.

Getting Started

For this assignment, you will be given the following:

•  a skeleton code file (a1. c) with a semi-complete main function, a set of function prototypes for you to complete, and comment space for your answers to written questions;

•  a set of test input files for the various levels (test0 . txt, test1 . txt, test2. txt); and,

•  examples of correct outputs for the test files both in this document,

and as a set of files such as (test0-level1-out. txt, test0-level2-out . txt, test0-level3-out. txt, test0-level4-out. txt) etc.

Before you start coding, you need to get to know the structure of the game. After reading this assignment and the FAQ at the end of this document, spend time familiarizing yourself with  (a1. c).  Pay attention to the vari- ables, constants, and function prototypes already in-place.  These will be useful hints at how to complete the functions later!

And remember, Algorithms are fun!

Level 1: Hello World? [4 marks]

In order to do any pathfinding, we need a representation of a “world” that we can move around in. But how do we represent that on a computer?

There are a variety of ways, but for simplicity we can think of our world like a map with a grid imposed on top of it.  This way every location on the map has an x and y coordinate that tells us where on the map it is.

We can extend this understanding to think about our map as a two-dimensional array. Every element of this 2D array is the relevant structure at that  (x, y) point.  For example, imagine a world where there are walls blocking our path; the array could store a symbol of a wall at the real wall’s (x, y) location to show us that it is there.

This leads us to our first task: create the map for our world!

Requirements

To successfully complete this level you must:

1.  Complete the function FillMap() so it can read in the map data from the test file;

Hey! Listen!

We are running your code using input redirection (using < in commandline) to pass the test file to program so you can use the standard input functions, like scanf! To have a closer look at the command we are running, see the BUILD HELP . txt file in the skeleton code folder we have provided.

2.  Complete a function called PrintMap() that prints out the map to the terminal screen; and,

3.  Save the starting and ending locations you found to the appropriate variables in the main function.

Hey! Listen!

Think about how this task interacts with C scopes, and what tools we have to manipulate variables in different scopes.

What we know about the problem

File structure.   The input file will always contain at least 3 lines of data.

•  Line 1:

– Two positive integers representing the row (y coordinate) and column (x coordinate) of the STARTING position

•  Line 2:

– Two positive integers representing the row (y coordinate) and column (x coordinate) of the ENDING position

•  Line 3:

– One positive integer representing the number of obstacles (i.e. BLOCKS) on the map

Depending on the number of blocks, the input file will also have the coor- dinates for those blocks.

Map size.   To make the process easier, we have fixed the map size as a square grid. The specific size value is defined as a preprocessor directive using #define!N at the top of the  (a1. c) file.  During graded testing this number and the input we test on may change. So when creating your code, make sure it can scale with the map size.

Location information.   You can assume for this input that we will not put the starting, ending, and/or blocks in the same location. This means the start and end will not be the same place. This will be true for all tests.

Sample Output

Your output for the Level given the same test file, should look like Fig. 1.

Figure 1: Example of expected output for Level 1 using test2 . txt

Level 2: Na…ıve Pathfinding [6 marks]

Great! Now we have our map rendered in the computer and know where the starting and ending points!

We now want to start working towards finding our way from the starting point to the exit point! Let’s start by taking a somewhat intuitive approach we will call na¨ıve pathfinding.

See requirements for a description of the algorithm below. Fig. 2 renders what the map would look like after each step.

Figure 2:  Example of each step the path would take for Level 2 using test2 . txt

For your second task, you will need to implement the described function and answer some questions about it.

Requirements

To successfully complete this level you must:

•  Complete the function SimpleDirections() so it can both render a path between the starting and ending space using +, and output the number of steps needed to reach the end. The pathfinding must use the following logic:

– From the starting point, the path will always try move along the rows towards the row containing the end point,

– If the path hits a block, it will move left or right one column in the direction towards the end point,

– The path will repeat the previous two steps until it reaches the correct row.

– The path then begins to move across the columns in the direc- tion of the end point.

– If at any stage, you cannot make a move following the above rules you must stop.

•  Modify the skeleton code, so that in the case that you have no more valid moves from the above algorithm, so that it now prints "SimpleDirections took N steps and got stuck. \n\n", and then the map instead of

"SimpleDirections took N steps to find the goal. \n\n"and then the map, where N is the number of steps taken before not having any valid moves or reaching the end point.

•  Answer the following questions in the comment section indicated at the end of your a1 . c file:

– List some cases where this process will not produce our ex- pected result of reaching the end point? Why is this?

Hey! Listen!

Think about how the assumptions we have to make about the problem space (i.e. the map).

– Do you think this process will beefficient for bigger maps? Why, or why not?

What we know about the problem

Assumptions about the map.   At this point you can assume the follow- ing information:

•  We have provided an example in Fig. 4 of the expected output.

•  There is only one starting and one ending position.  However, you should consider that the starting and ending positions could be any- where on the map grid.

Sample Output

Your output for the Level given the same test file, should look like Fig. 3 or Fig. 4.

Figure 3: Example of output from Level 2 using test2 . txt input.

Figure 4: Example of output from Level 2 using test3 . txt input.

Level 3: Closest Neighbours [4 marks]

Hooray that’s one way to find a path to the end! Let’s try to come up with another (slightly more generic) process!

Intuitively, we may want to start by finding a valid (i.e. unblocked, empty) space adjacent to our starting space — i.e. its neighbour. If we then move into that new valid space, we can repeat the search process by just looking for the next adjacent empty space.  In this way, we are not pre-emptively deciding on the direction of our search, and so we do not need to give our search an end point. We call this process Closest Neighbours.

Our third task, is to implement this Closest Neighbours algorithm as discussed. Fig. 5 illustrates what the path looks like on the map at every step of this Closest Neighbours algorithm.

Figure 5:  Example of each step the path would take for Level 3 using test1.txt

Requirements

To successfully complete this level you must:

•  Complete the function ClosestFreeNeighbour() to find a path from a known starting position to an unknown ending position using the following logic:

– Check if your neighbour is empty, and if yes then move to it

– We check the neighbours in the following order:

1.  Above

2.  Right

3.  Down

4.  Left

– We end the function once we find the ending position or there is no available neighbour to move to.

What we know about the problem

Assumptions about neighbours.   We know that any individual location will have at most four (4) neighbours: above, right, down, and left. Based on this we should be able to know where a neighbour is relative to our current location.

Structure of the process.   We can see that this process requires complet- ing the same process on a smaller version of the same problem.  We can leverage this to approach this problem using a particular technique that we covered in lecture.

Hey! Listen!

Think about the Triangles and Tower of Hanoi example from lecture!

Assumptions about Map data.    

This function is not needed in the current iteration of the program that runs each level with a seperate instance of the program, it does however still exist within the program.

Sample Output

Your output for the Level given the same test file, should look like Fig. 6.

Figure 6: Example of output from Level 3 using test2 . txt input.