AI生活（译文）

原文地址：https://www.codeproject.com/Articles/28858/AI-Life

原文作者：Rahul_Sindhu

译文由本站 robot-v1.0 翻译

前言

Steering Behaviours, Genetic Algorithms, and Neural Networks in games

游戏中的转向行为,遗传算法和神经网络

• 下载源616.25 KB(Download source - 616.25 KB)
• 下载演示-565.73 KB(Download demo - 565.73 KB) 小费(Tip):要使用该程序,请使用"设置"子菜单设置所需的参数,然后初始化适当的类型.(: To use the program, set the desired parameters by using the Settings sub-menu, and then initialize the appropriate type.)

介绍(Introduction)

该项目旨在开发可以演示和模拟人工生命的程序.该项目实施了游戏行业和机器人技术中用于编码智能代理的三种主要技术.这些是:(The project aims at developing a program which could demonstrate and simulate Artificial Life. The project implements three main technologies which are used in the Gaming industry and Robotics for coding intelligent agents. These are:)

• 神经网络(Neural Networks)

• 遗传算法(Genetic Algorithms)

• 转向行为(Steering Behaviours) 该项目将实现所有这些功能,并展示它们在创建智能代理中的有用性.(The project will implement each of these, and demonstrate their usefulness in creating Intelligent Agents.) 演示的算法几乎是每个游戏的核心.该项目功能的直接结果将使其可以用作了解各种创建智能代理技术的工具.一种适合特定需求的改进版本可以用于训练实际机器人,以进行实际应用,例如巡逻,寻找地雷,进化等.该项目还可以用作研究进化的手段.此外,该项目将允许创建具有智能代理功能的游戏.(The algorithms demonstrated are the core of almost every game. The direct consequence of the project’s capabilities will allow it to be used as a tool for understanding various techniques for creating Intelligent Agents. An improved version, suited for particular needs, could be used for training real robots for real applications such as Patrolling, Finding Landmines, Evolving, and others. The project can also be used as a means of studying evolution. Further, the project will allow creation of games that feature Intelligent Agents.) 应用范围:(Applications:)

• 游戏开发(Game Development)

• 模拟器开发(Simulator Development)

• 机器学习(Machine Learning)

• 智能玩具(Intelligent Toys)

背景(Background)

神经网络(Neural Networks)

人工神经网络(ANN)通常称为"神经网络"(NN),是基于生物神经网络的数学模型或计算模型.它由一组相互连接的人工神经元组成,并使用连接主义方法进行信息处理.在大多数情况下,人工神经网络是一种自适应系统,可以根据在学习阶段流经网络的外部或内部信息来更改其结构.(An artificial neural network (ANN), often just called a “neural network” (NN), is a mathematical model or computational model based on biological neural networks. It consists of an interconnected group of artificial neurons, and processes information using a connectionist approach to computation. In most cases, an ANN is an adaptive system that changes its structure based on external or internal information that flows through the network during the learning phase.) 实际上,神经网络是非线性统计数据建模工具.它们可用于对输入和输出之间的复杂关系进行建模,或查找数据中的模式.(In more practical terms, neural networks are non-linear statistical data modeling tools. They can be used to model complex relationships between inputs and outputs, or to find patterns in data.) 也许,人工神经网络的最大优势在于它们可以用作从观察到的数据中"学习"的任意函数逼近机制.但是,使用它们并不是那么简单,并且对基础理论的相对良好的理解是必不可少的.(Perhaps, the greatest advantage of ANNs is their ability to be used as an arbitrary function approximation mechanism which ‘learns’ from observed data. However, using them is not so straightforward, and a relatively good understanding of the underlying theory is essential.)

• 模型选择:这将取决于数据表示形式和应用程序.过于复杂的模型往往会导致学习问题.(Choice of model: This will depend on the data representation and the application. Overly complex models tend to lead to problems with learning.)
• 学习算法:学习算法之间存在许多折衷.几乎所有算法都可以在特定的固定数据集上使用正确类型的参数进行训练.但是,选择和调整用于训练看不见的数据的算法需要大量的实验.(Learning algorithm: There are numerous tradeoffs between learning algorithms. Almost any algorithm will work well with the correct type of parameters for training on a particular fixed dataset. However, selecting and tuning an algorithm for training on unseen data requires a significant amount of experimentation.)
• 鲁棒性:如果适当选择模型,成本函数和学习算法,则所得的ANN可能非常鲁棒.(Robustness: If the model, cost function, and learning algorithm are selected appropriately, the resulting ANN can be extremely robust.) 通过正确的实施,人工神经网络可以自然地用于在线学习和大型数据集应用中.它们的简单实现以及结构中展示的大多数本地依赖项的存在,允许在硬件中进行快速,并行的实现.(With the correct implementation, ANNs can be used naturally in online learning and large dataset applications. Their simple implementation and the existence of mostly local dependencies exhibited in the structure allows for fast, parallel implementations in hardware.)

遗传算法(Genetic Algorithms)

遗传算法(GA)是一种搜索技术,用于计算以查找精确或近似的解决方案来优化和搜索问题.遗传算法被归类为全局搜索启发式算法.遗传算法是一类特殊的进化算法(也称为进化计算),其使用受进化生物学启发的技术,例如继承,突变,选择和交叉(也称为重组).(A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (also known as evolutionary computation) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).) 遗传算法被实现为计算机模拟,其中优化问题的候选解决方案(称为个体,生物或表型)的抽象表示(称为染色体,基因型或基因组)的总体向着更好的解决方案发展.传统上,解决方案以二进制形式表示为0和1的字符串,但是其他编码也是可能的.(Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes, or the genotype, or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves towards better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.) 进化通常从随机生成的个体的群体开始,并且世代相传.在每一代中,评估种群中每个个体的适应度,从当前种群中随机选择多个个体(基于适应度),并进行修改(重组,并可能随机变异)以形成新种群.然后在算法的下一个迭代中使用新的种群.通常,当产生了最大数量的世代或已达到总体的满意适应性水平时,算法就会终止.如果算法由于最大数目的代数而终止,则可能会或可能不会达到令人满意的解决方案.(The evolution usually starts from a population of randomly generated individuals, and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined, and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.) 遗传算法在生物信息学,系统发育学,计算机科学,工程学,经济学,化学,制造,数学,物理和其他领域中得到应用.(Genetic algorithms find application in Bioinformatics, Phylogenetics, Computer Science, Engineering, Economics, Chemistry, Manufacturing, Mathematics, Physics, and other fields.)

转向行为(Steering Behaviours)

指导行为为动画和游戏中自主角色的一项要求提供了解决方案:以逼真的,即兴的方式在其世界中导航的能力.这些指导行为在很大程度上与角色的运动方式无关.转向行为的组合可用于实现更高的目标(例如:从这里到达那里,同时避开障碍物,沿着这条走廊,加入那组角色^).(Steering Behaviours present solutions for one requirement of autonomous characters in animation and games: the ability to navigate around their world in a life-like and improvisational manner. These Steering Behaviours are largely independent of the particulars of the character’s means of locomotion. Combinations of steering behaviours can be used to achieve higher level goals (for example: get from here to there while avoiding obstacles, follow this corridor, join that group of characters…).) 自治角色是一种自治代理,旨在用于计算机动画和交互式媒体(例如游戏和虚拟现实)中.这些特工代表故事或游戏中的角色,并具有即兴表演的能力.这与动画电影中的角色(事先编写脚本)和游戏或虚拟现实中的"化身"(由人类玩家或参与者实时指挥)形成鲜明对比.在游戏中,自治角色有时称为非玩家角色.自主角色必须将自主机器人的各个方面与即兴剧场中人类演员的某些技能结合起来.这些角色通常不是真正的机器人,当然也不是人类演员,但每个角色都有一些共同之处.(Autonomous characters are a type of autonomous agents intended for use in computer animation and interactive media such as games and virtual reality. These agents represent a character in a story or game, and have some ability to improvise their actions. This stands in contrast both to a character in an animated film, whose actions are scripted in advance, and to an “avatar” in game or virtual reality, whose actions are directed in real time by a human player or participant. In games, autonomous characters are sometimes called non-player characters. An autonomous character must combine aspects of an autonomous robot with some skills of a human actor in improvisational theater. These characters are usually not real robots, and are certainly not human actors, but share some properties of each.) 术语行为具有许多含义.它可能意味着基于意志或本能的人类或其他动物的复杂动作.它可能意味着简单的机械系统在很大程度上可以预见的动作,或者混沌系统的在复杂的动作.在虚拟现实和多媒体应用程序中,有时将其用作"动画"的同义词.在这里,术语"行为"用于指代具有自主性的即兴和逼真的行为.(The term behaviour has many meanings. It can mean the complex action of a human or other animal based on volition or instinct. It can mean the largely predictable actions of a simple mechanical system, or the complex action of a chaotic system. In virtual reality and multimedia applications, it is sometimes used as a synonym for “animation”. Here, the term behaviour is used to refer to the improvisational and lifelike actions of an autonomous character.)

设计(Design)

该项目有三个子项目,分别是:(The project has three sub-projects, namely:)

• 转向行为(Steering Behaviours)
• 弦乐(EStrings)
• 蚂蚁(Ants) 项目中的类组织如下所示:(The organization of classes in the project is depicted below:) 上图描述了类如何相互关联,而不是继承.简而言之,(The image above describes how classes are related to each other, and not inheritance. In brief, the) MainForm 类拥有的对象(class possesses objects of) SBC (转向行为控制器),((Steering Behaviours Controller),) Cosmos 和(and) EStrings (不断发展的字符串).((Evolving Strings).) MainForm 使用它们来管理程序.(uses them to manage the program.) 这里,(Here,) SBC 创建对象(creates objects of the) Vehicle 类;每(class; each) Vehicle 有权使用(has access to the) SteeringBehaviours 类,用于确定在当前行为下要施加到自身的力(方向和速度).(class, which it uses to determine the force (direction as well as speed) which is to be applied to itself under the present behaviour.) SteeringBehaviours 和(and) Vehicle ,两者都使用(, both use) Vector 用于向量计算.(for vector calculations.) 的(The) Cosmos 类代表其中的蚂蚁世界.它是面板的油漆区域.的(class represents a world for the ants in it. It is the paint area of the panel. The) Cosmos 类创建对象(class creates objects of) Ant s;(s;) Ant 依次创建以下对象(s in turn create objects of) Network (他们的大脑),用于确定位置,速度和旋转.((their brain), which they use to determine position, speed, and rotation.) 的(The) EStrings 本课程简单地演示了遗传算法,以及如何将其用于收敛到解决方案.在这里,目标是一个字符串,但实际上,它可以是任何可以在计算机中表示的东西.尝试找出您的名字演变需要几代人!(class is a simple demonstration of Genetic Algorithms and how they can be used to converge to the solution. Here, the target is a string, but in reality, it can be anything that can be represented in a computer. Try to find how many generations it takes for your name to evolve!)

使用代码(Using the Code)

现在,我将详细解释每个.第一个是:(Now, I will explain each one in detail. The first one is:)

转向行为(Steering Behaviours)

简而言之,“引导行为"是一种移动自主游戏代理的方式,使它看起来好像有头脑.几乎每个游戏都使用它们来产生类似人类的行为.但实际上,这没有什么聪明的,只是一种幻想,完全是数学上的.我已经实现了以下行为:(Steering Behaviours, in short, is a way to move your autonomous game agent so that it looks as if it has brains. Almost every game uses them to produce human like behaviour. But in reality, there is nothing intelligent about it, it’s just an illusion, it’s all mathematical. I have implemented the following behaviours:)

描述(Description)

转向行为使用以下模型作为模拟各种行为的基础.(Steering Behaviours use the following model as a basis for simulating various behaviours.) 参考(Refer to) 本文(this article) 更多细节.(for more details.) 一个简单的车辆模型:(A simple vehicle model:)

在此表示为:(Represented here by:)

private float mass;
private int max_speed, max_force, vehicleNo;
private Vector2 currentPosition, velocity, acceleration,
        heading, steerForce, targetPosition;

这些变量维护有关车辆当前状态的数据.转向行为功能使用这些来计算力.我认为所有这些都是不言自明的.然后,该力用于确定车辆的新位置,速度,加速度和航向.现在,在获得新值之后,这些值将再次用于计算新值!并且,周期继续.如转向行为所述,该循环连续更新车辆的位置.(These variables maintain data about the current state of the vehicle. These are used by the Steering Behaviour’s functions to calculate force. I think all of them are self-explanatory. This force is then used to determine the vehicle’s new position, velocity, acceleration, and heading. Now, after obtaining the new values, these are then again used to calculate new ones! And, the cycle continues. This cycle updates the vehicle’s position continuously as described by the Steering Behaviour.) 下面的代码行精确演示了如何实现.这里,(The following lines of code demonstrate exactly how to do it. Here,) steerForce 和(and) velocity 被截断,因为在现实生活中,车辆确实有其局限性.有点变化(are truncated because in real life, vehicles do have their limits. A little change of) max_force ,(,) max_speed 和(, and) mass 可以使最好的跑车与最差的跑车有所不同(前提是您在赛车游戏中使用它;这看起来可能很奇怪,但这仅此而已!).(can make all the difference between the best sports car and the worst (provided you are using this in a racing game; it might seem weird, but that is all there is to it!).)

steerForce = Vector2.Truncate(steerForce, max_force);
acceleration = steerForce / mass;
velocity = Vector2.Truncate(velocity + acceleration, max_speed);
currentPosition = Vector2.Add(velocity, currentPosition);

1.寻求(1. Seek)

现在,让我们谈谈(Now, let’s talk about) Seek !理解和编码是所有行为中最简单的.这是代码:(! It is the simplest of all behaviours to understand and code. Here’s the code:)

public static Vector2 Seek(ref Vector2 targetPosition, ref Vector2 currentPosition,
                           ref Vector2 Velocity, int max_speed)
{
    Vector2 desired_V = Vector2.Normalize(
       Vector2.Subtract(targetPosition, currentPosition)) * max_speed;
    return Vector2.Subtract(desired_V, Velocity);
}

首先,计算所需速度.这是代理在理想世界中达到目标位置所需的速度.它表示从代理到目标的向量,缩放为代理最大可能速度的长度.(First, the desired velocity is calculated. This is the velocity the agent would need to reach the target position in an ideal world. It represents the vector from the agent to the target, scaled to be the length of the maximum possible speed of the agent.) 通过此方法返回的转向力是所需的力,当将其添加到代理的当前速度矢量中时,便会提供所需的速度.为此,您只需从所需速度中减去代理的当前速度.(The steering force returned by this method is the force required, which when added to the agent’s current velocity vector gives the desired velocity. To achieve this, you simply subtract the agent’s current velocity from the desired velocity.) 而且,这是它对100个游戏代理商的影响(我让他们看起来像警车,也许他们正在追捕罪犯!).(And, here is the effect it has on 100 game agents (I made them to look like police vehicles, maybe they are chasing a criminal!).) 是的,通过使用左上角指示的按键,您可以实时控制第一个车辆的变量,并查看它如何影响车辆的行为.以绿色突出显示的是一般的,而以黄色突出显示的是特定的转向行为.(And yes, by using the keys, about which the top-left corner tells, you can control the first vehicle’s variables in real-time and see how it affects the vehicle’s behavior. The ones highlighted in green are general, and the ones highlighted in yellow are specific to a particular Steering Behavior.)

2.逃跑(2. Flee)

现在(Now, the) Flee .完全相反(. It is completely opposite to) Seek .在这里,我们减去(. Here, we subtract) targetPosition 从(from) currentPosition , 而不是(, rather than) currentPosition 从(from) targetPosition .这是代码(看一下(. Here is the code (look at the) else 部分):(part):)

public static Vector2 Flee(Graphics g,ref Vector2 targetPosition,
              ref Vector2 currentPosition, ref Vector2 Velocity,
              int max_speed, int FOV,int vehicleNo)
{
    if (mainForm.steeringBehaviour != SB.CF && mainForm.steeringBehaviour !=
       SB.FCS && mainForm.steeringBehaviour != SB.FCAS && vehicleNo ==1)
    {
        g.DrawEllipse(Pens.Red, new RectangleF(new PointF(targetPosition.X - FOV,
                      targetPosition.Y - FOV), new SizeF(FOV*2, FOV*2)));
    }
    if (Vector2.Length(Vector2.Subtract(targetPosition, currentPosition)) > FOV)
    {
          return None();
    }
    else
    {
          Vector2 desired_V = Vector2.Normalize(Vector2.Subtract(
                                 currentPosition, SBC.targetPosition)) * max_speed;
          return Vector2.Subtract(desired_V, Velocity);
    }
}

现在,您想知道其他代码的含义.好吧,我必须告诉你,转向行为有很多不同的实现方式.有些简单,有些更复杂.这使用了FOV(视场)的概念,即座席可见的区域.这使代理人可以看到危险就逃走了. (这是完全有道理的;在​​现实生活中,每个特工都有有限的FOV,例如,如果鹿会奔跑,(Now, you want to know what the other code is about. Well, I must tell you that there are a lot of different implementations possible for Steering Behaviours; some are simple, and some are more complex. This one uses a concept of FOV (Field of View) i.e., the area that is visible to the agent. This makes the agent respond by fleeing if it can see the danger. (It totally makes sense; in real life, every agent has limited FOV, e.g., a deer will run if it)看到(sees)狮子(即,如果狮子在其视野中)那么简单!现在,第一个(the lion (i.e., if the lion is in its FOV)) So simple! Now, the first) if() 关于是否显示/绘制FOV.下一个(is about whether to show/draw the FOV or not. The next) if() 确定是否要逃离(即FOV中的威胁吗？).(determines whether to flee or not (i.e., is the threat in the FOV?).) 这是100名特工在害怕时的反应!(Here’s how 100 agents react when they are scared!)请注意,您可以使用Y和H键更改FOV.(Notice that you can change the FOV by using the Y and H keys.)

3.到达(3. Arrive)

现在来了(Now comes) Arrive .(.) Seek 这对于使业务代表朝正确的方向移动很有用,但是通常,您会希望您的业务代表在目标位置轻轻停下来,正如您所见,(is useful for getting an agent moving in the right direction, but often, you’ll want your agents to come to a gentle halt at the target position, and as you’ve seen,) Seek 不能优雅地停下来.(is not too great at stopping gracefully.) Arrive 是一种行为,使代理减速到目标位置.(is a behavior that steers the agent in such a way it decelerates onto the target position.) 这是代码(请注意(Here’s the code (watch for) arriveRadius ):():)

public static Vector2 Arrive(Graphics g,ref Vector2 targetPosition,
              ref Vector2 currentPosition,ref Vector2 Velocity,
              int arriveRadius, int max_speed,int vehicleNo)
{
    if (vehicleNo == 1)
    {
        g.DrawEllipse(Pens.SkyBlue, new RectangleF(
                      new PointF(targetPosition.X - arriveRadius,
                      targetPosition.Y - arriveRadius),
                      new SizeF(arriveRadius * 2, arriveRadius * 2)));
    }
    Vector2 toTarget = Vector2.Subtract(targetPosition, currentPosition);
    double distance = toTarget.Length();
    if (distance > 0)
    {
        double speed = max_speed * (distance / arriveRadius);
        speed = Math.Min(speed, max_speed);
        Vector2 desired_V = toTarget * (float)(speed/distance);
        return Vector2.Subtract(desired_V, Velocity);
    }
    return new Vector2(0, 0);
}

不要因为使用而感到困惑(Don’t get confused by the use of the) if() 声明;在那里,只有一辆车辆绘制了到达半径,而不是全部.这样可以提高性能,这也是合乎逻辑的,因为100个圆圈之间没有任何意义.这里,(statement; it is there so that only one vehicle draws the arrive radius and not all. This improves performance, and is also logical since there’s no point in 100 circles on top of one another. Here,) (distance / arriveRadius) 会在车辆接近其目标位置时导致速度稳定降低,并最终停止.(causes a steady decrease in speed as the vehicle approaches its target position, and it eventually stops.) 这是停放100辆车时的样子!也许,他们是人们在讨论某些东西!(Here’s how 100 vehicles look when they are parked! Or maybe, they are people discussing something!)此操守行为和其他操守行为的确切用法取决于游戏.这一切都取决于设计师的想象力.(The exact uses of this and other Steering Behaviours depend on the game; it all depends upon the imagination of the designer.)

4.徘徊(4. Wander)

现在,它将是(Now, it will be) Wander .(.) Wander 是一种随机转向.一种简单的实现方式是在每个帧中生成一个随机的转向力,但这会产生无趣的运动.它抽搐,并且不产生持续的转弯.一种更有趣的方法是保留转向方向状态,并在每个帧中对其进行较小的随机位移.因此,在一帧中,角色可能会向右上转,而在下一帧中,角色仍会沿几乎相同的方向转弯.转向力从一个方向随机走到另一个方向.为了产生下一帧的转向力,将随机位移添加到前一值,然后将总和再次约束到球体的表面.球体的半径(大圆)决定了最大的漂移强度,随机位移的大小(小圆)决定了漂移率.(is a type of random steering. One easy implementation would be to generate a random steering force in each frame, but this produces rather uninteresting motion. It is twitchy, and produces no sustained turns. A more interesting approach is to retain the steering direction state and make small random displacements to it in each frame. Thus, at one frame, the character may be turning up and to the right, and on the next frame, it will still be turning in almost the same direction. The steering force takes a random walk from one direction to another. To produce the steering force for the next frame, a random displacement is added to the previous value, and the sum is constrained again to the sphere’s surface. The sphere’s radius (the large circle) determines the maximum wandering strength, and the magnitude of the random displacement (the small circle) determines the wander rate.) 这是代码:(Here’s the code:)

public static Vector2 Wander(Graphics g, ref Vector2 wanderTarget,
       ref Vector2 currentPosition, ref Vector2 Velocity, ref Vector2 heading,
       float wanderRadius, float wanderDistance, int wanderJitter)
{
    heading = Vector2.Normalize(Velocity);
    wanderTarget += new Vector2(random.Next(-wanderJitter, wanderJitter),
                                random.Next(-wanderJitter, wanderJitter));
    wanderTarget = Vector2.Normalize(wanderTarget);
    wanderTarget *= wanderRadius / 2;
    PointF circleCenterG = new PointF((heading.X * wanderDistance + currentPosition.X) -
                           wanderRadius / 2, (heading.Y * wanderDistance +
                           currentPosition.Y) - wanderRadius / 2);
    Vector2 circleCenterM = new Vector2((heading.X * wanderDistance) + currentPosition.X,
                            (heading.Y * wanderDistance) + currentPosition.Y);
    Vector2 pointOnCircle = new Vector2(circleCenterM.X + wanderTarget.X,
                                circleCenterM.Y + wanderTarget.Y);
    g.DrawEllipse(Pens.LightGreen, new RectangleF(new PointF(circleCenterG.X,
                  circleCenterG.Y), new SizeF(wanderRadius, wanderRadius)));
    g.FillEllipse(Brushes.LightYellow, new RectangleF(new PointF(
                  pointOnCircle.X - 4, pointOnCircle.Y - 4), new SizeF(8, 8)));
    return Vector2.Subtract(pointOnCircle, currentPosition);

}

而且,它的外观如下:(And, here’s how it looks:) 并且,在” Leave Trail"上:(And, with “Leave Trail” on:) 请假单的作用是让您看到行进的路径确实是随机且平滑的.任务完成!不要忘了使用左上角的变量.(What the leave trail does is that it lets you see that the path traveled was indeed random and smooth. Mission accomplished! Don’t forget to play with the variables in the top-left corner.)

5.路径跟踪(5. PathFollowing)

接下来是(Next is) PathFollowing .(.) PathFollowing 产生使车辆沿着一系列航路点移动并形成路径的转向力.有时,路径具有起点和终点,而在另一些时间,它们在自身上循环,形成永无止境的封闭路径.(creates a steering force that moves a vehicle along a series of waypoints, forming a path. Sometimes, paths have a start and end point, and at other times, they loop back around on themselves forming a never-ending, closed path.) 您会发现在游戏中使用路径的无数用途.您可以使用它们创建巡逻地图重要区域的特工,使部队能够穿越困难的地形,或帮助赛车在赛道周围导航.在座席必须访问一系列检查点的大多数情况下,它们很有用.(You’ll find countless uses for using paths in your game. You can use them to create agents that patrol important areas of a map, to enable units to traverse difficult terrain, or to help racing cars navigate around a racetrack. They are useful in most situations where an agent must visit a series of checkpoints.) 遵循路径的最简单方法是将当前路径点设置为列表中的第一个路径,使用(The simplest way of following a path is to set the current waypoint to the first in the list, steer towards that using) Seek 直到车辆到达目标距离之内,然后抓住下一个航路点,(until the vehicle comes within a target distance of it, then grab the next waypoint and) Seek 为此,依此类推,直到当前航点是列表中的最后一个航点.发生这种情况时,车辆应到达当前航路点,或者,如果路径为闭环,则应将当前航路点再次设置为列表中的第一个,然后车辆才继续行驶(to that, and so on, until the current waypoint is the last waypoint in the list. When this happens, the vehicle should either arrive at the current waypoint, or, if the path is a closed loop, the current waypoint should be set to the first in the list again, and the vehicle just keeps on) Seek ing.(ing.) 这是代码(Here’s the code for) PathFollowing :(:)

public static Vector2 PathFollowing(ref Vector2 targetPosition,
       ref Vector2 currentPosition, ref Vector2 Velocity,
       ref Point[] pathPoints, ref int currentPathPoint,
       int maxPathPoints, int max_speed)
{
    if (currentPathPoint > maxPathPoints - 1)
    {
        currentPathPoint = 0;
    }
    int nextPathPoint = currentPathPoint + 1;
    if ((nextPathPoint > (maxPathPoints - 1)))
    {
        nextPathPoint = 0;
    }
    Vector2 currentPath = new Vector2(pathPoints[currentPathPoint].X,
                                      pathPoints[currentPathPoint].Y);
    Vector2 differenceV = Vector2.Subtract(currentPosition, currentPath);
    if (Math.Abs(differenceV.Length()) < 5)
    {
        targetPosition = new Vector2(pathPoints[nextPathPoint].X,
                                     pathPoints[nextPathPoint].Y);
        ++currentPathPoint;
        return Seek(ref targetPosition, ref currentPosition, ref Velocity,max_speed);
    }
    else
    {
        targetPosition = new Vector2(pathPoints[currentPathPoint].X,
                                     pathPoints[currentPathPoint].Y);
        //currentPathPoint++;
        return Seek(ref targetPosition, ref currentPosition, ref Velocity,max_speed);
    }
}

小费(Tip):降低(: Decrease the) max_speed 看到士兵巡逻,并增加它以查看赛车经过检查站!(to see a soldier patrolling, and increase it to see a racing car going through check points!) 而且,这是一条遵循路径的代理:(And, here’s an agent following a path:)

6.分离(6. Separation)

接下来来(Next comes) Separation .的(. The) Separation 转向行为使角色能够与附近的其他角色保持一定的距离.这可以用来防止角色拥挤在一起.计算转向(Steering Behavior gives a character the ability to maintain a certain separation distance from others nearby. This can be used to prevent characters from crowding together. To compute steering for) Separation ,首先进行搜索以查找指定邻域内的其他字符.这可能是对模拟世界中所有字符的详尽搜索,或者可能使用某种空间分区或缓存方案将搜索限制为本地字符.对于每个附近的角色,通过减去我们的角色和附近的角色的位置,进行归一化,然后应用1/r权重,可以计算出排斥力. (也就是说,位置偏移矢量按1/r 2缩放.)请注意,1/r只是效果很好的设置,而不是基本值.将每个附近角色的这些排斥力加在一起,以产生总的转向力.(, first a search is made to find other characters within the specified neighborhood. This might be an exhaustive search of all characters in the simulated world, or might use some sort of spatial partitioning or caching scheme to limit the search to local characters. For each nearby character, a repulsive force is computed by subtracting the positions of our character and the nearby character, normalizing, and then applying a 1/r weighting. (That is, the position offset vector is scaled by 1/r 2.) Note that 1/r is just a setting that has worked well, not a fundamental value. These repulsive forces for each nearby character are summed together to produce the overall steering force.) 这是代码:(Here’s the code:)

public static Vector2 Separation(ref Vehicle[] allCars, Vehicle me,
       ref Vector2 currentPosition, ref Vector2 velocity, int max_speed)
{
    int j = 0;
    Vector2 separationForce = new Vector2(0);
    Vector2 averageDirection = new Vector2(0);
    Vector2 distance = new Vector2(0);
    for (int i = 0; i < allCars.Length; i++)
    {
        distance = Vector2.Subtract(currentPosition, allCars[i].CurrentPosition);
        if (Vector2.Length(distance) < 100 && allCars[i] != me)
        {
            j++;
            separationForce += Vector2.Subtract(currentPosition,
                                                allCars[i].CurrentPosition);
            separationForce = Vector2.Normalize(separationForce);
            separationForce = Vector2.Multiply(separationForce, 1 / .7f);
            averageDirection = Vector2.Add(averageDirection, separationForce);
        }
    }
    if (j == 0)
    {
        return None();
    }
    else
    {
        //averageDirection = averageDirection / j;
        return averageDirection;
    }
}

而且,这是它的外观(当每个人都试图在如此拥挤的世界中为自己找到一个安静的地方时,就会发生这种情况!):(And, here’s how it looks (that’s what happens when every one tries to find a quiet place for oneself in such a crowded world!):)

7.凝聚力(7. Cohesion)

接下来是(Next is) Cohesion .的(. The) Cohesion 指导行为使角色可以与附近的其他角色进行协调(接近并与之形成群组).指导(Steering Behavior gives a character the ability to cohere with (approach and form a group with) other nearby characters. Steering for) Cohesion 可以通过查找本地邻域中的所有字符来计算(如上所述)(can be computed by finding all the characters in the local neighborhood (as described above for) Separation ),并计算附近角色的平均位置(或重心).转向力可以沿该平均位置的方向施加,也可以用作寻求转向行为的目标.() and computing the average position (or center of gravity) of the nearby characters. The steering force can be applied in the direction of that average position, or it can be used as the target for seek Steering Behavior.) 这是代码:(Here’s the code:)

public static Vector2 Cohesion(ref Vehicle[] allCars,Vehicle me,
              Vector2 currentPosition, Vector2 velocity,
              int max_speed, int cohesionRadius)
{
    int j = 0;
    Vector2 averagePosition = new Vector2(0);
    Vector2 distance = new Vector2(0);
    for (int i = 0; i < allCars.Length; i++)
    {
        distance = Vector2.Subtract(currentPosition, allCars[i].CurrentPosition);
        if (Vector2.Length(distance) < cohesionRadius && allCars[i] != me)
        {
            j++;
            averagePosition = Vector2.Add(averagePosition, allCars[i].CurrentPosition);
            //averagePosition = Vector2.Multiply(averagePosition, 10);
            //averagePosition = Vector2.Add(averagePosition,
                    Vector2.Normalize(distance) / Vector2.Length(distance));
        }
    }
    if (j == 0)
    {
        return None();
    }
    else
    {
        averagePosition = averagePosition / j;
        return Seek(ref averagePosition, ref currentPosition,
                    ref velocity, max_speed);
    }
}

小费(Tip):发挥内聚半径,并观察其对组数的影响.而且,它看起来像(请注意,群体是如何形成的,它们是组成帮派吗？我的天哪!):(: Play with the cohesion radius and see its effect on the number of groups. And, it looks like (Notice how groups are forming, are they forming gangs? Oh my!):) 另外,尝试考虑这种行为的用途(谁想要组成一个小组？).(Also, try to think of uses of such a behaviour (who would want to form a group?).)

8.对齐(8. Alignment)

接下来是(Next is) Alignment .的(. The) Alignment 转向行为使角色能够与附近的其他角色对齐(即,以相同的方向和/或速度前进).可以通过查找本地邻域中的所有字符来计算对齐方式(如上所述)(Steering Behavior gives a character the ability to align itself with (that is, head in the same direction and/or speed as) other nearby characters. Steering for alignment can be computed by finding all characters in the local neighborhood (as described above for) Separation ),然后将附近角色的速度(或可替代地,单位前向矢量)平均在一起.该平均值是所需的速度,因此,引导向量是平均值与角色当前速度(或替代地,其单位正向向量)之间的差.这种转向将使我们的角色转向,使其与邻居保持一致.() and averaging together the velocity (or alternately, the unit forward vector) of the nearby characters. This average is the desired velocity, and so the steering vector is the difference between the average and our character’s current velocity (or alternately, its unit forward vector). This steering will tend to turn our character so it is aligned with its neighbors.) 这是代码:(Here’s the code:)

public static Vector2 Alignment(ref Vehicle[] allCars, Vehicle me,
       ref Vector2 currentPosition, ref Vector2 velocity, int max_speed)
{
    int j = 0;
    Vector2 averageDirection = new Vector2(0);
    Vector2 distance = new Vector2(0);
    for (int i = 0; i < allCars.Length; i++)
    {
        distance = Vector2.Subtract(currentPosition, allCars[i].CurrentPosition);
        if (Vector2.Length(distance) < 100 && allCars[i] != me)
        {
            j++;
            averageDirection = Vector2.Add(averageDirection, allCars[i].Velocity);
        }
    }
    if (j == 0)
    {
        return None();
    }
    else
    {
        averageDirection = averageDirection / j;
        return Vector2.Subtract(averageDirection, velocity);
    }
}

而且,它是这样的(您见过飞过的鸟吗？如果您想在自己的游戏中加入这种行为,您会怎么做？):(And, here’s how it looks like (Have you ever seen birds flying? What will you do if you want to incorporate such a behavior in your own game?):) 游戏中看到的许多有趣行为不是由单个行为产生的,而是由许多行为的组合产生的.如何综合所有行为的力量取决于问题.在这里,我演示一个这样的(Many of interesting behaviors seen in games is not produced by a single behavior, but by a combination of many. How the forces of all the behaviors are combined depends upon the problem. Here, I demonstrate one such)的组合(combination of) Flee ,(,) Separation ,(,) Cohesion 和(, and) Alignment (FCAS).((FCAS).) 当同时施加所有FCAS力时,代理商会怎样？好吧,每个特工都将试图逃离目标(F),试图组成一个小组(C),朝着其他人的方向(A)移动,并且还要求拥有自己的私人空间(S).观看这样的组合真的很有趣.(What happens to the agents when all FCAS forces are applied at the same time? Well, every agent will try to flee from a target (F), try to form a group (C), move in the direction of others (A), and demand its own private space also (S). It really is interesting to watch such a combination.) 下图将车辆设置为漂移行为,所有其他人都将该车辆视为威胁并实现了FCAS行为.好像狮子在追牛,或者鲨鱼在追小鱼!这完全取决于一个人的想象力.(The image below has a vehicle set to wander behavior, and all others see this vehicle as a threat and implement the FCAS behavior. It looks like a lion is chasing a herd of cattle, or maybe the shark is after small fish! It all depends upon one’s imagination.) 到此结束转向行为.(That concludes Steering Behaviors.)可能存在更多的转向行为,但它们涉及矩阵计算,并且更加复杂,但值得关注.您可能还想尝试一下!(There are a lot more possible steering behaviors, but they involve matrix calculations and are more complex, but much more interesting to watch; you may also want to try them!)

弦乐(EStrings)

EStrings将帮助刚接触GA(遗传算法)的人们更好地了解GA. GA是一种寻求解决方案的技术,用于查找对哪些问题知之甚少,微积分等传统技术失败或效率太低的问题的解决方案. GA的这种实现方式尝试从一些随机生成的字符串收敛到一个字符串.遗传算法基于达尔文的进化理论,因此使用了诸如变异,交叉,适应性,父母等之类的东西,这些在典型的应用程序中是找不到的.(EStrings will help people new to GA (Genetic Algorithms) understand GA better. GA is a search-for-solution technique, it is used to find solutions to problems about which not much is known, or where traditional techniques of calculus and others fail or are too inefficient. This implementation of GA tries to converge to a string from some randomly generated strings. GA is based on Darwin’s theory of evolution, and therefore things like Mutation, Crossover, Fitness, Parents, etc., are used, which are not found in typical applications.) 在游戏中,GA用于训练神经网络,通常是代理的大脑.因此,我们使用GA来查找代理的"最佳大脑状态",以便其更好地工作或适应环境等.尽管这种实现可能没有任何直接用途,但对于初学者来说,这是一个合理的选择-关.有些人可能会感到惊讶,但是GA几乎可以用于任何问题,任何可以在计算机中表示的问题,我们都知道如何评估解决方案.(In games, GAs are used to train neural networks, which are typically the brain of the agent. So, we use GAs to find an “optimal state of brain” for the agent so that it works better, or adjusts to the environment, etc. Though this implementation may not be of any direct use, for a beginner, it’s a sound take-off. It may surprise some, but GAs can be used for almost any problem, any that can be represented in a computer and we know how to evaluate a solution for.) 第一步是代表问题.从这里开始,我们正在收敛到(The first step is to represent the problem. Since here we are converging to a) string , 一种(, a) string 是最好的代表.接下来,我们生成随机总体(此处为(is the best representation. Next, we generate random population (here, of) string s).每(s). Each) string 被称为染色体,每个字符代表生物体的特征.(is called a chromosome, and each character represents a characteristic of the organism.)

static void Initialize(ref List<OneString> ones, ref  List<OneString> two,
                       ref  List<OneString> temp)
{
    string rString = "";
    for (int i = 0; i < popSize; i++)
    {
        rString = "";
        for (int j = 0; j < sLen; j++)
        {
            rString += (char)rand.Next(32, 142);
        }

        ones.Add(new OneString(rString, 0));
        two.Add(new OneString(rString, 0));
        temp.Add(new OneString(rString, 0));
    }

看看我们如何在ASCII 32和142之间生成随机字符.对此的排列构成了我们的搜索空间.由于我们的目标字符串必须从当前这一代演变而来,因此拥有大量人口是一件好事,因此我们找到特定特征(此处是字符)的机会也很好.在产生足够多的人口之后,我们对它们进行评估并尝试找到最高的;这是使用健身功能完成的:(Look how we are generating random characters between ASCII 32 and 142. A permutation of this constitutes our search space. Since our target string has to evolve from the present generation, it is good to have a large population, so that our chances for finding the particular characteristic (here, a character) are good. After generating a good enough population, we evaluate them and try to find the top; this is done using the fitness function:)

private static void CalculateFitness(ref List<OneString> ones)
{
    int fitness;
    for (int i = 0; i < popSize; i++)
    {
        fitness = 0;
        for (int j = 0; j < sLen; j++)
        {
            fitness += Math.Abs(ones[i].name[j] - target[j]);
        }
        ones[i].fitness = fitness;
    }
}

在此,目标和来自填充的字符串之间的ASCII差的绝对值就是错误.如果此错误为零,则意味着我们找到了解决方案,搜索停止了.如果没有,我们将使用突变,精英,跨界等方式来生成新一代,并使用新一代重复此过程.(Here, the absolute value of ASCII difference between the target and a string from the population is the error. If this error is zero, this means we have found a solution and the search stops. If not, we generate a new generation using mutation, elitism, crossover, etc., and repeat the process with the new generation.) 外观如下:(Here’s how it looks:)

蚂蚁(Ants)

这是该项目的最后一部分,它将结合GA和NN(神经网络).在这里,我们创建了可以学习如何寻找食物的蚂蚁!我们首先创建大量的蚂蚁(使用典型的蚂蚁模型),让他们的大脑(NN,每个蚂蚁都有自己的),将有关其当前运动的数据馈送到网络中,获取输出,然后使用它们进行移动他们再次(希望更接近食物).我们这样做了一段时间,然后我们看看哪个蚂蚁使用其大脑(NN)获得最多的食物. GA适应度函数用于评估.经过评估,我们按顺序对它们进行排序,选择最佳的,让它们成为父母并生孩子.我们不断循环直到蚂蚁真正学习为止.(This is the last part of this project, it will combine GAs with NNs (Neural Networks). Here, we create ants that can learn how to find food! We first create a lot of ants (using a typical ant model), give them their brain (the NN, each ant has its own), feed the data about its current motion into the network, get the outputs, and use them to move them again (hopefully closer to food). We do this for some time, and then we see which ant got the most food using its brain (the NN). A GA fitness function is used for evaluation. After evaluation, we sort them in some order, choose the best ones, let them be parents and have children. We loop until ants actually learn.) NN由数字列表表示((The NN is represented by a list of numbers ()注意(Notice)在EStrings中,它是一个字符列表,在这里是一个数字列表),这些数字构成了NN的权重.解决方案空间仍然是它们的排列,问题是找到将蚂蚁引向最近食物的组合.(that in EStrings, it was a list of characters, and here it’s a list of numbers), these numbers make up the weight of the NN. The solution space is again the permutation of them, and the problem is to find the combination which will steer an ant towards the nearest food.) 下图显示了网络的基本结构:(The image below shows the network’s basic structure:)

private void Update()
{
    int totalFit = CalculateFitness();
    PrintBest(totalFit);
    lastTotalFit = totalFit;
    NewGeneration();
    inCG = 0;
    generationCount++;
}

上面的方法显示了使用的分步方法,下面是适应性方法.(The above method shows the step method used, and below is the fitness method.)

private int CalculateFitness()
{
    int totalFit = 0;
    for (int i = 0; i < numAnts; i++)
    {
        totalFit += ants[i].GetFoodCollected;
    }
    return totalFit;
}

并输出:(And the output:) 在这里,绿点代表食物,每只蚂蚁的绿色数字是所收集食物的数量,黄色数字是蚂蚁数字,右侧的列表显示了前几代的详细信息.(Here, the green dots represent the food, the green number with each ant is the number of food collected, the yellow number is the ant number, and the list on the right shows the details of the previous generations.) 打开"地雷"进行实验.(Do the experiment with turning the “Land Mines” on.)

参考文献(References)

• 自主字符的转向行为(Steering Behaviors For Autonomous Characters)
• 通过示例编程游戏AI-Mat Buckland(Programming Game AI by Example - Mat Buckland)
• Al应用程序编程-M. Tim Jones(Al Application Programming - M. Tim Jones)
• 神经网络设计-Martin T. Hagan(Neural Network Design - Martin T. Hagan)
• 遗传算法(Genetic Algorithms)

历史(History)

• 26/08/2008:初始版本(26/08/2008: Initial release)
• 2008/09/10:较小的更改和代码改进(09/10/2008: Minor changes & code improvement)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。