#include <iostream>
using namespace std;
struct grid {
// legal values for these are 0 (no), 1 (yes), 2 (maybe), 3 (probably)
// wumpus and gold can be 4 or greater (indicating more squares show the wumpus/gold is there)
int pit;
int wumpus;
int gold;
int blank;
// legal values are 0 (no) and 1 (yes)
int visited;
int visited2;
int path;
// constructor
grid();
};
// constructor - set all flags to "maybe"
grid::grid() {
pit = 2;
wumpus = 2;
gold = 2;
blank = 2;
visited = 0;
visited2 = 0;
path = 0;
}
grid board[4][4]; // the wumpus board
int signal = 0; // IR signal
int y = 3, x = 0; // current position (algorithm coordinate system uses () w/ y=0 as the top row
bool foundGold = false, home = false, wumpusDead = false, foundWumpus = false, goldKnown = false;
// legal signal input values are: 16, 32, 48, 64, 80, 96, 112, 128, 144 (see RemoteCodes.doc)
void getSignal () {
cout << "Waiting for signal..." << endl << "Valid signals are multiples of 16 up to and including 144. See RemoteCodes.doc for more info." << endl << "> ";
cin >> signal;
while ((signal > 144) || (signal % 16 != 0) || (signal < 0)) {
cout << endl << "Invalid signal. Try again." << endl << "> ";
cin >> signal;
}
cout << endl;
}
// move up 1 square
void moveUp() {
board[y][x].visited2 = 1;
y -= 1;
board[y][x].visited = 1;
board[y][x].path = 1;
}
// move right 1 square
void moveRight() {
board[y][x].visited2 = 1;
x += 1;
board[y][x].visited = 1;
board[y][x].path = 1;
}
// move down 1 square
void moveDown() {
board[y][x].visited2 = 1;
y += 1;
board[y][x].visited = 1;
board[y][x].path = 1;
}
// move left 1 square
void moveLeft() {
board[y][x].visited2 = 1;
x -= 1;
board[y][x].visited = 1;
board[y][x].path = 1;
}
// try to get home
void goHome() {
if ((x > 0) && (board[y][x-1].visited2 == 1))
moveLeft();
else if ((y < 3) && (board[y+1][x].visited2 == 1))
moveDown();
else if ((x < 3) && (board[y][x+1].visited2 == 1))
moveRight();
else if ((y > 0) && (board[y-1][x].visited2 == 1))
moveUp();
}
// move back to previous location
void moveBack() {
board[y][x].path = 0;
if ((x > 0) && (board[y][x-1].path == 1))
moveLeft();
else if ((y < 3) && (board[y+1][x].path == 1))
moveDown();
else if ((x < 3) && (board[y][x+1].path == 1))
moveRight();
else if ((y > 0) && (board[y-1][x].path == 1))
moveUp();
else if ((y > 0) && (board[y-1][x].visited2 == 1))
moveUp();
else if ((x < 3) && (board[y][x+1].visited2 == 1))
moveRight();
else if ((x > 0) && (board[y][x-1].visited2 == 1))
moveLeft();
else if ((y < 3) && (board[y+1][x].visited2 == 1))
moveDown();
}
// kill the wumpus
void killWumpus(int yPos, int xPos) {
// kill wumpus effects go here; replace the next line w/ shoot & music lines
cout << "Shot the wumpus." << endl;
wumpusDead = true;
board[yPos][xPos].blank = 1;
}
void updateWump(int y, int x) {
int i, j;
board[y][x].wumpus = 1;
board[y][x].pit = 0;
board[y][x].gold = 0;
board[y][x].blank = 0;
foundWumpus = true;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (!((i == y) && (j == x)))
board[i][j].wumpus = 0;
}
}
}
void updateGold(int y, int x) {
int i, j;
board[y][x].gold = 1;
board[y][x].pit = 0;
board[y][x].wumpus = 0;
board[y][x].blank = 0;
goldKnown = true;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (!((i == y) && (j == x)))
board[i][j].gold = 0;
}
}
}
// update adjacent squares according to signal received
void updateAdj() {
int i, j, a, b; // loop control vars
int numsurrounding;
if (signal == 128) { // nothing
if (y > 0) {
board[y-1][x].wumpus = 0;
board[y-1][x].gold = 0;
board[y-1][x].pit = 0;
board[y-1][x].blank = 1;
}
if (y < 3) {
board[y+1][x].wumpus = 0;
board[y+1][x].gold = 0;
board[y+1][x].pit = 0;
board[y+1][x].blank = 1;
}
if (x > 0) {
board[y][x-1].wumpus = 0;
board[y][x-1].gold = 0;
board[y][x-1].pit = 0;
board[y][x-1].blank = 1;
}
if (x < 3) {
board[y][x+1].wumpus = 0;
board[y][x+1].gold = 0;
board[y][x+1].pit = 0;
board[y][x+1].blank = 1;
}
}
else if (signal == 144) { // gold
board[y][x].gold = 0;
board[y][x].blank = 1;
foundGold = true;
for (i = 0; i <= 3; i++) {
for (j = 0; j <= 3; j++) {
if (i != y && j != x) {
board[i][j].gold = 0;
}
}
}
}
else if (signal == 16) { // breeze
if ((y > 0) && (board[y-1][x].blank != 1)) {
board[y-1][x].wumpus = 0;
board[y-1][x].gold = 0;
if (board[y-1][x].pit == 2)
board[y-1][x].pit = 3;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
board[y+1][x].wumpus = 0;
board[y+1][x].gold = 0;
if (board[y+1][x].pit == 2)
board[y+1][x].pit = 3;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
board[y][x-1].wumpus = 0;
board[y][x-1].gold = 0;
if (board[y][x-1].pit == 2)
board[y][x-1].pit = 3;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
board[y][x+1].wumpus = 0;
board[y][x+1].gold = 0;
if (board[y][x+1].pit == 2)
board[y][x+1].pit = 3;
}
}
else if (signal == 32) { // stench
if ((y > 0) && (board[y-1][x].blank != 1)) {
board[y-1][x].pit = 0;
board[y-1][x].gold = 0;
if ((board[y-1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y-1][x].wumpus++;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
board[y+1][x].pit = 0;
board[y+1][x].gold = 0;
if ((board[y+1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y+1][x].wumpus++;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
board[y][x-1].pit = 0;
board[y][x-1].gold = 0;
if ((board[y][x-1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x-1].wumpus++;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
board[y][x+1].pit = 0;
board[y][x+1].gold = 0;
if ((board[y][x+1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x+1].wumpus++;
}
}
else if (signal == 64) { // glitter
if ((y > 0) && (board[y-1][x].blank != 1)) {
board[y-1][x].wumpus = 0;
board[y-1][x].pit = 0;
if ((board[y-1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y-1][x].gold++;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
board[y+1][x].wumpus = 0;
board[y+1][x].pit = 0;
if ((board[y+1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y+1][x].gold++;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
board[y][x-1].wumpus = 0;
board[y][x-1].pit = 0;
if ((board[y][x-1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x-1].gold++;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
board[y][x+1].wumpus = 0;
board[y][x+1].pit = 0;
if ((board[y][x+1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x+1].gold++;
}
}
else if (signal == 48) { // stench & breeze
if ((y > 0) && (board[y-1][x].blank != 1)) {
board[y-1][x].gold = 0;
if (board[y-1][x].pit == 2)
board[y-1][x].pit = 3;
if ((board[y-1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y-1][x].wumpus++;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
board[y+1][x].gold = 0;
if (board[y+1][x].pit == 2)
board[y+1][x].pit = 3;
if ((board[y+1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y+1][x].wumpus++;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
board[y][x-1].gold = 0;
if (board[y][x-1].pit == 2)
board[y][x-1].pit = 3;
if ((board[y][x-1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x-1].wumpus++;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
board[y][x+1].gold = 0;
if (board[y][x+1].pit == 2)
board[y][x+1].pit = 3;
if ((board[y][x+1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x+1].wumpus++;
}
}
else if (signal == 80) { // glitter & breeze
if ((y > 0) && (board[y-1][x].blank != 1)) {
board[y-1][x].wumpus = 0;
if ((board[y-1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y-1][x].gold++;
if (board[y-1][x].pit == 2)
board[y-1][x].pit = 3;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
board[y+1][x].wumpus = 0;
if ((board[y+1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y+1][x].gold++;
if (board[y+1][x].pit == 2)
board[y+1][x].pit = 3;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
board[y][x-1].wumpus = 0;
if ((board[y][x-1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x-1].gold++;
if (board[y][x-1].pit == 2)
board[y][x-1].pit = 3;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
board[y][x+1].wumpus = 0;
if ((board[y][x+1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x+1].gold++;
if (board[y][x+1].pit == 2)
board[y][x+1].pit = 3;
}
}
else if (signal == 96) { // glitter & stench
if ((y > 0) && (board[y-1][x].blank != 1)) {
board[y-1][x].pit = 0;
if ((board[y-1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y-1][x].gold++;
if ((board[y-1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y-1][x].wumpus++;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
board[y+1][x].pit = 0;
if ((board[y+1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y+1][x].gold++;
if ((board[y+1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y+1][x].wumpus++;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
board[y][x-1].pit = 0;
if ((board[y][x-1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x-1].gold++;
if ((board[y][x-1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x-1].wumpus++;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
board[y][x+1].pit = 0;
if ((board[y][x+1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x+1].gold++;
if ((board[y][x+1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x+1].wumpus++;
}
}
else if (signal == 112) { // glitter & stench & breeze
if ((y > 0) && (board[y-1][x].blank != 1)) {
if ((board[y-1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y-1][x].gold++;
if ((board[y-1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y-1][x].wumpus++;
if (board[y-1][x].pit == 2)
board[y-1][x].pit = 3;
}
if ((y < 3) && (board[y+1][x].blank != 1)) {
if ((board[y+1][x].gold > 1) && (board[y][x].visited2 == 0))
board[y+1][x].gold++;
if ((board[y+1][x].wumpus > 1) && (board[y][x].visited2 == 0))
board[y+1][x].wumpus++;
if (board[y+1][x].pit == 2)
board[y+1][x].pit = 3;
}
if ((x > 0) && (board[y][x-1].blank != 1)) {
if ((board[y][x-1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x-1].gold++;
if ((board[y][x-1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x-1].wumpus++;
if (board[y][x-1].pit == 2)
board[y][x-1].pit = 3;
}
if ((x < 3) && (board[y][x+1].blank != 1)) {
if ((board[y][x+1].gold > 1) && (board[y][x].visited2 == 0))
board[y][x+1].gold++;
if ((board[y][x+1].wumpus > 1) && (board[y][x].visited2 == 0))
board[y][x+1].wumpus++;
if (board[y][x+1].pit == 2)
board[y][x+1].pit = 3;
}
}
// go through the board and mark all confirmed empty squares as confirmed blanks
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if ((board[i][j].gold == 0) && (board[i][j].wumpus == 0) && (board[i][j].pit == 0)) {
board[i][j].blank = 1;
}
}
}
// check all the squares to try to determine location of wumpus
if (!foundWumpus) {
for (a = 0; a < 4; a++) {
for (b = 0; b < 4; b++) {
if (board[a][b].wumpus > 3)
updateWump(a, b);
else if (board[a][b].wumpus == 3) {
numsurrounding = 0;
if (a > 0) {
if (b > 0) {
if (board[a-1][b-1].wumpus > 2)
numsurrounding++;
}
if (b < 3) {
if (board[a-1][b+1].wumpus > 2)
numsurrounding++;
}
}
if (a < 3) {
if (b > 0) {
if (board[a+1][b-1].wumpus > 2)
numsurrounding++;
}
if (b < 3) {
if (board[a+1][b+1].wumpus > 2)
numsurrounding++;
}
}
if ((numsurrounding == 0) || (numsurrounding > 2)) {
updateWump(a, b);
}
}
}
}
}
// check all the squares to try to determine location of gold
if (!goldKnown) {
for (a = 0; a < 4; a++) {
for (b = 0; b < 4; b++) {
if (board[a][b].gold > 3)
updateGold(a, b);
if (board[a][b].gold == 3) {
numsurrounding = 0;
if (a > 0) {
if (b > 0) {
if (board[a-1][b-1].gold > 2)
numsurrounding++;
}
if (b < 3) {
if (board[a-1][b+1].gold > 2)
numsurrounding++;
}
}
if (a < 3) {
if (b > 0) {
if (board[a+1][b-1].gold > 2)
numsurrounding++;
}
if (b < 3) {
if (board[a+1][b+1].gold > 2)
numsurrounding++;
}
}
if ((numsurrounding == 0) || (numsurrounding > 2)) {
updateGold(a, b);
}
}
}
}
}
}
void decide() {
// priorities: definite gold, then possible gold (safe), then wumpus, then unexplored blank, then go back
// see if the squares might have gold and don't have a pit or wumpus
if (y > 0) {
if ((board[y-1][x].gold > 0) && (board[y-1][x].wumpus == 0) && (board[y-1][x].pit == 0) && (board[y-1][x].visited == 0)) {
moveUp();
return;
}
}
if (x < 3) {
if ((board[y][x+1].gold > 0) && (board[y][x+1].wumpus == 0) && (board[y][x+1].pit == 0) && (board[y][x+1].visited == 0)) {
moveRight();
return;
}
}
if (y < 3) {
if ((board[y+1][x].gold > 0) && (board[y+1][x].wumpus == 0) && (board[y+1][x].pit == 0) && (board[y+1][x].visited == 0)) {
moveDown();
return;
}
}
if (x > 0) {
if ((board[y][x-1].gold > 0) && (board[y][x-1].wumpus == 0) && (board[y][x-1].pit == 0) && (board[y][x-1].visited == 0)) {
moveLeft();
return;
}
}
// wumpus check
if (!wumpusDead) {
if (y > 0) {
if (board[y-1][x].wumpus == 1) {
killWumpus(y-1, x);
moveUp();
board[y][x].blank = 1;
return;
}
}
if (x < 3) {
if (board[y][x+1].wumpus == 1) {
killWumpus(y, x+1);
moveRight();
board[y][x].blank = 1;
return;
}
}
if (y < 3) {
if (board[y+1][x].wumpus == 1) {
killWumpus(y+1, x);
moveDown();
board[y][x].blank = 1;
return;
}
}
if (x > 0) {
if (board[y][x-1].wumpus == 1) {
killWumpus(y, x-1);
moveLeft();
board[y][x].blank = 1;
return;
}
}
}
// check for unexplored blank
if (y > 0) {
if ((board[y-1][x].blank == 1) && (board[y-1][x].path == 0) && (board[y-1][x].visited == 0)) {
moveUp();
return;
}
}
if (x < 3) {
if ((board[y][x+1].blank == 1) && (board[y][x+1].path == 0) && (board[y][x+1].visited == 0)) {
moveRight();
return;
}
}
if (y < 3) {
if ((board[y+1][x].blank == 1) && (board[y+1][x].path == 0) && (board[y+1][x].visited == 0)) {
moveDown();
return;
}
}
if (x > 0) {
if ((board[y][x-1].blank == 1) && (board[y][x-1].path == 0) && (board[y][x-1].visited == 0)) {
moveLeft();
return;
}
}
// otherwise, move back
moveBack();
}
void main() {
// set starting conditions of bottom-left 3 squares
// start at square [3][0] (bottom left corner), which must be a blank
board[3][0].blank = 1;
board[3][0].pit = 0;
board[3][0].wumpus = 0;
board[3][0].gold = 0;
board[3][0].visited = 1;
board[3][0].path = 1;
// 2 adjacent squares must be blanks also
board[3][1].blank = 1;
board[3][1].pit = 0;
board[3][1].wumpus = 0;
board[3][1].gold = 0;
board[2][0].blank = 1;
board[2][0].pit = 0;
board[2][0].wumpus = 0;
board[2][0].gold = 0;
// first move: move up (arbitrary - we could move right), then get a signal
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << " ";
if (y == i && x == j)
cout << "+";
else if (board[i][j].path == 1)
cout << "#";
else if (board[i][j].visited == 1)
cout << "*";
else
cout << "O";
}
cout << endl;
}
moveUp();
cout << endl;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << " ";
if (y == i && x == j)
cout << "+";
else if (board[i][j].path == 1)
cout << "#";
else if (board[i][j].visited == 1)
cout << "*";
else
cout << "O";
}
cout << endl;
}
getSignal();
updateAdj();
while (!foundGold) {
decide();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << " ";
if (y == i && x == j)
cout << "+";
else if (board[i][j].path == 1)
cout << "#";
else if (board[i][j].visited == 1)
cout << "*";
else
cout << "O";
}
cout << endl;
}
cout << endl << "x = " << x << " y = " << y << endl;
getSignal();
updateAdj();
}
while (!home) {
goHome();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << " ";
if (y == i && x == j)
cout << "+";
else if (board[i][j].path == 1)
cout << "#";
else if (board[i][j].visited == 1)
cout << "*";
else
cout << "O";
}
cout << endl;
}
cout << endl;
if (y == 3 && x == 0)
home = true;
}
cout << "Done, press enter to exit.";
cin.get();
cin.get();
}
©2008-2009