A library for solving mazes.
Diff: Lees_Algorithm.cpp
- Revision:
- 0:dddf6e50f1e7
- Child:
- 1:80b73beb7742
diff -r 000000000000 -r dddf6e50f1e7 Lees_Algorithm.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Lees_Algorithm.cpp Fri Jun 24 22:37:49 2011 +0000 @@ -0,0 +1,217 @@ +#include "Lees_Algorithm.h" +#include "mbed.h" + +Lees_Algorithm::Lees_Algorithm(unsigned char size_): mazeSize(size_) { + + map = new _cell*[mazeSize]; + for(int i = 0; i < mazeSize; i++) + { + map[i] = new _cell[mazeSize]; + } + + map[0][0].weight = 0; + map[0][0].weight -= 1; + maxWeight = map[0][0].weight; + + clearWeights(); + + for(int i = 0; i < mazeSize; i++) + { + for(int j = 0; j < mazeSize; j++) + { + if(i == 0) map[0][j].north = true; + else map[i][j].north = false; + if(j == 0) map[i][0].west = true; + else map[i][j].west = false; + } + } + + nextRead = 0; + nextWrite = 0; + stackSize = 0; + + return; +} + +Lees_Algorithm::~Lees_Algorithm(void) { + for(int i = 0; i < mazeSize; i++) + { + delete[] map[i]; + } + delete[] map; +} + + +void Lees_Algorithm::updateMap(_location position, bool wNorth, bool wWest, bool wSouth, bool wEast) { + _location buffer, newLoc; + unsigned char minimumWeight; + + // copy new walls to database + if(position.x == 0) wWest = true; // force some walls to true + if(position.y == 0) wNorth = true; + if(position.x == (mazeSize - 1)) wEast = true; + if(position.y == (mazeSize - 1)) wSouth = true; + + map[position.y][position.x].north = wNorth; + map[position.y][position.x].west = wWest; + map[((position.y + 1) % mazeSize)][position.x].north = wSouth; + map[position.y][((position.x + 1) % mazeSize)].west = wEast; + + // run lees algorthim + push(position); + + while(stackSize > 0) + { + buffer = pull(); + minimumWeight = 255; + + if(!map[buffer.y][buffer.x].north && map[(buffer.y - 1) % mazeSize][buffer.x].weight < minimumWeight) minimumWeight = map[(buffer.y - 1) % mazeSize][buffer.x].weight; + if(!map[buffer.y][buffer.x].west && map[buffer.y][(buffer.x - 1) % mazeSize].weight < minimumWeight) minimumWeight = map[buffer.y][(buffer.x - 1) % mazeSize].weight; + if(!map[(buffer.y + 1) % mazeSize][buffer.x].north && map[(buffer.y + 1) % mazeSize][buffer.x].weight < minimumWeight) minimumWeight = map[(buffer.y + 1) % mazeSize][buffer.x].weight; + if(!map[buffer.y][(buffer.x + 1) % mazeSize].west && map[buffer.y][(buffer.x + 1) % mazeSize].weight < minimumWeight) minimumWeight = map[buffer.y][(buffer.x + 1) % mazeSize].weight; + + if(map[buffer.y][buffer.x].weight != (minimumWeight + 1)) + { + if(map[buffer.y][buffer.x].weight != 0) map[buffer.y][buffer.x].weight = minimumWeight + 1; + + if(map[buffer.y][buffer.x].north == false) + { + newLoc.y = buffer.y - 1; + newLoc.x = buffer.x; + push(newLoc); + } + if(map[buffer.y][buffer.x].west == false) + { + newLoc.y = buffer.y; + newLoc.x = buffer.x - 1; + push(newLoc); + } + if(map[(buffer.y + 1) % mazeSize][buffer.x].north == false) + { + newLoc.y = (buffer.y + 1) % mazeSize; + newLoc.x = buffer.x; + push(newLoc); + } + if(map[buffer.y][(buffer.x + 1) % mazeSize].west == false) + { + newLoc.y = buffer.y; + newLoc.x = (buffer.x + 1) % mazeSize; + push(newLoc); + } + } + } + + return; +} + +char Lees_Algorithm::getDirection(_location position) { + char buffer; + return buffer; +} + +void Lees_Algorithm::initialFill(void) { + + int i,j; + bool finished = false; + + while(finished == false) + { + + for(i = 0; i < mazeSize; i++) + { + for(j = 0; j < mazeSize; j++) + { + if(map[i][j].weight == 0) + { + for(int k = j - 1; k >= 0; k--) + { + if(map[i][k].weight != 0) map[i][k].weight = map[i][k+1].weight + 1; + } + + for(int k = j + 1; k < mazeSize; k++) + { + if(map[i][k].weight != 0) map[i][k].weight = map[i][k-1].weight + 1; + } + } + if(i == (mazeSize - 1) && j == (mazeSize -1)) finished = true; + } + } + } + + for(int i = 0; i < mazeSize; i++) + { + if(map[i][0].weight < maxWeight) + { + for(int k = i - 1; k >= 0; k--) + { + if(map[k][0].weight == maxWeight) + { + for(int j = 0; j < mazeSize; j++) + { + map[k][j].weight = map[k+1][j].weight + 1; + } + } + } + for(int k = i + 1; k < mazeSize; k++) + { + if(map[k][0].weight == maxWeight) + { + for(int j = 0; j < mazeSize; j++) + { + map[k][j].weight = map[k-1][j].weight + 1; + } + } + } + } + } + + + return; +} + +void Lees_Algorithm::printMaze(Serial output) { + + for(int i = 0; i < mazeSize; i ++) + { + for(int j = 0; j < mazeSize; j++) + { + if(map[i][j].north == true) output.printf("+---"); + else output.printf("+ "); + } + output.printf("+\r\n"); + + for(int j = 0; j < mazeSize; j++) + { + if(map[i][j].west == true) output.printf("|"); + else output.printf(" "); + output.printf("%3i", map[i][j].weight); + } + if(map[i][0].west == true) output.printf("|\r\n"); + else output.printf(" \r\n"); + } + for(int j = 0; j < mazeSize; j ++) + { + if(map[0][j].north == 1) output.printf("+---"); + else output.printf("+ "); + } + output.printf("+\r\n"); + + return; +} + +void Lees_Algorithm::setDestination(_location target) { + map[target.y][target.x].weight = 0; +} + +void Lees_Algorithm::clearWeights(void) { + for (int j = 0; j < mazeSize; j++) + { + for (int i = 0; i < mazeSize; i++) + { + //map[0][0].weight = 0; + //map[0][0].weight -= 1; // should auto-set to 255 + map[j][i].weight = maxWeight; + } + } + return; +} \ No newline at end of file