游戏中常用的算法

❶ 大鱼吃小鱼游戏中用到过哪些算法

大鱼吃小鱼游戏中用到过ZooKeeper的算法。

ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby一个开源的实现（Chubby是不开源的），它是集群的管理者，监视着集群中各个节点的状态根据节点提交的反馈进行下一步合理操作。最终，将简单易用的接口和性能高效、功能稳定的系统提供给用户 。

Zookeeper一个最常用的使用场景就是用于担任服务生产者和服务消费者的注册中心，服务生产者将自己提供的服务注册到Zookeeper中心，服务的消费者在进行服务调用的时候先到Zookeeper中查找服务，获取到服务生产者的详细信息之后，再去调用服务生产者的内容与数据。

ZooKeeper 的架构图中我们需要了解和掌握的主要有：

（1）ZooKeeper分为服务器端（Server） 和客户端（Client），客户端可以连接到整个 ZooKeeper服务的任意服务器上（除非 leaderServes 参数被显式设置， leader 不允许接受客户端连接）。

（2）客户端使用并维护一个 TCP 连接，通过这个连接发送请求、接受响应、获取观察的事件以及发送信息。如果这个 TCP 连接中断，客户端将自动尝试连接到另外的 ZooKeeper服务器。

客户端第一次连接到 ZooKeeper服务时，可以接受这个连接的 ZooKeeper服务器会为这个客户端建立一个会话。当这个客户端连接到另外的服务器时，这个会话会被新的服务器重新建立。

（3）上图中每一个Server代表一个安装Zookeeper服务的机器，即是整个提供Zookeeper服务的集群（或者是由伪集群组成）。

❷ 棋类游戏的算法有哪些

棋类游戏的算法有哪些

棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。下面我来给大家讲讲各类棋类游戏的算法。

除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢?

1. 博弈与博弈树

博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如“二人零和、全信息、非偶然”博弈，也就是我们常说的零和博弈(Zero-sum Game)。所谓“零和”，就是有赢必有输，不存在双赢的结果。所谓“全信息”，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的“非偶然”，是指参与博弈的双方的决策都是“理智”的行为，不存在失误和碰运气的情况。

在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动(也可能是棋子落子)的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。

假设两个棋手(可能是两个人，也可能是两台计算机)MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树(Game Tree)。

2. 极大极小值搜索算法

极大极小值(Min-Max)搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的'最大利益(令对手的最大利益最小化)的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。

3. 负极大值搜索算法

博弈树的搜索是一个递归的过程，极大极小值算法在递归搜索的过程中需要在每一步区分当前评估的是极大值节点还是极小值节点。1975年Knuth和Moore提出了一种消除MAX节点和MIN节点区别的简化的极大极小值算法，称为负极大值算法Negamax。该算法的理论基础是：

max(a,b) = -min(-a, -b)

简单地将递归函数MiniMax()返回值取负再返回，就可以将所有的MIN 节点都转化为MAX节点，对每个节点的搜索都尝试让节点值最大，这样就将每一步递归搜索过程都统一起来。

4. “α-β”剪枝算法

有很多资料将“α-β”剪枝算法称为“α-β”搜索算法，实际上，它不是一种独立的搜索算法，而是一种嫁接在极大极小值算法和负极大值算法上的一种优化算法。“α-β”剪枝算法维护了一个搜索的极大极小值窗口：[α,β]。其中α表示在搜索进行到当前状态时，博弈的MAX一方所追寻的最大值中最小的那个值(也就是MAX的最坏的情况)。在每一步的搜索中，如果MAX所获得的极大值中最小的那个值比α大，则更新α值(用这个最小值代替α)，也就是提高α这个下限。

而β表示在搜索进行到当前状态时，博弈的MIN一方的最小值中最大的那个值(也就是MIN的最坏的情况)。在每一步的搜索中，如果MIN所获得的极小值中最大的那个值比β小，则更新β值(用这个最大值代替β)，也就是降低β这个上限。当某个节点的α≥β时，说明该节点的所有子节点的评估值既不会对MAX更有利，也不会对MIN更有利，也就是对MAX和MIN的选择不会产生任何影响，因此就没有必要再搜索这个节点及其所有子节点了。

5. 估值函数

对于很多启发式搜索算法，其“智力”的高低基本上是由估值函数(评估函数)所决定，棋类游戏的博弈树搜索算法也不例外。

估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力(棋力)、双方棋子占领的空间、落子的机动性、威胁性(能吃掉对方的棋子)、形和势等。

6. 置换表与哈希函数

置换表(transposition table)也是各种启发式搜索算法中常用的辅助算法，它是一种以空间换时间的策略，使用置换表的目的就是提高搜索效率。一般情况下，置换表中的每一项代表者一个棋局中最好的落子方法，直接查找置换表获得这个落子方法能避免耗时的重复搜索，这就是使用置换表能大幅提高搜索效率的原理。

使用置换表最大的问题是置换表的组织和查找的效率。一般来说，置换表越大，查找的命中率就越高。但这个关系不是绝对的，当置换表大小达到一定规模后，不仅不会再提高命中率，反而会因为耗时的查找操作影响算法的效率。所以置换表不是越大越好，需要根据计算机的性能以及搜索的深度选择一个合适的大小。此外，为了查找操作更高效，通常都会用可直接访问的哈希表方式组织置换表，哈希函数的性能就成为影响置换表性能的重要因素。棋类游戏普遍采用Zobrist哈希算法。

❸ 游戏中为什么用启发式a星算法

首先，A* 是启发式算法，在寻路过程中搜索的范围相比 Dijsktra 一般要小得多（当然，有时也可能一样）
其次，A* 算法的搜索速度和效率可控，可以通过控制代价函数来权衡搜索的速度和精度之间的关系

❹ 游戏攻击判定的三种模式

转自：http://www.gameres.com/677620.html

攻击判定流程几乎是所有包含战斗玩法的游戏都无法绕过的一块内容，常见的攻击判定流程有瀑布算法、圆桌算法以及混合算法三种。本文简述了这三种判定流程的特征，以实例对比分析了瀑布算法与圆桌算法各自的优点，以期为后续其他战斗数值设计内容的论述提供一定的基础。

攻击判定流程概述

自此开始正文内容的叙述——让我们直接代入一个实例：

在一款游戏中，攻击方有命中率和暴击率两个攻击属性，而防守方有闪避率、招架率和格挡率三个防御属性。于是相应的，一次攻击有可能产生6种判定结果：未命中、普通命中、闪避、招架、格挡和暴击。当采用不同的判定流程进行攻击结算时，6种判定结果出现的频率会截然不同。

1.  瀑布算法

顾名思义，在瀑布算法中，各事件的判定顺序如同瀑布一般自上而下。如果“水流”在某个位置被截断，则后面的流程都将不再继续进行。据我所知，瀑布算法是大多数游戏所采用的攻击判定算法。

上述实例若采用瀑布算法，则会以如下方式进行判定：

先判定攻方是否命中

再判定是否被守方闪避

再判定是否被守方招架

再判断是否被守方格挡

最后判定该次攻击是否为暴击

瀑布算法流程图

由此我们可以得出：

瀑布算法特征1：多次掷骰，一次掷骰只判定单个事件的发生与否

瀑布算法特征2：后置判定依赖于前置判定的通过

注：有的游戏会将命中和闪避合并在一次掷骰中判定，这意味着将攻方命中率与守方闪避率合并计算出实际击中概率后再进行掷骰判定，仍是瀑布算法

我们再代入一些具体的数值，设攻守双方角色的面板属性如下：

攻方命中率=90%

攻方暴击率=25%

守方闪避率=20%

守方招架率=15%

守方格挡率=30%

按照上述的流程判定，6种判定结果将会按如下的概率分布：

实际未命中概率=1-命中率=1-90%=10%

实际闪避概率=命中率*闪避率=90%*20%=18%

实际招架概率=命中率*（1-闪避率）*招架率=90%*(1-20%）*15%=10.8%

实际格挡概率=命中率*（1-闪避率）*（1-招架率）*格挡率=90%*(1-20%)*(1-15%)*30%=18.36%

实际暴击概率=命中率*（1-闪避率）*（1-招架率）*（1-格挡率）*暴击率=90%*(1-20%)*(1-15%)*(1-30%)*25%=10.71%

实际普通命中概率=命中率*（1-闪避率）*（1-招架率）*（1-格挡率）*（1-暴击率）=90%*(1-20%)*(1-15%)*(1-30%)*(1-25%)=32.13%

瀑布算法的判定结果分布

由此我们可以得出：

l 瀑布算法特征3：各事件出现的概率符合经典的概率计算方法

l 瀑布算法特征4：掷骰轮次越偏后的属性衰减程度越大，但不会出现无效的属性

2.圆桌算法

将所有可能出现的事件集合抽象成一个圆桌桌面，便是圆桌算法这一称呼的由来。圆桌算法的实质，是将所有可能发生的事件状态按优先级依次放上桌面，直至所有事件被放完或桌面被填满。圆桌算法正是史诗级巨作魔兽世界中所采用的算法。据笔者了解，使用该算法的游戏并不多见，但即便仅魔兽世界这一款，已足以使这种算法成为永恒的经典~

上述实例若采用圆桌算法，则会用一次掷骰判定该次攻击的结果。

圆桌算法流程图

圆桌算法的操作步骤可以归纳为：

（1）攻方角色的命中率决定圆桌桌面的大小

（2）将各个事件状态按优先级依次放上桌面，直至所有的事件均放置完或桌面被填满

（3）若桌面还未填满，则用普通命中填满空桌面

将先前设定的数值代入，6种判定结果将会按如下的概率分布：

实际未命中概率=10%

实际闪避概率=20%

实际招架概率=15%

实际格挡概率=30%

实际暴击概率=25%

实际普通命中概率=90%-实际闪避概率-实际招架概率-实际格挡概率-实际暴击概率=90%-20%-15%-30%-25%=0%

注：在上述计算中，优先级按如下排序：闪避>招架>格挡>暴击>普通命中

圆桌算法的判定结果分布

可以看出，由于普通命中的优先级最低，所以它被完全挤出了桌面。这意味着，若攻守双方以此数值模型进行对决，则攻击方的攻击结果中将不存在普通命中。

由此我们可以得出：

圆桌算法特征1：一次掷骰即得出该次攻击的判定结果

圆桌算法特征2：事件有优先级，圆桌放满后优先级低的事件将被挤出桌面。这意味着那部分溢出的属性将不再生效

圆桌算法特征3：圆桌内的各事件出现概率不会衰减，只要优先级低的属性没有被挤出圆桌，各种事件的实际发生概率就与面板属性数值吻合

3. 混合算法

这是一种先判定攻方事件，再判定守方事件的判定流程。笔者曾在一篇帖子中看到过这样判定流程，不确定是否有实际的游戏应用，故仅在此做一些简单的理论分析。

混合算法在单方事件的判定中采用圆桌算法，即：

攻方判定结果：普通命中OR未命中OR暴击

守方判定结果：闪避OR招架OR格挡OR被命中

混合算法流程图

注：上面这个图仅作示意之用，从流程图的角度来看可能不太严谨

将先前设定的数值代入，6种判定结果将会按如下的概率分布：

实际未命中概率=10%

实际闪避概率=攻方命中率*闪避率=90%*20%=18%

实际招架概率=攻方命中率*招架率=90%*15%=13.5%

实际格挡概率=攻方命中率*格挡率=90%*30%=27%

实际暴击概率=攻方暴击率*敌方被命中概率=25%*(1-20%-15%-30%)=8.75%

实际普通命中概率=攻方普通命中概率*敌方被命中概率=(90%-25%)*(1-20%-15%-30%)=22.75%

混合算法的判定结果分布

由此我们可以得出：

混合算法特征1：先判定攻方事件，再判定守方事件，共进行两次掷骰

混合算法特征2：先在单方事件的判定中采用圆桌算法，再用瀑布算法串联攻守双方事件

混合算法特征3：会产生并发动作，例如暴击被闪避等

注：这也正是实际暴击率较低原因所在

瀑布算法与圆桌算法的特性对比

在上一块内容的铺垫之下，我们不妨继续以魔兽世界中的攻击判定流程设计实例作为切入点，对比分析一下圆桌算法与瀑布算法各自的特性。

（1）面板属性传递信息的直观性

瀑布：由于各属性在判定流程上的生效时间有先后之分，所以各属性的实际效用与面板显示的不符。

圆桌：由于属性的判定没有先后之分，只要没有属性被挤出圆桌，则所有属性的实际效用与面板显示的相当。

这里可以看出圆桌算法的优点：

属性的实际效用与面板显示相符显然更易于普通玩家的理解，便于玩家掌握自身的战力情况。

（2）属性的价值

瀑布：掷骰轮次越偏后的属性衰减程度越大，但所有的属性均会生效。

圆桌：只要没有属性被挤出圆桌，则不存在属性效用的衰减。

这里可以看出圆桌算法的优点：

由于不存在判定流程上的先后，所以各属性的实际价值会比较接近，一般不会出现玩家堆了某个判定流程靠后的属性结果很废的情况。

同样也可以看出其缺点：

一旦有属性溢出，则该部分属性的效用为0，完全没有价值。

（3）相同面板数值下的生存能力

圆桌：在面板数值相同的情况下，魔兽世界用圆桌算法大大提高了坦克角色的生存能力，使得他们可以应对来自首领怪的超高攻击，匹配大型团队副本的玩法设计。

瀑布算法下，免伤概率=18%+10.8%+18.36%=47.16%

圆桌算法下，免伤概率=20%+15%+30%=65%

传统的概率为相乘关系，圆桌为相加关系，后者的概率总和要大的多

并且，当防御职业将三维堆至一个阈值（70%）后，配合技能可达100%的免伤覆盖，将命中和暴击全部挤出桌面，从而衍生出特定的玩法（70级年代伊利丹的剪切技能）。

瀑布：相同的面板数值在瀑布算法的框架下，免伤概率相较于圆桌算法要低得多。换言之，角色达到相同的有效生命值，所需的免伤属性要高得多。

这里可以看出：

在圆桌算法的框架之下，属性投放若是脱离了控制超过了阈值，将对平衡性产生较大的冲击（70级的盗贼单刷格鲁尔——当然在暴雪光环的作用下，玩家会认为这是精妙的设计~）。

在国产游戏收入导向的大环境下，设计者是否能顶住收入压力，严守属性投放的极值不越界，是值得慎思的问题。采用瀑布算法，能有更大的数值空间用于能力投放，更为适合现阶段的市场环境。

（4）运算量

瀑布：多次掷骰

圆桌：单次掷骰

显而易见：

掷骰次数越多，运算量越大。圆桌相较于瀑布，有着相对较小的运算量。简单即是美。

注：除魔兽世界外，《冒险与挖矿》的技能施放也采用了圆桌算法，大大简化了技能施放的判定流程。可以想象一下，一次攻击至多发动一个技能。而每一次攻击，一个队伍中有几十个角色的技能施放需要判定，如果采用瀑布算法，将产生多大的运算量。

思考与总结

对战斗数值的研究，应该基于理论推导而归于实践应用。毕竟游戏数值设计不是做数学研究，其本质应是一种体验设计。最后希望交流的是笔者个人对于这两种算法的一些理解。

（1）不同的攻击判定流程会向玩家传达不同的战斗感受

究其本质，不同的攻击判定流程，影响着一场战斗中的各种攻击判定结果将以何种概率分布出现。

假设在一款游戏中，闪避率的投放上限是30%，暴击率的投放上限是40%，命中率的投放上限是100%。瀑布算法下，出现闪避、暴击和普通命中的概率是30%、28%和42%；圆桌算法下，则为30%、40%和30%。这两种不同的概率分布，必然会带给玩家不同的战斗体验，但在缺少其他条件的情况下，并不能判断孰优孰劣。

使战斗体验匹配游戏的核心玩法，使属性投放的极限值能满足游戏的商业化需要，是设计攻击判定流程时首先要考虑的。

注：甚至于部分竞技游戏强调公平性，将暴击做成了伪随机。

使用瀑布算法，则不应该设计种类繁多的事件状态

若是仿照魔兽世界的做法设计一连串的事件状态（未命中、闪避、招架、格挡、暴击、普通命中、偏斜、碾压），非但运算繁杂，而且后置判定的属性衰减幅度较大，效果极不明显。这种隐晦的设计将不易传达，同时还会影响玩家的游戏感受（某个判定流程靠后的属性堆得很高结果却没用）。

使用圆桌算法，则应该严守属性投放的上限，防止平衡崩坏的情况发生

需要澄清的是，并不是说使用瀑布算法就可以无限投放数值，而是说，相较于瀑布算法，圆桌算法的属性投放上限会低很多（免伤概率的相加与相乘）

（2）不同的攻击判定流程将影响有效生命EHP和有效攻击EDPS的表达式

几乎每个数值策划都会将角色的属性转化为EHP和EDPS以衡量其的战斗能力，但曾见过不少人对所有的游戏都用统一的EHP、EDPS表达式进行分析模拟。这种偏差较大的模拟方式必然会影响体验设计的精准性。在不同的攻击判定流程之下，EHP与EDPS有着截然不同的表达式，举例说明如下。

瀑布算法下：

若命中闪避分两次判定：

EHP=HP/(1-免伤率)/(1-闪避率)/(1-招架率)

EDPS=DPS*命中率*[1+暴击率*(暴击伤害倍率-1)]

若命中闪避合并判定：

EHP=HP/(1-免伤率)/(命中率-闪避率)/(1-招架率)

EDPS=DPS*(1+暴击率*(暴击伤害倍率-1))

圆桌算法下：

EHP=HP/(1-免伤率)/(1-闪避率-招架率)

EDPS=DPS*[命中率-敌方闪避率-敌方招架率+暴击率*(暴击伤害倍率-1)]

注：闪避、招架>暴击>普通命中，且各状态发生概率之和未超过圆桌大小

混合算法下：

EHP=HP/(1-免伤率)/(1-闪避率-招架率)

EDPS=DPS*[命中率+暴击率*(暴击伤害倍率-1)]

可能有人会觉得：模拟得这么准又有什么卵用，数值平衡最后还不是靠调？诚然，在数值设计领域，确实有名言曰：数值平衡是调出来的。但在笔者看来，调节应该建立在正确的理论推导的基础之上。依靠调节来掩盖数值模型的错误设计，是本末倒置的行为。即便达到了所谓的平衡，也不过是扭曲的平衡，会为后续版本的迭代埋下隐患。

写在最后

市面上的大多数游戏，都不会设计复杂繁多的攻击事件，且基本采用瀑布算法。如此看来，攻击判定流程的设计十分简单。那么为什么要大费周章地将简单问题复杂化呢？

爱因斯坦曾说过：Everythingmust be made as simple as possible, but not one bit simpler——凡事应该力求简单，但不能过于简单。从了解一种数值设计方法到理解如此设计的目的，从模仿成功游戏的数值设计到理解其设计的内在意义，这是每个数值策划成长的必经之路。

从全盘照搬一种数值体系到能够融会贯通并根据实际情况灵活运用，这是一条并不好走的路。知其然，也应知其所以然——这是一个入行一年有余的新人的一点感悟。

免责申明：

1.笔者无法保证本文所用词汇的普适性，能力所限，请多包涵~

2.不保证文中魔兽世界实例中的设定均与原作完全相符。但即便不相符，也不会影响圆桌理论的推

❺ 游戏中的常用的寻路算法有哪些

f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
?;) = g(n? 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
A*算法
? h(n) = 从结点n到目的结点的耗费评估值，启发函数
?，程序返回n
else 生成结点n的每一个后继结点n;
foreach 结点n的后继结点n;{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n?? 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径;)
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ;) + h(n?? 包含我们还没有处理到的结点
? g(n) = 从初始结点到结点n的耗费
?? 包含我们已经处理过的结点
，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点?? 启发式搜索
– 在搜索中涉及到三个函数
??? 我们最开始将起始结点放入到Open列表中
– Closed列表
?

❻ 游戏攻击算法

普攻伤害为攻击力（基础伤害加装备加成）。ad技能伤害为基础伤害加攻击力ad加成（比如一个技能ad加成0.5，就是你攻击力乘0.5）。ap伤害为基础伤害加法强加成，具体同攻击力加成一样。还有的技能加成特殊，比如流浪的技能受魔法值加成。狗头的q杀死目标积累伤害。但计算是一样的有的技能没有加成，比如盖伦的大招。收到的物理伤害会受护甲见面，比如100的护甲则你受到的伤害会减免100/（100+护甲值），即减伤50%。魔法伤害受魔抗减免，计算同物理伤害。真实伤害无视抗性。ps，点燃为真实伤害，伤害随等级提升。日炎斗篷造成魔法伤害 ，也随等级等级提升。

❼ 连连看的游戏，用的是什么原理算法，求指教一二

连连看核心算法如下：

#include <iostream>
using namespace std;

int board[102][102];
int nRowCount, nColCount;

bool isHorizontalLineValid(int c1, int c2, int r)
{
if(c1>c2) // 交换 C1, C2
{
c1 ^= c2 ^= c1 ^= c2;
}
for(int i=c1+1; i<=c2-1; i++)
{
if(board[r][i]!=0)
return false;
}
return true;
}

bool isVerticalLineValid(int r1, int r2, int c)
{
if(r1>r2) // 交换 r1, r2
{
r1 ^= r2 ^= r1 ^= r2;
}
for(int i=r1+1; i<=r2-1; i++)
{
if(board[i][c]!=0)
return false;
}
return true;
}

bool check(int r1, int c1, int r2, int c2)
{
// 如果该位置没有棋子或者两棋子不一致，则返回假
if(board[r1][c1]==0 || board[r2][c2]==0 || board[r1][c1]!=board[r2][c2])
return false;

// 两条水平线和一条垂直线
for(int i=0; i<=nColCount+1; i++)
{
if( (i!=c1 && board[r1][i]!=0) || (i!=c2 && board[r2][i]!=0) )
continue;
if( isHorizontalLineValid(i, c1, r1) &&
isVerticalLineValid(r1, r2, i) &&
isHorizontalLineValid(i, c2, r2))
{
board[r1][c1] = board[r2][c2] = 0;
return true;
}
}
// 两条垂直线和一条水平线
for(int i=0; i<=nRowCount+1; i++)
{
if( (i!=r1 && board[i][c1]!=0) || (i!=r2 && board[i][c2]!=0) )
continue;
if( isVerticalLineValid(i, r1, c1) &&
isHorizontalLineValid(c1, c2, i) &&
isVerticalLineValid(i, r2, c2))
{
board[r1][c1] = board[r2][c2] = 0;
return true;
}
}

return false;
}

int main(int argc, char** argv)
{
int nRound, nSuccess;
int x1, y1, x2, y2;

// 输入棋盘数据
cin >> nRowCount >> nColCount;
for(int i = 1; i <= nRowCount; ++i)
for(int j = 1; j <= nColCount; ++j)
cin >> board[i][j];

cin >> nRound;

for(int i = 0; i < nRound; ++i)
{
cin >> x1 >> y1 >> x2 >> y2;
if( check(x1, y1, x2, y2) )
cout << "Yes\n";
else
cout << "No\n";
}

system("pause");
return 0;
}

测试数据：
3 4
1 1 2 2
3 3 4 4
2 2 1 1
6
1 1 1 2
1 3 1 4
2 1 2 2
2 3 2 4
3 1 3 2
3 3 3 4

c1 ^= c2 ^= c1 ^= c2;语句中对于a^=b就相当于a=a^b，即代表a与b取位异或运算之后再把值赋给a的。楼主如果觉得还行的话请加点分的哦。

❽ 即时战略游戏中实用的寻路算法都有哪些

Potential Field，它是将地图用一个矩阵来表示，矩阵储存着大小不同的电势（整数）。例如，正电势表示吸引，负电势表示排斥。而游戏中的单位本身是一个负电势，游戏以一个数组储存所有单位的电势和位置。这样，在计算一个单位需要怎么从A点到B点时，我们可以用一个新的矩阵将目的地B点设成正电势，并以不同方式（如圆形、四边形等）辐射开来，离B点越远电势越低，直到0。然后将地图矩阵，目的地矩阵，和所有单位数组的电势相加，得出一个新的、反映当前游戏世界的电势矩阵，然后单位再选择周围所有电势点中的最高电势点去走。不过这里坑很多，因为它本质上是Greedy Algorithm，所以它未必能找出解。然而在某些设定中，例如在没有过于复杂地形，并且需要单位自动不相互覆盖的情况下，Potential Field还是可以完成任务。

Flocking Behavior，在对于一大群单位的寻路，计算量是很大的，而且往往会有很多的重复，这些都是可以避免的。如果单位的移动是利用Steering Behavior来实现的话，那么就可以为其中一个单位，称之为Leader，计算路径（例如用导航网格），然后其他单位按照以下Flocking原则来移动：1. 分离，避开相邻单位2. 一致，和整体的移动方向一致，这里应该是Leader的移动方向3. 聚合，向整体的平均位置靠拢这样的话，就可以降低寻路的计算量，并且得到更加真实的群体单位行进效果。