summaryrefslogtreecommitdiffstats
path: root/labb8/src/trailblazergui.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'labb8/src/trailblazergui.cpp')
-rwxr-xr-xlabb8/src/trailblazergui.cpp1029
1 files changed, 1029 insertions, 0 deletions
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.");
+ }
+}
generated by cgit v1.2.1 (git 2.18.0) at 2025-12-14 00:46:50 +0100