AI 助理
备案控制台
开发者社区 人工智能 文章 正文

连连看.NET 1.41 发布(改造路径提示，提供算法源码)

2017-11-26 1113
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

连连看.NET 1.41 版本下载 （源码在本文内）

除路径提示外，其他未做任何改变，可能播放音乐列表有问题，暂时不做修正了，大不了关一下再开吧；

关于修正路径提示：
本来写这个游戏是为了做个迷宫求解的算法，结果被做成这个了；一直路径绘制还是用的寻路的算法，今天改了改，改成实际的连线路径，因为有2位说过寻路路径太不顺眼；

关于源码：
我相信真正的开发人员是不屑一顾的，毕竟这些只是很基本的一些算法罢了，关于我先前写了两片笔记『 连连看路径求解的算法』『 "连连看"算法笔记』，如果肯动手的估计已经做好了，实在思路不清楚的可以阅读我的代码，我加了详细的注解，包括考虑绘图的时候图块的安排；

开发记录：
连连看.net到今天为止，我已经努力满足了大多数用过的朋友的要求，如果还有什么不满意的，只能说我尽力了；连连看的核心无非就是寻折点（这个不同于寻路），具体的实现可以看到关键的方法“CheckOneCorner”函数，它是寻找一个折点的目标，关于折点换算说出来是很简单的，还是看『 连连看路径求解的算法』一文，这个代码就是它的翻译体。如果有兴趣做做看，建议还是自己去想，自己做才能懂得更多；


以下是源码，可以判断两点是否在2折范围内，并记录路径点，2折的时候输出路径时取最短路径

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，如需转载请自行联系原作者
文章标签：
算法
定位技术
关键词：
算法源码
路径算法
.NET源码
算法.net
算法路径
老朱教授
目录
相关文章
ephemerals__
|
16天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
63 8
ephemerals__
|
16天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
54 7
维小帮
|
1月前
|
数据采集 监控 安全
厂区地图导航制作：GIS技术与路径导航算法融合
在智能化、数字化时代，GIS技术为厂区的运营管理带来了革命性变化。本文探讨了如何利用GIS技术，通过数据采集、地图绘制、路径规划、位置定位和信息查询等功能，打造高效、精准的智能厂区地图导航系统，提升企业的竞争力和管理水平。
维小帮
50 0
厂区地图导航制作：GIS技术与路径导航算法融合
不愿透漏名字的帅哥
|
5月前
|
搜索推荐 算法 小程序
基于Java协同过滤算法的电影推荐系统设计和实现(源码+LW+调试文档+讲解等)
基于Java协同过滤算法的电影推荐系统设计和实现(源码+LW+调试文档+讲解等)
不愿透漏名字的帅哥
103 0
不愿透漏名字的帅哥
|
5月前
|
搜索推荐 算法 小程序
基于Java协同过滤算法的图书推荐系统设计和实现(源码+LW+调试文档+讲解等)
基于Java协同过滤算法的图书推荐系统设计和实现(源码+LW+调试文档+讲解等)
不愿透漏名字的帅哥
102 0
dream_ready
|
1月前
|
存储 算法 安全
ArrayList简介及使用全方位手把手教学(带源码)，用ArrayList实现洗牌算法，3个人轮流拿牌(带全部源码)
文章全面介绍了Java中ArrayList的使用方法，包括其构造方法、常见操作、遍历方式、扩容机制，并展示了如何使用ArrayList实现洗牌算法的实例。
dream_ready
19 0
Onebound19970109110
|
3月前
|
JSON 算法 API
京东以图搜图功能API接口调用算法源码python
京东图搜接口是一款强大工具，通过上传图片即可搜索京东平台上的商品。适合电商平台、比价应用及需商品识别服务的场景。使用前需了解接口功能并注册开发者账号获取Key和Secret；准备好图片的Base64编码和AppKey；生成安全签名后，利用HTTP客户端发送POST请求至接口URL；最后解析JSON响应数据以获取商品信息。
Onebound19970109110
88 3
软件算法开发
|
3月前
|
算法
基于多路径路由的全局感知网络流量分配优化算法matlab仿真
本文提出一种全局感知网络流量分配优化算法，针对现代网络中多路径路由的需求，旨在均衡分配流量、减轻拥塞并提升吞吐量。算法基于网络模型G(N, M)，包含N节点与M连接，并考虑K种不同优先级的流量。通过迭代调整每种流量在各路径上的分配比例，依据带宽利用率um=Σ(xm,k * dk) / cm来优化网络性能，确保高优先级流量的有效传输同时最大化利用网络资源。算法设定收敛条件以避免陷入局部最优解。
软件算法开发
90 1
米码收割机
|
3月前
|
数据采集 机器学习/深度学习 算法
【python】python客户信息审计风险决策树算法分类预测（源码+数据集+论文）【独一无二】
【python】python客户信息审计风险决策树算法分类预测（源码+数据集+论文）【独一无二】
米码收割机
83 1
米码收割机
|
3月前
|
算法 Python
【python】python基于 Q-learning 算法的迷宫游戏（源码+论文）【独一无二】
【python】python基于 Q-learning 算法的迷宫游戏（源码+论文）【独一无二】
米码收割机
67 0

热门文章

最新文章

  • 1
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 2
    字符串相似度算法 递归与动态规划求解分析
  • 3
    【算法研究】Bresenham画线算法
  • 4
    【TDOA定位】基于chan和talor算法实现TDOA定位含性能对比matlab代码
  • 5
    openssl中算法的组织方式
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    JVM内存模型及垃圾回收算法
  • 8
    九连环的递归算法（C和C++）
  • 9
    iOS 算法之排序、查找、递归
  • 10
    希尔排序(shellsort)算法实现
  • 1
    LabVIEW加载.NET程序集
    94
  • 2
    LabVIEW中使用.NET方法时出现错误1316
    110
  • 3
    LabVIEW中加载.NET 2.0,3.0和3.5程序集
    148
  • 4
    .NET Compact Framework下的GPS NMEA data数据分析（二）转
    44
  • 5
    ASP.NET AJAX使用方法概述（三）
    51
  • 6
    Asp.net 2.0专题之一：MasterPage（2）
    41
  • 7
    使用PyTorch实现L1, L2和Elastic Net正则化
    93
  • 8
    C#/ASP.NET应用程序配置文件app.config/web.config的增、删、改操作
    73
  • 9
    Asp.net 2.0专题之一：MasterPage(2)
    40
  • 10
    安装ASP.NET AJAX (一安装)
    102

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 函数计算入门-HelloWorld应用开发
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 使用云助手公共命令快速安装Java环境
    • 下一篇
    无影云桌面