Repository files navigation

This is a university project at FIIT STU, Bratislava, Slovakia.

Resonance cascade at Black Mesa has caused massive damage to the society of the modernEarth. 7 Hour War brought Combine tyrany upon whole planet. But these events had effectnot only on the future of the humanity, but also on its past.

As multi-dimensional portals were opening around the whole globe, they were causingtearing between parallel universes. Present and the past were colliding. During this chaos,Ancient Dragon from foreign galaxy has entered skies of the medieval Europe.Reigning fear and death, people were certain that this was the end of the world.

Dragon breathed fire upon countries and burned thousands of men, women, and children.Noone could stop him. But he was not just an animal, self-aware and hehad plans for the Earth. He wanted to control all of the kingdoms and become the soleEmperor.

His first action towards his plan was to kidnap princesses of the Samhradh royal family.King Samhradh was devastated, but he wanted his daughters back! So he anounced an enormousaward to anyone who could manage to slay the dragon and return princesses back home. But toKing's disappointment, there was noone willing to risk his life... Except one person.

After few days since kidnapping, a mysterious knight arrived to Samhradh Castle. Hepromised to the King that he would slay the beast and bring back all of his daughters.Hope filled King's heart and he promised that he would double the award if the mysteriousknight would succeed in his mission. So he set horses towards the Dark Mountain, where theAncient Dragon had taken Samhradh princesses.

When he arrived to the foot of the mountain, he saw a massive labyrinth of passages throughsharp cliffs. This was the only way to proceed towards the dragon... Before he entered thelabyrinth, he heard a strainge voice behind his back. When he turned, he saw an elderlyman with a covered face. Man spoke:

"You cannot defeat him when he is awake. You must wait... thenyou shall strike. Make haste, for now his slumber begins..."

Save Princesses - is a small program to solve maze like maps with the goal to slay thedragon, before he wakes up, and save all of the princesses that he has kidnapped.

Program receives 2 dimensional array of characters that represents the maze, as wellas the wake parameter of the dragon. Set of allowed characters is defined as follows:

Input can be provided in the form of a file (one map per file), where first line of thefile contains three numbers:rows,cols,dragon's wake parameter. Rest of the filemust containrows amount lines, where each line length equalscols. Each charactermust be from the set of the allowed characters.

File path can be provided as an argument for the program. For example:

$ save_princesses data/map

wheredata/map stands for the filepath. When program is called with an argument, itsolves the labyrinth provides an output to the console and exits. If file was not foundor could not be opened, program will fallback to the interaction mode.

This project comes with an interaction tool which launches when no filepath for thelabyrinth is specified as a command line argument, or if opening of the specified filehad failed.

After launching, interaction tool will greet you with the commands list:

You can compile program with the providedMakefile. It will compilesave_princessesprogram intoout folder relative to the project directory. Make sure you havemakeandgcc installed on your system, then simply run:

$ make

If you wish to run provided test scenarios, you can compile them by providing additionalargumenttests to the make:

$ make tests

Tests executable file will be put into the sameout folder. In an old UNIX fashion, ifeverything is ok, running the executable won't produce any output to the console. However,if you wish to see what functions are being tested and what results are being produced,you can provide an additional--verbose or-v argument to the test program:

$ out/tests --verbose

This will run tests and output information about test functions to the console.

Project contains implementations of Dijkstra's shortest path algorithm (SPA), min-heap,and stack. Min-heap and Dijkstra's SPA are used to solve mazes: kill the dragonand save the princesses before the dragon wakes up. Stack is used for generating mapsfor testing purposes.

As mentioned above, Dijkstra's SPA and min-heap were used for maze solving.Dijkstra's algorithm works as BFS (breadth first search), but with a priority queue.

To solve the maze, it is converted to an undirected graph. All walls and intermediateroads are skipped.

When looking for the shortest path between two nodes of the graph, we start with an emptypriority queue (heap):

structPath*find_shortest_path(structGraph*graph,intstart[2],intdest[2]){structHeap*heap=new_heap(graph->nodes_count);...}

We create a boolean array that tells us which nodes we already have visited. Then We setour start node's priority to0, because we are already on that node, and for the rest ofthe graph we set all of its nodes priorities toinfinity, or as in our case, toINT_MAX, which represents that we haven't visited those nodes yet, and we don't knowhow far they are:

boolvisited[graph->rows*graph->cols];memset(visited,0,sizeof(bool)*graph->rows*graph->cols);reset_priorities(graph);graph->nodes[start[0]][start[1]].priority=0;

Then we insert start node into our queue:

insert(heap,&graph->nodes[start[0]][start[1]]);

Finally, we enter the main loop which runs until the queue is empty, or we've found ourdestination, in which case we justbreak out of the loop.

Each iteration we extract (pop) the minimum value in our queue, which is always on thetop, and check if it is our destination. If yes, then we exit the loop. Otherwise we checkits neighbours, and if they were not visited, we compute their priority relative to thecurrent node, and if it is less then their current priority, we update them and insertthem into our queue:

while (!isempty(heap)) {node=extract_min(heap);if (node->row==dest[0]&&node->col==dest[1])break;for (inti=0;i<DIRECTIONS_COUNT;i++) {structNode*neigh=node->neighbours[i];if (!neigh||visited[(neigh->row*graph->cols)+neigh->col])continue;intpriority=node->priority+calc_distance(node,neigh);if (priority<neigh->priority) {set_priority(node,neigh);insert(heap,neigh);}}visited[node->row*graph->cols+node->col]= true;}

This algorithm is guaranteed to find the shortest path between two nodes of the graph.

After scanning the maze and discovering all of the key nodes (dragon and princesses), weneed to compute the most optimal path from the dragon to each princess. This can beachieved with a permutation of all possible paths:

staticvoidpermute(inttargets[][2],intstart,inttargetsc,intresults[][2],int*offset) {if (start==targetsc) {for (inti=0;i<targetsc;i++)copy_pos(results[*offset+i],targets[i]);*offset+=targetsc;return;}for (inti=start;i<targetsc;i++) {swap_pos(targets[start],targets[i]);permute(targets,start+1,targetsc,results,offset);swap_pos(targets[start],targets[i]); } }

Note: this algorithm is taken fromwww.geeksforgeeks.com.

This algorithm takesO(2 * N * N!) time, whereN is the amount of target coordinates.Then, for each of these permutations we find the shortest path with Dijkstra's algorithm.

Dijkstra's SPA has time complexity ofO(|V|+|E| * log|V|) (where|V| is the number ofnodes and|E| is the number of edges). Combined with our permutations and initialiazationtime of the Dijkstra's algorithm, this gives usO(2 * P * P! + P! * P * ((|V| + |E| * log|V|) + L + M)), whereP is the amount ofprincesses.L + M is the time it takes to concatenate two paths, whereL is the amountof cells in the first path, andM is the amount of cells in the second path.

Finally, we need to sort our paths and take the shortest one as the main path. For thispurposes we can use quick sort. Quick sort takesO(N * logN) comparisons to sortNitems, In the worst case, it makesO(N^2) comparisons. So if we take the worst casescenario, then our program will takeO(2 * P * P! + P! * P * ((|V| + 4 * log|V|) + L + M) + O(N!^2)) time to compute thebest path.4 is the maximum amount of edges that node may have in theManhattan likepaths, which is exactly the case with our mazes.

Each node of the graph has a structure:

structNode {charspan;introw;intcol;intpriority;structNode*previous;structNode*neighbours[DIRECTIONS_COUNT]; };

whereDIRECTIONS_COUNT equals4. This structure has size of56 bytes.

To reduce amount of generated nodes, intermediate roads are skipped. For example, map:

CCCCDCCCP

will produce only 3 nodes: starting node, dragon node, princesses node.

Map generation is realized through simple algorithm with stack. Simply put, we just walkentire map by pushing each coordinate onto stack. If we've encounter a dead end, we can easilybacktrack by popping coordinates from the stack. There isn't really much to stay aboutthe logic of this algorithm, more challenging part (at least for me) is to create wallsbetween paths. The most important bit is thiswhile loop:

while (peek_top(stack)) {intdir=find_direction(map,visited,row,col);if (dir<0) {if (pop_pair(stack,&col,&row)<0)gotostack_failure;continue;}add_walls(map,dir,row,col);if (push_direction(stack,visited,dir,&row,&col)<0)gotostack_failure;}

Similar to searching paths, we keep track of the visited nodes. We keep traversing themap until we backtrack all the way back to the beginning of the map, i.e. the stack is empty.So in that regard, this loop is a bit similar to Dijkstra's SPA main loop.

Testing was realized through custom and random generated maps. Custom maps were takenfrom thissource.

Here are some of the testing results:

Nizomiddin Toshpulatov (tremul27@gmail.com)FIIT STU, Bratislava, 2020