QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

实习版主

Rank: 10Rank: 10

技术值
查看: 768|回复: 5

[技术交流] 【原创】A*算法求解转珠游戏MaxComb的最优路径

[复制链接]
最佳答案
65 
累计签到:380 天
连续签到:2 天
jerryxjr1220 发表于 2017-2-10 21:06:32 7685 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-2-10 21:17 编辑

不知道有鱼油玩过类似"神魔之塔"之类的转珠游戏,就是连续交换相邻的珠子,使横排或者竖排有3个或以上同色珠子,即可消除,连续消除多组就会产生Max Comb。
类似这样的:

                               
登录/注册后可看大图

如果我们把不同颜色的珠子,用不同的数字表示的话(心为0,红为1,绿为2,蓝为3,黄为4,紫为5),那么上图的排列就可以写成一个二维数组:
“452102,304555,500452,450415,102112”。然后就可以解题啦!

我们先来看程序的输出:
==================================================
original puzzle:
4 5 2 1 0 2
3 0 4 5 5 5
5 0 0 4 5 2
4 5 0 4 1 5
1 0 2 1 1 2
Find way:  [[4, 2], [3, 2], [3, 1], [4, 1], [4, 2], [4, 3], [4, 4], [3, 4], [3, 5], [2, 5]]
solution:
4 5 2 1 0 2
3 0 4 5 5 5
5 0 0 4 5 2
4 0 5 4 5 2
1 0 1 1 1 2
Max Comb: 5
Optimization Movement:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 10
0 3 2 0 8 9
0 4 5 6 7 0
==================================================
注:由于第一个个(4,2)被后一个(4,2)覆盖了,所以在Optimization Movement里面没有显示“1”,其实“1”与“5”的位置重合了。
按照上述的顺序移动就可以在不考虑“天降”的情况下,完成至少5 Combo 。如果算上后期天降,每轮7 Combo不是梦

下面就让我们详细分析源代码:
游客,如果您要查看本帖隐藏内容请回复


A*算法结合了深度优先搜索和广度优先搜索的优点,它是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或在线游戏的BOT的移动计算上。

该算法综合了BFS(Breadth First Search)和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。
在此算法中,如果以 g(n)表示从起点到任意顶点n的实际距离,h(n)表示任意顶点n到目标顶点的估算距离(根据所采用的评估函数的不同而变化),那么 A*算法的估算函数为:
f(n) = g(n)+h(n)
这个公式遵循以下特性:
如果g(n)为0,即只计算任意顶点n到目标的评估函数h(n),而不计算起点到顶点n的距离,则算法转化为BFS(Breadth First Search),此时使用的是贪心策略,速度最快,但可能得不出最优解;
如果h(n)不为0,则一定可以求出最优解,而且h(n)越小,需要计算的节点越多,算法效率越低,常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离;
如果h(n)为0,即只需求出起点到任意顶点n的最短路径g(n),而不计算任何评估函数h(n),则转化为单源最短路径问题,即Dijkstra算法,此时需要计算最多的定点;

所以,可以看到A*算法是同时结合了深度优先搜索和广度优先搜索的一种搜索算法,可以利用2种算法的优点,既快又准地找到最优路径。
楼层
跳转到指定楼层
最佳答案
15 
累计签到:527 天
连续签到:2 天
$DIM 发表于 2017-2-11 09:29:46 | 显示全部楼层
最佳答案
0 
累计签到:1 天
连续签到:1 天
Abner_jue 发表于 2018-2-10 21:57:09 | 显示全部楼层
前来插眼
最佳答案
0 

尚未签到

dennis701007 发表于 2018-4-24 13:02:09 From FishC Mobile | 显示全部楼层
最近研究這部分問題看看代碼先
最佳答案
37 
累计签到:15 天
连续签到:3 天
ABC23 发表于 2018-4-24 16:49:51 | 显示全部楼层
回复
最佳答案
10 
累计签到:68 天
连续签到:15 天
溯影 发表于 2018-4-24 17:23:42 | 显示全部楼层
预习一下先
帮顶

发表回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /1 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2018-5-22 19:43

快速回复 返回顶部 返回列表