寻路AI（译文）

原文地址：https://www.codeproject.com/Articles/7413/Path-Finder-AI

原文作者：andrea contoli

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

前言

A class to define a 2D space, put walls, set a start & end point, and return the best path.

定义2D空间,放置墙,设置起点和终点并返回最佳路径的类.

• 下载测试窗口-13.2 Kb(Download test window - 13.2 Kb)
• 下载源代码44.9 Kb(Download source code - 44.9 Kb)

介绍(Introduction)

我开始思考构建游戏AI的方法,该方法可以定义从起点到终点并穿过某些墙的路径.我创建了一个C#库((I started thinking the way to build a game AI that allows to define a path from a start point to an end point, through some walls. I created a C# library ()路径(path.dll)),它可以定义2D空间(MAXX,MAXY)并添加一些"墙".墙壁不过是矩形而已.添加完所有墙后,路径类将计算允许绕墙旋转的AI节点. “可见"的AI节点(它们之间没有墙)被链接.因此,该类实现了路径查找算法(基于用于与AI节点实例进行通信的C#委托).该O_O算法的结果是一个子类,该子类表示来自每个AI节点的AI NODE目的地的集合.在示例图像中,我们可以看到墙壁(橙色),AI NODES(红色),起点(蓝色)和终点(蓝色).() that allows to define a 2D space (MAXX, MAXY) and to add some “Walls”. Walls are nothing else than rectangles. After I add all the walls, the path class computes the AI nodes that allows to turn around the walls. The AI nodes that are “visible” (no wall between them) are linked. So, the class implements a path find algorithm (based on C# delegates used to communicate from AI node instances). The result of this O_O algorithm is a sub class that represents a collection of AI NODE destinations from each AI node. In the sample image, we can see the walls (orange), the AI NODES (red), the start point (blue), and the end point (blue).)

我建议一个测试窗口来运行(I propose a test window to run the)*路径(path.dll)*图书馆.(library.)

这个主意(The idea)

这个想法是要定义一个2D空间.这是通过初始化(The idea is to define a 2D space. This is done by initialization of the) Cartesio 类.此类允许在2D空间中将墙壁添加为矩形.(class. This class permits to add walls as rectangles in the 2D space.)

创建墙后,(After creating the walls, the) Cartesio 类创建((class creates () Create_ai_nodes() 方法)将AI节点"绕过"墙壁.在示例中,我们可以看到2面墙(红色)和关联的AI节点.(method) the AI nodes to “walk around” the walls. In the example, we can see 2 walls (in red) and the associated AI nodes.)

创建AI节点,(Creating AI nodes,) Cartesio 自动创建将节点相互链接的"可见弧”.可见弧线可以看作是链接2个节点而不"触摸"墙的线. (请参见示例.)(automatically creates the “visibility arcs” that links nodes with each other. A visibility arc can be seen as a line that links 2 nodes without “touch"ing a wall. (See example.))

最后,(Finally,) Cartesio 为每个节点创建一个目的地列表,以及要遍历到达目的地的相邻节点(我称之为(creates for each node, a list of destinations, and the adjacent node to walk through to reach the destination (I call it) AI_star ).因此,当我们在一个节点中(或我们可以看到它)时,我们知道下一个要到达的节点.(). So, when we are in a node (or we can see it), we know the next node to go to reach each other node.)

最后,上课(Finally, the class) Super_path 通过传递一个来初始化(is initialized by passing a) Cartesio 对象和起点(object, and a starting point) P1 和终点(and an end point) P2 .的(. The) Next() 方法"动作”(method “moves”) P1 至(to) P2 一步步.(step by step.)

While (!(supe_path.Next())) { //render 2d schene }

使用代码(Using the code)

您可以在我提交的演示代码中看到如何使用(You can see in the demo code I submitted, how the use of the) Cartesio Super_path 上课真的很简单:(classes is really easy:)

// initialize Cartesio with a 2d space of 300 X 300
  cart = new Cartesio(300,300);
  // add  walls to the 2d space
  cart.AddWall(56,56,100,10);
  cart.AddWall(156,15,11,231);
  cart.AddWall(10,135,114,26);
  // creates ai nodes and ai_stars for each node
  cart.Create_ai_nodes();

可能需要一些时间,具体取决于节点数(对于80-90个节点,我们有可接受的时间,请记住此操作只需执行一次).可见弧的数量也会影响创建时间.(It might take some time depending on the number of nodes (with 80-90 nodes, we have acceptable time, remember that this operation has to be done only once). The number of visibility arcs influences creation time too.)

 // initialize Super_path with start and end point , and Cartesio object.
  Np = new super_path(P1,P2,cart);
  
   // Next() consent to move the point Np.Pa on the path from P1 to P2
   while (!Np.Next())
   {
    P = Np.Pa;
    // render scene..

优化(Optimization)

当您将一堵墙放在花药墙(或另一组墙)上时,(When you put one wall over anther wall (or another set of walls), then the) Create_ai_nodes 方法丢弃放置在墙上的无用节点.参见示例:(method discards the non-useful nodes that are positioned into a wall. See example:)

代表和查找路径算法(Delegates and the find path algorithm)

我假设读者知道C#中的委托/事件是如何工作的.(I assume that the reader knows how delegates/events work in C#.)

我试图解释如何从相邻节点中找出最佳选择,以使节点S到达节点E.(I tried to explain how to find out the best choice from the adjacent nodes for a node S to reach a node E.)

首先,在创建AI节点期间,我们为每个节点创建一个委托,然后将所有相邻节点添加到由该委托代表的"侦听器"列表中.(First of all, during the creation of AI nodes, we create a delegate for each node, and we add to the “listener” list represented by that delegate, all the adjacent nodes.)

要从S转到E,让我们从E(向后)开始. E"广播"一条消息,其中包含对E(收件人)的引用,对S(发件人的)的引用以及对对其进行强制转换的节点的引用(通过)(在这种情况下为E);该消息还包含距离D(在这种情况下为0).(To go from S to E, let’s start from E (backwards). E “casts” a message that contains a reference to E (To), a reference to S (From), and a reference to the node that casts it (Through) (in this case, E); the message contains also a distance D (0 in this case).)

当节点收到消息M:(When a node receives a message M:)

• 如果它是第一条消息,它将存储距离D + dist(this,M.Throu),并投射一个新消息,其中D随D + dist(this,M.Throu)和M.Throu一起改变;(if it’s the first message, it stores the distance D + dist(this, M.Throu), and it casts a new message changing D with D + dist(this,M.Throu) and M.Throu with itself;)
• 如果不是第一条消息,则如果D + dist(this,M.Throu)<节点中存储的距离,则它将存储距离D + dist(this,M.Throu),并转换为D的新消息用D + dist(this,M.Throu)和M.Throu本身;(if it’s not the first message, if D + dist(this,M.Throu) < the distance stored in the node, then it stores the distance D + dist(this,M.Throu), and it casts a new message changing D with D + dist(this,M.Throu) and M.Throu with itself;) 对于S收到的每条消息M,S认为M.D为最小,因此S知道它可以从M.Trou到达E.(For each message M received by S, S considers the one with min M.D, and so S knows that it can reach E passing from M.Trou.)

在下图中,我们举一个从E到S的消息传播示例(蓝色箭头).该示例仅显示一些消息.当S收到消息9和10时,它将评估(考虑消息所携带的距离)哪个路径是最佳路径.(In the next figure, we se an example of message propagation form E to S (blue arrows). The example shows only some messages. When S receives messages 9 and 10, it evaluates (considering the distance carried by the messages) which path is the best.)

如何使用测试窗口(How To Use Test Window)

测试窗口的界面非常简单.您可以绘制墙(在鼠标左键单击时在屏幕上移动鼠标).之后,请记住单击"创建AI节点".然后,您可以设置起点和终点(单击鼠标左键和鼠标右键),然后查看起点是否到达目的地. (这是一种即点即用界面).您也可以点击(Test window’s interface is very simple. You can draw Walls (move mouse on screen while left click). After that, remember to click “Create AI Nodes”. Then you can set the start and end points (right and left click) and see the origin point reach the destination. (It’s a kind of click and go interface). You can also click on)*模拟(Simulation)*看到在2000条路径上的自动化可以强烈地测试我的工作.最后但并非最不重要的一点是,您可以清除墙壁,以便重新绘制它们.(to see an automation on 2000 paths to strongly test my work. Last but not least, you can clear the walls, so you can redraw them.)

希望您喜欢它,并给我一些好的建议.(Hope you enjoy it and return me some good suggestions.)

许可

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

C# Windows .NET WinXP Visual-Studio Dev 新闻 翻译