From: Daily Coding Challenge #23
I have been wanting to do something like this... since I read about it today. It makes me want to get into robotics and make them find their way around the house!
How it works: very basic -- we start with a node at the starting point and it checks clockwise each cardinal direction - up, right, down, left - to see if any of those are the goal node. Meanwhile, the nodes it's checking also check their available nodes clockwise, while keeping a log to not check the same node twice and start an infinite loop.
Below is the test map used in this program. 't' represents 'true'=a walkable path. 'f' represents 'false'=a wall where it can't walk. (Used 'Y' for true and 'L' for false in the code below's console output for legibility)
t f t f
t t f t
f t t f
f t t f
Starting point is (0,0) and end point/goal is (2,3). As you can see from this test map, we need to go: Down, Right, Down, Right, Down to get to the goal. Or Down, Right, Down, Down, Right. Our program should find both ways to get there.
Although we defined our maze block in a hard-coded way, it could be redefined and the same structs used for any non-zero sized 2-D matrix of booleans.
// test-compiled @ onlinegdb.com using C++
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
std::string dirFrom4Bit(unsigned char dir){
if(dir == 8) return "Up";
if(dir == 4) return "Right";
if(dir == 2) return "Down";
if(dir == 1) return "Left";
if(dir == 0) return "Nowhere";
return "Unknown";
}
unsigned char flipDir(unsigned char dir){ // for path reporting; path stores the 'from' values but we want directions to get there. (we want 'to right', not 'from left')
if(dir == 8) return 2;
if(dir == 4) return 1;
if(dir == 2) return 8;
if(dir == 1) return 4;
return dir;
}
// globals
bool mazeMap[4][4]; // true's are walkable, false's are walls.
bool mazeFound[4][4]; // where we've been, so we don't infinitely loop
int propagationAttempts = 0;
int targetX = 2;
int targetY = 3;
#define maxAttempts 100
struct mazeBounds{
int x = 0; // lowest index x axis
int y = 0; // lowest index y axis
int w = 3; // highest index x axis
int h = 3; // highest index y axis
}bounds;
struct mazePath{ // for outputting a winning path
std::vector<unsigned char> dirs; // up/right/down/left, low order 4 bits
void resetTo(unsigned int index){ // for currentPath: done with child mazePoint, back up to parent by erasing child's entries in this path
index++; // so it is the necessary length of the vector
while(dirs.size() > index)
dirs.pop_back();
}
};
std::vector<mazePath> paths;
mazePath currentPath; // stay the course, men!
struct mazePoint{
int x = 0;
int y = 0;
int myPathIndex = 0; //
mazePoint(){}
mazePoint(int x, int y, unsigned int myPathIndex=0){
this->x = x;
this->y = y;
this->myPathIndex=myPathIndex;
}
// dirBit: low-order 4 bits: up/right/down/left: which way we went from the last point to get to this one, so we don't back track
// return: true if found target down that propagation path, false if not
bool propagate(unsigned char dirBit){
if(mazeMap[x][y] == false) return false; // wall, can't be here
if(mazeFound[x][y]) return false; // been here, done that
mazeFound[x][y] = true; // don't consider this same point in the future
if(propagationAttempts >= maxAttempts) return false;
propagationAttempts++;
cout << "Try: # " << propagationAttempts << ", Level " << myPathIndex << ", from " << dirFrom4Bit(dirBit) << ", x = " << x << ", y = " << y << endl;
if(targetX == x && targetY == y){ // this is the target
// log path to victory
mazePath p;
for(int xint = 0, len = currentPath.dirs.size();xint < len;xint++)
p.dirs.push_back(currentPath.dirs[xint]);
paths.push_back(p);
mazeFound[x][y] = false; // allow alternate paths to find the goal
return true;
}
bool foundTarget = false; // found target through this path? if so, we'll pass back up true at the end, after trying all paths
if((dirBit & 8) == 0){ // try up
if(y > bounds.y){ // can go up
mazePoint n(x, y-1, myPathIndex+1);
currentPath.dirs.push_back(2);
if(n.propagate(2)) // came from...2=below
foundTarget = true;
currentPath.resetTo(myPathIndex);
}
}
if((dirBit & 4) == 0){ // try right
if(x < bounds.w){ // can go right
mazePoint n(x+1, y, myPathIndex+1);
currentPath.dirs.push_back(1);
if(n.propagate(1)) // came from left
foundTarget = true;
currentPath.resetTo(myPathIndex);
}
}
if((dirBit & 2) == 0){ // try down
if(y < bounds.h){
mazePoint n(x, y+1, myPathIndex+1);
currentPath.dirs.push_back(8);
if(n.propagate(8)) // came from above
foundTarget = true;
currentPath.resetTo(myPathIndex);
}
}
if((dirBit & 1) == 0){ // try left
if(x > bounds.x){
mazePoint n(x-1, y, myPathIndex+1);
currentPath.dirs.push_back(4);
if(n.propagate(4)) // came from right
foundTarget = true;
currentPath.resetTo(myPathIndex);
}
}
return foundTarget;
}
}entryPoint(0,0);
int main(){
// setup the maze
mazeMap[0][0] = true;
mazeMap[1][0] = false;
mazeMap[2][0] = true;
mazeMap[3][0] = false;
mazeMap[0][1] = true;
mazeMap[1][1] = true;
mazeMap[2][1] = false;
mazeMap[3][1] = true;
mazeMap[0][2] = false;
mazeMap[1][2] = true;
mazeMap[2][2] = true;
mazeMap[3][2] = false;
mazeMap[0][3] = false;
mazeMap[1][3] = true;
mazeMap[2][3] = true;
mazeMap[3][3] = false;
cout << "Here's the map:" << endl;
for(int xint = 0;xint < 4;xint++){
for(int yint = 0;yint < 4;yint++)
cout << " " << (mazeMap[yint][xint] ? "Y" : "L"); // print 4 columns, then next columns
cout << endl;
}
// clear history of where we've already been
for(int xint = 0;xint < 4;xint++){
for(int yint = 0;yint < 4;yint++)
mazeFound[xint][yint] = false;
}
if(entryPoint.propagate(0)){
cout << "Found the goal! In total, there were " << paths.size() << " viable paths. A total of " << propagationAttempts << " propagation attempts were made." << endl << endl;
int shortestPathIndex = 0;
int longestPathIndex = 0;
for(int xint = 0, len = paths.size();xint < len;xint++){
if(paths[xint].dirs.size() < paths[shortestPathIndex].dirs.size()) shortestPathIndex = xint;
if(paths[xint].dirs.size() > paths[longestPathIndex].dirs.size()) longestPathIndex = xint;
}
cout << "The shortest path size was " << paths[shortestPathIndex].dirs.size() << " steps, and the longest was " << paths[longestPathIndex].dirs.size() << " steps." << endl << endl;
std::string printPath = "Shortest path steps: ";
int stepCount = paths[shortestPathIndex].dirs.size();
if(stepCount > 0) printPath += dirFrom4Bit(flipDir(paths[shortestPathIndex].dirs[0]));
for(int xint = 1;xint < stepCount;xint++){
printPath += ", ";
printPath += dirFrom4Bit(flipDir(paths[shortestPathIndex].dirs[xint]));
}
cout << printPath << endl << endl << "Wow!" << endl;
}else{
cout << "Didn't find any paths. " << paths.size() << endl;
}
return 0;
}
No comments:
Post a Comment