这个算是用我上次发布的连连看中的一个两点连接算法，上次发布了源码以后，很多朋友发邮件或能过MSN寻问源码中问题，算法占了一大部分，我当时答应会发一篇文章，详细讲解一下这个算法，但由于最近忙于工作，所以一拖再拖，在这里先说声Sorry.
希望各位看了这个算法后，能给点评价，谢谢。
还有，上次把我连连看最终发布版拿到我在的C#开发群里，没想到一下子就发现了BUG，比较郁闷的，主要平时也没做测试，给女朋友玩的时候，都已经明确告诉她，这个不用点的，没用的，这边有用的。看来还是要好好测试一下，所以我决定过一两天把那个最终版发布出来，希望大家帮忙测试一下（就当是工作之余玩点小游戏轻松一下）。
下面就来讲算法
基本算法如下：
首先是知道它的要求：
1：两个目标是相同的
2：两个目标之间连接线的折点不超过两个。（连接线由x轴和y轴的平行线组成） 那么分析一下连接的情况可以看到，一般分三种情况
1：直线相连 2：一个折点 3：两个折点。
可以发现，如果有折点，每个折点必定有且至少有一个坐标（x或者y）是和其中一个目标点是相同的，也就是说，折点必定在两个目标点所在的x方向或y方向的直线上。
所以设计思路如下：
假设目标点 p1 , p2 ,如果有两个折点分别为z1 , z2 那么，所要进行的是
1：如果验证p1 , p2 直线连线，则连接成立
2：搜索以p1,p2的x,y方向四条直线即下文所讲的十字路径（可能某两条直线会重合）上的有限点，每次取两点作为z1,z2 ,验证p1到z1/z1到z2/z2到p2 是否都能直线相连 ，是则连接成立。（如果z1=z2也就是只有一个折点，对判断没影响）
看下面的一个矩阵
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
希望连接的是两个点(9)
分别取出点1（3，2）和点2（12，5）的十字路径（点1的路径线以数字1表示，
点2的路径以数字2表示，交叉点任取一数），得结果也下，
0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
1 1 1 9 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
2 2 2 1 2 2 2 2 2 2 2 2 9 2 2 2
0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
以上是具体思路，下面从代码来具体讲解思路，
要判断两点是否可连接，
首先要分别获得这两点的十字路径，
/// <summary>
/// 获点指定点的水平可达路径
/// </summary>
private int[,] GetTempPointX(Common.Position p, int[,] buffer)
{
// 横向检测，基点为1以左
int nBufX = 1;
buffer[0,0] = p.x;
buffer[0,1] = p.y;
for (int TmpX = p.x - 1; TmpX >= 0; --TmpX)
{
if (map[p.y,TmpX] == 0)
{
buffer[nBufX,0] = TmpX;
buffer[nBufX,1] = p.y;
++nBufX;
}
else
{
break;
}
}
// 横向检测，基点为1以右
for (short TmpX = (short)(p.x + 1); TmpX < Common.MAP_WIDTH; ++TmpX)
{
if (map[p.y,TmpX] == 0)
{
buffer[nBufX,0] = TmpX;
buffer[nBufX,1] = p.y;
++nBufX;
}
else
{
break;
}
}
buffer[nBufX,0] = -1;
buffer[nBufX,1] = -1;
return buffer;
}
/// <summary>
/// 获点指定点的垂直可达路径
/// </summary>
private int[,] GetTempPointY(Common.Position p, int[,] buffer)
{
int nBufY = 1;
buffer[0,0] = p.x;
buffer[0,1] = p.y;
// 纵向检测，基点1以上
for (int TmpY = p.y - 1; TmpY >= 0; --TmpY)
{
if (map[TmpY,p.x] == 0)
{
buffer[nBufY,0] = p.x;
buffer[nBufY,1] = TmpY;
++nBufY;
}
else
{
break;
}
}
// 纵向检测，基点1以下
for (int TmpY = p.y + 1; TmpY < Common.MAP_HEIGHT; ++TmpY)
{
if (map[TmpY,p.x] == 0)
{
buffer[nBufY,0] = p.x;
buffer[nBufY,1] = TmpY;
++nBufY;
}
else
{
break;
}
}
buffer[nBufY,0] = -1;
buffer[nBufY,1] = -1;
return buffer;
}
获得水平与垂直可达路径的方法都已经有了，现在就可以进行判断了
private bool CheckInLineX(int[,] buffer1, int[,] buffer2, bool isInternal)
{
//判断是否在同一条直线上，可加速检测
if(CheckInLine(buffer1,buffer2))
{//该检查方法CheckInLine略
return false;
}
// 横向检测：纵向通路检测
// 连通标志
bool isInLine = false;
for (int nChkLink1 = 0; !(buffer1[nChkLink1,0] < 0 && buffer1[nChkLink1,1] < 0); ++nChkLink1)
{
// 设置同轴加速检查标志
bool bShortPass = false;
for (int nChkLink2 = 0; !(buffer2[nChkLink2,0] < 0 && buffer2[nChkLink2,1] < 0); ++nChkLink2)
{
// 检查是否在同一纵轴
if (buffer1[nChkLink1,0] == buffer2[nChkLink2,0])
{
// 因为已经检查到同轴点，所以设置同轴对比加速度检查标志为true
bShortPass = true;
// 计算对比点距离
int nStep = buffer1[nChkLink1,1] - buffer2[nChkLink2,1];
// 偏移量
int OpNum;
if (nStep > 0)
{
OpNum = -1;
--nStep;
}
else
{
OpNum = 1;
++nStep;
}
isInLine = true;
int tmpvx = buffer1[nChkLink1,0];
for (int mStep = nStep; mStep != 0; mStep += OpNum)//Math.Abs(mStep-0) < 1
{
if (map[buffer1[nChkLink1,1] - mStep,tmpvx] == 0)
{
// 继续检查下一点
continue;
}
else
{
// 通路有阻碍，无法连通
isInLine = false;
break;
}
}
// 如果连通
if (isInLine == true)
{
#if DEBUG
System.Windows.Forms.MessageBox.Show("Linked\n");
#endif
return true;
}
}
else
{
// 判断同轴加速检查标志，以确定检查加速
if (bShortPass == true)
{
break;
}
}
}
}
return false;
}
判断的思路基本如下：
从得到的两个十字路径中，先拿出横轴（两点的横向线上的点），然后拿点1横纵上的第一个连，找到点2横纵上与其相对在同一直线上的点，然后判断这两个点是否可连能，如果可加通，则表示点1和点2是可连通的，如果不能连通，则拿点1横轴上的下一个点，再去与点2横轴上相应的点进行判断，直到找到相连通的点或点1上的点全部判断完。
如果两点的横轴不能连通，然后比较两点的纵轴。
同轴加速检查标志是用来提早结束循环的，当两个横轴进行比较是否有点相连通时，其中一点如果比到与其同纵轴时，不管是否可连通，都不需要再比较下面的点。其实在这个地方可以加以修改，使其直接定位到对比轴内的相应位置（呵，由于比较忙，也没空去搞这个东西，做完到现在已经好几个月没碰了）
这个算法在连点上的扩展性不好，如果它的要求变成可以四折，五折，那样的话，就很难扩展，相比之下，普通的那种寻路算法，就要好多了，
但我发现这个算法在维度上的扩展比较好，如果将来有个3D的连连看，需要在3维空间中连接，也许这个算法的扩展性可能会相对好一些。
不知道各位有没明白，其实我当时就觉得这个算法好理解，才用它的，在效率上，我也不知道是这个算法怎么样，或许还是大部分人用的寻路算好，希望各位评价一下这个算法，给点意见，谢谢
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。