_chessb.cpp

利用c++编写的带人工智能的跳棋程序。屏幕的中央是棋盘

//此文件定义了棋盘类
#include "_ChessB.h"
#include <math.h>
#include<graphics.h>
#include<conio.h>
#include<iostream.h>
/* 棋盘的初始化，参数为棋盘所在区域左上角的横、纵坐标和该区域的高度、宽度 */
_ChessBoard::_ChessBoard(int left,int top,int height,int width)		// 参数为棋盘左上角的坐标
{									// 和棋盘的高度和宽度
	float distance,radius,lheight,startx,starty,topx,topy;
	struct _Nodes TempNodes[200];					// 临时的节点数组,用来存储最初生成的所有结点
	distance=(height/17.0)*2/sqrt(3);   	   			// 因为总共有17行,所以distance即为相邻节点圆心之间的距离
	radius=distance*0.35;                 				// 半径
	lheight=height/17.0;               				// 行距
	topx=left+width*0.5;						// 最上面的结点的横坐标的绝对坐标值
	topy=top+(height/17.0)*0.5;					// 最上面的结点的纵坐标的绝对坐标值
	int lineheight;			
	int j,i,t=0;
	head=tail=NULL;							// 构造函数初始化head和tail为空
	
	/* 赋予临时数组中的每个元素位置坐标 */
	for(i=0;i<13;i++)						// 从上到下、从下到上进行13行，
									// 保证含盖了所有的节点
	{
		startx=topx-(i)*distance/2;				// 第i行的初始横坐标
		starty=topy+(i)*lheight;				// 第i行的初始纵坐标
		for(j=0;j<=i;j++)					// 为第i行的各个结点赋坐标
		{
			TempNodes[t].cood.x=startx+j*distance;		// 第i行的第j个节点的横坐标
			TempNodes[t++].cood.y=starty;			// 第i行的第j个节点的纵坐标
			TempNodes[t].cood.x=TempNodes[t-1].cood.x;	// 第17-i行的第j个节点的横坐标
			TempNodes[t++].cood.y=topy+(16-i)*lheight;	// 第17-i行的第j个节点的纵坐标
		}
	}
	for(i=t;i< 200;i++)  						// 把临时数组的剩余节点的的横纵
									// 坐标设为无效值(1000)
		TempNodes[i].cood.x=TempNodes[i].cood.y=1000;

	cut(TempNodes,t);						// 将临时数组中相同的元素去掉一个（置坐标值为无效值1000）
	sort(TempNodes);						// 将临时数组中的元素进行排序并标记序号
	
	int a=0.5*distance;						// 用于两行的起始横坐标的计算
	int b=lheight;							// 行距
	int m[6][2]={{2*a,0},{a,b},{-a,b},{-2*a,0},{-a,-b},{a,-b}};	// 相邻节点坐标的变换值,从最右侧开始,顺时针变换
	joint(Nodes,m);							// 连接所有结点
}

/* 删掉具有相同坐标的节点之一 */
void _ChessBoard::cut(struct _Nodes *p,int t )				// 参数为指向棋盘的指针和有效的节点数
{
	int i,j,k=0;
	for (i=0;i< t-1;++i)
	{
		if( p[i].cood.x!=0&& p[i].cood.y!=0)
		for (j=i+1;j< t;++j)
		{
			/* 如果i点的横纵坐标和j点的横纵坐标重合(3为误差值)
					则将j点的横纵坐标设为无效值(删掉此点) */
			if (abs(p[i].cood.x-p[j].cood.x)< 3&&abs(p[i].cood.y-p[j].cood.y)<3)
			{
				p[j].cood.x=1000;
				p[j].cood.y=1000;
				break;					// 只可能有一次相同，所以找到后就应该跳出本次循环
			}
		}
	}
}

//对数组中的元素进行排序，按照y、x从小到大排序
void _ChessBoard::sort(struct _Nodes *p){
	struct _Nodes node;
	int j,i,MinIndex,t=0;
	for(i=0;i<182;i++)
		if(p[i].cood.x<800&&p[i].cood.y<800)
			Nodes[t++]=p[i];				// 记录有效节点于Nodes数组中

	for(i=0;i<120;i++)						// 选择法排序
	{
		MinIndex=i;
		for(j=i;j<121;j++)
		{
			if(Nodes[j].cood.y-Nodes[MinIndex].cood.y>2)	// Nodes[j]所在行为Nodes[MinIndex]
									// 所在行的下一行,则跳出这层循环
				continue;  						
			if(Nodes[j].cood.y-Nodes[MinIndex].cood.y<-2)
				MinIndex=j; 				// Nodes[j]所在行为Nodes[MinIndex]
									// 所在行的上一行,则用j替换MinIndex 
			else if(Nodes[j].cood.x<Nodes[MinIndex].cood.x) // 若Nodes[j]所在行和Nodes[MinIndex]
									// 所在行为同一行,则若Nodes[j]的横坐标小于
				MinIndex=j; 				// Nodes[MinIndex]时,用j置换MinIndex;
		}
									// 把坐标最小的结点依次放在Nodes数组的最前面
		node=Nodes[i],Nodes[i]=Nodes[MinIndex],Nodes[MinIndex]=node;
	}
									// 对于每个数组元素的index赋予序号，
									// 从0开始共有121个序号
	for (i=0;i<121;i++)
		Nodes[i].index=i;
}

/* 将每一个节点与相邻节点连接起来 */
void _ChessBoard::joint(struct _Nodes *q,int (*p)[2])			// p指针接受传来得m数组
{
	int i,j,k;
	for (i=0;i<121;++i)
		for (j=0;j<6;++j)
		{
			for (k=0;k<121;++k)
			{
									// 判断i节点和k节点是否为邻近点,
									// 是则i节点的一个指针指向k结点
				if (abs((q[i].cood.x+p[j][0])-q[k].cood.x)<3&&
						abs((q[i].cood.y+p[j][1])-q[k].cood.y)<3)
				{
					q[i].pointers[j]=&q[k];
					break;
				}
			}
			if(k==121) Nodes[i].pointers[j]=NULL;		// k==121则没有找到i结点的邻近点,
									// 则其pointers指针值空
		}
}

/* 按选择对棋盘进行棋子的初始化 */
int **_ChessBoard::Reset()		
{
	countstep=0;							// 记录已走棋的步数
	while(head!=NULL)						// 如果头指针不为空，则释放已经
	{								// 存在的空间
		head=head->next;
		delete head->before;
	}
	/* 搜索开始时所有标志位清零,棋盘没有某一方的棋子(Chessman=0),没有选择要走的棋子(sellect=0) */
	for(int i=0;i<121;i++)
	{
		Nodes[i].visited=0;
		Nodes[i].sellect=0;
		Nodes[i].Chessman=0;
	}
	int a[2][10]={   						// 20个棋子的初始序号	
			{0,1,2,3,4,5,6,7,8,9},                          // 上（游戏者1）
			{111,112,113,114,115,116,117,118,119,120},      // 下（游戏者2）
			};
	int **c;
	/* c为指向一个指针数组,数组里的每个元素指向一个代表一个游戏方的数组,里面包括
		游戏者序号和10个棋子的节点序号 */
	c=new int*[2];
	for(int k;k<2;k++)
	{
		c[k]=new int[11];					
	}
	c[0][0]=1;							// 为参与游戏的2个游戏者分配棋子
	c[1][0]=2;
	for(i=0;i<10;i++)
	{
		Nodes[c[0][i+1]=a[0][i]].Chessman=1;			// 激活最上的10个棋子为游戏者1
		Nodes[c[1][i+1]=a[1][i]].Chessman=2;			// 激活最下的10个棋子为游戏者2
	}
	return c;							// 返回包含游戏者信息的数组
}

/* 判断选子是否合法 */
int _ChessBoard::JudgeSellect(int gamerID,int sellect)
{
	if(Nodes[sellect].Chessman==gamerID)
	{								// 如果合法
		for(int i=0;i<121;i++)					// 先将所有的节点标志清零
			Nodes[i].sellect=0;
		Nodes[sellect].sellect=1;				// 选定该子
		return 1;
	}
	else return 0;
}

/* 用深度优先搜索搜索从节点序号start到节点序号end是否存在路径，并记录在road数组中 */
int _ChessBoard::DFS(int start,int end)
{
	_Nodes *Node=NULL;
	Nodes[start].visited=1;						// 起始点start被访问,visited置1
	road[++Nowroad]=start;						// 用road[]数组存储路径
	if(Nodes[start].index==end)					// 如果start结点就是end结点则返回1
		return 1;
	else									//否则搜索start周围的6个指针
		for(int i=0;i<6;i++)					// 遍历一个结点的周围六个结点
		{
			Node=Nodes[start].pointers[i];
			if(Node==0||Node->pointers[i]==0)		// 此方向没有节点，则跳出本次循环
				continue;
			if(Node->Chessman!=0&&Node->pointers[i]->Chessman==0&&Node->pointers[i]->visited==0)//此方向可以走棋
			{
				if(DFS(Node->pointers[i]->index,end))	// 递归调用，搜寻可以走棋的路径
					return 1;
			}
		}
	Nowroad--;							// 如果不存在路径则Nowroad减1,退回
	return 0;							// 未找到路径，返回
}

/* 判断棋子能否从start走到end,能够的话则同时记录路径于数组road中，第一个参数为游戏者序号 */
int _ChessBoard::JudgeMove(int gamerID,int start,int end)
{
	/* instant为start与end节点两圆心之间的距离的平方,用于判断start与end是否相邻 */
	int instant=abs(Nodes[start].cood.x-Nodes[end].cood.x)*abs(Nodes[start].cood.x-Nodes[end].cood.x)+abs(Nodes[start].cood.y-Nodes[end].cood.y)*abs(Nodes[start].cood.y-Nodes[end].cood.y);
	/* 若所选的棋子并非自己的棋子或者目标结点已经有棋子则JudgeMove返回0,棋子不能移动 */
	if(!JudgeSellect(gamerID,start)||(Nodes[end].Chessman!=0))
		return 0;
	Nowroad=-1; 							// Nowroad的初值为-1
	if(instant<30*30)
		/* 判断棋子是否移到附近的点由于两邻近结点之间的距离为27,
			所以只要instant<30*30则次二结点即为邻近接结点 */
	{
		for(int i=0;i<121;i++)					// 搜索开始时的初始化
		{
			Nodes[i].visited=0;				// 所有标志位(visited)清零
			Nodes[i].sellect=0;				// 所有结点都未选定
		}
		Nowroad=-1;
		/* 若目标结点即为邻近的结点则路径数组里只用记录节点序号start和节点序号end */
		road[++Nowroad]=start;
		road[++Nowroad]=end;
		return 1;
	}
									// 若棋子是跳走,则搜索图,看是否
									// 存在符合规则的目标节点
	else if( DFS( start,end))    					// 若存在路径，记录路径，返回1
		 {
			for( int i=0;i< 121;i ++)			// 为下一次的搜索做初始化
			{
				Nodes[i].visited=0;			// 所有标志位(visited)清零
				Nodes[i].sellect=0;			// 所有结点都未选定
			}
			return 1;
		 }
		 else							// 棋子既不能移步也不能跳走则此步不可走,返回0
		{
			for(int i=0;i< 121;i++)				// 为下一次的搜索做初始化
			{
				Nodes[i].visited=0;			// 所有标志位(visited)清零
				Nodes[i].sellect=0;			// 所有结点都未选定
			}
			return 0;
		}
}

//判断是否已经有游戏者胜利
int _ChessBoard::Decide(int gamerID)
{
	int a[6][10]={	{0,1,2,3,4,5,6,7,8,9},
			{111,112,113,114,115,116,117,118,119,120}};
	int row=gamerID-1;  						// gamerID-1对应a数组的第row行
	if(row%2==0)       						// 如果row为偶数,则他的目标结点
		row++;							// 序号为a数组的row++行对应的序号
	else row--;							// 如果row为奇数,则他的目标结点
									// 序号为a数组的row--行对应的序号
	for(int i=0;i<10;i++)
	{								// 如果还有一个棋子未到达对面的结点上则还未胜利
			if(Nodes[a[row][i]].Chessman!=gamerID)
			return 0;
	}
	return 1;
}

_Nodes *_ChessBoard::AllNodes()						// 返回Nodes数组
{
	return Nodes;
}

int * _ChessBoard::MoveRoad()						// 返回road数组
{
	return road;
}

void _ChessBoard::record(int start,int end)				// 记录每次走棋棋，也就是将记录路径的链表增加一位
{
	_link *p=new _link;						// 一个指向_link指针类型的指针
	p->start=start;
	p->end=end;
	p->next=NULL;
	p->before=tail;
	tail->next=p;
	tail=p;
	countstep++;							// 步骤数加一

}
void _ChessBoard::MoveIt(int start,int end)				// 移动棋子
{
	record(start,end);						// 记录下来便于悔棋
	Nodes[end].Chessman=Nodes[road[0]].Chessman;			// end点的棋子类型和初始点的一样
	Nodes[road[0]].Chessman=0;					// 初始点的棋子的Chessman置位0,即此处无棋子
	for(int i=0;i< 121;i++)						// 为下一次的选定重新初始化
		Nodes[i].sellect=0;
	Nowroad=-1;							// 恢复记录路径用到的Nowroad
}

void _ChessBoard::back()						// 悔棋时返回到上一步的状态
{
	if(tail==NULL||countstep<2)	//若尾指针没有指向任何节点（没有走棋）或对方还没有走第一步棋，不能悔棋
		return;
	for(int i=2;i>0;i--)
	{
		Nodes[tail->start].Chessman=Nodes[tail->end].Chessman;	// 恢复原先结点的棋子
		Nodes[tail->end].Chessman=0;				// 后来结点恢复无子状态
		tail=tail->before;					// 尾指针迁移
		delete tail->next;					// 释放最后一个指针
		countstep--;						// 步骤数减一
	}

}

_ChessBoard::~_ChessBoard()						// 析构函数释放记录每步棋路进的链表
{
	while(head!=NULL)
	{
		head=head->next;
		delete head->before;
	}
}