三、程序代码
首先，要声明的是，游戏网格在程序中对应着一个拥有10个成员变量的数组，网格每个位置按照从左到右、从上到下的位置排序。对于网格状态，可实现一个状态类，它对应着网格的各种状态，并拥有所有操作网格时所需要的代码和变量，这个类命名为CState，代码如下：
/* 声明网格中空格所有可能移动的方向，至于为什么要包括"NONE"将在后面的代码中显现出来；*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };
// 声明CState类
class CState {
private:
// 使用1 to 9号索引来对应网格的每个位置, 定义为 char类型是为了节省内存；
char Grid[10];
char Depth; //Depth变量对游戏的最初原始状态演变到当前状态所经历的步数；
//我们需要记录下父状态是如何进行移动而得到当前状态的；
DIRECTION OperatorApplyed;
// 父状态指针，当程序结束时，我们可以利用它跟踪所经历的状态，从而给出答案；
CState *PrevState;
// 寻找当前网格中的空格位置或某一个具体数字的位置，默认状态是寻找空格位置；
inline int FindBlank(char Search=0) {
int Blank=1;
while (Grid[Blank] != Search) {
Blank++;
}
return Blank;
}
// 按照规定的方向移动空格；
void MoveBlank(DIRECTION Direction) {
int Blank = FindBlank();
// 我们需要记住本次操作所移动的方向；
OperatorApplyed = Direction;
switch (Direction) {
case NORTH:
Grid[Blank] = Grid[Blank - 3];
Grid[Blank - 3] = 0;
break;
case EAST:
Grid[Blank] = Grid[Blank + 1];
Grid[Blank + 1] = 0;
break;
case SOUTH:
Grid[Blank] = Grid[Blank + 3];
Grid[Blank + 3] = 0;
break;
case WEST:
Grid[Blank] = Grid[Blank - 1];
Grid[Blank - 1] = 0;
break;
}
}
/* 下面的函数将被用于第一种方法的heuristics函数的一部分，它得到两个索引位置的直角距离，它还用于确定一个数字当前位置与其应该所在位置的直角距离；
int GetDistanceBetween(int Tile1, int Tile2) {
int X1, X2;
int Y1, Y2;
int temp=0;
// 将grid位置转换为X,Y坐标；
Y1 = 1;
Y2 = 2;
X1 = Tile1;
X2 = Tile2;
if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; }
if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; }
if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; }
if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; }
//为了确保距离值为正说，进行必要的换位处理；
if(Y1 - Y2 < 0) {
temp = Y1;
Y1 = Y2;
Y2 = temp;
}
if(X1 - X2 < 0) {
temp = X1;
X1 = X2;
X2 = temp;
}
return ((Y1 - Y2) + (X1 - X2));
}
public:
// 异常处理；
class ERROR_ILLEGAL_MOVE{};
class ERROR_NO_MORE_DIRECTIONS{};
class ERROR_OUT_OF_BOUNDS{};
//用于heuristic函数；它代表了当前状态与前一状态的距离；这个数值越小越好。
int GetDepth() {
return Depth;
}
// CState类构造函数；
CState() {
Depth = 0;
Grid[1] = 6; // for slower machines use 4
Grid[2] = 1; // for slower machines use 1
Grid[3] = 7; // for slower machines use 3
Grid[4] = 3; // for slower machines use 2
Grid[5] = 0; // for slower machines use 0
Grid[6] = 4; // for slower machines use 5
Grid[7] = 5; // for slower machines use 8
Grid[8] = 8; // for slower machines use 7
Grid[9] = 2; // for slower machines use 6
PrevState = 0;
/*由于还没有以前移动的操作，所以这就是为什么我们需要声明NONE 变量的原因。*/
OperatorApplyed = NONE;
}
void SetPrevState(CState *Set) {
PrevState = Set;
}
CState* GetPrevState() {
return PrevState;
}
// 用于确定移动操作是否合法
bool CanBlankMove(DIRECTION Direction) {
int Blank = FindBlank();
switch (Direction) {
case NORTH:
if (Blank > 3) {
return true;
}
else {
return false;
}
break;
case EAST:
if (Blank != 3 && Blank != 6 && Blank != 9) {
return true;
}
else {
return false;
}
break;
case SOUTH:
if (Blank < 7) {
return true;
}
else {
return false;
}
break;
case WEST:
if (Blank != 1 && Blank != 4 && Blank != 7) {
return true;
}
else {
return false;
}
break;
default:
return false;
break;
}
}
void setgrid(int index, int value) {
Grid[index] = value;
}
/*该函数如果返回"true", 当前状态将是最终状态，以前的状态指针可以用来回退，从而得到解决问题的答案。*/
bool Solution() {
if (Grid[1] == 1 && Grid[2] == 2 && Grid[3] == 3 && Grid[4] == 8 && Grid[5]
== 0 && Grid[6] == 4 && Grid[7] == 7 && Grid[8] == 6 && Grid[9] == 5)
{
return true;
}
else {
return false;
}
}
char GetGridValue(int Index) {
if (Index < 1 || Index > 9) {
throw ERROR_OUT_OF_BOUNDS();
}
else {
return Grid[Index];
}
}
// 含一个参数的构造函数；
CState(CState* Init) {
Depth = (Init->GetDepth());
OperatorApplyed = Init->GetLastOperator();
PrevState = Init->GetPrevState();
for (int n=1; n<=9; n++) {
Grid[n] = Init->GetGridValue(n);
}
}
DIRECTION GetLastOperator() {
return OperatorApplyed;
}
// 两个参数的构造 函数；
CState(CState* Init, DIRECTION Direction) {
int n;
PrevState = Init;
Depth = (Init->GetDepth() + 1);
for (n=1; n<=9; n++) {
Grid[n] = Init->GetGridValue(n);
}
MoveBlank(Direction);
}
// 另外一个heuristic函数，它计算错误网格的数量；
int GetWrongTiles() {
return ((Grid[1] != 1) +
(Grid[2] != 2) +
(Grid[3] != 3) +
(Grid[4] != 3) +
(Grid[5] != 3) +
(Grid[6] != 3) +
(Grid[7] != 3) +
(Grid[8] != 3) +
(Grid[9] != 3) +
(Depth )); // 也用于第二种heuristic (A*)的depth
}
/* ManhattanDistance是一个技术术语，它代表了所有当前位置数字与其应该处于的位置的直角距离之和*/
int GetManhattanDistance() {
int Result=0;
Result = GetDistanceBetween(1, FindBlank(1));
Result = Result + GetDistanceBetween(2, FindBlank(2));
Result = Result + GetDistanceBetween(3, FindBlank(3));
Result = Result + GetDistanceBetween(4, FindBlank(8));
Result = Result + GetDistanceBetween(5, FindBlank(0));
Result = Result + GetDistanceBetween(6, FindBlank(4));
Result = Result + GetDistanceBetween(7, FindBlank(7));
Result = Result + GetDistanceBetween(8, FindBlank(6));
Result = Result + GetDistanceBetween(9, FindBlank(5));
Result = Result + Depth;// 也用于第二种heuristic (A*)的depth；
return Result;
}
}; |
正如你所看到的，这是一个很"巨大"的类，但是，它一点都不复杂，仅仅是一些简单的数据操作。比较难的部分是跟踪各种状态，并按照正确的顺序操作它们，这将是我们下面要做的。
这部分与人工智能关系不大，但是人工智能程序不能没有它。如果你不了解为什么我们使用链表而不用数组，那末这里告诉你原因，数组在设计时有固定的尺寸，在运行时不能改变，所以如果程序一开始，你就拥有一个含有6 百万个Cstates类对象的数组的话，而且这时你还不需要它，那将浪费大量的内存。
说明：本教程来源互联网或网友上传或出版商，仅为学习研究或媒体推广，wanshiok.com不保证资料的完整性。
2/2 首页 上一页 1 2 |
