三、程序代码
首先,要声明的是,游戏网格在程序中对应着一个拥有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 |