l8 commentsHEADlab8master

1 files changed, 44 insertions, 0 deletions

diff --git a/labb8/src/trailblazer.cpp b/labb8/src/trailblazer.cpp
index c8496f9..17f73de 100755
--- a/labb8/src/trailblazer.cpp
+++ b/labb8/src/trailblazer.cpp
@@ -1,3 +1,9 @@
+/*
+ * TDDD86 Lab 8 - gusso230 (group 11)
+ * This file contains implementations of DFS, BFS, Dijkstra's algorithm and A*.
+ *
+ * NOTE The UI sometimes hangs when calling setColor on a node.
+ */
 #include "costs.h"
 #include "trailblazer.h"
 
@@ -10,8 +16,12 @@
 
 using namespace std;
 
+/*
+ * Construct a path from end by recursively adding and following node.previous.
+ */
 vector<Node*> path_from_end(Node* end, bool color_green = false) {
     if (!end->previous) {
+        // no more nodes to follow
         return {};
     }
     Node* cur = end;
@@ -27,6 +37,9 @@ vector<Node*> path_from_end(Node* end, bool color_green = false) {
     return path;
 }
 
+/*
+ * push_back all items from 'from' to 'to'.
+ */
 template <typename T>
 void push_back_from(vector<T>& to, const vector<T>& from) {
     for (const auto& el : from) {
@@ -34,6 +47,9 @@ void push_back_from(vector<T>& to, const vector<T>& from) {
     }
 }
 
+/*
+ * Recursively find a path from start to end with DFS.
+ */
 vector<Node*> dfs_helper(BasicGraph& graph, Vertex* start, Vertex* end) {
     start->setColor(GREEN);
     vector<Node*> path = { start };
@@ -56,11 +72,19 @@ vector<Node*> dfs_helper(BasicGraph& graph, Vertex* start, Vertex* end) {
     return {};
 }
 
+/*
+ * Find any path from start to end with DFS.
+ */
 vector<Node*> depthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) {
     graph.resetData();
     return dfs_helper(graph, start, end);
 }
 
+/*
+ * Find a path from start to end with BFS.
+ *
+ * The path found will have the least amount of steps, but ignores edge weights.
+ */
 vector<Node *> breadthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) {
     graph.resetData();
 
@@ -86,6 +110,12 @@ vector<Node *> breadthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end)
     return path_from_end(end);
 }
 
+/*
+ * Find a path from start to end with Dijkstra's algorithm.
+ *
+ * The path found will have the smallest total weight in a terrain and
+ * the least amount of steps in a maze.
+ */
 vector<Node*> dijkstrasAlgorithm(BasicGraph& graph, Vertex* start, Vertex* end) {
     graph.resetData();
 
@@ -96,20 +126,24 @@ vector<Node*> dijkstrasAlgorithm(BasicGraph& graph, Vertex* start, Vertex* end)
     while (q.size() > 0) {
         Node* cur = q.dequeue();
         cur->visited = true;
+        // we have found the shortest path here so color as green
         cur->setColor(GREEN);
         if (cur == end) {
+            // all nodes in q have 'previous' set to we can follow it all the way to start
             break;
         }
         for (const auto& arc : cur->arcs) {
             if (!arc->finish->visited) {
                 double new_dist = arc->start->cost + arc->cost;
                 if (arc->finish->cost == 0.0) {
+                    // this is the first time we queue this node
                     arc->finish->previous = cur;
                     arc->finish->cost = new_dist;
                     arc->finish->setColor(YELLOW);
                     q.enqueue(arc->finish, new_dist);
                 }
                 else if (new_dist < arc->finish->cost) {
+                    // we have queued this before but have now found a cheaper path
                     arc->finish->previous = cur;
                     arc->finish->cost = new_dist;
                     q.changePriority(arc->finish, new_dist);
@@ -120,6 +154,12 @@ vector<Node*> dijkstrasAlgorithm(BasicGraph& graph, Vertex* start, Vertex* end)
     return path_from_end(end);
 }
 
+/*
+ * Find a path from start to end with A*.
+ *
+ * The path found will have the smallest total weight in a terrain and
+ * the least amount of steps in a maze.
+ */
 vector<Node*> aStar(BasicGraph& graph, Vertex* start, Vertex* end) {
     graph.resetData();
 
@@ -130,20 +170,24 @@ vector<Node*> aStar(BasicGraph& graph, Vertex* start, Vertex* end) {
     while (q.size() > 0) {
         Node* cur = q.dequeue();
         cur->visited = true;
+        // we have found the shortest path here so color as green
         cur->setColor(GREEN);
         if (cur == end) {
+            // all nodes in q have 'previous' set to we can follow it all the way to start
             break;
         }
         for (const auto& arc : cur->arcs) {
             if (!arc->finish->visited) {
                 double new_dist = arc->start->cost + arc->cost;
                 if (arc->finish->cost == 0.0) {
+                    // this is the first time we queue this node
                     arc->finish->previous = cur;
                     arc->finish->cost = new_dist;
                     arc->finish->setColor(YELLOW);
                     q.enqueue(arc->finish, new_dist + arc->finish->heuristic(end));
                 }
                 else if (new_dist < arc->finish->cost) {
+                    // we have queued this before but have now found a cheaper path
                     arc->finish->previous = cur;
                     arc->finish->cost = new_dist;
                     q.changePriority(arc->finish, new_dist + arc->finish->heuristic(end));