计算“可移动范围”的问题 - WEB三国 - 设计与修改


	aklin

组别	百姓
级别	在野武将
功绩	0
帖子	29
编号	52170
注册	2005-11-1

#1

发表于 2005-12-28 17:14 资料短消息只看该作者

在不同阵型、不同地形条件下，每个武将可移动的范围是如何计算出来的？——包括有赤兔马的移动范围，和无赤兔马的移动范围。

譬如，下图中关羽在那种阵型中向东只能移动一步。

这个问题我一直搞不清楚，既然这里在讨论设计“WEB三国 ”，那么，显然全部程序都要重新设计，而不是修改了，希望有人能解开我这个疑惑。

[广告] 真诚支持说岳，携手共创辉煌


	东方无翼


	燕王

组别	诸侯
级别	卫将军
好贴	6
功绩	849
帖子	6143
编号	1704
注册	2003-10-27

#2

发表于 2005-12-28 17:49 资料主页个人空间短消息只看该作者

这个首先要计算从格（X，Y）移动到与之相邻的格子（X+1，Y）、（X，Y+1）等等所消耗的移动力点数。这个不同的游戏的计算公式不一样。
比如说曹操传，似乎是考虑了地形和此格是否临近敌人这两个因素。而恶路强行和无视敌人这两个宝物属性，正是针对这两点来的。
关于移动范围的计算，根据不同的规则有不同的优化方法。大体的思想就是在这一格上标记上到达此格时所能剩余的最大移动力点数，再以此移动力为基础，向四方继续移动。
通过修改曹操传，发现他是遍历整个地图，来寻找移动力为N的点，再从移动力为N的点向四周移动。其中N从最大移动力递减到0，如上循环重复。其实效率蛮低的。不过战棋游戏的确不用太注重效率。
PS：如果以上有误van和周大赶快过来纠正哈

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	aklin

组别	百姓
级别	在野武将
功绩	0
帖子	29
编号	52170
注册	2005-11-1

#3

发表于 2005-12-28 19:21 资料短消息只看该作者

象上图中的关羽向右移动，就跟移动力无关，如果没有赤兔马，就是只能移一格。

但如果貂禅不在那里，就可以移动了，真不知道这个计算方法是怎么得来的。

[广告] 真诚支持说岳，携手共创辉煌


	浮生宛若寄


	忠信伯宁武军节度使

组别	节度使
级别	破贼校尉
功绩	61
帖子	74
编号	55707
注册	2005-12-21

#4

发表于 2005-12-28 21:02 资料文集短消息只看该作者

恩，这个问题以前困扰了我好久。差点把声波如何消减的用上了。

原理说深奥也不深奥，和连连看的算法类似，也是树的搜索。

我们看关羽所在的格子，他可以上下左右移动。

这是第一辈树枝，它有四个杈。其中上面因为有人，该被剪掉，有效的枝桠就是 3 个。关羽这个格子是树根（handle）。

第二辈也从上下左右四个方向发散，其中回退的枝桠剪掉。

由于每个格子消耗的移动力，这棵树只能长到一定大小。树所覆盖到的格子也就是移动范围。

一般搜索这棵树的空间使用深度搜索算法，占的内存比较小。

[广告] 真诚支持说岳，携手共创辉煌


	van


	平曲侯泸川军节度使 ★

组别	节度使
级别	军师将军
好贴	3
功绩	475
帖子	984
编号	25461
注册	2004-11-24

#5

发表于 2005-12-29 20:41 资料主页文集短消息只看该作者

类似于最短路，bfs+prior queue

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	wzh415 (zhihong)

组别	百姓
级别	在野武将
功绩	0
帖子	4
编号	66683
注册	2006-4-20

#6

发表于 2007-4-28 23:33 资料短消息只看该作者

补充一点，如果计算到某一点，这点的周围有敌军，则剩余移动力就直接消耗到0

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！