A Star Search
Project 1 for Xcode Users/.DS_Store
__MACOSX/Project 1 for Xcode Users/._.DS_Store
Project 1 for Xcode Users/main.cpp
Project 1 for Xcode 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
/
highgui
/
highgui
.
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
(
"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 Xcode Users/._main.cpp
Project 1 for Xcode 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 Xcode Users/._RandomGenerator.cpp
Project 1 for Xcode 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 Xcode Users/._RandomGenerator.h
Project 1 for Xcode Users/SolutionSearch.cpp
#include "SolutionSearch.h" SolutionSearch::SolutionSearch(void) { } SolutionSearch::~SolutionSearch(void) { } /* Student Implementation: here you need to implement the A-star 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 Xcode Users/._SolutionSearch.cpp
Project 1 for Xcode 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 Xcode Users/._SolutionSearch.h
Project 1 for Xcode 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. So you need to comment out others. */ void VisualDisplay::showSolution() { path.clear(); 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 Xcode Users/._VisualDisplay.cpp
Project 1 for Xcode 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(); };