轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 计算“可移动范围”的问题 [打印本页]

作者: aklin 时间: 2005-12-28 17:14

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

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

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

作者: 东方无翼 时间: 2005-12-28 17:49

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

作者: aklin 时间: 2005-12-28 19:21

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

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

作者: 浮生宛若寄 时间: 2005-12-28 21:02

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

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

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

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

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

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

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

作者: van 时间: 2005-12-29 20:41

类似于最短路，bfs+prior queue

作者: wzh415 时间: 2007-4-28 23:33

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

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)