National University of Computer and Emerging Sciences
School of Computing Spring 2023 Islamabad Campus
CL2001: Data Structures
2022 Lab (Spring
2023)
Semester Project
(Deadline: 7th May 2023, 11:59 PM)
Project groups: This project can be done within a group of three (3) students. There is no restriction
on the selection of group members. Students are allowed to make groups according to their
preferences. However, the group members must belong to the same data structure lab section.
Submission: All submissions MUST be made using the google form. Solutions sent to the emails will
not be graded. To avoid last minute problems (unavailability of Internet, load shedding, Internet down
etc.), you are strongly advised to start working on the project from day one.
Combine all your work (solution folder) in one .zip file after performing “Clean Solution”. Submit zip
file on Google Form within given deadline. If only .cpp file is submitted, it will not be considered for
evaluation. The naming convention for the zip file is rollno1_rollno2_rollno3.zip
Deadline: Deadline to submit project is 7th May 2023, 11:59 PM. No submission will be considered
for grading outside Google Form or after 7th May 2023, 11:59 PM. Correct and timely submission of
project is responsibility of every group; hence no relaxation will be given to anyone.
Plagiarism: -100% marks in the project if any significant part of project is found plagiarized. A code
is considered plagiarized if more than 20% code is not your own work.
Project Title: "The Quest for the Crystal Kingdom"
Scenario:
The player is on a quest to retrieve a legendary crystal from a dangerous and enchanted forest. The forest
is filled with enemies and obstacles, and the player must navigate through it to find the crystal. The player
has a map of the forest, which shows the location of the crystal and the player's current location (always
(0,0)). However, the map is not detailed, and the player must explore the forest to find the best route to
the crystal.
In the forest, the player must defeat enemies and overcome obstacles to progress through the journey. The
player can also collect reward items that will help them on their journey.
Tasks:
Implement an AVL tree to store the player's inventory of item scores. The AVL tree should allow
the player to add and remove item scores (based on rewards). The first generated id should be 100.
The rest of ids will be generated randomly (0-200). All nodes beside the root should be inserted
based on the value of id.
o The node class/structure should be maintained as follows:
class Node
{
int id; //generated randomly
int reward_score; //score of a particular reward you obtained
int count; //to avoid duplicate id nodes (maintain count of the id)
Node *next;
Page 1 of 4
National University of Computer and Emerging Sciences
School of Computing Spring 2023 Islamabad Campus
2022
}
Implement Floyd's algorithm to calculate. the shortest path between any two areas in the forest.
The algorithm should take into account the locations of enemies and obstacles
Implement Prim's algorithm to find the minimum spanning tree of the forest. The algorithm should
take into account the locations of enemies and obstacles.
Implement Kruskal's algorithm to find the minimum spanning tree of the forest. The algorithm
should take into account the locations of enemies and obstacles.
Implement Dijkstra's algorithm to find the shortest path from the player's current location to the
crystal. The algorithm should take into account the locations of enemies and obstacles.
Note: You can specify the weights of the edges towards the obstacles as 100, all other edges have a
weight of 1.
Details of the Game Map:
The game map is built with alphabets and special characters specified in the key given below. A sample
map is given in figure 1.
C: Clear path
J: Jewel
P: Potion
W: Weapon
%: Death point
#: Obstacle
&: Dragon
$: Goblin
@: Werewolf
*: Crystal (goal point)
Figure 1: A sample Game Map
Page 2 of 4
National University of Computer and Emerging Sciences
School of Computing Spring 2023 Islamabad Campus
The map has the following entities: 2022
i. Safe paths: These are the nodes where you (the character) can move without any restriction.
ii. Obstacles: These are the nodes from where you should not move any further since the weights
of their edges are costly. The player should choose an alternate path on encountering an
obstacle.
iii. Rewards: These are the nodes on which you visit to collect items such as Jewels, Weapons,
and Potions. On collecting a jewel, weapon, or a potion, you will get +50, +30, and +70,
respectively in your score.
iv. Enemies: These are the nodes that if you visit them, one of your reward item will be removed
from the item inventory based on the following three enemies:
a. If you visit the node with a Werewolf, you will lose a weapon.
b. If you visit the node with a Goblin, you will lose a potion.
c. If you visit the node with a Dragon, you will lose a Jewel.
Note: Losing a reward will decrement the score for that reward as well.
v. Death points: These are the nodes that if you visit on them, you will die. You will have to
restart the game from the starting point.
Expected Outcomes:
1. The shortest path between any two areas in the forest.
2. The shortest path from current location.
3. The minimum spanning tree of the forest by both algorithms.
4. The score increased/decreased at every step, and the final score at the end.
5. The menu must have these features but is not limited to
Shortest path using default location (0,0) by Floyd/ Dijkstra.
Shortest path using custom location (coordinates entered by the user) by Floyd/ Dijkstra.
Minimum Spanning Tree by Prims and Kruskal.
Restrictions:
The algorithms should be implemented from scratch, without using any pre-built libraries or APIs.
The program should be written in C++ and should be well-documented and easy to understand.
Page 3 of 4
