POSITION.H THESE TXT FILE OF TEST MAPS WILL BE USED: testmap1.txt testmap2.txt t

Question

POSITION.H

THESE TXT FILE OF TEST MAPS WILL BE USED:

testmap1.txt

testmap2.txt

testmap3.txt

testmap4.txt

1.

Your first job is to use the Map class to read in a map file, and write a display function that takes a Map object (by reference!) to display it at the console.

2.

Your next job is to find that path.

There are several ways to find a path from point A and point B, but they all involve searching. That is, take the next step, then the next, then the next and see if you get where you're trying to go. If not, try a different one. The tricky parts are:

Making sure you don't go back over places you've already been

Making sure that you don't settle for a longer path when a shorter one is available

Knowing when to quit because there is no path

One solution to this problem is called Breadth First Search (BFS). In this approach, you check all the spots 1 step away from you. Then all the spots 2 steps away. Then 3 and so on. This guarantees that if you do find the end, there couldn't have been any shorter paths. When you run out of positions to check, you know that you're done. Here's what it looks like in practice. The * indicate positions that we have checked.

BFS is implemented with a queue. The algorithm looks like this:

Push the start position onto the queue

While the queue is not empty...

Pop the front position off the queue

If it is the end, we're there! Declare success!

Otherwise, push all the unblocked, unvisited neighbors of that position onto the back of the queue

If the queue empties and we haven't found the end, there is no path

The key detail is in step 2.3, that we only add unvisited neighbors. That is, positions you can move to from the current position which we haven't checked yet. In our adventurer and dog problem, we'll say that the adventurer can only move left, right, up or down. That means that each position has up to 4 neighbors (the positions on the edges have 2 or 3).

The reason a queue works here is that all the one-step-away positions get in line first, then the two-step-away positions and so on.

Add a queue to hold positions. Then add a function to your code that takes a Map object (by reference!) and performs a Breadth-First Search. Here is a skeleton to get you started.

bool FindPath(Map &map)
{
// create a queue object

// push the starting position (from map) onto the queue

// while the queue isn't empty

    // pop the next position off

    // check if that position is the end position

      // if so, return true!

    // otherwise, repeat this code for each of the four potential neighbors

    // if it's not off the map (e.g. position 0,1 doesn't have a neighbor to the left)
    // ...and not blocked
    // ...and hasn't already been visited
      // then push onto the queue and have the map mark it visited

// if the queue empties and we haven't found the end, return false

}
In main, call your FindPath function and print whether or not a path was found for that map. Test maps 1,2 and 4 all have paths, but 3 does not.

Update your display function to show visited positions as *. Then, each time through the loop in your FindPath function, display the map. Use this statement to clear the screen before each display call, creating a cheap animation effect.

system("cls");

The system calls are Windows-only, but you can find an equivalent in MacOS and/or Linux.

Next, show the actual path that was found. In order to do this, you have to keep track for each position of what position you came from. This is why the Map::MarkVisited method requires 2 parameters: the position being visited and the position you're coming from. When you find the end of the path in FindPath, call the Map::GeneratePath method and it will figure out which positions are part of the final path. Finally, update your display function to show OnPath positions as ..

To show the final path, you'll want to add a parameter to display to hide the visited positions, so it looks nice

Do not call Map::GeneratePath before you've found the complete path, or unexpected things will happen

Explanation / Answer

#include "map.h" void Map::Read(const string& filename) { ifstream in; in.open(filename); in >> _width >> _height; _occupied = new bool[_width*_height]; _visited = new bool[_width*_height]; _back = new int[_width*_height]; char ch; int i = 0; for (int row = 0; row < _height; row++) { for (int col = 0; col < _width; col++) { in >> ch; if (ch == 'X') { _occupied[i] = true; } else { _occupied[i] = false; } if (ch == 'S') { _start.col = col; _start.row = row; } else if (ch == 'E') { _end.col = col; _end.row = row; } _visited[i] = false; _back[i] = -1; i++; } } in.close(); } void Map::MarkVisited(const position& newloc, const position& fromloc) { int to = newloc.row*_width + newloc.col; int from = fromloc.row*_width + fromloc.col; _visited[to] = true; _back[to] = from; } void Map::GeneratePath() { int next = _end.row*_width + _end.col; int begin = _start.row*_width + _start.col; while (next != begin) { int back = _back[next]; _back[next] = PATH_INDICATOR; next = back; } } MAP.H #pragma once #include #include using namespace std; #include "position.h" const int PATH_INDICATOR = -101; class Map { public: // Read in a text-based map file from the same directory void Read(const string& filename); // Return the width (columns) and height (rows) of the map int Width() { return _width; } int Height() { return _height; } // Return the start and end positions specified in the map position Start() { return _start; } position End() { return _end; } // Returns true if the specified position in the map is blocked (can't walk there) bool Blocked(const position& loc) { return _occupied[loc.row*_width + loc.col]; } // The following functions are used for the Breadth-First Search // Mark a given position visited during the search // newloc is the position being visited // fromloc is the prior position in the search void MarkVisited(const position& newloc, const position& fromloc); // Check if a given position has already been visited during the search bool Visited(const position& loc) { return _visited[loc.row*_width + loc.col]; } // Call this method after the search when end has been found void GeneratePath(); // Once the path is generated, // call this method to check if a given position is on the path bool OnPath(const position& loc) { return _back[loc.row*_width + loc.col] == PATH_INDICATOR; } private: int _width, _height; bool * _occupied; bool * _visited; int * _back; position _start; position _end; };

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---