人工智能、数理算法

oraclelang

在飞行射击游戏中，我们的飞机大多都是三角形的，我们可以用三角形作近似的边界框。现在我们假设飞机是一个正三角形（或等要三角形，我想如果谁把飞机设计成左右不对称的怪物，那他的审美观一定有问题），我的飞机是正着的、向上飞的三角形，敌人的飞机是倒着的、向下飞的三角形，且飞机不会旋转（大部分游戏中都是这样的）。我们可以这样定义飞机：中心点O(Xo,Yo),三个顶点P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。中心点为正三角形的中心点，即中心点到三个顶点的距离相等。接下来的问题是怎样确定两个三角形互相干扰了呢？嗯，现在我们接触到问题的实质了。如果你学过平面解析几何，我相信你可以想出许多方法解决这个问题。判断一个三角形的各个顶点是否在另一个三角形里面，看起来是个不错的方法，你可以这样做，但我却发现一个小问题：一个三角形的顶点没有在另一个三角形的里面，却可能发生了碰撞，因为另一个三角形的顶点在这个三角形的里面，所以要判断两次，这很麻烦。有没有一次判断就可以的方法？我们把三角形放到极坐标平面中，中心点为原点，水平线即X轴为零度角。我们发现三角形成了这个样子：在每个角度我们都可以找到一个距离，用以描述三角形的边。既然我们找到了边到中心点的距离，那就可以用这个距离来检测碰撞。如图一，两个三角形中心点坐标分别为（Xo,Yo）和(Xo1,Yo1),由这两个点的坐标求出两点的距离及两点连线和X轴的夹角θ，再由θ求出中心点连线与三角形边的交点到中心点的距离，用这个距离与两中心点距离比较，从而判断两三角形是否碰撞。因为三角形左右对称，所以θ取-90～90度区间就可以了。哈，现在问题有趣多了，-90～90度区间正是正切函数的定义域，求出θ之后再找对应的边到中心点的距离就容易多了，利用几何知识，如图二，将三角形的边分为三部分,即图2中红绿蓝三部分，根据θ在那一部分而分别对待。用正弦定理求出边到中心点的距离，即图2中浅绿色线段的长度。但是，如果飞机每次移动都这样判断一次，效率仍然很低。我们可以结合半径法来解决，先用半径法判断是否可能发生碰撞，如果可能发生碰撞，再用上面的方法精确判断是不是真的发生了碰撞，这样基本就可以了。如果飞机旋转了怎么办呢，例如，如图三所示飞机旋转了一个角度α，仔细观察图三会发现，用（θ-α）就可以求出边到中心点的距离，这时你要注意边界情况，即（θ-α）可能大于90度或小于-90度。啰罗嗦嗦说了这么多，不知道大家明白了没有。我编写了一个简单的例程，用于说明我的意图。在例子中假设所有飞机的大小都一样，并且没有旋转。

/////////////////////////////////////////////////////////////////////

oraclelang

//faction/////////////////////////////////////////////////////////////
//根据角度求距离
float AngToDis(struct object obj, float angle)
{
    float dis, R;
    R = obj.radius;
    if (angle <= ang_30)
        dis = R / (2 * sin(-angle));
    else if (angle >= 0)
        dis = R / (2 * sin(angle + ang60));
    else dis = R / (2 * sin(ang120 - angle));
    return dis;
}

//碰撞检测
int CheckHit(struct object obj1, struct object obj2)
{
    float deltaX, deltaY, angle, distance, bumpdis;
    deltaX = abs(obj1.xo - obj2.xo);
    deltaY = obj1.yo - obj2.yo;
    distance = sqrt(deltaX * deltaX + deltaY * deltaY);
    if (distance <= obj.radio)
    {
         angle = atan2(deltaY, deltaX);
         bumpdis1 = AngToDis(obj1, angle);
         return (distance <= 2 * bumpdis);
    }
    ruturn 0;
}
//End//////////////////////////////////////////////////////////////

oraclelang

精美的随机数生成器程序



/////////////////////////////////////////////////////////////////////////////
// ELEMENT GDI/DX Game Engine [Version 2002/3/1]
/////////////////////////////////////////////////////////////////////////////
// Original Author : 邱海峰[Southdy]
// OICQ : 359766
// EMAIL: topmud@263.net
/////////////////////////////////////////////////////////////////////////////
// DESCRIPTION :
//
// OTHER : 邱海峰创建于2002/3/1
//
// 使用此随机数生成器者请无条件保留以下版权声明：
// (C) Copyright Beman Dawes 1998. Permission to copy, use, modify, sell and
// distribute this software is granted provided this copyright notice appears
// in all copies. This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
/////////////////////////////////////////////////////////////////////////////
#pragma once
/////////////////////////////////////////////////////////////////////////////
// 包含文件
/////////////////////////////////////////////////////////////////////////////
#include <cassert>
/////////////////////////////////////////////////////////////////////////////
class EK_Rand
{
// 不要有改动这几个常量的想法，否则……打你屁屁！
enum
{
modulus = 2147483647L,
multiplier = 48271L,
validation = 399268537L,
q = modulus / multiplier,
r = modulus % multiplier
};
// 种子数
long value; // 0 < value <= modulus
public:
explicit min_rand( long seed_value=1 ) : value( seed_value )
{
assert( value > 0 && value <= modulus );
}
　

operator long() const { return value; }

double fvalue() const { return double(value) / modulus; }

min_rand& operator=( long new_value )
{
value = new_value;
assert( value > 0 && value <= modulus );
return *this;
}

long operator++()
{
value = multiplier*(value%q) - r*(value/q);
if ( value <= 0 ) value += modulus;
assert( value > 0 && value <= modulus );
return value;
}

long operator++(int) { long temp = value; operator++(); return temp; }

long ten_thousandth() const { return validation; }

long operator()( long n ) { return operator++() % n; }

long operator()() { return operator++(); }

typedef long argument_type;
typedef long result_type;
};
/////////////////////////////////////////////////////////////////////////////

在boost里看到的绝对好东东。

oraclelang

关于SLG中人物可到达范围计算的想法


下面的没有经过实践，因此很可能是错误的，觉得有用的初学朋友读一读吧：）
希望高人指点一二

简介：
在标准的SLG游戏中，当在一个人物处按下鼠标时，会以人物为中心，向四周生成一个菱形的可移动区范围，如下：

  0
000
00s00
000
  0

oraclelang

这个图形在刚开始学习PASCAL时就应该写过一个画图的程序（是否有人怀念？）。那个图形和SLG的扩展路径一样。

一、如何生成路径：
从人物所在的位置开始，向四周的四个方向扩展，之后的点再进行扩展。即从人物所在的位置从近到远进行扩展（类似广宽优先）。

二、扩展时会遇到的问题：
1、当扩展到一个点时，人物的移动力没有了。
2、当扩展的时候遇到了一个障碍点。
3、当扩展的时候这个结点出了地图。
4、扩展的时候遇到了一个人物正好站在这个点（与2同？）。
5、扩展的点已经被扩展过了。当扩展节点的时候，每个节点都是向四周扩展，因此会产生重复的节点。

当遇到这些问题的时候，我们就不对这些节点处理了。在程序中使用ALLPATH[]数组记录下每一个等扩展的节点，不处理这些问题节点的意思就是不把它们加入到ALLPATH[]数组中。我们如何去扩展一个结点周围的四个结点，使用这个结点的坐标加上一个偏移量就可以了，方向如下：

  3
  0 2
  1

oraclelang

偏移量定义如下：
int offx[4] = { -1, 0, 1, 0 };
int offy[4] = { 0, 1, 0, -1 };

扩展一个节点的相邻的四个节点的坐标为：
for(int i=0; i<4; i )
{
    temp.x = temp1.x offx;
    temp.y = temp1.y offy;
}

oraclelang

typedef struct tagNODE{
    int x,y;   //扩展路径中的一个点在地图中的坐标。
    int curmp; //人物到了这个点以后的当前的移动力。
}NODE,*LPNODE;

上面的结构是定义扩展路径中的一个点的结构。扩展路径是点的集合，因此用如下的数组进行定义：

NODE AllPath[PATH_MAX_LENGTH];

其中的PATH_MAX_LENGTH代表扩展路径的点的个数，我们不知道这个扩展的路径中包含多少个点，因此定义一个大一点的数字使这个数组不会产生溢出：

#define PATH_MAX_LENGTH 200

上面的这个数组很有用处，以后的扩展就靠它来实现，它应该带有两个变量nodecount 代表当前的数组中有多少个点。当然，数组中的点分成两大部分，一部分是已经扩展的结点，存放在数组的前面；另一部分是等扩展的节点，放在数组的后面为什么会出现已扩展节点和待扩展节点？如下例子：

当前的人物坐标为x,y；移动力为mp。将它存放到AllPath数组中，这时的起始节点为等扩展的节点。这时我们扩展它的四个方向，对于合法的节点（如没有出地图，也没有障碍......），我们将它们存放入AllPath数组中，这时的新加入的节点（起始节点的子节点）就是等扩展结点，而起始节点就成了已扩展节点了。下一次再扩展节点的时候，我们不能再扩展起始节点，因为它是已经扩展的节点了。我们只扩展那几个新加入的节点（待扩展节点），之后的情况以此类推。那么我们如何知道哪些是已经扩展的结点，哪些是等扩展的节点？我们使用另一个变量cutflag，在这个变量所代表的下标以前的结点是已扩展节点，在它及它之后是待扩展结点。

oraclelang

五、下面是基本框架（只扩展一个人物的可达范围）：

int nodecount=0; //AllPath数组中的点的个数（包含待扩展节点和已经扩展的节点
int cutflag=0; //用于划分已经扩展的节点和待扩展节点
NODE temp; //路径中的一个点（临时）
temp.x=pRole[cur]->x; //假设有一个关于人物的类，代表当前的人物
temp.y=pRole[cur]->y;
temp.curmp=pRole[cur]->MP; //人物的最大MP
AllPath[nodecount ]=temp; //起始点入AllPath，此时的起始点为等扩展的节点

oraclelang

while(curflag<nodecount) //数组中还有待扩展的节点
{
    int n=nodecount; //记录下当前的数组节点的个数。
    for(int i=cutflag;i<nodecount;i ) //遍历待扩展节点
    {
        for(int j=0;j<4;j ) //向待扩展节点的四周各走一步
        {
            //取得相邻点的数据
            temp.x=AllPath.x offx[j];
            temp.y=AllPath.y offy[j];
            temp.curmp=AllPath.curmp-pMap[AllPath.x][AllPath.y].decrease;
//以下为检测是否为问题点的过程，如果是问题点，不加入AllPath数组，继续处理其它的点
            if(pMap[temp.x][temp.y].block)
                continue; //有障碍，处理下一个节点
            if(temp.curmp<0)
                continue; //没有移动力了
            if(temp.x<0||temp.x>=MAP_MAX_WIDTH|| temp.y<0||temp.y>=MAP_MAX_HEIGHT)
                continue; //出了地图的范围
            if(pMap[temp.x][temp.y].flag)
                continue; //已经扩展了的结

oraclelang

AllPath[nodecount]=temp;
        }
        pMap[AllPath.x][AllPath.y].flag=1; //将已经扩展的节点标记为已扩展节点
    }
    cutflag=n; //将已扩展节点和待扩展节点的分界线下标值移动到新的分界线
}
for(int i=0;i<nodecount;i )
    pMap[AllPath.x][AllPath.y].bFlag=0; //标记为已扩展节点的标记设回为待扩展节点。