A Star Search
Jack Jonshen
Project1forVisualStudiousers.zipProject 1 for Visual Studio users/.DS_Store
__MACOSX/Project 1 for Visual Studio users/._.DS_Store
Project 1 for Visual Studio users/main.cpp
Project 1 for Visual Studio users/main.cpp
/**********************************************************************************************************************/
/* This project is for students to practice search algorithms by appling them to solve the 9 puzzle problems. */
/* */
/* Usage: The whole image is divided into 3-by-3 squares. There are 8 sub-images and 1 empty space. */
/* These sub-images are placed in a random order, which makes the whole pattern look messy. */
/* So the goal is to re-organize these sub-images to align them in the right order. */
/* User can only move one sub-image at each time by left clicking it follwed by clicking the empty space. */
/* Each time, only neighboring sub-images around the empty space can be moved. At any time, even in the */
/* begining, if you do not want to continue playing the game, you can simply hit the keyboard - "s" key to */
/* obtain the solution. The system then automatically search for a possible path by using your implemented */
/* search algorithmns. So after you click the "s" key, what you should do is just to wait for the search */
/* result and see the sub-images move automatically followed by the output path until all the sub-images */
/* become perfectly aligned. */
/* */
/* Author: Ju Shen, Department of Computer Science, University of Dayton */
/* */
/* Instructions: */
/* For this project, you only focus on implementing the search algorithms. They are the functions */
/* in the "SolutionSearch" class, which are marked as "Student Implementation:" in the comments. */
/* You can search the key words "Student Implementation" to find the places require you to write */
/* your code. */
/* */
/* The GUI has already been implemted, so there is no need to do anything on it for this project. */
/* However, students are encouraged to get farmiliar with them, as you may need to implement them in */
/* the future projects. */
/* */
/**********************************************************************************************************************/
#include
<
vector
>
// std::vector
#include
<
iostream
>
#include
<
queue
>
#include
<
map
>
#include
<
opencv2
/
core
/
core
.
hpp
>
#include
<
opencv2
/
highgui
/
highgui
.
hpp
>
#include
<
opencv2
/
imgproc
/
imgproc
.
hpp
>
#include
<
opencv
/
cv
.
h
>
#include
"stdio.h"
#include
"math.h"
using
namespace
cv
;
using
namespace
std
;
#include
"RandomGenerator.h"
#include
"VisualDisplay.h"
void
printData
(
int
*
data
)
{
printf
(
"%d, %d, %d\n %d, %d, %d\n %d, %d, %d\n"
,
data
[
0
],
data
[
1
],
data
[
2
],
data
[
3
],
data
[
4
],
data
[
5
],
data
[
6
],
data
[
7
],
data
[
8
]);
}
int
main
(
int
arg
,
char
**
argv
)
{
int
num_seq
[
9
]
=
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
};
//These numbers are used to represent those sub-images (or pieces),
// by default, the number 8 represents the empty space.
// So when these numbers are in different order, it means the correseponding sum-images
// are in different places. Initially, we make all the sub-images in the correct order.
// But they will be randomly reshuffled in the following code.
/* For example: {0, 1, 2, 3, 4, 5, 6, 7, 8} in the GUI, its layout is:
0 1 2
3 4 5
6 7 8
which is the one we want.
*/
RandomGenerator
rg
;
//Used to generate different random orders
rg
.
getRandomSeq
(
num_seq
,
52
);
//The generated random order is stored in the "num_seq" array. The second parameter is an
// integer which indicates how much degree you want to mess up the sub-images. The bigger
// it is, the more messy it could be.
/* For example, the random sequence after reshuffle can be: num_seq = {3, 8, 5, 2, 0, 4, 6, 7, 1}
3 8 5
2 0 4
6 7 1
*/
VisualDisplay
display
;
//The class for the GUI, which you do not need to do any change
int
target_pos
;
//This stores the posit
/*Find the position of the empty space*/
for
(
int
i
=
0
;
i
<
9
;
i
++
)
{
if
(
num_seq
[
i
]
==
8
)
target_pos
=
i
;
}
/*For testing purpose, you can see the output of the generated random order in the console*/
printf
(
"The Current Pattern is :\n"
);
printData
(
num_seq
);
/******************************************* The two lines below are to show and run the game **************************************************/
/* Before you implement the code, if you run the program, and hit the "s" key, there is nother happened. Because you the "s" */
/* is to trigger the search algorithm to find the possible solution. Since you have not done anything on it yet, it returns */
/* an empty path, which you can see from the console. */
/* */
/* When you are testing your code or doing debug, you can simply comment out these two lines of codes. So you can focus on the */
/* data and may output them to the console or use the debug tool to analyze them. After you are confident of your search code, */
/* you can not uncomment these lines and enjoy the game. */
/* */
display
.
load
(
const_cast
<
char
*>
(
"test.jpg"
),
num_seq
,
target_pos
);
//The first parameter is the image file name. For fun, you can place any image you like,
//no need to be square image, as long as it is close to square.
//The second parameter is the generated random sequence.
//The third parameter is the detected empty space position in the array
display
.
run
();
return
1
;
}
__MACOSX/Project 1 for Visual Studio users/._main.cpp
Project 1 for Visual Studio users/RandomGenerator.cpp
#include "RandomGenerator.h" #include <ctime> // std::time #include <algorithm> #include <iostream> RandomGenerator::RandomGenerator(void) { /***************** Pre-store the available moving direction or child of current tree ********/ /* 0 1 2 */ /* 3 4 5 */ /* 6 7 8 */ /***************** The order is left, bottom, right, top ***********************************/ moving_directions[0].push_back(3); //for each position, tell the piece-8 which one in the array that it can be swapped with. // So only two pieces are considered each time, when the piece-8 is moving. moving_directions[0].push_back(1); moving_directions[1].push_back(0); moving_directions[1].push_back(4); moving_directions[1].push_back(2); moving_directions[2].push_back(1); moving_directions[2].push_back(5); moving_directions[3].push_back(6); moving_directions[3].push_back(4); moving_directions[3].push_back(0); moving_directions[4].push_back(3); moving_directions[4].push_back(7); moving_directions[4].push_back(5); moving_directions[4].push_back(1); moving_directions[5].push_back(4); moving_directions[5].push_back(8); moving_directions[5].push_back(2); moving_directions[6].push_back(7); moving_directions[6].push_back(3); moving_directions[7].push_back(6); moving_directions[7].push_back(8); moving_directions[7].push_back(4); moving_directions[8].push_back(7); moving_directions[8].push_back(5); } RandomGenerator::~RandomGenerator(void) { } /*Generate the random sequence based on moving from goal status*/ void RandomGenerator::getRandomSeq(int* num, int steps) { int cur_pos = 8; //The position of the 8-piece int swap_pos; //The position that is used to be swapped with the 8-piece int temp; //Used for data swap int choices; //The number of choiece for different positions of 8-piece int x; //The choice randomly made from different choieces srand(time(NULL)); for(int i = 0; i < steps; i++) { int choices = moving_directions[cur_pos].size(); x = rand() % choices; swap_pos = moving_directions[cur_pos][x]; temp = num[cur_pos]; num[cur_pos] = num[swap_pos]; num[swap_pos] = temp; cur_pos = swap_pos; } } /*Purely generate random number, not gurantee it has a solution*/ void RandomGenerator::getRandomSeq2(int* num) { std::srand ( unsigned ( std::time(0) ) ); std::vector<int> myvector; for (int i = 0; i < 9; i++) myvector.push_back(i); // 0 1 2 3 4 5 6 7 8 // using built-in random generator: std::random_shuffle ( myvector.begin(), myvector.end() ); int idx = 0; for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) { num[idx] = *it; idx++; } };
__MACOSX/Project 1 for Visual Studio users/._RandomGenerator.cpp
Project 1 for Visual Studio users/RandomGenerator.h
#pragma once #include <vector> class RandomGenerator { private: std::vector<int> moving_directions[9]; public: RandomGenerator(void); ~RandomGenerator(void); void getRandomSeq2(int *num); /*Purely generate random number, not gurantee it has a solution*/ void getRandomSeq(int *num, int steps); /*Generate the random sequence based on moving from goal status*/ };
__MACOSX/Project 1 for Visual Studio users/._RandomGenerator.h
Project 1 for Visual Studio users/SolutionSearch.cpp
#include "SolutionSearch.h" SolutionSearch::SolutionSearch(void) { } SolutionSearch::~SolutionSearch(void) { } /* Student Implementation: here you need to implement the Breadth First Search Method */ /* */ /* Input: the first parameter is the random order of the 9 numbers, which you need to */ /* re-organize to make them into the correct order. */ /* the second parameter is actually an output. It returns or stores the moving */ /* path of the "empty space" that it is involved to make all the sub-images in */ /* the correct position. The integer seqence varible "solution" should store */ /* all the steps along the path */ /* */ /* For example: */ /* Input: data = {8, 4, 1, 3, 0, 2, 6, 7, 5 }; */ /* to make it into the correct order {0, 1, 2, 3, 4, 5, 6, 7, 8} */ /* you need to make the following changes on the number 8, since the */ /* number 8 represents the empty space, moving 8 to its neigboring */ /* numbers equals to moving the corresponding number to the empty space. */ /* Below it shows a demo of the steps: */ /* */ /* 8 4 1 swap with 4 8 0 1 swap with 1 8 1 0 swap with 2 8 1 2 swap with 5 0 1 2 */ /* 3 0 2 ------------> 3 4 2 -------------> 3 4 2 --------------> 3 4 8 --------------> 3 4 5 ---> End */ /* 6 7 5 6 7 5 6 7 5 6 7 5 6 7 8 */ /* */ /* So from this example, the right path should be {1, 2, 5, 8}. */ /* WHY? You may thought it was {4, 1, 2, 5}, since the number 8 has swapped with them in this order. */ /* That is true. However, we do not care which number it swapped with, but which position the number 8 */ /* has gone through. As the numbers can be in any positions during different time, which give no hint */ /* about where the number 8 is. In contrast, the positions are fixed. So we assume the positions are */ /* in the same order as an increasing sequence: */ /* */ /* [0] [1] [2] */ /* Fixed Position = [3] [4] [5] */ /* [6] [7] [8] */ /* */ /* Here, I use "[]" to distinguish the positions from the numbers. So now you can see, the number 8 starts */ /* from position [4], then swapped with number 4, which goes to the position [1]; then swapped with number */ /* 1, which goes to the position [2]; then swapped with number 2, which goes to the position [5]; finally, */ /* swapped with number 5, which goes to the position [8]. So the path you should assign to the parameter */ /* "&solution" with the path sequence {1, 2, 5, 8}. */ bool SolutionSearch::AStarSearch(int *data, vector<int> &solution) { return 1; }
__MACOSX/Project 1 for Visual Studio users/._SolutionSearch.cpp
Project 1 for Visual Studio users/SolutionSearch.h
/* To make the code compatible, different search algorithms have the same input and output parameters */ #pragma once #include <vector> // std::vector using namespace std; class SolutionSearch { public: SolutionSearch(void); ~SolutionSearch(void); bool AStarSearch(int *data, vector<int> &solution); //Student Implementation: you need to implement this function };
__MACOSX/Project 1 for Visual Studio users/._SolutionSearch.h
Project 1 for Visual Studio users/test.jpg
__MACOSX/Project 1 for Visual Studio users/._test.jpg
Project 1 for Visual Studio users/VisualDisplay.cpp
#include "VisualDisplay.h" #define STANDARD_SIZE 600 #define CONTAINER_SIZE 640 #define GAP 10 //gap between each piece #define PIECE_SIZE 200 #define MOVING_SPEED 20 void onMouse( int event, int x, int y, int flags, void* param ) { VisualDisplay* vd = (VisualDisplay*) param; int cur_selection = -1; switch( event ) { case CV_EVENT_LBUTTONDOWN: //find selected position for(int i = 0; i < 9; i++) { if(vd->piece_positions[i].top_left.x <= x && x <= vd->piece_positions[i].bottom_right.x && vd->piece_positions[i].top_left.y <= y && y <= vd->piece_positions[i].bottom_right.y) { if(i == vd->target_pos) { //Make sure there has already been a candiate selected before swaping the pieces; otherwise no actions are taken if(!(vd->selected_piece == -1)) { printf("Make a swap with %d!\n", vd->selected_piece); vd->swap(vd->selected_piece); vd->selected_piece = -1; } } else //if current selection is not the target pos, check whether current position is in the neighborhood of the target position { for(int nb_idx = 0; nb_idx < (int) vd->moving_directions[vd->target_pos].size(); nb_idx++) { if(i == vd->moving_directions[vd->target_pos][nb_idx]) { cur_selection = i; break; } } } } } vd->selected_piece = cur_selection; break; case CV_EVENT_RBUTTONDOWN: vd->selected_piece = -1; break; case CV_EVENT_LBUTTONUP: break; case CV_EVENT_RBUTTONUP: break; } } VisualDisplay::VisualDisplay(void) { cv::namedWindow("window", 1); cv::setMouseCallback("window", onMouse, this); //specify the posi }on of each piece on the container for(int i = 0; i < 9; i++) { int row_idx = i / 3; int col_idx = i % 3; piece_positions[i].top_left.x = col_idx * GAP + 10 + PIECE_SIZE * col_idx; piece_positions[i].top_left.y = row_idx * GAP + 10 + PIECE_SIZE * row_idx; piece_positions[i].bottom_right.x = piece_positions[i].top_left.x + PIECE_SIZE; piece_positions[i].bottom_right.y = piece_positions[i].top_left.y + PIECE_SIZE; } /***************** The order is left, bottom, right, top ***********************************/ moving_directions[0].push_back(3); //for each position, tell the empty space which one in the array that it can be swapped with. // So only two pieces are considered each time, when the empty space is moving. moving_directions[0].push_back(1); moving_directions[1].push_back(0); moving_directions[1].push_back(4); moving_directions[1].push_back(2); moving_directions[2].push_back(1); moving_directions[2].push_back(5); moving_directions[3].push_back(6); moving_directions[3].push_back(4); moving_directions[3].push_back(0); moving_directions[4].push_back(3); moving_directions[4].push_back(7); moving_directions[4].push_back(5); moving_directions[4].push_back(1); moving_directions[5].push_back(4); moving_directions[5].push_back(8); moving_directions[5].push_back(2); moving_directions[6].push_back(7); moving_directions[6].push_back(3); moving_directions[7].push_back(6); moving_directions[7].push_back(8); moving_directions[7].push_back(4); moving_directions[8].push_back(7); moving_directions[8].push_back(5); //Initialize Mouse data selected_piece = -1; } VisualDisplay::~VisualDisplay(void) { } /* Draw the container by putting all the 8 sub-images based on their orders*/ void VisualDisplay::paintContainer() { container = cv::Mat(CONTAINER_SIZE, CONTAINER_SIZE, CV_8UC3, cv::Scalar(255, 255, 255));//make the container white color //put all the pieces into container for(int i = 0; i < 9; i++) { int cur_idx = current_states[i]; if(cur_idx != 8) //piece-8 does not paint { if(selected_piece == i) { cv::Mat high_light = cv::Mat(PIECE_SIZE, PIECE_SIZE, CV_8UC3, cv::Scalar(100, 100, 100)); cv::Mat temp = high_light + piece[cur_idx]; temp.copyTo(container(cv::Range(piece_positions[i].top_left.y, piece_positions[i].bottom_right.y), cv::Range(piece_positions[i].top_left.x, piece_positions[i].bottom_right.x))); } else piece[cur_idx].copyTo(container(cv::Range(piece_positions[i].top_left.y, piece_positions[i].bottom_right.y), cv::Range(piece_positions[i].top_left.x, piece_positions[i].bottom_right.x))); } } } /*Make a swap between the selected candiate piece and the target piece*/ void VisualDisplay::swap(int candidate) { //do the motion generateVisualMotion(candidate, target_pos); //change the current state int temp = current_states[candidate]; current_states[candidate] = current_states[target_pos]; current_states[target_pos] = temp; //change the target_pos target_pos = candidate; } /*Generate the motion from the selected piece to the target position*/ void VisualDisplay::generateVisualMotion(int candidate, int target) { cv::Point top_left; //store the transition position of the moving piece cv::Point bottom_right; top_left.y = piece_positions[candidate].top_left.y; top_left.x = piece_positions[candidate].top_left.x; bottom_right.y = piece_positions[candidate].bottom_right.y; bottom_right.x = piece_positions[candidate].bottom_right.x; cv::Mat white_piece = cv::Mat(PIECE_SIZE, PIECE_SIZE, CV_8UC3, cv::Scalar(255, 255, 255)); //used to clear last position of the moving piece int cur_idx = current_states[candidate]; int num_steps = PIECE_SIZE / MOVING_SPEED; //check the direction first if(candidate < target) { //moving right if((target - candidate) == 1) { printf("moving right\n"); //Gradually copy the candidate piece to the transiation position for(int step_idx = 1; step_idx <= num_steps; step_idx++) { top_left.x = piece_positions[candidate].top_left.x + MOVING_SPEED * step_idx; bottom_right.x = piece_positions[candidate].bottom_right.x + MOVING_SPEED * step_idx; //clear last position white_piece.copyTo(container(cv::Range(piece_positions[candidate].top_left.y, piece_positions[candidate].bottom_right.y), cv::Range(piece_positions[candidate].top_left.x, piece_positions[candidate].bottom_right.x))); piece[cur_idx].copyTo(container(cv::Range(top_left.y, bottom_right.y), cv::Range(top_left.x, bottom_right.x))); int delay = 300/num_steps; cv::waitKey(delay); imshow("window", container); } } else //moving down { printf("moving down\n"); //Gradually copy the candidate piece to the transiation position for(int step_idx = 1; step_idx <= num_steps; step_idx++) { top_left.y = piece_positions[candidate].top_left.y + MOVING_SPEED * step_idx; bottom_right.y = piece_positions[candidate].bottom_right.y + MOVING_SPEED * step_idx; //clear last position white_piece.copyTo(container(cv::Range(piece_positions[candidate].top_left.y, piece_positions[candidate].bottom_right.y), cv::Range(piece_positions[candidate].top_left.x, piece_positions[candidate].bottom_right.x))); piece[cur_idx].copyTo(container(cv::Range(top_left.y, bottom_right.y), cv::Range(top_left.x, bottom_right.x))); int delay = 300/num_steps; cv::waitKey(delay); imshow("window", container); } } } else { if((candidate - target) == 1) //moving left { printf("moving left\n"); //Gradually copy the candidate piece to the transiation position for(int step_idx = 1; step_idx <= num_steps; step_idx++) { top_left.x = piece_positions[candidate].top_left.x - MOVING_SPEED * step_idx; bottom_right.x = piece_positions[candidate].bottom_right.x - MOVING_SPEED * step_idx; //clear last position white_piece.copyTo(container(cv::Range(piece_positions[candidate].top_left.y, piece_positions[candidate].bottom_right.y), cv::Range(piece_positions[candidate].top_left.x, piece_positions[candidate].bottom_right.x))); piece[cur_idx].copyTo(container(cv::Range(top_left.y, bottom_right.y), cv::Range(top_left.x, bottom_right.x))); int delay = 300/num_steps; cv::waitKey(delay); imshow("window", container); } } else //moving top { printf("moving top\n"); //Gradually copy the candidate piece to the transiation position for(int step_idx = 1; step_idx <= num_steps; step_idx++) { top_left.y = piece_positions[candidate].top_left.y - MOVING_SPEED * step_idx; bottom_right.y = piece_positions[candidate].bottom_right.y - MOVING_SPEED * step_idx; //clear last position white_piece.copyTo(container(cv::Range(piece_positions[candidate].top_left.y, piece_positions[candidate].bottom_right.y), cv::Range(piece_positions[candidate].top_left.x, piece_positions[candidate].bottom_right.x))); piece[cur_idx].copyTo(container(cv::Range(top_left.y, bottom_right.y), cv::Range(top_left.x, bottom_right.x))); int delay = 300/num_steps; cv::waitKey(delay); imshow("window", container); } } } } /*Load necessary information into the class: image name, original sequence, and the position of empty space*/ void VisualDisplay::load(char* file_name, int* data, int pos) { cv::Mat temp = cv::imread(file_name); int height = temp.rows; int width = temp.cols; cv::Mat sub_img; if(width > height) { int start_col = (width - height)/2; int end_col = start_col + height; sub_img = temp(cv::Range(0, height), cv::Range(start_col, end_col)); } else { int start_row = (height - width)/2; int end_row = start_row + width; sub_img = temp(cv::Range(start_row, end_row), cv::Range(0, width)); } cv::resize(sub_img, image, cv::Size(STANDARD_SIZE, STANDARD_SIZE)); //Assign different parts of the image into different pieces for(int i = 0; i < 9; i++) { int col_idx = i % 3; int row_idx = i / 3; image(cv::Range(row_idx * PIECE_SIZE, (row_idx + 1) * PIECE_SIZE), cv::Range(col_idx * PIECE_SIZE, (col_idx + 1) * PIECE_SIZE)).copyTo(piece[i]); } original_states = data; //Load the data sequence current_states = data; target_pos = pos; //store the current target position } /*Run the game: showing the container of multiple sub-images and enabling user to re-organize the sub-images */ void VisualDisplay::run() { while(1) { paintContainer(); //draw the whole pattern by putting all the sub-images into the container imshow("window", container); char c = cv::waitKey(1); if(c == 27) break; else if(c == 's' || c == 'S') //At any time, when the user press the "s" or "S" key, it automatically finds the solution { showSolution(); //Use your implemented search algorithm to find the solution and show it } } } /*Student Implementation: actually you do not need to implement anything here. Just for testing purpose, you may test different search algorithms here. But be aware, only one algorithm is called everytime. */ void VisualDisplay::showSolution() { path.clear(); /*Only one of the following search function is called each time, so comment the others*/ solution_finder.AStarSearch(current_states, path); //use A-star to find the solution showPath(); //show the path on the GUI } /* Show the solution on the GUI by moving those sub-images step by step until all the sub-image get to the right order */ void VisualDisplay::showPath() { //Printout the solution on the console printf("The solution path is: \n"); for(int i = 0; i < (int)path.size(); i++) { printf("%d, ", path[i]); } printf("\n"); //Show the path visually selected_piece = -1; for(int i = 0; i < (int)path.size(); i++) { swap(path[i]); paintContainer(); imshow("window", container); cv::waitKey(800); } }
__MACOSX/Project 1 for Visual Studio users/._VisualDisplay.cpp
Project 1 for Visual Studio users/VisualDisplay.h
/* This class is used to visually show the puzzle game. All the code have already been provided. So you do not need */ /* to do any moidification here. The only thing you may touch is in the "showSolution()" function. As you may test */ /* different search functions by comment or uncomment a couple of lines there. */ #pragma once #include <opencv2/highgui/highgui.hpp> #include <opencv2/imgproc/imgproc.hpp> #include <opencv/cv.h> using namespace cv; #include "SolutionSearch.h" struct Square{ //this structure define a square region on the container (image) by using two points cv::Point top_left; cv::Point bottom_right; }; class VisualDisplay { private: int *original_states; int *current_states; vector<int> path; //the path for solution int target_pos; //Store the position of the 8-piece cv::Mat image; cv::Mat piece[9]; cv::Mat container; //the image that actually show the pieces and board Square piece_positions[9]; //define the position on the container that each piece will lay out. //here it has the order of 0, 1, 2, ..., 8. So initially, it is assign the position value in the constructor SolutionSearch solution_finder; //the most important component that is used to find the possible solutions //Below are used for mouse actions int selected_piece; //whether there is any piece has been selected -1 means no selection, 0-7 means a particular piece is selected std::vector<int> moving_directions[9]; public: VisualDisplay(void); ~VisualDisplay(void); void paintContainer(); //draw all the sub-images onto a single image void load(char* file_name, int* data, int pos); //load the image file to the image object void run(); //the main function of the class that shows different pieces of the image and support user's interaction friend void onMouse( int event, int x, int y, int flags, void* param ); void swap(int candidate); void generateVisualMotion(int candidate, int target); void showSolution(); void showPath(); };
