代写代做COMP20003 ASSMT3游戏开发程序

日期：2025-10-21 07:37

General Info

You must read fully and carefully the assignment specification and instructions.

Course: COMP20003 Algorithms and Data Structures @ Semester 2, 2025

Deadline Submission: Friday 24th October 2025 @ 5pm (end of Week 12)

Course Weight: 15%

Assignment type: individual

ILOs covered: 2, 4

Submission method: via ED

Purpose

The purpose of this assignment is for you to:

Increase your proficiency in C programming, your dexterity with dynamic memory allocation

and your understanding of data structures, through programming a search algorithm over

Graphs.

Gain experience with applications of graphs and graph algorithms to solving combinatorial

games, one form of artificial intelligence.

Impassable Gate Intro

In this programming assignment, you’ll be expected to build an AI algorithm to solve puzzles

inspired by the Professor Layton and the Lost Future puzzle, Impassable Gate. The puzzle, created

by Akira Tago, asks the player to move the protagonists (the grey block), to the goal position at

the top of the board. The game counts a move as anywhere a piece can slide to unhindered by any

other piece. You can see how this works by looking at the step-by-step solution on the Wiki. The

game can also be found on the Nintendo DS and on mobile devices.

The code in this assignment was adapted from the open-source terminal version of the classic

puzzle game, Sokoban using ncurses made available by CorrentinB.

Game Rules

The game is played on a board of squares, where each square is open space or a wall. Some

open spaces contain parts of pieces, and the Professor Layton and Little Luke piece will always be

on the board. In the simplified AI approach we use, each movement is limited to a single

direction, rather than any open space. Each piece takes up multiple spaces on the board, and all

parts of a piece must move together. If any part of a piece cannot move in the direction (i.e. a

piece already occupies the location, or there is a wall) then no part of the piece can move.

For simplicity of implementation, the Professor Layton and Little Luke piece is always numbered

as piece 0. The pieces are confined to the board, and the goal is always the same size and shape

as the Professor Layton and Little Luke piece. Like the original puzzles, only one goal location is

given.

Puzzle Solution (DS)

An example of solving the first Impassable Gate puzzle is shown in this playthrough:

For the curious puzzle solver

The Science of Impassable Gate

Like a number of puzzles, the problem of finding the shortest Impassable Gate solution can be

formulated as a decision problem. In simple terms, for a given puzzle, we can ask if a solution

exists in kk or fewer steps, we can then - in polynomial time - check that a solution of kk or fewer

steps is a valid solution (i.e. that each move made is valid and that the final state solves the

problem).

NP-complete problems are hard to solve. The best algorithms to solve NP-Complete problems run

in exponential time as a function of the size of the problem and the shortest accepted

solution. Hence, be aware that your AI solver may struggle more as the number of pieces and size

of the board increases. We talked in the lectures about the Travelling Salesman Problem as one

example of an NP-Complete problem. In fact, many real-world problems fall under this category.

We are going to learn more about NP-Complete problems in the last lecture of the course via an

invited talk in week 12.

Interestingly, the naïve approach (Algorithm 1), for a puzzle with nn pieces and kk steps, is

O((4n)k)O((4n)k). The duplicate checking algorithm (Algorithm 2) mostly replicates this worst-case

bound (O((3+4(n−1))k)O((3+4(n−1))k)) for an unbounded sized board, but will be much more

powerful as it avoids re-exploring seen states, and avoids returning to the immediate prior state -

for a bounded board, each board square could potentially have one of each piece, so at most we

would see, with qq being the number of open squares on the board, O(nq)O(n**q) states. The

novelty checking algorithm (Algorithm 3) improves this significantly, reducing the complexity to

O(nqw)O(nqw), where ww is the width of the search. Algorithm 3's worst case (in this puzzle)

happens when the solution is not found until w=nw=n, which leads to O(nq+1)O(n**q+1)

complexity due to re-exploring the puzzle ww times.

References:

Images from HD remake gameplay.

Graph = <V, E> implicit graph

unweighted, directed

########

###GG###

###HH###

# 00 #

## ##

# #

# #

# #

# #

########

########

###HH###

###HH###

# #

## ##

# #

# #

# #

# #

########

########

###GG###

###GG###

# 00 #

## 00 ##

# #

# #

# #

# #

########

dfs

Iterated Width (IW) Search

Iterative Deepening is a search algorithm that works similarly to depth-first search, but with a

small change, whenever we reach the current depth limit, the search does not generate any

successors (next moves). Once no more search nodes are generated, the search stops and we

increase the depth limit by one, then repeat the search from the start.

Iterated Width Search is a search algorithm that works similarly to breadth-first search, but any

node which is reached which has been seen before does not generate any successors. A more

nuanced version of "seen before", known as novelty, is how this algorithm makes its gains. For

this algorithm, any node which has a higher novelty rank than the current *width* limit of the

search does not generate any successors. A state which has been fully seen before has

maximum novelty rank. Once no more search nodes are generated, the search stops and we

increase the *width* by one, then repeat the search.

Iterated Width (IW) search

The novelty of a state is the size of the smallest combination of atoms that have been true

together for the first time. For example:

seen: {(2,2,3)}, {(1,3,2)}

{(2,2,3), (1,3,2)}

If at(1,3,2) has never been true until this state, the novelty is 1 , because we only need to

look at one atom to see something we haven't seen before.

If the piece 1 has been at (3,2) and the piece 2 has been at (2,3) separately before, but

piece 1 has never been at (3,2) with piece 2 at (2,3) before, then the novelty is 2 ,

because we need to look at this combination of two atoms to see something we haven't

seen before.

If at(1,3,2) , at(2,2,3) and at(3,3,3) are all true in a given state, and all combinations

of those pairs (i.e. at(1,3,2) and at(2,2,3) , at(1,3,2) and at(3,3,3) , at(2,2,3) and

at(3,3,3) ) have been true in previous states, but this state is the first time we've seen these

three atoms true together, then the novelty is 3 , because we need to look at this

combination of three atoms to see something we haven't seen before.

In Iterated Width (IW) search, we start at width 1 (referred to as IW(1)), and then increase the

width after the search generates no new nodes and restart from the root. The maximum novelty

of a state is the maximum number of atoms that can be true in any state + 1. This value is

assigned to a state if all its combination of atoms have been seen before in the search. When the

maximum width k = max number of atoms is used, **IW(k)** becomes a breadth first search

of the full problem with duplicate states excluded.

To see the advantage of novelty, let's consider a puzzle:

In this puzzle, assume we can slide the red and yellow square, and we want to reach the green

square. Looking at the first level of the novelty 1 search tree, we see it runs the same way as

breadth first search:

But we see a difference on the next level. We look first at the left node (where red has moved left),

three moves are generated:

Yellow moves right - this state is eliminated because we have seen the yellow block in the

second column before (on the first level). In particular, it has novelty 2, because we need to

look at the position of the red and yellow block to see something new.

Red moves left - this state is eliminated because we have seen the yellow block in this

column, and the red block in this column (in the zeroth level). In particular, it has novelty 3

(assuming we only have 2 atoms in a state), because we have seen this state in its

entirety before.

Red moves right - this state remains because we have not seen the red block in the third

column before. In particular, it has novelty 1, the current width of the search.

Completing this level of the tree, two new states are retained in the search, similarly from the right

node:

level 0: [(R,0,0), (Y,1,0)]

level 1: [(R,0,1), (Y,1,0)], [(R,0,0), (Y,1,1)]

level 2: [(R,0,2), (Y,1,0)], [(R,0,0), (Y,1,0)],[(R,0,1), (Y,1,1)], [(R,0,1),

(Y,1,1)], [(R,0,0), (Y,1,2)], [(R,0,0), (Y,1,0)]

level 3: ...................................

w=1

seen:

size = 1 {(R,0,0)}, {(Y,1,0)}, {(R,0,1)}, {(Y,1,1)}, {R,0,2}

Assessment:

Solver (finds solutions for capability test cases) [4

marks]

[0.5 marks] ILO 4 – Able to find solutions that require moving from the starting location (test

case 1)

[0.5 marks] ILO 4 – Able to find solutions that require more than one state exploration (test

case 2)

[0.5 marks] ILO 4 – Able to find solutions to single l/r moves (test case 3)

[0.5 marks] ILO 4 – Able to find each single move solution (u,d,l,r) (test case 4)

[0.5 marks] ILO 4 – Able to find a 2-move solution if the same move is made (test case 5)

[0.5 marks] ILO 4 – Able to find 2-move solutions (up to test case 7)

[0.5 marks] ILO 4 - Able to move pieces out of the way, but may not be able to handle extra

pieces that don't need to move (up to test case 9)

[0.5 marks] ILO 4 - Able to solve puzzles even when it is necessary to move pieces out of the

way (all test cases)

These all involve the implementation of given algorithms. It is necessary to utilise the radix tree

data structure to implement the novelty-based search, though its implementation isn't assessed in

this assignment.

Memory correctly freed [1 mark]

[0.5 marks] ILO4 - Able to free memory of growing memory usage elements (i.e. states) in the

context of implementing a given algorithm.

[0.5 marks] ILO4 - Able to free memory of constant memory usage elements (e.g. initial state

data, etc.) in the context of implementing a given algorithm.

These all involve adding to the given algorithm to handle the return of memory once it is no longer

needed, in the context of this problem, this is likely necessary to achieve puzzle solving under the

more challenging memory constraints of Ed.

Memory is free of errors [1 mark]

[0.5 marks] ILO4 - Able to implement the given algorithm in C for solving the puzzles without

significant enough errors to affect the output.

[0.5 marks] ILO4 - Able to implement the given algorithm in C for solving the puzzles, applying

a systematic approach to eliminate all errors detectable through Valgrind memory checking.

These all involve the implementation of the given algorithm. A number of minor errors might

appear that don't affect the output, this set of standards is meant to capture your ability to resolve

those errors.