using System; using System.Drawing; using System.Collections; namespace LLK.AI 
{ 
/**/ /// <summary> 
/// 连连看的连线算法 /// 作者：随飞 /// 编写日期：2005-6-6 /// 首先是 x to x ,这个是横向比较直连 /// 然后是 y to y ,这个是竖向比较直连 /// /// 然后是 1个折点 /// 算法很简单;比如 /// 7x3的 /// 0001000 /// 0000000 /// 0000001 /// /// p1 是 3,0 /// p2 是 6,2 /// /// 那么折点是 /// 000100x /// 0000000 /// 000x001 /// 折点1是 6,0 ,折点2是 3,2 /// 注意这个值和p1,p2的比较,是不是很简单,折点出来了,就可以比较x/y直线了,如果成立则通过. /// /// 2折就复杂一点,在上面都不成立后, /// 一次根据上下左右分别按1折算法再比较即可. 
/// </summary> public class TestPath { int pathPointCount = 0; ArrayList PathRecord = new ArrayList(); int[,] map = null; // 地图 Point startPos; // 起点 Point endPos; // 终点 public TestPath() {;} public TestPath(Point StartPos,Point EndPos, int[,] Map) { this.startPos = StartPos; this.endPos = EndPos; this.map = Map; } private void EmptyPathRecord() { PathRecord.Clear(); PathRecord.TrimToSize(); PathRecord.Add( this.startPos); PathRecord.Add( this.endPos); } private bool IsEmptyPoint(Point p) { return this.map[p.X,p.Y]==0; } private bool CheckHorizontal(Point p1,Point p2) { return this.CheckHorizontal(p1,p2, false); } private bool CheckHorizontal(Point p1,Point p2, bool isAddPath) { // 检查水平，x位移,y相同 Point sp = p1.X<p2.X?p1:p2; Point ep = p2.X<p1.X?p1:p2; for( int x =sp.X+1;x<ep.X;x++) { // 允许记录 if(isAddPath) { this.PathRecord.Add( new Point(x,p1.Y)); } // 不可通过 if(map[x,p1.Y]!=0) return false; } return true; } private bool CheckVertical(Point p1,Point p2) { return CheckVertical(p1,p2, false); } private bool CheckVertical(Point p1,Point p2, bool isAddPath) { // 检查垂直，y位移,x相同 Point sp = p1.Y<p2.Y?p1:p2; Point ep = p2.Y<p1.Y?p1:p2; for( int y =sp.Y+1; y<ep.Y; y++) { // 允许记录 if(isAddPath) { this.PathRecord.Add( new Point(p1.X,y)); } // 不可通过 if(map[p1.X,y]!=0) return false; } return true; } private bool CheckOneCorner(Point p1,Point p2) { return CheckOneCorner(p1,p2, true, true); } private bool CheckOneCorner(Point p1,Point p2, bool isAddPath, bool isClear) { // 计算夹角 // 取起始x Point CrossStart; Point CrossEnd; if(p1.X<p2.X) { CrossStart = p1; CrossEnd = p2; } else { CrossStart = p2; CrossEnd = p1; } // 交叉点X // 正向 Point CrossX ; // 交叉点Y // 反向 Point CrossY ; if(CrossStart.Y<CrossEnd.Y) { CrossX = new Point( Math.Max(CrossStart.X,CrossEnd.X), Math.Min(CrossStart.Y,CrossEnd.Y) ); CrossY = new Point( Math.Min(CrossStart.X,CrossEnd.X), Math.Max(CrossStart.Y,CrossEnd.Y) ); } else { CrossX = new Point( Math.Min(CrossStart.X,CrossEnd.X), Math.Min(CrossStart.Y,CrossEnd.Y) ); CrossY = new Point( Math.Max(CrossStart.X,CrossEnd.X), Math.Max(CrossStart.Y,CrossEnd.Y) ); } // 检查交叉点是否为可通过 if(! this.IsEmptyPoint(CrossX) && ! this.IsEmptyPoint(CrossY)) return false; // 检查交叉点X if( this.IsEmptyPoint(CrossX)) { // 检查横位 if(CrossStart.Y<CrossEnd.Y) { // 方向为~| if( this.CheckHorizontal(CrossStart,CrossX) && this.CheckVertical(CrossX,CrossEnd)) { // 允许清空 if(isClear) { this.EmptyPathRecord(); } // 允许记录 if(isAddPath) { this.PathRecord.Add(CrossX); // 记录当前交叉点 } return ( this.CheckHorizontal(CrossStart,CrossX, true) && this.CheckVertical(CrossX,CrossEnd, true)); } // 不跳出，留下一点检测 } else { // 方向为|~ if( this.CheckHorizontal(CrossX,CrossEnd) && this.CheckVertical(CrossX,CrossStart)) { // 允许清空 if(isClear) { this.EmptyPathRecord(); } // 允许记录 if(isAddPath) { this.PathRecord.Add(CrossX); // 记录当前交叉点 } return ( this.CheckHorizontal(CrossX,CrossEnd, true) && this.CheckVertical(CrossX,CrossStart, true)); } // 不跳出，留下一点检测 } } // 检查交叉点Y if( this.IsEmptyPoint(CrossY)) { // 检查竖位 if(CrossStart.Y<CrossEnd.Y) { // 方向为|_ if( this.CheckVertical(CrossStart,CrossY) && this.CheckHorizontal(CrossY,CrossEnd)) { // 允许清空 if(isClear) { this.EmptyPathRecord(); } // 允许记录 if(isAddPath) { this.PathRecord.Add(CrossY); // 记录当前交叉点 } return ( this.CheckVertical(CrossStart,CrossY, true) && this.CheckHorizontal(CrossY,CrossEnd, true)); } } else { // 方向_| if( this.CheckVertical(CrossEnd,CrossY) && this.CheckHorizontal(CrossY,CrossStart)) { // 允许清空 if(isClear) { this.EmptyPathRecord(); } // 允许记录 if(isAddPath) { this.PathRecord.Add(CrossY); // 记录当前交叉点 } return ( this.CheckVertical(CrossEnd,CrossY, true) && this.CheckHorizontal(CrossY,CrossStart, true)); } } } return false; // 全部不成立,留给2次折点检测 } private bool CheckTwoCornerLeft(Point p1,Point p2, bool isAddPath) { // 左 // 清空记录 this.EmptyPathRecord(); for( int x = p1.X -1; x>-1; x--) { if( this.map[x,p1.Y]!=0) return false; // 允许记录 if(isAddPath) { this.PathRecord.Add( new Point(x,p1.Y)); } // 不允许清空 if( this.CheckOneCorner( new Point(x,p1.Y),p2, false, false)) { return this.CheckOneCorner( new Point(x,p1.Y),p2,isAddPath, false); } } return false; } private bool CheckTwoCornerRight(Point p1,Point p2, bool isAddPath) { // 右 // 清空记录 this.EmptyPathRecord(); for( int x = p1.X +1; x< this.map.GetLength(0); x++) { if( this.map[x,p1.Y]!=0) return false; // 允许记录 if(isAddPath) { this.PathRecord.Add( new Point(x,p1.Y)); } // 不允许清空 if( this.CheckOneCorner( new Point(x,p1.Y),p2, false, false)) { return this.CheckOneCorner( new Point(x,p1.Y),p2,isAddPath, false); } } return false; } private bool CheckTwoCornerUp(Point p1,Point p2, bool isAddPath) { // 上 // 清空记录 this.EmptyPathRecord(); for( int y = p1.Y -1; y>-1; y--) { if( this.map[p1.X,y]!=0) return false; // 允许记录 if(isAddPath) { this.PathRecord.Add( new Point(p1.X,y)); } // 不允许清空 if( this.CheckOneCorner( new Point(p1.X,y),p2, false, false)) { return this.CheckOneCorner( new Point(p1.X,y),p2,isAddPath, false); } } return false; } private bool CheckTwoCornerDown(Point p1,Point p2, bool isAddPath) { // 下 // 清空记录 this.EmptyPathRecord(); for( int y = p1.Y +1; y< this.map.GetLength(1); y++) { if( this.map[p1.X,y]!=0) return false; // 允许记录 if(isAddPath) { this.PathRecord.Add( new Point(p1.X,y)); } // 不允许清空 if( this.CheckOneCorner( new Point(p1.X,y),p2, false, false)) { return this.CheckOneCorner( new Point(p1.X,y),p2,isAddPath, false); } } return false; } private void CopyArrayListTo( ref ArrayList srcAl, ref ArrayList destAl) { destAl.Clear(); destAl.TrimToSize(); foreach(Point p in srcAl) { Point newPnt = new Point(p.X,p.Y); destAl.Add(newPnt); } } private bool CheckTwoCorner(Point p1,Point p2) { // 取起始x Point CrossStart; Point CrossEnd; if(p1.X<p2.X) { CrossStart = p1; CrossEnd = p2; } else { CrossStart = p2; CrossEnd = p1; } // 这里为寻找最短路径的算法 // 方法很简单，因为当前的起点方向不确定，可以选择重复尝试能成功的起点 // 然后找到路径最少的 // 测试4次，寻找最短的路径 ArrayList[] backFindPath = new ArrayList[4]; bool isFind = false; int nextPathList=0; while(nextPathList<4) { backFindPath[nextPathList] = null; if( this.CheckTwoCornerUp(CrossStart,CrossEnd, false)) { this.PathRecord.Clear(); this.CheckTwoCornerUp(CrossStart,CrossEnd, true); backFindPath[nextPathList] = new ArrayList(); CopyArrayListTo( ref this.PathRecord, ref backFindPath[nextPathList]); isFind = true; nextPathList ++; } if( this.CheckTwoCornerDown(CrossStart,CrossEnd, false)) { this.PathRecord.Clear(); this.CheckTwoCornerDown(CrossStart,CrossEnd, true); backFindPath[nextPathList] = new ArrayList(); CopyArrayListTo( ref this.PathRecord, ref backFindPath[nextPathList]); isFind = true; nextPathList ++; } if( this.CheckTwoCornerLeft(CrossStart,CrossEnd, false)) { this.PathRecord.Clear(); this.CheckTwoCornerLeft(CrossStart,CrossEnd, true); backFindPath[nextPathList] = new ArrayList(); CopyArrayListTo( ref this.PathRecord, ref backFindPath[nextPathList]); isFind = true; nextPathList ++; } if( this.CheckTwoCornerRight(CrossStart,CrossEnd, false)) { this.PathRecord.Clear(); this.CheckTwoCornerRight(CrossStart,CrossEnd, true); backFindPath[nextPathList] = new ArrayList(); CopyArrayListTo( ref this.PathRecord, ref backFindPath[nextPathList]); isFind = true; nextPathList ++; } // 没有结果 if(!isFind) break; } // 有结果返回 if(isFind) { // 检查起点最小数 int minCount = 0; // 记录位 int index = 0; for( int i=0;i<4;i++) { if(backFindPath[i]!= null) { if(backFindPath[i].Count>0) { if(minCount==0) { minCount=backFindPath[i].Count; index = i; } else if(backFindPath[i].Count<minCount) { minCount = backFindPath[i].Count; index = i; } } } } // 回复属性数据 this.PathRecord.Clear(); this.PathRecord.TrimToSize(); CopyArrayListTo( ref backFindPath[index], ref this.PathRecord); return true; } return false; } public bool Execute() { pathPointCount = -1; // 检查目标位置是否一样 if( this.startPos.X== this.endPos.X && this.startPos.Y== this.endPos.Y) { pathPointCount = -1; return false; } // 检查为同一横坐标 if( this.startPos.Y== this.endPos.Y) if( this.CheckHorizontal( this.startPos, this.endPos)) { this.EmptyPathRecord(); pathPointCount = 1; return ( this.CheckHorizontal( this.startPos, this.endPos, true)); } // 检查为同一纵坐标 if( this.startPos.X== this.endPos.X) if( this.CheckVertical( this.startPos, this.endPos)) { this.EmptyPathRecord(); pathPointCount = 1; return ( this.CheckVertical( this.startPos, this.endPos, true)); } // 检查一个折点 if( this.CheckOneCorner( this.startPos, this.endPos)) { pathPointCount =2; return true; } // 检查两个折点 if( this.CheckTwoCorner( this.startPos, this.endPos)) { pathPointCount =3; return true; } return false; } /**/ /// <summary> /// 起点坐标 /// </summary> public Point StartPosition { get { return this.startPos; } set { this.startPos = value; } } /**/ /// <summary> /// 终点坐标 /// </summary> public Point EndPosition { get { return this.endPos; } set { this.endPos = value; } } /**/ /// <summary> /// 地图数据 /// </summary> public int[,] MapData { get { return this.map; } set { this.map = value; } } /**/ /// <summary> /// 获取折点数 /// </summary> public int PathPointCount { get { return this.pathPointCount; } } /**/ /// <summary> /// 获取路径表 /// </summary> public Point[] PathPointList { get { if( this.PathRecord.Count>=0) { Point[] tmpPointList = new Point[ this.PathRecord.Count]; int i = 0; foreach(Point p in this.PathRecord) { tmpPointList[i] = p; i++; } return tmpPointList; } else { return null; } } } public ArrayList PathPointArray { get { return this.PathRecord; } } } 
} int[,] map = new int[14,10] { {0,0,0,0,0,0,0,0,0,0}, {0,2,0,3,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,1,1,1,1,1,1,1,1,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,1,1,1,1,1,1,1,1,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0} }; AI_Engine.TestPathing TP = new AI_Engine.TestPathing(); TP.StartPosition = new Point(( int)numericUpDown1.Value,( int)numericUpDown2.Value); TP.EndPosition = new Point(( int)numericUpDown3.Value,( int)numericUpDown4.Value); TP.MapData = this.map; if(TP.Execute()) { lbInfo.Text = "连通！"; AddPathInfo(TP.PathPointList); // 绘制路径 } else { lbInfo.Text = "不通！"; } 本文转自suifei博客园博客，原文链接：http://www.cnblogs.com/Chinasf/archive/2005/06/06/169153.html，如需转载请自行联系原作者