代做COSC1076、代写Programming Techniques、代写C++设计、C++程序语言调试

日期：2019-08-03 11:45

School of Science

COSC1076 Advanced Programming Techniques

Assignment 1

Assessment Type: Individual assignment; no group work. Submit online via Canvas→Assignments→Programming

Assignment 1. Marks awarded for meeting requirements as closely as possible. Clarifications/updates may be made via

announcements/relevant discussion forums.

Due date: 23:59pm, 25/Aug/2019; Deadlines will not be advanced but they may be extended. Please check

Canvas→Syllabus or via Canvas→Assignments→Programming Assignment 1 for the most up to date information.

As this is a major assignment in which you demonstrate your understanding, a university standard late penalty of 10% per

each working day applies for up to 5 working days late, unless special consideration has been granted.

Weighting: 15 marks

1.1 Overview

In this assignment you will implement a simplified algorithm for Path Planning, and use it with a simple simulated 2D robot moving

around a room.

In this assignment you will:

Practice the programming skills covered throughout this course, such as:

– Pointers

– Dynamic Memory Management

– Provided API

Correctly Implement a pre-defined API

Implement a medium size C++ program

Use a prescribed set of C++11/14 language features

This assignment is divided into four Milestones:

Milestone 1: Writing Unit Tests

Milestone 2: Minimum required component for implementing a simple Grid Search

Milestone 3: Optional component to extend the search for a simplified path planner

Milestone 4: Optional component for efficient memory management

If there are questions, you must ask via the relevant Canvas discussion forums in a general manner (replicate your problem in a

different context in isolation before posting).

1.2 Relevant Lecture/Lab Material

To complete this assignment, you will require skills and knowledge from lecture and lab material for Weeks 2 to 4 (inclusive).

You may find that you will be unable to complete some of the activities until you have completed the relevant lab work.

However, you will be able to commence work on some sections. Thus, do the work you can initially, and continue to build in new

features as you learn the relevant skills.

1.3 Start-up Code

On Canvas you will find starter code to help you get running with the assignment. This code includes:

Header files, of the API (C++ classes) that you will implement

Dummy (empty) code files, for you to implement

Unit Testing code, to help you write and run tests on your implementation

Example Unit Test case(s)

,

Page 2 of 11

2. Learning Outcomes

This assessment is relevant to the following Learning Outcomes:

1. Analyse and Solve computing problems; Design and Develop suitable algorithmic solutions using software concepts and

skills both (a) introduced in this course, and (b) taught in pre-requisite courses; Implement and Code the algorithmic

solutions in the C++ programming language.

2. Discuss and Analyse software design and development strategies; Make and Justify choices in software design and

development; Explore underpinning concepts as related to both theoretical and practical applications of software design

and development using advanced programming techniques.

3. Discuss, Analyse, and Use appropriate strategies to develop error-free software including static code analysis, modern

debugging skills and practices, and C++ debugging tools.

4. Implement small to medium software programs of varying complexity; Demonstrate and Adhere to good programming

style, and modern standards and practices; Appropriately Use typical features of the C++ language include basic language

constructs, abstract data types, encapsulation and polymorphism, dynamic memory management, dynamic data structures,

file management, and managing large projects containing multiple source files; Adhere to the C++11/C++14/C++17 ISO

language definition and features.

5. Demonstrate and Adhere to the standards and practice of Professionalism and Ethics, such as described in the ACS Core

Body of Knowledge (CBOK) for ICT Professionals.

3. Assessment details

One challenge in robotics is called path planning. This is the process of the robot figuring out how to navigate between two points

within some environment. In this assignment you will implement a simplified path planning problem for a robot moving about a

simple 2D maze.

In this assignment, the simple 2D maze will be represented as a grid of ASCII characters. For example:

Aspects of the maze are represented by different symbols:

Symbol Meaning

. (dot) Empty/Open Space. The robot can enter any open space.

= (equal) Wall or Obstacle within the maze. The robot cannot pass obstacles

~ (tilda) The edge of the maze. Every maze is always bounded by the edge symbols

Each location in the maze (including the maze edges) is indexed by a cartesian (x,y) co-ordinate. The top-left corner of the maze

is always the co-ordinate (0,0), the x-coordinate increases right-wards, and the y-coordinate increases down-wards. For the

above maze, the four corners have the following co-ordinates:

(0,0) . . (12,0)

(0,6) . . (12,6)

For the purposes of this assignment we will make two important assumptions:

1 The robot knows the map of the whole maze

2 It may not be possible for the robot to reach every empty space

For this assignment, the robot:

May only be located at cells with empty spaces.

The robot can move to any one of 4 cells, that are to the left, right, up, or down from the robots originating cell.

For this assignment the direction the robot is “facing” is ignored.

,

Page 3 of 11

!

In worked examples, the robot’s position will be marked by a star *.

For example, if the robot is at position (8,2):

then the robot could move to positions (8,1) or (8,3).

3.1 Reachable Positions

For this assignment, you will develop a simplified path planning solution1

. In Milestone 2 you will develop a base algorithm, which

can be used in Milestone 3 to develop the path planning algorithm.

The Milestone 2 algorithm, is given the starting position of the robot and calculates:

All possible locations that the robot can reach from x

The number of spaces that each position is from x, which is equivalent to the number of moves the robot would need to make to

reach each position.

This algorithm is given below.

To conduct this algorithm, each position must be annotated by the distance that the position is from the robot’s starting position, x.

Pseudocode for Milestone 2: Generate all Reachable Positions

Let x be the starting position of the robot with distance 0

Let P be a list of positions the robot can reach, with distances (initially contains x)

Let T be a temporary list (initially empty)

repeat

| Select an item p from P that is not in T

| foreach Position, q that the robot can reach from p do

| | Set the distance of q to be one more than the distance of p

| | Add q to P if and only if there is no item in P with the same co-ordinate as q

| end

| Add p to T

until No such position p can be found

3.2 Worked Example

A worked example of stage 1 is given using the above maze.

Let us assume that the robot knows the map, and it’s starting position, x, is at co-ordinate (8,2). To help with annotations, the

distance that the robot is from the starting position, x will added to the co-ordinate to form a 3-tuple:

(<x-coordinate>, <y-coordinate>, <distance>)

For example, as the distance from the starting location is 0, this gives the tuple: (8,2,0).

Initially, P contains the starting location and distance, such that P = [(8,2,0)]. Also initially, the temporary list, T is empty.

In the loop, since P contains one item, it is selected, so that p =(8,2,0). Since T does not contain an item with the co-ordinate of

p, the loop continues. By looking at the map, it is possible to determine all places from p that the robot can reach:

This is a simplified algorithm for the purposes of this assignment. There are many variations in literature, so be careful!

,

Page 4 of 11

These are given below. They are also a distance of 1 from the starting position, x, so they form tuples:

1. (8,1,1)

2. (8,3,1)

All of these are added to P, such that: P =[(8,2,0),(8,1,1),(8,3,1)]. Also p is added to T, such that:

T =[(8,2,0)]. The loop then repeats.

In the 2nd iteration of the loop, an item is selected from P. This item may be:

1. (8,1,1)

2. (8,3,1)

since the item (8,2,0) has a co-ordinate that is in T, it is not considered. For this example, the item (8,1,1) is selected so that

p =(8,1,1), and the loop continues. By looking at the map, it is possible to determine all places from p that the robot can reach:

~ ~ ~

. * .

= . =

These locates are, with their respective distances:

1. (7,1,2)

2. (9,1,2)

3. (8,2,2)

Note that the distance is always one more than the distance in p. The first two are added to P, but the third has a co-ordinate that

is already in P, so it is not added. Thus:

P =[(8,2,0),(8,1,1),(8,3,1),(7,1,2),(9,1,2)].

Also p is added to T, such that: T =[(8,2,0),(8,1,1)]

The loop repeats until it is impossible to find an item in P that does not have the same co-ordinate as an item in T. Eventually P

contains the list of all positions the robot can reach in the maze and the distance to those positions. These will be all but the squares

marked with an x.

~~~~~~~~~~~~~

~...........~

~=======.===~

~xx=...=....~

~xx=.....=..~

~xx=..=..=..~

~~~~~~~~~~~~~

The final cost of reaching each co-ordinate (from starting position (8,2) which has a cost of 0) :

~~~~~~~~~~~~~

~87654321234~

~=======0===~

~xx=765=1234~

~xx=65432=45~

~xx=76=43=56~

~~~~~~~~~~~~~

,

Page 5 of 11

4. Task

This assignment is divided 4 Milestones. To receive a PS grade, you only need to complete Milestones 1 & 2.

To receive higher grades, you will need to complete Milestones 3 & 4. You must complete these milestones in sequence. See the

Marking Rubric on Canvas for more details.

4.1 Milestone 1: Unit Tests

Before starting out on implementation, you need to write a series of unit tests, so that you can test if your implementation is 100%

correct.

A Unit test consists of three text files:

1. <testname>.maze - The complete maze

2. <testname>.initial - The starting position of the robot.

3. <testname>.pos - The list of all position(s) and distances that the robot can reach from the starting position.

4. <testname>.goal - (Milestone 3 only) The goal co-ordinate for path planning

5. <testname>.path - (Milestone 3 only) The path from the starting position to the goal

Your unit tests should be sufficient so that, if all of your unit tests pass, you are confident that your code in 100% correct.

The starter code provides sample unit tests to help you get started These example tests are not sufficient. You will need to write

your own tests!

!

The starter code provides a simple unit testing wrapper to help run your unit tests.

The testing code is executed by: ./test <testname>

4.2 Milestone 2: Reachable Positions with Distances

Your task is to implement the an API that facilitates the simplified path planning algorithm described in Section 3.1 using three C++

Classes:

PostionDistance

PDList

PathPlanning

For each class, you are given the API that you must implement. This API is a set of pre-defined methods on the classes. You are able

to add any of your own code, but you must not modify the provided API.

In addition to implementing the classes:

You must provide some documentation about your implementation.

Your code should be well formatted, following the style guide

Your implementation of the API must comply with the a set of requirements and restrictions.

!

You are implementing an API (set of methods), not a full C++ program. To actually run your code, you will need the unit

testing file provided in the starter code.

Remember you cannot modify the pre-defined methods!

,

Page 6 of 11

4.2.1 PositionDistance Class

The PositionDistance classes represents one co-ordinate (x,y) of the robot within a maze, and the distance of that coordinate

from the starting position. It has three methods that provide the components of the position of the robot.

To help with using Position-Distance’s, the PDPtr type is defined. This is a pointer to a PositionDistance object.

4.2.2 PDList Class

The PDList class provides a method for storing a list of PositionDistance objects, as used in the pseudocode (Section 3.1). It

has one constructor, one de-constructor, and a number of methods.

To implement the PDList you MUST use an array of pointers. To help you with this, the starter code gives an example way for

storing the array of pointers. You are free to change this if you wish.

The PDList class has full control over all pointers that are stored in the list. Thus, if items are removed from the list you must

remember to “delete” the PositionDistance object.

// x-co-ordinate

int getX();

// y-co-ordinate

int getY();

// Distance

int getDistance();

// Pointer to a PositionDistance

typedef PositionDistance* PDPtr;

// Create a New Empty List

PDList();

// Clean-up the list

~PDList();

// Number of items in the list

int size();

// Get a pointer to the position-distance at index i

PDPtr get(int i);

// Add a position-distance (as a pointer) to the list

// This class now has control over the pointer

// And should delete the pointer if the position-distance is removed from the list

void addBack(PDPtr position);

// Checks if the list contains a position-distance with the same co-ordinate

// as the given position.

bool containsCoordinate(PDPtr position);

// Remove everything from the list

// Don't forget to clean-up the memory!

void clear();

PDPtr positions[100];

int numPositions;

,

Page 7 of 11

! Make sure you correctly clean-up the memory used by the PDList!

4.2.3 PathPlanning Class

The PathPlanning class provides an API (set of methods) to implementation of the algorithm in Section 3.1, and a simplified

path planning algorithm. It has three components:

1. Creating the class, using a map of the maze

2. Providing the initial position of the robot

3. The method for Milestone 2 for retrieving the possible positions the robot can reach, along with the distances

4. The path planning method for Milestone 3

The map of the maze is provided in the constructor of the PathPlanning

The maze is provided as a Grid, which is defined as a 2D array (see below). The top-left corner of the 2D array corresponds to the

location (0,0). The parameters rows and cols give the size of the maze.

It is very important to understand what the Grid type is. It is defined as a 2D array (given below). If you recall from lectures/labs, a

2D array is indexed by rows then columns. So if you want to look-up a position (x,y) in the maze, you find this by

maze[y][x], that is, first you look-up the y value, then you look-up the x value.

The initial position of the robot is given to the PathPlanning class through the method

After being given the initial position, the PathPlanning may be asked for all of the possible positions (with distances) that the

robot can reach:

The getReachablePositions method returns a deep copy of the PDList.

!

A deep copy of a PDList is a new list is with a copy of all of the PositionDistance objects.

4.2.4 Code Description

At the top of your PathPlanning implementation you must provide a description of the design of your implementation.

Provide this in a comment-block. This block should:

Describe (briefly) the approach you have taken in your implementation

Describe (briefly) any issues you encountered

Justify choices you made in your software design and implementation

Analyse (briefly) the efficiency and quality of your implementation, identifying both positive and negative aspects of your

software

// Initialise a with a given maze of size (x,y)

PathPlanning(Grid maze, int rows, int cols);

// A 2D array to represent the maze or observations

// REMEMBER: in a grid, the location (x,y) is found by grid[y][x]!

typedef char** Grid;

// The initial position

void initialPosition(int x, int y);

// Method for Milestone 2

// Return a DEEP COPY of the PDList of all position-distance's

// that the robot can reach

PDList* getReachablePositions();

,

Page 8 of 11

4.2.5 Code Style

Your code style will be assessed. It should be well-formatting and comply with the course style guide.

4.2.6 Mandatory Requirements and Restrictions

!

Take careful note. If your submission does not comply with these requirements it will receive a NN grade.

Your implementation MUST:

Your PDList implementation must use an Array of Pointers to store all PositionDistance objects.

Your implementation may:

Add additional methods to the given classes. However, your code will ONLY be assessed using the methods listed in this spec,

and provided in the starter code.

Your implementation MUST NOT:

Alter the definition of the provided methods.

Use the STL containers (such as array, vector, list, deque, map, or any of utility). For this assignment

they are banned. If you are unsure if you can use an STL container, ask on the forum first.

4.3 Milestone 3: Path Planning

!

This is an extension Milestone. You only need to attempt this if seek a DI grade for this assignment.

The PathPlanning class contains an additional method:

This method finds a path from the robot’s starting position to the specified goal co-ordinate. This should contain the ordered

sequence of PositionDistance objects including the starting position and the given goal co-ordinate. You may assume that the

goal co-ordinate can be reached from the starting position.

To solve this problem, you will be able to use the list of reachable positions that is generated in your Milestone 2. The algorithm is

not given to you. However, think carefully about what information is contained in the list, specifically the distance information.

There may also be more than one valid path.

You will need to include additional Milestone 3 tests as part of your submission.

4.4 Milestone 4: Efficient Memory Management

!

This is an extension Milestone. You only need to attempt this if seek a HD grade for this assignment.

For this Milestone, you need implement the classes to use memory as efficiently as possible. Your code should only consume as

much memory as is necessary.

To do this, you may wish to consider the following:

Limiting the size of the array of pointers in PDList to only the number of cells needed to store all of the elements of the list.

Storing the maze in PathPlanning to use only the number of rows and columns given in the constructor

Which class(es) have ownership over any memory, variable or parameter.

// Method for Milestone 3

// Get the path from the starting position to the given co-ordinate

// The path should be a DEEP COPY

PDList* getPath(int toX, int toY);

,

Page 9 of 11

4.4.1 Code Description

Finally, for this Milestone, in your implementation of the PathPlanning class, you must:

Describe (briefly) the approach you have taken in your implementation.

Justify (briefly) why your implementation is efficient.

5. Starter Code

The starter code comes with the following files:

File Description

Types.h Header file the typeedefs used in the assignment

PositionDistance.h/cpp The PositionDistance class

PDList.h/cpp The PDList class

PathPlanning.h/cpp The PathPlanning class

unit_tests.cpp Code file to run unit tests

To compile individual files, into object file for testing, you can use the command:

g++ -Wall -Werror -std=c++14 -O -c file.cpp

5.1. Running Unit Tests

To compile the unit test code, with your implementation into an executable, you can use the command:

g++ -Wall -Werror -std=c++14 -O -o unit_tests PositionDistance.cpp PDList.cpp

PathPlanning.cpp unit_tests.cpp

A unit test can be run with the command:

./unit_tests <testname>

For example, using the starter code

./unit_tests sampleTest/milestone2

5.2. Getting Started

Part of the learning process of the skill of programming is devising how to solve problems. The best way to get started is to try just

give some programming a go and try things out. Experimenting and practising are important to the process of learning the skills of

programming and this course.

6. Submission Instructions

The assignment submission is divided into two ZIP files:

1. Your code solution (in <student_id>.zip>)

2. Your unit tests (in <student_id>_tests.zip)

Upload both ZIP files to the Assignment 1 Module on Canvas.

You may re-submit multiple times, however, only your latest submission will be marked. Be careful, resubmissions after the duedate

are subject to late penalties.

,

Page 10 of 11

6.1. Submitting Code Files (.h/.cpp)

Place all of your code, header files (.h/.hpp) and code files (.cpp) into a single ZIP file. Do not use sub-directories.

The ZIP file must be named by your student number:

<student_id>.zip

For example, if your student number is s123456, your code file submission should be:

s123456.zip

6.2 Submitting Unit Tests (.maze/.initial/.pos)

Place all of your unit test files in a separate ZIP file. You may organise these tests in a clear manner to help us.

!

This must also include what you wrote to test your Milestone 3.

The ZIP file must be named by your student number + the "tests" label:

<student_id>_tests.zip

For example, if your student number is s123456, your unit tests submission should be:

s123456_tests.zip

7. Academic integrity and plagiarism (standard warning)

Academic integrity is about honest presentation of your academic work. It means acknowledging the work of others while

developing your own insights, knowledge and ideas. You should take extreme care that you have:

? Acknowledged words, data, diagrams, models, frameworks and/or ideas of others you have quoted (i.e. directly copied),

summarised, paraphrased, discussed or mentioned in your assessment through the appropriate referencing methods,

? Provided a reference list of the publication details so your reader can locate the source if necessary. This includes material

taken from Internet sites.

If you do not acknowledge the sources of your material, you may be accused of plagiarism because you have passed off the work

and ideas of another person without appropriate referencing, as if they were your own.

RMIT University treats plagiarism as a very serious offence constituting misconduct. Plagiarism covers a variety of inappropriate

behaviours, including:

? Failure to properly document a source

? Copyright material from the internet or databases

? Collusion between students

For further information on our policies and procedures, please refer to the University website.

8. Assessment declaration

When you submit work electronically, you agree to the assessment declaration.

,

Page 11 of 11

9. Rubric/assessment criteria for marking

Weight HD+ HD DI CR PA FL NN

Unit Tests 10% Outstanding

and Flawless

Comprehensive Unit tests

for Milestones 2 & 3,

covering the majority of

common use cases, and

most edge cases

Comprehensive Unit tests

for Milestones 2 & 3,

covering the majority of

common use cases, and

most edge cases

Comprehensive Unit tests

for Milestone 2, covering

the majority of common

use cases, and most edge

cases

Sufficient Unit tests for

Milestone 2, covering the

majorit

Poor (or missing) Unit

tests for any part of the

assignment, with poor

coverage

Not Completed

Unit tests contain no

errors

Unit tests contain no

errors

Unit tests contain no

errors

Unit tests contain no

errors

Unit tests may contain

errors

Software

Implementation

60% Outstanding

and Flawless

Complete and error-free

implementation of

Milestones 2, 3 & 4.

Complete and error-free

implementation of

Milestones 2 & 3.

Complete and error-free

implementation of

Milestone 2.

Complete and mostly

error-free implementation

of Milestone 2.

Incomplete or error

ridden implementation of

Milestone 2.

Not Completed

Compiles with the

Milestone 2 & 4

mandatory requirements

and restrictions.

Compiles with the

Milestone 2 mandatory

requirements and

restrictions.

Compiles with the

Milestone 2 mandatory

requirements and

restrictions.

Compiles with the

Milestone 2 mandatory

requirements and

restrictions.

Failure to comply with the

Milestone 2 mandatory

requirements and

restrictions.

Code Style 15% Outstanding

and Flawless

Exceptional and clear

software design.

Good and clear software

design.

Suitable consideration

given to quality software

design.

Some consideration given

to quality software design.

Poor and messy software

design.

Not Completed

Exceptional coding style

and suitably documented

code. No input from the

developers is required to

comprehend the code.

Exceptional coding style

and suitably documented

code.

Suitable coding style and

suitably documented

code. Code is readable,

but parts of the software

may not be clear

Suitable coding style and

suitably documented

code, but code is

confusing to comprehend

without further

explanation from the

developers

Poor and messy coding

style with minimal

documented code

Excellent use of permitted

C++11/14 language

features.

Excellent use of permitted

C++11/14 language

features.

Excellent use of permitted

C++11/14 language

features.

Sufficient use of permitted

C++11/14 language

features.

Poor use of permitted

C++11/14 language

features.

Code Description

/Report

15% Outstanding

and Flawless

Suitable report for

Milestones 2, 3 & 4, with

good analysis

Suitable report for

Milestones 2 & 3, with

good analysis

Suitable report for

Milestone 2, with good

analysis

Suitable report for

Milestone 2, with limited

analysis

Poor, unclear, and

confusing code

description & report.

Not Completed