Elysian Shadows

Code: Select all

#ifndef GRAPH_H
#define GRAPH_H

#include "puzzle.h"
#include <vector>

using namespace std;

class Graph {
public:

	//Employed using push_heap, pop_heap so they act as a PQ.
	//STL priority_queue does not allow iterating through elements, which A* requires.
	vector<PuzzleState*> openNodes;
	vector<PuzzleState*> closedNodes;
	bool Open(PuzzleState& p);
	bool Close(PuzzleState* p);
	PuzzleState* top();
	Graph();
	~Graph();
};

#endif

Code: Select all

#include "puzzle.h"
#include "graph.h"
#include <vector>
#include <algorithm>

using namespace std;

/***Graph::Open(PuzzleState* p)***
If p is not in the 'open' list, it is added and true is returned.
Otherwise, if it is found, parent is set to p's parent if necessary,
	depth is fixed, and false is returned.
****************************/
bool Graph::Open(PuzzleState& p) {

	vector<PuzzleState*>::iterator found;

	//Loop prevention
	//(Generating its set of neighbors that are not on C)

	found = find(closedNodes.begin(), closedNodes.end(), p);
	if (found != closedNodes.end()) {
		delete &p;
		return false;
	}

	//For each element that IS on O, if the path through x to N is
	//better than the currently known path, update g(x) := g(n) + d(n, x)
	//and associate the pointer to N with X, update f^(x) = g(x) + h(x)
	found = find(openNodes.begin(), openNodes.end(), p);
	if (found != openNodes.end()) {
		if ((*found)->getDepth() > p.getDepth()) {
			(*found)->setParent(p.getParent());
			(*found)->setDepth(p.getDepth());
			(*found)->CalculateHeuristic();
		}
		delete (&p);
		//Reorder O according to updated values of f^
		make_heap(openNodes.begin(), openNodes.end(), PSGreater);
		return false;
	}

	//For each node on M that is not on O, establish a pointer to N (constructor),
	//set g(x) := g(n) + d(n,x) [constructor],
	//set f^(x) = g(x) + h(x) [calculateHeuristic was called on generation (moveBlank)]
	//Add our new one (or replace the old one)
	openNodes.push_back(&p);
	//Reorder O according to updated values of f^
	push_heap(openNodes.begin(), openNodes.end(), PSGreater);
	return true;
}

/***Graph::Close(PuzzleState* p)***
If p is not in the 'closed' list, it is added and true is returned.
Otherwise, false is returned.
*****************************/
bool Graph::Close(PuzzleState* p) {

	vector<PuzzleState*>::iterator found;

	pop_heap(openNodes.begin(), openNodes.end(), PSGreater);
	found = find(openNodes.begin(), openNodes.end(), p);
	openNodes.erase(found);
	//make_heap(openNodes.begin(), openNodes.end(), PSGreater);

	if (find(closedNodes.begin(), closedNodes.end(), p) != closedNodes.end())
		return false;

	closedNodes.push_back(p);
	push_heap(closedNodes.begin(), closedNodes.end(), PSGreater);
	return true;
}

//Returns top of openNodes (lowest f^ value)
PuzzleState* Graph::top() {
	return *(openNodes.begin());
}

Graph::Graph() {
	//Don't think this is necessary, but...
	make_heap(openNodes.begin(), openNodes.end(), PSGreater);
	make_heap(closedNodes.begin(), closedNodes.end(), PSGreater);
}

//Deallocates everything
Graph::~Graph() {
	for (vector<PuzzleState*>::iterator i = openNodes.begin();i != openNodes.end();++i) {
		delete (*i);
		*i = NULL;
	}

	for (vector<PuzzleState*>::iterator i = closedNodes.begin();i != closedNodes.end();++i) {
		delete (*i);
		*i = NULL;
	}
}

Code: Select all

#ifndef PUZZLE_H
#define PUZZLE_H

#include <string>
using namespace std;

enum DIRECTION { NODIR = -1, UP, DOWN, LEFT, RIGHT, MAXDIR };

DIRECTION& operator++(DIRECTION& dir);

class Piece {
public:
	int number;
	Piece* neighbors[4];
	Piece();
};

class PuzzleState {
	const static int BOARD_WIDTH = 4;
	const static int BOARD_HEIGHT = 4;

	Piece board[BOARD_WIDTH][BOARD_HEIGHT];	//PuzzleState board, 0 == blank

	int blankX, blankY;		//Current coordinates of the blank tile
	int heuristic;
	int depth;
	PuzzleState* parent;

	void Swap(int x, int y);
	int CalculateManhattan();
	int CalculateMisplaced();

public:
	bool useManhattan;	//Determines what fn CalculateHeuristic() uses
						//[ CalculateManhattan() vs CalculateMisplaced() ]
	bool useAStar;		//If false, then depth is ignored, making this into Best-First

	PuzzleState();
	PuzzleState(const PuzzleState& rhs);

	bool MoveBlank(DIRECTION dir);
	void Scramble(int moves);
	int CalculateHeuristic();
	string generateOutput();

	//Accessors -----------
	void setParent(PuzzleState* pparent)	{ parent = pparent; }
	void setDepth(int pdepth)				{ depth = pdepth; }

	PuzzleState* getParent() const		{ return parent; }
	int getDepth() const				{ return depth; }
	int getHeuristic() const			{ return heuristic; }
	const int getBoardHeight() const	{ return BOARD_HEIGHT; }
	const int getBoardWidth() const		{ return BOARD_WIDTH; }

	friend bool operator==(const PuzzleState* lhs, const PuzzleState& rhs);
};

bool PSGreater(const PuzzleState* lhs, const PuzzleState* rhs);

#endif

Code: Select all

#include "puzzle.h"
#include <cstdlib>			//rand, abs
#include <ctime>			//time for rand
#include <string>			//for puzzlestate::generateoutput
#include <sstream>			//for puzzlestate::generateoutput

#include "graph.h"			//for Scramble()...
#include <vector>			//for Scramble()...
#include <algorithm>		//for Scramble()...
#include <iostream>

using namespace std;

DIRECTION& operator++(DIRECTION& dir) {
	return dir = (dir == MAXDIR) ? UP : DIRECTION(dir + 1);
}

/***Piece() [constructor]***
Sets piece to a blank
***************************/
Piece::Piece() {
	number = 0;
}

/***PuzzleState() [constructor]***
Initializes PuzzleState board to ascending numerical order, blank tile at
	bottom-right. Initializes relevant variables.
****************************/
PuzzleState::PuzzleState() {

	Piece curPiece;
	curPiece.number = 1;

	for (int y = 0; y < BOARD_HEIGHT;y++) {
		for (int x = 0; x < BOARD_WIDTH;x++) {
			if (curPiece.number >= BOARD_HEIGHT * BOARD_WIDTH)
				curPiece.number = 0;
			board[x][y] = curPiece;
			curPiece.number++;
		}
	}

	parent = NULL;
	blankX = BOARD_WIDTH-1;
	blankY = BOARD_HEIGHT-1;
	depth = 0;
	useManhattan = true;
	useAStar = true;
}

/***PuzzleState(const PuzzleState& rhs)***
Copies all members from rhs to *this
*****************************************/
PuzzleState::PuzzleState(const PuzzleState& rhs) {
	for (int curY = 0; curY < BOARD_HEIGHT;curY++)
		for (int curX = 0; curX < BOARD_WIDTH;curX++)
			board[curX][curY].number = rhs.board[curX][curY].number;
	//Establish a pointer to N,
	//set g(x) := g(n) + d(n,x),
	//set f^(x) = g(x) + h(x)
	blankX = rhs.blankX;
	blankY = rhs.blankY;

	useAStar = rhs.useAStar;
	useManhattan = rhs.useManhattan;

	if (useAStar)
		depth = rhs.depth+1;				//g(x) := g(n) + d(n,x),
	else
		depth = 0;

	parent = const_cast<PuzzleState*>(&rhs);
	heuristic = rhs.heuristic;

	CalculateHeuristic();	//f^(x) = g(x) + h(x), although a Move should be called or we have a duplicate, deeper state.
}

bool operator==(const PuzzleState* lhs, const PuzzleState& rhs) {
	for (int curY = 0; curY < lhs->BOARD_HEIGHT; curY++) {
		for (int curX = 0; curX < lhs->BOARD_WIDTH; curX++)
			if (lhs->board[curX][curY].number != rhs.board[curX][curY].number)
				return false;
	}
	return true;
}

bool PSGreater(const PuzzleState* lhs, const PuzzleState* rhs) {
	return lhs->getHeuristic() > rhs->getHeuristic();
};

/***Swap(int x, int y)***
 Swaps board[x][y] & board[blankX][blankY] whether the move is legal or not
************************/
void PuzzleState::Swap(int x, int y) {
	Piece blank;

	board[blankX][blankY] = board[x][y];
	board[x][y] = blank;
	blankX = x;
	blankY = y;
	CalculateHeuristic();
}

/***MoveBlank(DIRECTION dir)***
 Swaps blank tile with the tile to its DIRECTION
 Returns true on success.
******************************/
bool PuzzleState::MoveBlank(DIRECTION dir) {
	if (dir == UP && blankY == 0)
		return false;
	if (dir == DOWN && blankY == BOARD_HEIGHT-1)
		return false;
	if (dir == LEFT && blankX == 0)
		return false;
	if (dir == RIGHT && blankX == BOARD_WIDTH-1)
		return false;

	int x = blankX;
	int y = blankY;

	if (dir == RIGHT)
		x++;
	else if (dir == LEFT)
		x--;
	else if (dir == UP)
		y--;
	else if (dir == DOWN)
		y++;
	else //NODIR
		return false;

	Swap(x, y);
	return true;
}

/***isAdjacent(int x, int y)***
 Returns direction to blank tile if blank is adjacent to board[x][y]
***************************/
/*DIRECTION PuzzleState::isAdjacent(int x, int y) {

	for (int direction = 0;direction < (int)MAXDIR;direction++) {
		if (board[x][y].neighbors[direction]->number == 0)
			return (DIRECTION)direction;
	}
	return NODIR;
}*/

/***Scramble(int moves)***
 Scrambles the PuzzleState by randomly moving the blank tile 'moves' spaces.
 Records this amount in PuzzleState::scrambleMoves
 Returns scrambleMoves.
*************************/
void PuzzleState::Scramble(int moves) {

	int scrambleMoves = 0;
	//Keep from getting same random # more than once
	srand((unsigned int)time(NULL));
	unsigned int lastRand = rand();

	PuzzleState* test;
	vector<PuzzleState*> states;

	test = new PuzzleState(*this);				//Initialize our test space
	states.push_back(new PuzzleState(*this));	//Push a copy of the start state
	cout << this->generateOutput();

	while (scrambleMoves < moves) {
		srand(lastRand + (unsigned int)time(NULL));
		lastRand = rand();
		//Don't move if the movement is already on the state list
		//In other words, make sure the movments are contiguous.

		//Guarantee that the move is legal
		if (test->MoveBlank((DIRECTION)(lastRand % 4))) {
			//Guarantee nonrepeating scramble
			if (find(states.begin(), states.end(), *test) == states.end()) {
				//Now that we have a move that wasn't on the state list, do the move
				MoveBlank((DIRECTION)(lastRand % 4));
				scrambleMoves++;
				states.push_back(new PuzzleState(*this));		//Push a copy onto the state listing
				cout << this->generateOutput();
			}
		}
		//Reset test state to either 1) the not moved version or 2) the moved version of 'this'
		delete test;
		test = new PuzzleState(*this);
	}
	delete test;
	test = NULL;
	cout << "--------------" << endl;
	for (vector<PuzzleState*>::iterator i = states.begin(); i != states.end(); ++i) {
		delete (*i);
		*i = NULL;
	}
}

int PuzzleState::CalculateManhattan() {
	// 1  2  3  4 % 4: 1 2 3 0, -1: 0 1 2 -1
	// 5  6  7  8 % 4: 1 2 3 0
	// 9 10 11 12 % 4
	//13 14 15 00

	int properx, propery;
	int xdist, ydist;

	heuristic = 0;
	for (int y = 0;y < BOARD_HEIGHT;y++) {
		for (int x = 0;x < BOARD_WIDTH;x++) {
			properx = (board[x][y].number % BOARD_WIDTH)-1;
			if (properx == -1)
				properx = BOARD_WIDTH-1;
			xdist = abs(x-properx);

			if (board[x][y].number == 0)
				propery = BOARD_HEIGHT-1;
			else
				propery = int( (board[x][y].number-1) / BOARD_HEIGHT);
			ydist = abs(y-propery);

			heuristic += xdist + ydist;
		}
	}

	heuristic += depth;
	return heuristic;
}

int PuzzleState::CalculateMisplaced() {

	int curNumber = 1;
	int misplaced = 0;

	for (int curY = 0;curY < BOARD_HEIGHT;curY++) {
		for (int curX = 0;curX < BOARD_WIDTH;curX++) {
			if (board[curX][curY].number != curNumber)
				misplaced++;
			curNumber++;
			if (curNumber == 16)
				curNumber = 0;
		}
	}

	heuristic = misplaced + depth;
	return heuristic;
}

int PuzzleState::CalculateHeuristic() {
	if (useManhattan)
		return CalculateManhattan();
	else
		return CalculateMisplaced();
}

string PuzzleState::generateOutput() {
	string retval;
	for (int y = 0; y < BOARD_HEIGHT;y++) {
		for (int x = 0; x < BOARD_WIDTH;x++) {
			stringstream conv;
			if (board[x][y].number < 10)
				conv << " ";
			conv << board[x][y].number;
			retval += conv.str() + " ";
			conv.clear();
		}
		retval += "\n";
	}
	retval += "---\n";
	return retval;
}

Code: Select all

#include "puzzle.h"
#include "graph.h"
#include <vector>
#include <algorithm>		//for make_heap, sort_heap, push_heap, pop_heap...
#include <iostream>
#include <string>

using namespace std;

int main() {

	//Create lists Open & Closed
	Graph g;

	PuzzleState* start = new PuzzleState();		//Gets scrambled later
	PuzzleState goal;						//Unmodified PuzzleState, used to test for goal state

	start->useAStar = true; //if false, best-first search is used
	start->useManhattan = true; //if false, misplaced tiles is used
	start->Scramble(5);//change this to change how many moves we scramble (you probably want to do <= 10)

	//Put initial node on O
	g.Open(*start);

	//O can't be empty. If it could be, we would test for it & exit w/ fail here

	PuzzleState* current;
	PuzzleState* neighbor;
	unsigned int examined = 0;

	while (!g.openNodes.empty()) {

		//Take 1st node, remove it from O, put it on C.
		current = g.top();
		g.Close(current);
		examined++;

		//If current is a goal, exit with success
		if (current == goal) {
			cout << "====" << endl;
			int steps = -1;
			string output = "";
			PuzzleState* state = current;
			while (state != NULL) {
				steps++;
				output = (state->generateOutput() + output);
				state = state->getParent();
			}
			cout << output << endl;
			cout << "Goal reached in " << steps << " moves." << endl;
			cout << "There were " << examined << " states examined." << endl;
			if (current->useAStar)
				cout << "And a maximum depth of " << current->getDepth() << endl;
#ifdef _WIN32
			system("pause");
#endif
			return 0;
		}

		//Expand N, generating the set of its neighbors that are not on C, call it M.
		//Add all neighbors to heap
		for (DIRECTION dir = DIRECTION(NODIR+1);dir < MAXDIR;++dir) {
			//For each node not in O,  establish a pointer to N, ...

			//Constructor: establish a pointer to N, g(x) := g(n) + d(n,x)
			neighbor = new PuzzleState(*current);
			if (neighbor->MoveBlank(dir))					//gen. child and f^(x) = g(x) + h(x)
				g.Open(*neighbor);
			else
				delete neighbor;
		}
	}

	cout << "No goal." << endl;
#ifdef _WIN32
	system("pause");
#endif
	return 1;
}