12 files changed, 2383 insertions, 0 deletions
diff --git a/labb8/src/BasicGraph.cpp b/labb8/src/BasicGraph.cpp
new file mode 100755
index 0000000..2c4e239
--- /dev/null
+++ b/labb8/src/BasicGraph.cpp
@@ -0,0 +1,264 @@
+/*
+ * TDDD86 Trailblazer
+ * This file contains the implementation of some useful graph types,
+ * specifically the Node and Arc structures used in the typical graph.
+ * We also implement BasicGraph, an instantiation of
+ * Stanford's Graph class using Node and Arc as its type parameters.
+ *
+ * See BasicGraph.h for documentation of each member.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#include <sstream>
+#include "BasicGraph.h"
+
+/*
+ * Node member implementations
+ */
+
+Grid<double>* Node::s_world = nullptr;
+double (* Node::s_heuristicFunction)(Node* const from, Node* const to, const Grid<double>& world) = nullptr;
+
+Node::Node(string name, int row, int col, double gridValue) {
+    this->name = name;
+    this->m_row = row;
+    this->m_col = col;
+    this->m_gridValue = gridValue;
+    this->resetData();
+}
+
+Color Node::getColor() const {
+    return this->m_color;
+}
+
+double Node::heuristic(Node* const other) const {
+    if (s_world == nullptr || s_heuristicFunction == nullptr) {
+        return 0.0;
+    } else {
+        return s_heuristicFunction(const_cast<Node*>(this), const_cast<Node*>(other), *s_world);
+    }
+}
+
+void Node::resetData() {
+    this->cost = 0.0;
+    this->previous = nullptr;
+    this->visited = false;
+    this->m_color = WHITE;
+}
+
+void Node::setColor(Color c) {
+    this->m_color = c;
+    if (s_world != nullptr) {
+        colorCell(*s_world, makeLoc(this->m_row, this->m_col), c);
+    }
+}
+
+void Node::setHeuristicFunction(double (* func)(Node* const from, Node* const to, const Grid<double>& world)) {
+    s_heuristicFunction = func;
+}
+
+void Node::setWorld(const Grid<double>& world) {
+    s_world = const_cast<Grid<double>*>(&world);
+}
+
+string Node::toString() const {
+    ostringstream out;
+    out << *this;
+    return out.str();
+}
+
+ostream& operator<<(ostream& out, const Node& node) {
+    out << "Node{name=" << node.name;
+    if (node.cost != 0.0) {
+        out << ", cost=" << node.cost;
+    }
+    out << ", cost=" << node.cost;
+    out << ", visited=" << (node.visited ? "true" : "false");
+    out << ", previous=" << (node.previous == nullptr ? string("nullptr") : node.previous->name);
+
+    out << ", neighbors={" << node.arcs;
+    int i = 0;
+    foreach (Arc* arc in node.arcs) {
+        if (i > 0) {
+            out << ", ";
+        }
+        if (arc->finish) {
+            out << arc->finish->name;
+        } else {
+            out << "nullptr";
+        }
+    }
+    out << "}";
+    out << "}";
+    return out;
+}
+
+
+/*
+ * Arc member implementations
+ */
+
+Arc::Arc(Node* start, Node* finish, double cost) {
+    this->start = start;
+    this->finish = finish;
+    this->cost = cost;
+    this->resetData();
+}
+
+void Arc::resetData() {
+    this->visited = false;
+}
+
+string Arc::toString() const {
+    ostringstream out;
+    out << *this;
+    return out.str();
+}
+
+ostream& operator<<(ostream& out, const Arc& arc) {
+    out << "Arc{start=" << arc.start->name << ", finish=" << arc.finish->name;
+    if (arc.cost != 0.0) {
+        out << ", cost=" << arc.cost;
+    }
+    if (arc.visited) {
+        out << ", visited=" << (arc.visited ? "true" : "false");
+    }
+    out << "}";
+    return out;
+}
+
+
+/*
+ * BasicGraph member implementations
+ */
+
+Arc* BasicGraph::getArc(Node* v1, Node* v2) const {
+    foreach (Arc* arc in this->getArcSet(v1)) {
+        if (arc->finish == v2) {
+            return arc;
+        }
+    }
+    return nullptr;
+}
+
+Arc* BasicGraph::getArc(string v1, string v2) const {
+    return this->getArc(this->getVertex(v1), this->getVertex(v2));
+}
+
+Arc* BasicGraph::getEdge(Node* v1, Node* v2) const {
+    return this->getArc(v1, v2);
+}
+
+Arc* BasicGraph::getEdge(string v1, string v2) const {
+    return this->getArc(v1, v2);
+}
+
+Arc* BasicGraph::getInverseArc(Arc* arc) const {
+    return this->getArc(arc->finish, arc->start);
+}
+
+Arc* BasicGraph::getInverseEdge(Arc* arc) const {
+    return this->getInverseArc(arc);
+}
+
+bool BasicGraph::isNeighbor(string v1, string v2) const {
+    return this->isNeighbor(this->getVertex(v1), this->getVertex(v2));
+}
+
+bool BasicGraph::isNeighbor(Node* v1, Node* v2) const {
+    foreach (Arc* edge in this->getEdgeSet(v1)) {
+        if (edge->finish == v2) {
+            return true;
+        }
+    }
+    return false;
+}
+
+void BasicGraph::resetData() {
+    foreach (Node* node in getNodeSet()) {
+        node->resetData();
+    }
+    foreach (Arc* arc in getArcSet()) {
+        arc->resetData();
+    }
+}
+
+
+// members below are just mirrors of ones from Graph
+
+Arc* BasicGraph::addEdge(string v1, string v2, double cost, bool directed) {
+    return this->addEdge(getVertex(v1), getVertex(v2), cost, directed);
+}
+
+Arc* BasicGraph::addEdge(Node* v1, Node* v2, double cost, bool directed) {
+    Arc* e = new Arc(v1, v2, cost);
+    return addEdge(e, directed);
+}
+
+Arc* BasicGraph::addEdge(Arc* e, bool directed) {
+    Arc* result = this->addArc(e);
+    if (!directed) {
+        Arc* result2 = this->addArc(e->finish, e->start);
+        result2->cost = e->cost;
+    }
+    return result;
+}
+
+Node* BasicGraph::addVertex(string name) {
+    return this->addNode(name);
+}
+
+Node* BasicGraph::addVertex(Node* v) {
+    return this->addNode(v);
+}
+
+const Set<Arc*>& BasicGraph::getEdgeSet() const {
+    return this->getArcSet();
+}
+
+const Set<Arc*>& BasicGraph::getEdgeSet(Node* v) const {
+    return this->getArcSet(v);
+}
+
+const Set<Arc*>& BasicGraph::getEdgeSet(string v) const {
+    return this->getArcSet(v);
+}
+
+Node* BasicGraph::getVertex(string name) const {
+    return this->getNode(name);
+}
+
+const Set<Node*>& BasicGraph::getVertexSet() const {
+    return this->getNodeSet();
+}
+
+void BasicGraph::removeEdge(string v1, string v2, bool directed) {
+    this->removeEdge(this->getVertex(v1), this->getVertex(v2), directed);
+}
+
+void BasicGraph::removeEdge(Node* v1, Node* v2, bool directed) {
+    this->removeArc(v1, v2);
+    if (!directed) {
+        this->removeArc(v2, v1);
+    }
+}
+
+void BasicGraph::removeEdge(Arc* e, bool directed) {
+    this->removeArc(e);
+    if (!directed) {
+        this->removeArc(e->finish, e->start);
+    }
+}
+
+void BasicGraph::removeVertex(string name) {
+    this->removeNode(name);
+}
+
+void BasicGraph::removeVertex(Node* v) {
+    this->removeNode(v);
+}
diff --git a/labb8/src/BasicGraph.h b/labb8/src/BasicGraph.h
new file mode 100755
index 0000000..e0bdeee
--- /dev/null
+++ b/labb8/src/BasicGraph.h
@@ -0,0 +1,230 @@
+/*
+ * TDDD86 Trailblazer
+ * This file contains the declaration of some useful graph types,
+ * specifically the Node and Arc structures used in the typical graph.
+ * We also declare BasicGraph, an instantiation of
+ * Stanford's Graph class using Node and Arc as its type parameters.
+ *
+ * See BasicGraph.cpp for implementation of each member.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#ifndef _basicgraph_h
+#define _basicgraph_h
+
+#include <string>
+#include "graph.h"
+#include "grid.h"
+#include "set.h"
+#include "trailblazergui.h"
+using namespace std;
+
+/*
+ * Forward declarations of Node/Arc structures so that they can refer
+ * to each other mutually.
+ */
+struct Node;
+struct Arc;
+
+/*
+ * Canonical Node structure implementation needed by Graph class template.
+ * A Node structure represents a vertex in the graph.
+ */
+struct Node {
+public:
+    string name;      // required by Stanford Graph; vertex's name
+    Set<Arc*> arcs;   // edges outbound from this vertex; to neighbors
+
+    /*
+     * The following three fields are 'supplementary data' inside each vertex.
+     * You can use them in your path-searching algorithms to store various
+     * information related to the vertex
+     */
+    double cost;      // cost to reach this vertex (initially 0; you can set this)
+    bool visited;     // whether this vertex has been visited before (initally false; you can set this)
+    Node* previous;   // vertex that comes before this one (initially nullptr; you can set this)
+
+    /*
+     * The following three fields are used internally and not by your code.  You
+     * must not use their values nor rely on them in any way in your algorithms.
+     */
+    int m_row;
+    int m_col;
+    double m_gridValue;
+
+    /*
+     * Constructs a vertex with the given name and optional extra information.
+     * The extra information is used internally to convert it back to a Grid
+     * entry for legacy support if needed.
+     */
+    Node(string name = "", int row = 0, int col = 0, double gridValue = 0.0);
+
+    /*
+     * Returns the color of this node, if any.  Initially WHITE.
+     */
+    Color getColor() const;
+
+    /*
+     * Returns a 'heuristic' value, or rough estimation, of the distance between
+     * this vertex and the given other vertex.
+     * The heuristic function is guaranteed to be an 'admissible heuristic',
+     * meaning that it is never an overestimation of the distance.
+     * That property is important for the heuristic function to work properly
+     * when used with the A* search algorithm.
+     */
+    double heuristic(Node* const other) const;
+
+    /*
+     * Wipes the supplementary data of this vertex back to its initial state.
+     * Specifically, sets cost to 0, visited to false, and previous to nullptr.
+     */
+    void resetData();
+
+    /*
+     * Sets the color of this vertex to be the given color.
+     * The color must be one of WHITE, GRAY, YELLOW, or GREEN.
+     * Future calls to getColor will return the color you pass here.
+     */
+    void setColor(Color c);
+
+    /*
+     * Returns a string representation of this vertex for debugging, such as
+     * "Node{name=r13c42, cost=11, visited=true, previous=r12c41, neighbors={r12c41, r12c43}}".
+     */
+    string toString() const;
+
+    /*
+     * These static functions are used by the provided client code to set up
+     * information about the world and heuristic functions used by nodes.
+     * You should not call these functions directly in your path algorithms.
+     */
+    static void setHeuristicFunction(double (* func)(Node* const from, Node* const to, const Grid<double>& world));
+    static void setWorld(const Grid<double>& world);
+
+private:
+    Color m_color;   // node's color as passed to setColor
+    static double (* s_heuristicFunction)(Node* const from, Node* const to,
+                                          const Grid<double>& world);
+    static Grid<double>* s_world;
+};
+
+/*
+ * Makes a node printable to an output stream.
+ * See toString for an example of the output format.
+ * Note that printing a node is not the same as printing a node pointer.
+ * If you try to print a pointer, you will just see its address in hex.
+ */
+ostream& operator<<(ostream& out, const Node& node);
+
+/*
+ * You can refer to a Node as a Vertex if you prefer.
+ */
+#define Vertex Node
+
+/*
+ * Canonical Arc structure implementation needed by Graph class template.
+ * An Arc structure represents an edge in the graph.
+ */
+struct Arc {
+public:
+    Node* start;    // edge's starting vertex (required by Graph)
+    Node* finish;   // edge's ending vertex (required by Graph)
+    double cost;    // edge weight (required by Graph)
+    bool visited;   // whether this edge has been visited before (initally false; you can set this)
+
+    /*
+     * Constructs a new edge between the given start/end vertices with
+     * the given cost.
+     */
+    Arc(Node* start = nullptr, Node* finish = nullptr, double cost = 0.0);
+
+    /*
+     * Wipes the supplementary data of this vertex back to its initial state.
+     * Specifically, sets visited to false.
+     */
+    void resetData();
+
+    /*
+     * Returns a string representation of this edge for debugging, such as
+     * "Arc{start=r12c42, finish=r12c41, cost=0.75}".
+     */
+    string toString() const;
+
+    /*
+     * The following fields are used internally and not by your code.  You
+     * must not use their values nor rely on them in any way in your algorithms.
+     */
+    int m_startRow;
+    int m_startCol;
+    int m_finishRow;
+    int m_finishCol;
+};
+
+/*
+ * Makes an arc printable to an output stream.
+ * See toString for an example of the output format.
+ * Note that printing an arc is not the same as printing an arc pointer.
+ * If you try to print a pointer, you will just see its address in hex.
+ */
+ostream& operator<<(ostream& out, const Arc& arc);
+
+/*
+ * You can refer to an Arc as an Edge if you prefer.
+ */
+#define Edge Arc
+
+
+/*
+ * BasicGraph is just basically an instantiation of Graph using Node and Arc
+ * as its template parameters.  It also adds a few convenience functions such
+ * as mirroring members like "addArc" with an equivalent more familiar name
+ * like "addEdge".
+ *
+ * There are a few convenience functions related to neighbors, like isNeighbor.
+ * BasicGraph contains a DFS implementation called isReachable, not found
+ * in the normal Stanford Graph class.
+ *
+ * There are also a few functions added to make edges more convenient to work with:
+ * getEdge(v1, v2) to get the edge between a given pair of vertices,
+ * and getInverseArc(arc) to get the edge v2 -> v1 for a given edge v1 -> v2.
+ */
+class BasicGraph : public Graph<Node, Arc> {
+public:
+    Arc* getArc(Node* v1, Node* v2) const;
+    Arc* getArc(string v1, string v2) const;
+    Arc* getEdge(Node* v1, Node* v2) const;
+    Arc* getEdge(string v1, string v2) const;
+    Arc* getInverseArc(Arc* arc) const;
+    Arc* getInverseEdge(Arc* arc) const;
+    bool isNeighbor(string v1, string v2) const;
+    bool isNeighbor(Node* v1, Node* v2) const;
+    void resetData();
+
+    /*
+     * The members below are mirrors of ones from Graph but with 'Node' changed
+     * to 'Vertex' and/or 'Arc' changed to 'Edge', with identical behavior,
+     * and so they are not documented in detail.  See Graph documentation.
+     */
+    Arc* addEdge(string v1, string v2, double cost = 0.0, bool directed = true);
+    Arc* addEdge(Node* v1, Node* v2, double cost = 0.0, bool directed = true);
+    Arc* addEdge(Arc* e, bool directed = true);
+    Node* addVertex(string name);
+    Node* addVertex(Node* v);
+    const Set<Arc*>& getEdgeSet() const;
+    const Set<Arc*>& getEdgeSet(Node* v) const;
+    const Set<Arc*>& getEdgeSet(string v) const;
+    Node* getVertex(string name) const;
+    const Set<Node*>& getVertexSet() const;
+    void removeEdge(string v1, string v2, bool directed = true);
+    void removeEdge(Node* v1, Node* v2, bool directed = true);
+    void removeEdge(Arc* e, bool directed = true);
+    void removeVertex(string name);
+    void removeVertex(Node* v);
+};
+
+#endif
diff --git a/labb8/src/adapter.cpp b/labb8/src/adapter.cpp
new file mode 100755
index 0000000..e4700c3
--- /dev/null
+++ b/labb8/src/adapter.cpp
@@ -0,0 +1,231 @@
+/*
+ * TDDD86 Trailblazer
+ * This file implements code to serve as an "adapter" to convert between various
+ * data types used by legacy support code and new code for the current version
+ * of this assignment.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp
+ * Slight modifcations by Tommy Farnqvist
+ */
+
+#include <algorithm>
+#include <iomanip>
+#include <iostream>
+#include <vector>
+#include "graph.h"
+#include "map.h"
+#include "random.h"
+#include "BasicGraph.h"
+#include "costs.h"
+#include "trailblazer.h"
+#include "trailblazergui.h"
+#include "types.h"
+#include "adapter.h"
+
+// global variables
+static Map<Grid<double>*, BasicGraph*> WORLD_CACHE;
+static double (*heuristicFunction)(TBLoc from, TBLoc to, const Grid<double>& world) = NULL;
+
+
+// function prototype declarations
+static double heuristicAdapter(Node* const from, Node* const to, const Grid<double>& world);
+
+
+// function implementations
+
+BasicGraph* gridToGraph(const Grid<double>& world,
+                        double costFn(TBLoc from, TBLoc to, const Grid<double>& world)) {
+    BasicGraph* graph = new BasicGraph();
+
+    // add vertices
+    int rows = world.numRows();
+    int cols = world.numCols();
+    int rowColDigits = 0;
+    for (int temp = max(rows, cols); temp > 0; temp /= 10) {
+        rowColDigits++;
+    }
+    for (int r = 0; r < rows; r++) {
+        for (int c = 0; c < cols; c++) {
+            string name = vertexName(r, c, world);
+            Vertex* v = new Vertex(name, r, c);
+            v->m_gridValue = world.get(r, c);
+            // cout << "  ensureWorldCache adding vertex " << name << endl;
+            graph->addVertex(v);
+        }
+    }
+
+    // add edges
+    for (int r = 0; r < rows; r++) {
+        for (int c = 0; c < cols; c++) {
+            Vertex* v = graph->getVertex(vertexName(r, c, world));
+            for (int dr = -1; dr <= 1; dr++) {
+                for (int dc = -1; dc <= 1; dc++) {
+                    int nr = r + dr;
+                    int nc = c + dc;
+                    if ((dr == 0 && dc == 0) || !world.inBounds(nr, nc)) {
+                        continue;
+                    }
+                    Vertex* neighbor = graph->getVertex(vertexName(nr, nc, world));
+                    double cost = costFn(makeLoc(r, c), makeLoc(nr, nc), world);
+                    if (cost != POSITIVE_INFINITY) {
+                        Edge* e = new Edge(v, neighbor, cost);
+                        e->m_startRow = r;
+                        e->m_startCol = c;
+                        e->m_finishRow = nr;
+                        e->m_finishCol = nc;
+                        graph->addEdge(e);
+                        // cout << "  ensureWorldCache adding edge from "
+                        //      << v->name << " to " << neighbor->name
+                        //      << " (cost " << setprecision(4) << cost << ")" << endl;
+                    }
+                }
+            }
+        }
+    }
+
+    return graph;
+}
+
+Grid<double>* graphToGrid(BasicGraph* graph) {
+    int maxRow = -1;
+    int maxCol = -1;
+    foreach (Vertex* v in graph->getVertexSet()) {
+        maxRow = max(maxRow, v->m_row);
+        maxCol = max(maxCol, v->m_col);
+    }
+    if (maxRow < 0 || maxCol < 0) {
+        return NULL;
+    }
+
+    // initially set all to be walls
+    Grid<double>* grid = new Grid<double>(maxRow + 1, maxCol + 1);
+    for (int r = 0; r <= maxRow; r++) {
+        for (int c = 0; c <= maxCol; c++) {
+            grid->set(r, c, kMazeWall);
+        }
+    }
+    foreach (Vertex* v in graph->getVertexSet()) {
+        grid->set(v->m_row, v->m_col, v->m_gridValue);
+    }
+
+    return grid;
+}
+
+void ensureWorldCache(const Grid<double>& world,
+                      double costFn(TBLoc from, TBLoc to, const Grid<double>& world)) {
+    Grid<double>* const pWorld = const_cast<Grid<double>*>(&world);
+    if (!WORLD_CACHE.containsKey(pWorld)) {
+        cout << "Preparing world model ..." << endl;
+        BasicGraph* graph = gridToGraph(world, costFn);
+        cout << "World model completed." << endl;
+        WORLD_CACHE[pWorld] = graph;
+    }
+}
+
+void flushWorldCache() {
+    foreach (Grid<double>* grid in WORLD_CACHE) {
+        BasicGraph* graph = WORLD_CACHE[grid];
+        delete graph;
+    }
+    WORLD_CACHE.clear();
+}
+
+Vector<TBLoc>
+shortestPath(TBLoc start,
+             TBLoc end,
+             const Grid<double>& world,
+             double costFn(TBLoc from, TBLoc to, const Grid<double>& world),
+             double heuristicFn(TBLoc from, TBLoc to, const Grid<double>& world),
+             AlgorithmType algorithm) {
+    // modified by Marty to use an actual Graph object
+    ensureWorldCache(world, costFn);
+    cout << endl;
+
+    Grid<double>* const pWorld = const_cast<Grid<double>*>(&world);
+    BasicGraph* graph = WORLD_CACHE[pWorld];
+    // graph->resetData();   // make the student worry about this
+
+    heuristicFunction = heuristicFn;
+    Vertex::setWorld(world);
+    Vertex::setHeuristicFunction(heuristicAdapter);
+
+    // convert start/end from Loc to Vertex
+    Vertex* startVertex = graph->getVertex(vertexName(start.row, start.col, world));
+    Vertex* endVertex   = graph->getVertex(vertexName(end.row, end.col, world));
+    if (startVertex == NULL) {
+        error(string("Graph can not find start vertex with name \"") + vertexName(start.row, start.col, world) + "\"");
+        foreach (Vertex* v in graph->getVertexSet()) {
+            cout << v->name << " ";
+        }
+        cout << endl;
+    }
+    if (endVertex == NULL) {
+        error(string("Graph can not find end vertex with name \"") + vertexName(start.row, start.col, world) + "\"");
+        foreach (Vertex* v in graph->getVertexSet()) {
+            cout << v->name << " ";
+        }
+        cout << endl;
+    }
+
+    cout << "Looking for a path from " << startVertex->name
+         << " to " << endVertex->name << "." << endl;
+
+    vector<Vertex*> result;
+    switch (algorithm) {
+    case BFS:
+        cout << "Executing breadth-first search algorithm ..." << endl;
+        result = breadthFirstSearch(*graph, startVertex, endVertex);
+        break;
+    case DIJKSTRA:
+        cout << "Executing Dijkstra's algorithm ..." << endl;
+        result = dijkstrasAlgorithm(*graph, startVertex, endVertex);
+        break;
+    case A_STAR:
+        cout << "Executing A* algorithm ..." << endl;
+        result = aStar(*graph, startVertex, endVertex);
+        break;
+    case DFS:
+    default:
+        cout << "Executing depth-first search algorithm ..." << endl;
+        result = depthFirstSearch(*graph, startVertex, endVertex);
+        break;
+    }
+
+    cout << "Algorithm complete." << endl;
+
+    // convert vector<Vertex*> to Vector<Loc>
+    Vector<TBLoc> locResult;
+    foreach (Vertex* v in result) {
+        locResult.add(makeLoc(v->m_row, v->m_col));
+    }
+    return locResult;
+}
+
+Set<TBEdge> createMaze(int /* numRows */, int /* numCols */) {
+    Set<TBEdge> set;
+    return set;
+}
+
+static double heuristicAdapter(Node* const from, Node* const to, const Grid<double>& world) {
+    if (heuristicFunction == NULL) {
+        return 0.0;
+    } else {
+        return heuristicFunction(makeLoc(from->m_row, from->m_col),
+                                 makeLoc(to->m_row, to->m_col), world);
+    }
+}
+
+string vertexName(int r, int c, const Grid<double>& world) {
+    // zero-pad the number of rows/cols for better alphabetic sorting
+    int digits = 0;
+    for (int temp = max(world.numRows(), world.numCols()); temp > 0; temp /= 10) {
+        digits++;
+    }
+    ostringstream out;
+    out << 'r' << setw(digits) << setfill('0') << r
+        << 'c' << setw(digits) << setfill('0') << c;
+    return out.str();
+}
diff --git a/labb8/src/adapter.h b/labb8/src/adapter.h
new file mode 100755
index 0000000..51740ec
--- /dev/null
+++ b/labb8/src/adapter.h
@@ -0,0 +1,111 @@
+/*
+ * TDDD86 Trailblazer
+ * This file declares code to serve as an "adapter" to convert between various
+ * data types used by legacy support code and new code for the current version
+ * of this assignment.
+ * Specifically, past quarters represented a graph as a Grid<double> and each
+ * of its vertices/edges as a Loc (TBLoc) and Edge (TBEdge), while the
+ * current version of the assignment represents the graph as a BasicGraph
+ * (an extension of Stanford's Graph class) and each vertex/edge as a
+ * Node (Vertex) / Arc (Edge) object.
+ * This code converts between the two formats to help localize changes.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#ifndef _adapter_h
+#define _adapter_h
+
+#include "grid.h"
+#include "set.h"
+#include "BasicGraph.h"
+#include "types.h"
+
+/* Type: AlgorithmType
+ *
+ * An enumerated type representing the various algorithms to choose from.
+ */
+enum AlgorithmType {
+    AUTODETECT,
+    BFS,
+    DFS,
+    DIJKSTRA,
+    A_STAR
+};
+
+/*
+ * Finds the shortest path between the locations given by start and end in the
+ * specified world.  The cost of moving from one edge to the next is specified
+ * by the given cost function.  The resulting path is then returned as a
+ * Vector<Loc> containing the locations to visit in the order in which they
+ * would be visited.
+ * If no path is found, this function should report an error.
+ */
+Vector<TBLoc>
+shortestPath(TBLoc start,
+             TBLoc end,
+             const Grid<double>& world,
+             double costFn(TBLoc from, TBLoc to, const Grid<double>& world),
+             double heuristicFn(TBLoc from, TBLoc to, const Grid<double>& world),
+             AlgorithmType algorithm = AUTODETECT);
+
+// Support functions called by the GUI to improve loading times for large graphs.
+
+/*
+ * Converts the given graph into a 2D grid structure, which is returned;
+ * essentially the opposite of gridToGraph.
+ * Used to convert randomly generated mazes into grids for legacy code support.
+ */
+Grid<double>* graphToGrid(BasicGraph* graph);
+
+/*
+ * Converts the given 2D grid structure into a BasicGraph object,
+ * using the Grid to grab the vertices and the given cost function to grab
+ * the edge weights between neighbors.
+ * Returns a pointer to the graph that was created.
+ */
+BasicGraph* gridToGraph(const Grid<double>& world,
+                        double costFn(TBLoc from, TBLoc to, const Grid<double>& world));
+
+/*
+ * Makes sure that the given world has already been converted into an equivalent
+ * BasicGraph.  If it has not, does so (by calling gridToGraph) and caches the
+ * result to be used on future calls.
+ * This is done to improve runtime when very large/huge mazes and terrains are
+ * loaded and then searched multiple times by the user.
+ */
+void ensureWorldCache(const Grid<double>& world,
+                      double costFn(TBLoc from, TBLoc to, const Grid<double>& world));
+
+/*
+ * Removes all entries from the internal cache of BasicGraphs and frees
+ * any memory associated with them.
+ */
+void flushWorldCache();
+
+/*
+ * Returns a name for the given row/column location in the given world,
+ * such as "r08c17".
+ * The reason you have to pass the world is so that I know how many rows/cols
+ * it has so I can zero-pad the numbers in the string.
+ */
+string vertexName(int r, int c, const Grid<double>& world);
+
+/*
+ * (Extension)
+ *
+ * Creates a maze of the specified dimensions using a randomized version of
+ * Kruskal's algorithm, then returns a set of all of the edges in the maze.
+ *
+ * As specified in the assignment handout, the edges you should return here
+ * represent the connections between locations in the graph that are passable.
+ * Our provided starter code will then use these edges to build up a Grid
+ * representation of the maze.
+ */
+Set<TBEdge> createMaze(int numRows, int numCols);
+
+#endif
diff --git a/labb8/src/costs.cpp b/labb8/src/costs.cpp
new file mode 100755
index 0000000..1b663b1
--- /dev/null
+++ b/labb8/src/costs.cpp
@@ -0,0 +1,107 @@
+/*
+ * TDDD86 Trailblazer
+ * This file contains functions for computing the costs of navigating the
+ * terrain and maze worlds, as well as heuristics for predicting costs.
+ * See costs.h for declarations of each function and related constants.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp, Keith Schwarz, et al
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#include "costs.h"
+#include <cmath>
+#include <limits>
+using namespace std;
+
+/*
+ * The cost of moving from one location to another in the world is computed as
+ *
+ * distance(loc1, loc2) * k * |Delta h|
+ *
+ * This means that the cost of moving from one point to another depends on two
+ * factors: the change in elevation and the absolute distance between those
+ * points.	Moving in a cardinal direction has base cost 1, while moving
+ * diagonally has base cost sqrt(2).
+ *
+ * The secondary cost associated with moving in the terrain is based on the
+ * change in the height between the two points.	 This implementation makes the
+ * cost linear in the difference in height.
+ */
+double terrainCost(TBLoc from, TBLoc to, const Grid<double>& world) {
+    // The cost of moving from a location to itself is 0.
+	if (from == to) return 0.0;
+
+    // Confirm that the locations are adjacent to one another.
+	int drow = abs(to.row - from.row);
+	int dcol = abs(to.col - from.col);
+	if (drow > 1 || dcol > 1) {
+		error("Non-adjacent locations passed into cost function.");
+	}
+
+    // Determine the absolute distance between the points.
+	double distance = sqrt(double(drow * drow + dcol * dcol));
+    double dheight = fabs(world.get(to.row, to.col) - world.get(from.row, from.col));
+	return distance + kAltitudePenalty * dheight;
+}
+
+/*
+ * Our terrain heuristic simply returns the straight-line distance between
+ * the two points, plus the height differential scaled appropriately.
+ */
+double terrainHeuristic(TBLoc from, TBLoc to, const Grid<double>& world) {
+	int drow = to.row - from.row;
+	int dcol = to.col - from.col;
+    double dheight = fabs(world.get(to.row, to.col) - world.get(from.row, from.col));
+	return sqrt((double) (drow * drow + dcol * dcol)) + kAltitudePenalty * dheight;
+}
+
+/*
+ * The cost of moving in a maze is 1.0 when moving in cardinal directions from
+ * floors to floors and is infinite otherwise.	This prevents any motion across
+ * walls or diagonally.
+ */
+double mazeCost(TBLoc from, TBLoc to, const Grid<double>& world) {
+    // The cost of moving from a location to itself is 0.
+	if (from == to) return 0.0;
+
+    // Confirm that the locations are adjacent to one another.
+	int drow = abs(to.row - from.row);
+	int dcol = abs(to.col - from.col);
+	if (drow > 1 || dcol > 1) {
+		error("Non-adjacent locations passed into cost function.");
+	}
+	
+    // Moving diagonally costs infinitely much.
+    if (drow == 1 && dcol == 1) {
+        // return numeric_limits<double>::infinity();
+        return POSITIVE_INFINITY;
+    }
+
+    // See if we're moving to or from a wall.
+    if (world.get(from.row, from.col) == kMazeWall
+            || world.get(to.row, to.col) == kMazeWall) {
+        // return numeric_limits<double>::infinity();
+        return POSITIVE_INFINITY;
+    }
+
+	return 1.0;
+}
+
+/*
+ * The maze heuristic is the rectangular "Manhattan" distance for moving around
+ * in a grid world.
+ */
+double mazeHeuristic(TBLoc from, TBLoc to, const Grid<double>& /*world*/) {
+	return abs(from.row - to.row) + abs(from.col - to.col);
+}
+
+/*
+ * The zero heuristic, unsurprisingly, returns zero and ignores its
+ * arguments.
+ */
+double zeroHeuristic(TBLoc, TBLoc, const Grid<double>&) {
+	return 0.0;
+}
diff --git a/labb8/src/costs.h b/labb8/src/costs.h
new file mode 100755
index 0000000..2c4cc91
--- /dev/null
+++ b/labb8/src/costs.h
@@ -0,0 +1,64 @@
+/*
+ * TDDD86 Trailblazer
+ * This file contains functions for computing the costs of navigating the
+ * terrain and maze worlds, as well as heuristics for predicting costs.
+ * See costs.cpp for implementation of each function.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp, Keith Schwarz, et al
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#ifndef _costs_h
+#define _costs_h
+
+#include <cmath>
+#include <limits>
+#include "grid.h"
+#include "types.h"
+
+// represents 'infinity' for use in your various algorithms as needed
+const double POSITIVE_INFINITY =  1.0 / 0.0;
+const double NEGATIVE_INFINITY = -1.0 / 0.0;
+
+/* Constants representing the value of a wall and floor cell in a maze. */
+const double kMazeWall = 0.0;
+const double kMazeFloor = 1.0;
+
+const double kAltitudePenalty = 100;
+
+
+/*
+ * A function that given two adjacent locations in a terrain, returns the cost
+ * associated with moving from the first location to the second.
+ */
+double terrainCost(TBLoc from, TBLoc to, const Grid<double>& world);
+
+/*
+ * A function that, given two locations in a terrain, estimates the cost
+ * of moving from the first location all the way to the second.
+ */
+double terrainHeuristic(TBLoc from, TBLoc to, const Grid<double>& world);
+
+/*
+ * A function that, given two adjacent locations in a maze, returns the cost
+ * associated with moving from the first location to the second.
+ */
+double mazeCost(TBLoc from, TBLoc to, const Grid<double>& world);
+
+/*
+ * A function that, given two locations in a maze, estimates the cost of
+ * moving from the first location all the way to the second.
+ */
+double mazeHeuristic(TBLoc from, TBLoc to, const Grid<double>& world);
+
+/*
+ * A heuristic function that always returns 0.  This function is used so that
+ * the shortestPath function can be used to run Dijkstra's algorithm, which is
+ * the same as running A* search with a zero heuristic function.
+ */
+double zeroHeuristic(TBLoc from, TBLoc to, const Grid<double>& world);
+
+#endif
diff --git a/labb8/src/trailblazer.cpp b/labb8/src/trailblazer.cpp
new file mode 100755
index 0000000..38e168b
--- /dev/null
+++ b/labb8/src/trailblazer.cpp
@@ -0,0 +1,45 @@
+// This is the CPP file you will edit and turn in.
+// Also remove these comments here and add your own, along with
+// comments on every function and on complex code sections.
+// TODO: write comment header for this file; remove this comment
+
+#include "costs.h"
+#include "trailblazer.h"
+// TODO: include any other headers you need; remove this comment
+using namespace std;
+
+vector<Node *> depthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) {
+    // TODO: implement this function; remove these comments
+    //       (The function body code provided below is just a stub that returns
+    //        an empty vector so that the overall project will compile.
+    //        You should remove that code and replace it with your implementation.)
+    vector<Vertex*> path;
+    return path;
+}
+
+vector<Node *> breadthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) {
+    // TODO: implement this function; remove these comments
+    //       (The function body code provided below is just a stub that returns
+    //        an empty vector so that the overall project will compile.
+    //        You should remove that code and replace it with your implementation.)
+    vector<Vertex*> path;
+    return path;
+}
+
+vector<Node *> dijkstrasAlgorithm(BasicGraph& graph, Vertex* start, Vertex* end) {
+    // TODO: implement this function; remove these comments
+    //       (The function body code provided below is just a stub that returns
+    //        an empty vector so that the overall project will compile.
+    //        You should remove that code and replace it with your implementation.)
+    vector<Vertex*> path;
+    return path;
+}
+
+vector<Node *> aStar(BasicGraph& graph, Vertex* start, Vertex* end) {
+    // TODO: implement this function; remove these comments
+    //       (The function body code provided below is just a stub that returns
+    //        an empty vector so that the overall project will compile.
+    //        You should remove that code and replace it with your implementation.)
+    vector<Vertex*> path;
+    return path;
+}
diff --git a/labb8/src/trailblazer.h b/labb8/src/trailblazer.h
new file mode 100755
index 0000000..154085e
--- /dev/null
+++ b/labb8/src/trailblazer.h
@@ -0,0 +1,23 @@
+/*
+ * TDDD86 Trailblazer
+ * This file declares the functions you will write in this assignment.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#ifndef _trailblazer_h
+#define _trailblazer_h
+
+#include <vector>
+#include "BasicGraph.h"
+
+vector<Node*> depthFirstSearch(BasicGraph& graph, Node* start, Node* end);
+vector<Node*> breadthFirstSearch(BasicGraph& graph, Node* start, Node* end);
+vector<Node*> dijkstrasAlgorithm(BasicGraph& graph, Node* start, Node* end);
+vector<Node*> aStar(BasicGraph& graph, Node* start, Node* end);
+
+#endif
diff --git a/labb8/src/trailblazergui.cpp b/labb8/src/trailblazergui.cpp
new file mode 100755
index 0000000..86a38df
--- /dev/null
+++ b/labb8/src/trailblazergui.cpp
@@ -0,0 +1,1029 @@
+/*
+ * TDDD86 Trailblazer
+ * This file implements functions to perform drawing in the graphical user
+ * interface (GUI).
+ * This file also contains the main function to launch the program.
+ * See trailblazergui.h for documentation of each public function.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp, Keith Schwarz, et al
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#include <cctype>
+#include <cmath>
+#include <iomanip>
+#include <iostream>
+#include <limits>
+#include <string>
+
+// code for setting a large stack size on non-Windows GCC platforms
+#ifndef _WIN32
+#include <sys/resource.h>
+#include <stdint.h>
+#endif
+
+#include "error.h"
+#include "filelib.h"
+#include "gevents.h"
+#include "ginteractors.h"
+#include "gobjects.h"
+#include "gwindow.h"
+#include "set.h"
+#include "strlib.h"
+#include "vector.h"
+#include "adapter.h"
+#include "costs.h"
+#include "trailblazer.h"
+#include "trailblazergui.h"
+using namespace std;
+
+// internal constants
+const int MIN_DELAY = 0;
+const int MAX_DELAY = 2000;
+static int animationDelay = 0;
+static bool pathSearchInProgress = false;
+
+// various UI strings
+const string kSelectedLocationColor("RED");
+const string kPathColor("RED");
+const string kBackgroundColor("Black");
+const string GUI_STATE_FILE = "trailblazer-gui-state.sav";
+const bool SHOULD_SAVE_GUI_STATE = true;
+const bool RANDOM_OPTION_ENABLED = false;
+
+/*
+ * The size, in pixels, of the displayed world.
+ * Number of padding pixels between the border of the window and the the
+ * start of the content.
+ * Constants controlling the amount we should adjust the size of the window
+ * to reflect the extra space used up by the border and controls.
+ */
+const int kDisplayWidth = 600;
+const int kDisplayHeight = 600;
+const int kMargin = 5;
+const int kWidthAdjustment  =  0;
+const int kHeightAdjustment = 75;
+
+/*
+ * Maximum number of rows or columns we allow in a world.    This is mostly a
+ * safety feature to prevent an OOM on a malformed input file.
+ */
+const int kMaxRows = 400;
+const int kMaxCols = 400;
+
+/*
+ * Constants controlling the number of rows/cols in the different sizes of
+ * worlds.  The indices into these arrays are controlled by the enumerated
+ * type WorldSize.
+ */
+const int kTerrainNumRows[] = { 10, 33, 65, 129, 257 };
+const int kTerrainNumCols[] = { 10, 33, 65, 129, 257 };
+const int kMazeNumRows[]    = {  5, 10, 30,  80, 160 };
+const int kMazeNumCols[]    = {  5, 10, 30,  80, 160 };
+
+/*
+ * Constants reflecting the colors that are used to highlight cells different
+ * colors.  This is an array of arrays, where each array contains RGB triplets
+ * for the collors.  The ordering here should be consistent with the ordering
+ * of the Color type.
+ */
+const int kColorMultipliers[6][3] = {
+    {   0,   0,   0 },   // UNCOLORED
+    { 255, 255, 255 },   // WHITE
+    { 192, 192, 192 },   // GRAY
+    { 255, 255,   0 },   // YELLOW
+    {   0, 255,   0 },   // GREEN
+    { 255,   0,   0 }    // RED
+};
+
+
+// Internal global variables
+
+static GWindow* gWindow = NULL;
+static GChooser* gWorldChooser = NULL;
+static GChooser* gAlgorithmList = NULL;
+static GSlider* gDelaySlider = NULL;
+static GRect* gFirstSelected = NULL;      // which cells were seletected so far
+static GRect* gSecondSelected = NULL;
+static GTextField* gPositionField = NULL;
+static string gPositionFieldText = " r???c???";
+static Grid<Color> gMarked;               // which cells have been colored by the user
+static Grid<double> gMarkedValues;        // the values we've marked them with
+static Vector<GLine*> gHighlightedPath;   // all highlighting lines
+static TBLoc gStartLocation;              // their corresponding locations
+static TBLoc gEndLocation;
+static double gPixelsPerWidth;            // width of each cell
+static double gPixelsPerHeight;           // height of each cell
+static State state;
+
+
+// internal function prototypes (see implementations for documentation)
+
+static void colorLocation(TBLoc loc, double value, Color locColor);
+static TBLoc coordToLoc(double x, double y);
+static void drawWorld(Grid<double>& world);
+static void fillRect(int x, int y, int width, int height, string color);
+static void findMidpoint(TBLoc loc, double& xc, double& yc);
+static Set<string> getFiles(string substr);
+//static WorldSize getWorldSize(string worldFile);
+static void intro();
+static bool loadGUIState();
+static void locToCoord(TBLoc loc, double& x, double& y);
+static bool readWorldFile(ifstream& input, Grid<double>& world, WorldType& worldType);
+static bool regenerateWorld(Grid<double>& world, WorldType& worldType);
+static bool registerClick(Grid<double>& world, double x, double y, WorldType worldType);
+static void removeAndDelete(GObject* object);
+static void removeMarkedSquares();
+static void removeOverlays();
+static void restoreWorldDisplay();
+static void runSearch(State& state);
+static void runShortestPath(const Grid<double>& world, WorldType worldType,
+                            TBLoc start, TBLoc end, Vector<TBLoc>& path, double& pathCost);
+static bool saveGUIState();
+static void uncolorSquares();
+static void updateDelay(bool forbidZero = false);
+static string valueToColor(double value, Color locColor);
+static void worldUpdated(Grid<double>& world, WorldType worldType);
+
+
+// function implementations
+
+#ifndef _WIN32
+/*
+ * This function increases the system stack size on Unixy platforms (Linux+Mac),
+ * making it possible to make many nested calls of depth-first search without
+ * crashing the system.
+ * Windows MinGW systems set their stack size through compiler/linker flags
+ * that are set in the project's .pro file.
+ */
+static void setStackSize(const rlim_t stackSize) {
+#if defined(__USE_LARGEFILE64)
+    // 64-bit version
+    rlimit64 rl;
+    int result = getrlimit64(RLIMIT_STACK, &rl);
+#else
+    // 32-bit version
+    rlimit rl;
+    int result = getrlimit(RLIMIT_STACK, &rl);
+#endif
+    if (result == 0) {
+        if (rl.rlim_cur < stackSize || rl.rlim_max < stackSize) {
+            rl.rlim_cur = stackSize;
+            rl.rlim_max = stackSize;
+#if defined(__USE_LARGEFILE64)
+            // 64-bit version
+            result = setrlimit64(RLIMIT_STACK, &rl);
+#else
+            result = setrlimit(RLIMIT_STACK, &rl);
+#endif
+            if (result != 0) {
+                cerr << "Warning: Unable to increase system stack size to "
+                     << stackSize << endl;
+            }
+        }
+    }
+}
+#endif
+
+/*
+ * Main program.
+ */
+int main() {
+#ifndef _WIN32
+    setStackSize(100 * 1024 * 1024);   // increase function call stack
+#endif
+
+    setConsoleEcho(true);
+    setConsolePrintExceptions(true);
+
+    initializeGUI();
+
+    // Main event loop to process events as they happen.
+    while (true) {
+        GEvent e = waitForEvent(ACTION_EVENT | MOUSE_EVENT);
+        if (e.getEventType() == MOUSE_CLICKED || e.getEventType() == MOUSE_MOVED) {
+            processMouseEvent(GMouseEvent(e));
+        } else if (e.getEventClass() == ACTION_EVENT) {
+            processActionEvent(GActionEvent(e));
+        }
+    }
+    return 0;
+}
+
+/*
+ * (public function)
+ * Colors the specified cell in the world the indicated color.
+ */
+void colorCell(Grid<double>& world, TBLoc loc, Color locColor) {
+    colorLocation(loc, world[loc.row][loc.col], locColor);
+    gMarked[loc.row][loc.col] = locColor;
+
+    // possibly delay and then repaint the square, for animation
+    if (animationDelay > 0) {
+        gWindow->repaint();
+
+        // while I'm here, check if delay updated
+        updateDelay(true);
+
+        pause(animationDelay);
+    }
+}
+
+/*
+ * (public function)
+ * Initializes state of the GUI subsystem.
+ */
+void initializeGUI() {
+    // Calculate the intended width and height of the window based on the content
+    // area size, the margin size, and the adjustment amount.
+    int windowWidth = kDisplayWidth + 2 * kMargin + kWidthAdjustment;
+    int windowHeight = kDisplayHeight + 2 * kMargin + kHeightAdjustment;
+
+    gWindow = new GWindow(windowWidth, windowHeight);
+    gWindow->setWindowTitle("TDDD86 Trailblazer");
+
+    // Add the algorithms list.
+    gAlgorithmList = new GChooser();
+    gAlgorithmList->addItem("Depth-first Search");
+    gAlgorithmList->addItem("Breadth-first Search");
+    gAlgorithmList->addItem("Dijkstra's Algorithm");
+    gAlgorithmList->addItem("A* Search");
+    gWindow->addToRegion(gAlgorithmList, "NORTH");
+
+    gWindow->addToRegion(new GLabel("Delay:"), "NORTH");
+    gDelaySlider = new GSlider(MIN_DELAY, MAX_DELAY, MIN_DELAY);
+    gWindow->addToRegion(gDelaySlider, "NORTH");
+    gWindow->addToRegion(new GButton("Run"), "NORTH");
+    gWindow->addToRegion(new GButton("Clear"), "NORTH");
+    gPositionField = new GTextField(7);
+    gPositionField->setText(gPositionFieldText);
+    gWindow->addToRegion(gPositionField, "NORTH");
+
+    // Add in the list of existing world files.
+    gWorldChooser = new GChooser();
+    Set<string> worldFiles = getFiles("maze") + getFiles("terrain");
+    foreach (string worldFile in worldFiles) {
+        gWorldChooser->addItem(worldFile);
+    }
+    if (RANDOM_OPTION_ENABLED) {
+        gWorldChooser->addItem("Random Maze (tiny)");
+        gWorldChooser->addItem("Random Maze (small)");
+        gWorldChooser->addItem("Random Maze (medium)");
+        gWorldChooser->addItem("Random Maze (large)");
+        gWorldChooser->addItem("Random Maze (huge)");
+        gWorldChooser->addItem("Random Terrain (tiny)");
+        gWorldChooser->addItem("Random Terrain (small)");
+        gWorldChooser->addItem("Random Terrain (medium)");
+        gWorldChooser->addItem("Random Terrain (large)");
+        gWorldChooser->addItem("Random Terrain (huge)");
+    }
+
+    gWindow->addToRegion(new GLabel("World:"), "SOUTH");
+    gWindow->addToRegion(gWorldChooser, "SOUTH");
+    gWindow->addToRegion(new GButton("Load"), "SOUTH");
+    gWindow->addToRegion(new GButton("Exit"), "SOUTH");
+
+    intro();
+    if (SHOULD_SAVE_GUI_STATE) {
+        loadGUIState();
+    }
+
+    if (!regenerateWorld(state.world, state.worldType)) {
+        error("Cannot set up initial world properly!");
+    }
+    state.uiState = FRESH;
+    drawWorld(state.world);
+}
+
+/*
+ * (public function)
+ * Reacts to an action event in the window.
+ */
+void processActionEvent(GActionEvent e) {
+    string cmd = e.getActionCommand();
+    if (cmd == "Load") {
+        // Want to load a new world?  Try to do so and update the UI accordingly.
+        if (regenerateWorld(state.world, state.worldType)) {
+            drawWorld(state.world);
+            state.uiState = FRESH;
+        }
+    } else if (cmd == "Run") {
+        // Rerunning the search is only possible if we already did a search.
+        if (state.uiState == DRAWN) {
+            uncolorSquares();
+            removeOverlays();
+            runSearch(state);
+        } else {
+            cout << "Cannot rerun a search; no search has been done." << endl;
+        }
+    } else if (cmd == "Clear") {
+        // Clearing the display just sets us back to the fresh state.
+        restoreWorldDisplay();
+        state.uiState = FRESH;
+    } else if (cmd == "Exit") {
+        // Trying to quit exits the entire program.
+        cout << endl;
+        cout << "Exiting." << endl;
+        if (SHOULD_SAVE_GUI_STATE) {
+            saveGUIState();
+        }
+        exitGraphics();
+    }
+}
+
+/*
+ * (public function)
+ * Reacts to a mouse event in the window.
+ */
+void processMouseEvent(GMouseEvent e) {
+    if (e.getEventType() == MOUSE_CLICKED) {
+        switch (state.uiState) {
+        case DRAWN:
+            // Already have something drawn?  Clear it and pretend we're fresh.
+            restoreWorldDisplay();
+            state.uiState = FRESH;
+            // deliberate: don't break.
+
+        case FRESH:
+            // In a fresh state?  Try to select what the user clicked on.
+            if (registerClick(state.world, e.getX(), e.getY(), state.worldType)) {
+                state.uiState = MARKED;
+            }
+            break;
+
+        case MARKED:
+            // Already marked?  Try to select what the user clicked on, then
+            // try to find a path if it worked.
+            if (registerClick(state.world, e.getX(), e.getY(),
+                              state.worldType)) {
+                runSearch(state);
+                state.uiState = DRAWN;
+            }
+        }
+    } else if (e.getEventType() == MOUSE_MOVED) {
+        // update display of current mouse row/col position to aid testing
+        TBLoc loc = coordToLoc(e.getX(), e.getY());
+        if (state.world.inBounds(loc.row, loc.col)) {
+            string newPositionText = vertexName(loc.row, loc.col, state.world);
+            if (newPositionText != gPositionFieldText) {
+                gPositionFieldText = newPositionText;
+                gPositionField->setText(newPositionText);
+            }
+        }
+    }
+}
+
+/*
+ * Given a physical screen location, maps it to a logical grid location.
+ */
+static TBLoc coordToLoc(double x, double y) {
+    TBLoc loc;
+    loc.row = (int) ((y - kMargin) / gPixelsPerHeight);
+    loc.col = (int) ((x - kMargin) / gPixelsPerWidth);
+    return loc;
+}
+
+/*
+ * Colors the given location, which has the specified intensity, the indicated
+ * color.
+ */
+static void colorLocation(TBLoc loc, double value, Color locColor) {
+    double x, y;
+    locToCoord(loc, x, y);
+
+    fillRect(x, y, gPixelsPerWidth, gPixelsPerHeight,
+             valueToColor(value, locColor));
+}
+
+/*
+ * Given a path, returns the cost of that path.
+ */
+static double costOf(Vector<TBLoc>& path,
+                     const Grid<double>& world,
+                     double costFn(TBLoc, TBLoc, const Grid<double>&)) {
+    double result = 0.0;
+    for (int i = 1; i < path.size(); i++) {
+        result += costFn(path[i - 1], path[i], world);
+    }
+    return result;
+}
+
+/*
+ * Given a path, draws that path on the screen.
+ */
+static void drawPath(Vector<TBLoc>& path) {
+    for (int i = 1; i < path.size(); i++) {
+        // highlight connection between path[i - 1] and path[i]
+        double srcX, srcY, dstX, dstY;
+        findMidpoint(path[i - 1], srcX, srcY);
+        findMidpoint(path[i], dstX, dstY);
+
+        GLine* connection = new GLine(srcX, srcY, dstX, dstY);
+        connection->setColor(kPathColor);
+        connection->setLineWidth(3.0);
+        gWindow->add(connection);
+        gHighlightedPath.add(connection);
+    }
+}
+
+/*
+ * Draws the specified grid in the world.
+ */
+static void drawWorld(Grid<double>& world) {
+    if (gWindow == NULL) error("Cannot draw world before window is set up.");
+
+    // This should act as if we are repainting the top-level display, so we
+    // will remove all overlays.
+    removeMarkedSquares();
+    removeOverlays();
+
+    // Recompute the size of a cell in the display.
+    gPixelsPerWidth = (double) kDisplayWidth / world.numCols();
+    gPixelsPerHeight = (double) kDisplayHeight / world.numRows();
+
+    // Draw the background.
+    fillRect(0, 0, kDisplayWidth + 2 * kMargin, kDisplayHeight + 2 * kMargin,
+             kBackgroundColor);
+
+    // With the redraw, no locations are marked anymore.
+    gMarked.resize(world.numRows(), world.numCols());
+    gMarkedValues = world;
+
+    // Draw each cell.
+    for (int row = 0; row < world.numRows(); row++) {
+        for (int col = 0; col < world.numCols(); col++) {
+            TBLoc loc = { row, col };
+            double x, y;
+            locToCoord(loc, x, y);
+
+            fillRect(x, y, gPixelsPerWidth, gPixelsPerHeight,
+                     valueToColor(world[row][col], WHITE));
+        }
+    }
+
+    // Issue a repaint so that we see the changes.
+    gWindow->repaint();
+}
+
+/*
+ * A convenience wrapper that sets the given color and then fills a rectangle
+ * of the given dimensions.  Saves a line of code on each call.
+ */
+static void fillRect(int x, int y, int width, int height, string color) {
+    gWindow->setColor(color);
+    gWindow->fillRect(x, y, width, height);
+}
+
+/*
+ * Given a logical grid location, returns the physical screen coordinates of
+ * its midpoint.
+ */
+static void findMidpoint(TBLoc loc, double& xc, double& yc) {
+    locToCoord(loc, xc, yc);
+    xc += gPixelsPerWidth / 2;
+    yc += gPixelsPerHeight / 2;
+}
+
+/*
+ * Returns which type of algorithm is currently selected in the drop-down
+ * menu.
+ */
+static AlgorithmType getAlgorithmType() {
+    if (gWindow == NULL) error("Window has not yet been initialized.");
+    string algorithmLabel = gAlgorithmList->getSelectedItem();
+
+    if (algorithmLabel == "Depth-first Search") {
+        return DFS;
+    } else if (algorithmLabel == "Breadth-first Search") {
+        return BFS;
+    } else if (algorithmLabel == "Dijkstra's Algorithm") {
+        return DIJKSTRA;
+    } else if (algorithmLabel == "A* Search") {
+        return A_STAR;
+    } else {
+        error("Invalid algorithm provided.");
+        return DIJKSTRA;
+    }
+}
+
+/*
+ * Returns all files in the current directory that start with the given
+ * substring prefix.  Used to find all maze and/or terrain files to display.
+ */
+static Set<string> getFiles(string substr) {
+    substr = toLowerCase(substr);
+    Vector<string> files;
+    listDirectory(".", files);
+    Set<string> result;
+    foreach (string file in files) {
+        string fileLC = toLowerCase(file);
+        if (startsWith(fileLC, substr) && endsWith(fileLC, ".txt")) {
+            result.add(file);
+        }
+    }
+    return result;
+}
+
+/*
+ * Given the contents of the world size selector, returns a WorldSize encoding
+ * the desired world size.
+ */
+//static WorldSize getWorldSize(string worldFile) {
+//    string worldLC = toLowerCase(worldFile);
+//    if (worldLC.find("tiny") != string::npos) {
+//        return TINY_WORLD;
+//    } else if (worldLC.find("small") != string::npos) {
+//        return SMALL_WORLD;
+//    } else if (worldLC.find("medium") != string::npos) {
+//        return MEDIUM_WORLD;
+//    } else if (worldLC.find("large") != string::npos) {
+//        return LARGE_WORLD;
+//    } else if (worldLC.find("huge") != string::npos) {
+//        return HUGE_WORLD;
+//    } else {
+//        error("Invalid world size provided.");
+//        return SMALL_WORLD;
+//    }
+//}
+
+/*
+ * Prints an introductory text message on the screen.
+ */
+static void intro() {
+    cout << "Welcome to TDDD86 Trailblazer!" << endl;
+    cout << "This program searches for paths through graphs representing mazes" << endl;
+    cout << "and rocky terrains.  It demonstrates several graph algorithms for" << endl;
+    cout << "finding paths, such as depth-first search (DFS), breadth-first" << endl;
+    cout << "search (BFS), Dijkstra's Algorithm, and A* search." << endl;
+}
+
+/*
+ * Restores the previously saved GUI state, including which algorithm is
+ * currently selected, the animation delay, and the world file chosen.
+ * If the saved state does not exist or is corrupt, returns false and
+ * uses a default initial state.
+ */
+static bool loadGUIState() {
+    ifstream input;
+    input.open(GUI_STATE_FILE.c_str());
+    if (input.fail()) {
+        return false;
+    }
+    string algorithm;
+    getline(input, algorithm);
+    if (input.fail()) {
+        return false;
+    }
+
+    string line;
+    getline(input, line);
+    if (input.fail()) {
+        return false;
+    }
+    int delay = stringToInteger(line);
+
+    string worldFile;
+    getline(input, worldFile);
+    if (input.fail()) {
+        return false;
+    }
+    input.close();
+
+    // delete the save state file in case there is a crash loading a world
+    deleteFile(GUI_STATE_FILE);
+
+    gAlgorithmList->setSelectedItem(algorithm);
+    gDelaySlider->setValue(delay);
+    gWorldChooser->setSelectedItem(worldFile);
+    return true;
+}
+
+/*
+ * Given a logical grid location, maps it to a physical screen location.
+ */
+static void locToCoord(TBLoc loc, double& x, double& y) {
+    x = loc.col * gPixelsPerWidth + kMargin;
+    y = loc.row * gPixelsPerHeight + kMargin;
+}
+
+/*
+ * Tries to read a world file from the specified stream.  On success, returns
+ * true and updates the input parameters to mark the type of the world and
+ * the world contents.  On failure, returns false, but may still modify the
+ * input parameters.
+ */
+static bool readWorldFile(ifstream& input, Grid<double>& world, WorldType& worldType) {
+    try {
+        // Enable exceptions on the stream so that we can handle errors using try-
+        // catch rather than continuously testing everything.
+        input.exceptions(ios::failbit | ios::badbit);
+
+        // The file line of the file identifies the type, which should be either
+        // "terrain" or "maze."
+        string type;
+        input >> type;
+
+        if (type == "terrain") {
+            worldType = TERRAIN_WORLD;
+        } else if (type == "maze") {
+            worldType = MAZE_WORLD;
+        } else {
+            cerr << "world file does not contain type (terrain/maze) as first line." << endl;
+            return false;
+        }
+
+        // Read the size of the world.
+        int numRows, numCols;
+        input >> numRows >> numCols;
+
+        if (numRows <= 0 || numCols <= 0 ||
+                numRows >= kMaxRows || numRows >= kMaxCols) {
+            cerr << "world file contains invalid number of rows/cols: "
+                 << numRows << "," << numCols << endl;
+            return false;
+        }
+
+        world.resize(numRows, numCols);
+
+        for (int row = 0; row < numRows; row++) {
+            for (int col = 0; col < numCols; col++) {
+                double value;
+                input >> value;
+                if (input.fail()) {
+                    cerr << "Illegal input file format; row #" << (row+1)
+                         << "does not contain " << numCols << " valid numbers" << endl;
+                    return false;
+                }
+
+                // Validate the input based on the type of world.
+                if (worldType == MAZE_WORLD) {
+                    if (value != kMazeWall && value != kMazeFloor) {
+                        cerr << "world file contains invalid square value of " << value
+                             << ", must be " << kMazeFloor << " or " << kMazeWall << endl;
+                        return false;
+                    }
+                } else {  // worldType == TERRAIN_WORLD
+                    if (value < 0.0 || value > 1.0) {
+                        cerr << "world file contains invalid terrain value of " << value
+                             << ", must be 0.0 - 1.0" << endl;
+                        return false;
+                    }
+                }
+                world[row][col] = value;
+            }
+        }
+
+        return true;
+    } catch (...) {
+        // Something went wrong, so report an error.
+        cerr << "exception thrown while reading world file" << endl;
+        return false;
+    }
+}
+
+/*
+ * Generates a new world based on the user's preferences.
+ */
+static bool regenerateWorld(Grid<double>& world, WorldType& worldType) {
+    string worldFile = gWorldChooser->getSelectedItem();
+    // code for generating random worlds commented out for this quarter
+//    if (startsWith(worldFile, "Random")) {
+//        // To make this gracefully handle exceptions, we'll make a dummy world and
+//        // world type that we'll set up out here.
+//        Grid<double> newWorld;
+//        WorldSize worldSize = getWorldSize(worldFile);
+//        WorldType newType = (worldFile.find("errain") == string::npos ? MAZE_WORLD : TERRAIN_WORLD);
+
+//        // Based on the type of world, generate a different world of an appropriate size.
+//        if (newType == TERRAIN_WORLD) {
+//            int numRows = kTerrainNumRows[worldSize];
+//            int numCols = kTerrainNumCols[worldSize];
+//            newWorld = generateRandomTerrain(numRows, numCols);
+//        } else if (newType == MAZE_WORLD) {
+//            int numRows = kMazeNumRows[worldSize];
+//            int numCols = kMazeNumCols[worldSize];
+
+//            // The default student code throws an exception, which we must handle.
+//            try {
+//                // The maze's logical number of rows and columns is not the same as its
+//                // physical number of rows and columns in the grid.  In particular, an
+//                // m x n maze has size (2m - 1) x (2n - 1), so we rescale the size of the
+//                // maze based on the number of logical rows and columns we want.
+//                newWorld = generateRandomMaze(numRows / 2 + 1, numCols / 2 + 1);
+//            } catch (const ErrorException& e) {
+//                cout << e.what() << endl;
+//                return false;
+//            }
+//        } else {
+//            error("Invalid world type provided.");
+//        }
+
+//        world = newWorld;
+//        worldType = newType;
+//        worldUpdated(world, worldType);
+//        return true;
+//    } else {
+        // not random (most common); load a pre-defined maze or terrain input file
+        cout << endl;
+        cout << "Loading world from " << worldFile << " ..." << endl;
+        ifstream input;
+        input.open(worldFile.c_str());
+        if (input.fail()) {
+            error(string("Unable to open input file ") + worldFile);
+            return false;
+        }
+
+        // Try reading in the world file.  If we can't, report an error.
+        Grid<double> newWorld;
+        WorldType newWorldType;
+        if (!readWorldFile(input, newWorld, newWorldType)) {
+            cerr << worldFile << " is not a valid world file." << endl;
+            return false;
+        }
+
+        world = newWorld;
+        worldType = newWorldType;
+        worldUpdated(world, worldType);
+        return true;
+//    }
+}
+
+/*
+ * Registers that a click occurred, storing the location appropriately and
+ * updating the graphics.  If the click was on an invalid location, returns
+ * false.  If the click was at a valid location, returns true.
+ */
+static bool registerClick(Grid<double>& world, double x, double y,
+                          WorldType worldType) {
+    if (gWindow == NULL) {
+        error("Window has not yet been initialized.");
+    }
+    if (gFirstSelected != NULL && gSecondSelected != NULL) {
+        error("Two tiles have already been selected.");
+    }
+
+    // Determine where we clicked and make sure it's in-bounds.
+    TBLoc loc = coordToLoc(x, y);
+    if (!world.inBounds(loc.row, loc.col) ||
+            (worldType == MAZE_WORLD && world[loc.row][loc.col] == kMazeWall)) {
+        return false;
+    }
+
+    // Add the selection to the display.
+    double selectionX, selectionY;
+    locToCoord(loc, selectionX, selectionY);
+    GRect* selection = new GRect(selectionX, selectionY, gPixelsPerWidth, gPixelsPerHeight);
+    selection->setLineWidth(2.0);
+    selection->setColor(kSelectedLocationColor);
+    gWindow->add(selection);
+
+    // Store the selection appropriately based on whether this is the first or
+    // second click.
+    if (gFirstSelected == NULL) {
+        gFirstSelected = selection;
+        gStartLocation = loc;
+    } else {
+        gSecondSelected = selection;
+        gEndLocation = loc;
+    }
+
+    return true;
+}
+
+/*
+ * Utility function to remove a GObject from the display window and deallocate
+ * it.
+ */
+static void removeAndDelete(GObject* object) {
+    if (object != NULL) {
+        gWindow->remove(object);
+        delete object;
+    }
+}
+
+/*
+ * Removes the highlighted squares from the display.
+ */
+static void removeMarkedSquares() {
+    removeAndDelete(gFirstSelected);
+    removeAndDelete(gSecondSelected);
+    gFirstSelected = gSecondSelected = NULL;
+}
+
+/*
+ * Removes the line overlays.
+ */
+static void removeOverlays() {
+    // Clear the lines drawn from the path.
+    for (int i = 0; i < gHighlightedPath.size(); i++) {
+        removeAndDelete(gHighlightedPath[i]);
+    }
+    gHighlightedPath.clear();
+}
+
+/*
+ * Clears all cells that are currently selected and deselects any currently-
+ * selected squares.
+ */
+static void restoreWorldDisplay() {
+    if (gWindow == NULL) {
+        error("Window has not yet been initialized.");
+    }
+
+    uncolorSquares();
+    removeMarkedSquares();
+    removeOverlays();
+
+    // Repaint the window so the changes show.
+    gWindow->repaint();
+}
+
+/*
+ * Runs the currently selected graph path-searching algorithm on the current
+ * world, then displays information about the path that was found.
+ */
+static void runSearch(State& state) {
+    try {
+        updateDelay();
+        Vector<TBLoc> path;
+        double pathCost;
+        runShortestPath(state.world, state.worldType, gStartLocation,
+                        gEndLocation, path, pathCost);
+        cout << "Path length: " << path.size() << endl;
+        cout << "Path cost: " << pathCost << endl;
+        int greenGray = 0;
+        int yellow = 0;
+        for (int r = 0; r < gMarked.numRows(); r++) {
+            for (int c = 0; c < gMarked.numCols(); c++) {
+                Color color = gMarked.get(r, c);
+                if (color == GREEN || color == GRAY) {
+                    greenGray++;
+                } else if (color == YELLOW) {
+                    yellow++;
+                }
+            }
+        }
+        cout << "Locations visited: " << greenGray << endl;
+
+    } catch (const ErrorException& e) {
+        cout << e.what() << endl;
+    }
+}
+
+/*
+ * Computes the shortest path between the start and end locations, displaying
+ * it on the screen and returning its length.
+ */
+static void runShortestPath(const Grid<double>& world, WorldType worldType,
+                            TBLoc start, TBLoc end,
+                            Vector<TBLoc>& path, double& pathCost) {
+    AlgorithmType algType = getAlgorithmType();
+
+    // Determine which cost/heuristic functions to use.
+    double (*costFn)(TBLoc, TBLoc, const Grid<double>&);
+    double (*hFn)(TBLoc, TBLoc, const Grid<double>&);
+
+    if (worldType == TERRAIN_WORLD) {
+        costFn = terrainCost;
+        hFn = terrainHeuristic;
+    } else if (worldType == MAZE_WORLD) {
+        costFn = mazeCost;
+        hFn = mazeHeuristic;
+    } else {
+        error("Unknown world type.");
+    }
+
+    // Invoke the student's shortestPath function to find out the cost of the path.
+    pathSearchInProgress = true;
+    path = shortestPath(start, end, world, costFn, hFn, algType);
+    pathSearchInProgress = false;
+
+    if (path.isEmpty()) {
+        cout << "Warning: Returned path is empty." << endl;
+    } else if (path[0] != start) {
+        cout << "Warning: Start of path is not the start location." << endl;
+    } else if (path[path.size() - 1] != end) {
+        cout << "Warning: End of path is not the end location." << endl;
+    }
+
+    drawPath(path);
+    pathCost = costOf(path, world, costFn);
+}
+
+/*
+ * Saves the GUI's current state, including which algorithm is
+ * currently selected, the animation delay, and the world file chosen.
+ * If the saved state does not exist or is corrupt, returns false and
+ * uses a default initial state.
+ */
+static bool saveGUIState() {
+    string algorithm = gAlgorithmList->getSelectedItem();
+    int delay = gDelaySlider->getValue();
+    string worldFile = gWorldChooser->getSelectedItem();
+    ofstream output;
+    output.open(GUI_STATE_FILE.c_str());
+    if (output.fail()) {
+        return false;
+    }
+    output << algorithm << endl;
+    output << delay << endl;
+    output << worldFile << endl;
+    if (output.fail()) {
+        return false;
+    }
+    output.flush();
+    output.close();
+    return true;
+}
+
+/*
+ * Reads the delay slider and uses its value to decide on an animation delay.
+ */
+static void updateDelay(bool forbidZero) {
+    int delay = gDelaySlider->getValue();
+    double percent = 100.0 * delay / MAX_DELAY;
+    // convert scale so delays don't increase so rapidly
+    if (percent == 0.0) {
+        delay = forbidZero ? 1 : 0;
+    } else if (percent <= 10) {
+        delay = MAX_DELAY / 1000;
+    } else if (percent <= 20) {
+        delay = MAX_DELAY / 500;
+    } else if (percent <= 30) {
+        delay = MAX_DELAY / 200;
+    } else if (percent <= 40) {
+        delay = MAX_DELAY / 100;
+    } else if (percent <= 50) {
+        delay = MAX_DELAY / 50;
+    } else if (percent <= 60) {
+        delay = MAX_DELAY / 25;
+    } else if (percent <= 70) {
+        delay = MAX_DELAY / 10;
+    } else if (percent <= 80) {
+        delay = MAX_DELAY / 5;
+    } else if (percent <= 90) {
+        delay = MAX_DELAY / 2;
+    } else {  // percent > 90
+        delay = MAX_DELAY;
+    }
+
+    animationDelay = delay;
+}
+
+/*
+ * Given an elevation and a color, determines what #rrggbb format color to use
+ * to draw it.
+ */
+static string valueToColor(double value, Color locColor) {
+    // To make non-gray colors show up better, we artificially cap the lowest
+    // possible intensity at 0.2, rather than 0.0.  This next step is a linear
+    // remapping of the range [0, 1] to [0.2, 1].
+    if (locColor != WHITE) {
+        value = 0.8 * value + 0.2;
+    }
+
+    stringstream hexValue;
+    hexValue << "#" << hex << setfill('0');
+    for (int i = 0; i < 3; i++) {
+        int intensity = int(value * kColorMultipliers[locColor][i]);
+        hexValue << setw(2) << intensity;
+    }
+
+    return hexValue.str();
+}
+
+/*
+ * Restores all squares to their original colors.
+ */
+static void uncolorSquares() {
+    // Restore all colored cells to their original condition.
+    for (int row = 0; row < gMarked.numRows(); row++) {
+        for (int col = 0; col < gMarked.numCols(); col++) {
+            if (gMarked[row][col] != UNCOLORED && gMarked[row][col] != WHITE) {
+                TBLoc loc = { row, col };
+                colorLocation(loc, gMarkedValues[row][col], WHITE);
+
+                // Unmark this cell; it's no longer colored.
+                gMarked[row][col] = UNCOLORED;
+            }
+        }
+    }
+}
+
+/*
+ * Called anytime the current world is changed, so that we can update the
+ * cache of Grid -> Graph.
+ */
+static void worldUpdated(Grid<double>& world, WorldType worldType) {
+    flushWorldCache();
+    if (worldType == TERRAIN_WORLD) {
+        ensureWorldCache(world, terrainCost);
+    } else if (worldType == MAZE_WORLD) {
+        ensureWorldCache(world, mazeCost);
+    } else {
+        error("Unknown world type.");
+    }
+}
diff --git a/labb8/src/trailblazergui.h b/labb8/src/trailblazergui.h
new file mode 100755
index 0000000..9eb7971
--- /dev/null
+++ b/labb8/src/trailblazergui.h
@@ -0,0 +1,87 @@
+/*
+ * TDDD86 Trailblazer
+ * This file declares functions to perform drawing in the graphical user
+ * interface (GUI).
+ * See gui.cpp for implementation of each function.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp, Keith Schwarz, et al
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#ifndef _gui_h
+#define _gui_h
+
+#include "gevents.h"
+#include "grid.h"
+#include "types.h"
+
+/*
+ * An enumerated type tracking what type of world is currently selected so that
+ * we can determine which clicked locations are legal.
+ */
+enum WorldType {
+    TERRAIN_WORLD,
+    MAZE_WORLD
+};
+
+/*
+ * An enumerated type representing how large the world is, categorized as one
+ * of three different size classes.
+ */
+enum WorldSize {
+    TINY_WORLD,
+    SMALL_WORLD,
+    MEDIUM_WORLD,
+    LARGE_WORLD,
+    HUGE_WORLD
+};
+
+/*
+ * The UI is a state machine that can be in one of four states:
+ *
+ *  1. Fresh:  Nothing has been done yet.
+ *  2. Marked: One location has been selected.
+ *  3. Drawn:  Both locations have been selected, and a path is drawn.
+ *
+ * This enumerated type stores this information.
+ */
+enum UIState {
+    FRESH,
+    MARKED,
+    DRAWN
+};
+
+/*
+ * A utility struct that bundles together the state of the world.
+ */
+struct State {
+    Grid<double> world;    // The world.
+    WorldType worldType;   // The type of world.
+    UIState uiState;       // Which state we're in.
+};
+
+/*
+ * Highlights the specified cell in the world the given color, which must be
+ * either GRAY, YELLOW, or GREEN.
+ */
+void colorCell(Grid<double>& world, TBLoc loc, Color locColor);
+
+/*
+ * Initializes state of the GUI subsystem.
+ */
+void initializeGUI();
+
+/*
+ * Reacts to an action event in the window.
+ */
+void processActionEvent(GActionEvent e);
+
+/*
+ * Reacts to a mouse event in the window.
+ */
+void processMouseEvent(GMouseEvent e);
+
+#endif
diff --git a/labb8/src/types.cpp b/labb8/src/types.cpp
new file mode 100755
index 0000000..001b67e
--- /dev/null
+++ b/labb8/src/types.cpp
@@ -0,0 +1,106 @@
+/*
+ * TDDB86 Trailblazer
+ * This file implements fundamental types used by the Trailblazer assignment.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp, Keith Schwarz, et al
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#include "types.h"
+
+/*
+ * A large prime number used in hash code computation.
+ */
+const int kLargePrime = 78979871;
+
+/*
+ * A value that can be bitwise-ANDed with an integer to force it to be nonnegative,
+ * which is useful when writing hash functions.
+ */
+const int kHashMask = 0x7FFFFFF;
+
+/*
+ * Utility constructor functions.
+ */
+TBLoc makeLoc(int row, int col) {
+    TBLoc result = { row, col };
+    return result;
+}
+TBEdge makeEdge(TBLoc start, TBLoc end) {
+    TBEdge result = { start, end };
+    return result;
+}
+
+/*
+ * Overloaded comparison operators.
+ */
+bool operator < (TBLoc lhs, TBLoc rhs) {
+        if (lhs.row != rhs.row)
+                return lhs.row < rhs.row;
+        return lhs.col < rhs.col;
+}
+
+bool operator > (TBLoc lhs, TBLoc rhs) {
+    return rhs < lhs;
+}
+
+bool operator <= (TBLoc lhs, TBLoc rhs) {
+    return !(rhs < lhs);
+}
+
+bool operator >= (TBLoc lhs, TBLoc rhs) {
+    return !(lhs < rhs);
+}
+
+bool operator == (TBLoc lhs, TBLoc rhs) {
+    return lhs.row == rhs.row && lhs.col == rhs.col;
+}
+
+bool operator != (TBLoc lhs, TBLoc rhs) {
+    return !(lhs == rhs);
+}
+
+/*
+ * Hash code function to make it possible to store nodes in a hash set/map.
+ */
+int hashCode(TBLoc l) {
+    return (l.row + kLargePrime * l.col) & kHashMask;
+}
+
+/*
+ * Overloaded comparison operators.
+ */
+bool operator < (TBEdge lhs, TBEdge rhs) {
+    if (lhs.start != rhs.start) return lhs.start < rhs.start;
+    return lhs.end < rhs.end;
+}
+
+bool operator > (TBEdge lhs, TBEdge rhs) {
+    return rhs < lhs;
+}
+
+bool operator <= (TBEdge lhs, TBEdge rhs) {
+    return !(rhs < lhs);
+}
+
+bool operator >= (TBEdge lhs, TBEdge rhs) {
+    return !(lhs < rhs);
+}
+
+bool operator == (TBEdge lhs, TBEdge rhs) {
+    return lhs.start == rhs.start && lhs.end == rhs.end;
+}
+
+bool operator != (TBEdge lhs, TBEdge rhs) {
+    return !(lhs == rhs);
+}
+
+/*
+ * Hash code function to make it possible to store arcs in a hash set/map.
+ */
+int hashCode(TBEdge e) {
+    return (hashCode(e.start) + kLargePrime * hashCode(e.end)) & kHashMask;
+}
diff --git a/labb8/src/types.h b/labb8/src/types.h
new file mode 100755
index 0000000..606f398
--- /dev/null
+++ b/labb8/src/types.h
@@ -0,0 +1,86 @@
+/*
+ * TDDD86 Trailblazer
+ * This file declares fundamental types used by the Trailblazer assignment.
+ *
+ * Please do not modify this provided file. Your turned-in files should work
+ * with an unmodified version of all provided code files.
+ *
+ * Author: Marty Stepp, Keith Schwarz, et al
+ * Slight modifications by Tommy Farnqvist
+ */
+
+#ifndef _types_h
+#define _types_h
+
+/* Type: Loc
+ *
+ * A type representing a location in the world, represented as a pair of a row
+ * and a column.
+ */
+struct TBLoc {
+    int row;
+    int col;
+};
+
+/* Utility function to construct a Loc from its location. */
+TBLoc makeLoc(int row, int col);
+
+/* Type: Color
+ *
+ * An enumerated type representing a color for a node during an execution of
+ * Dijkstra's algorithm or A* search.
+ */
+enum Color {
+    UNCOLORED, WHITE, GRAY, YELLOW, GREEN, RED
+};
+
+/* Type: Edge
+ *
+ * A type representing an edge in the grid, as encoded by its start and end node.
+ * This type will be useful when implementing Kruskal's algorithm, though you may
+ * also find it useful when writing Dijkstra's algorithm or A* search.
+ */
+struct TBEdge {
+    TBLoc start;
+    TBLoc end;
+};
+
+/* Utility function to create an Edge from its endpoints. */
+TBEdge makeEdge(TBLoc start, TBLoc end);
+
+
+
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/* The functions below this point are provided for convenience and are not
+ * strictly necessary for your implementation.
+ */
+
+/* Comparison operators for Loc and Edge.    Our Map and Set type cannot store
+ * custom structs as keys (for a map) or values (for a set) unless they can be
+ * compared with the relational operators.  You will probably not directly use
+ * these in your solution, but you're welcome to do so if you find them useful.
+ */
+bool operator <  (TBLoc lhs, TBLoc rhs);
+bool operator >  (TBLoc lhs, TBLoc rhs);
+bool operator == (TBLoc lhs, TBLoc rhs);
+bool operator != (TBLoc lhs, TBLoc rhs);
+bool operator <= (TBLoc lhs, TBLoc rhs);
+bool operator >= (TBLoc lhs, TBLoc rhs);
+
+bool operator <  (TBEdge lhs, TBEdge rhs);
+bool operator >  (TBEdge lhs, TBEdge rhs);
+bool operator == (TBEdge lhs, TBEdge rhs);
+bool operator != (TBEdge lhs, TBEdge rhs);
+bool operator <= (TBEdge lhs, TBEdge rhs);
+bool operator >= (TBEdge lhs, TBEdge rhs);
+
+/* Hash function for Loc and Edge.  These functions are provided so that you can
+ * store Locs and Edges in our HashMap or HashSet type, which require a hashCode
+ * function to be available.    You will probably not directly use these in your
+ * solution, but you're welcome to do so if you find them useful.
+ */
+int hashCode(TBLoc l);
+int hashCode(TBEdge e);
+
+#endif