首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >路径查找器AI

路径查找器AI

作者头像
东心木水
修改2018-01-30 16:58:53
1.3K0
修改2018-01-30 16:58:53
举报
文章被收录于专栏:翻译翻译

首先放出测试程序和path库源码。

测试程序
测试程序

介绍

问题源于我想建立一个游戏AI,它要能够定义一条从起点到终点的路径,同时避开路上的墙壁障碍物。为此,我写了一个C#库(path.dll),它允许定义一个二维空间(MAXX,MAXY),并为这个空间设立一些矩形的“墙“。在添加完所有的墙后,path类将计算能够绕过墙的AI所有“可见”的AI节点(可见指节点之间没有墙)之间是连接的。这个类实现了一个路径查找算法,使用C#的Delegates(委托)与AI节点实例进行通信。最后,使用这个O_O算法(扩展欧几里得算法)将会得到一个子类,它是所节点的下一个目的AI节点的集合。在示例图中,可以看到墙(橙色),AI NODES(红色),起点(蓝色)和终点(蓝色)。

上面还给了一个path库的测试程序。

想法

这个想法是通过初始化Cartesio类定义一个2D空间。这个类允许在二维空间中添加矩形的墙。

墙

创建墙后,Cartesio类会创建(Create_ai_nodes()方法)一些“围绕”在墙壁四角的AI节点。在这个例子中,我们可以看到2个墙(红色)和相关的AI节点。

AI节点
AI节点

创建AI节点时,Cartesio类会自动创建“可视弧”,可视弧,也就是把相邻的节点连接到一起,同时避开所有的墙壁的线段。(看图)

可视弧
可视弧

然后,Cartesio为每个节点创建一个区域以及相邻节点(我称之为AI_star)列表,通过它来到达目的地。所以,当我们在一个节点(或者我们可以看到它)时,我们就可以做到遍历每一个节点。

最后,通过传递一个Cartesio对象,起点P1和终点P2来初始化Super_path类。Super_path.Next()可以一步一步地从起点移动到终点。



While (!(supe_path.Next())) { 

    //渲染2D图像 

}

使用path库

使用Cartesio的 Super_path类非常简单,如示例。



  //初始化 Cartesio ,2D空间大小:300*300
  cart = new Cartesio(300,300);
  // 添加一些墙到空间中
  cart.AddWall(56,56,100,10);
  cart.AddWall(156,15,11,231);
  cart.AddWall(10,135,114,26);
  // 生成AI节点 和对应的ai_stars
  cart.Create_ai_nodes();

可能需要一段时间,具体取决于节点的数量(这一步只需进行一次)。可见弧的数量也影响生成时间。



 // 初始化Super_path ,参数:起点P1,终点P2 ,Cartesio对象cart
  Np = new super_path(P1,P2,cart);
  
   // Next() 从起点一步步移动到终点
   while (!Np.Next())
   {
    P = Np.Pa;
    // 渲染场景..

优化

当两个墙壁重叠时,那么Create_ai_nodes方法会忽略定位在墙上的无用节点。看例子:

路径优化
路径优化

委托和路径查找算法

假设读者了解C#中的委托(delegate)和事件(event)。

解释一下如何从节点S的相邻节点中找出最佳选择以到达节点E.

首先,在创建AI节点的过程中,我们为每个节点创建一个委托,并且添加到由该委托所代表的监听器列表中的所有相邻节点。

从起点S到终点E,我们从终点E开始往回看。E抛出以下信息

  1. 对E(目的)的引用
  2. 对S(来源)的引用
  3. 一个指向它的节点的引用(即上一个节点,在本例中为E);
  4. 距离D(终点到E的距离,在这种情况下为0)。

当中间某个节点A收到消息M:

  • 如果它是第一个消息,则保存距离D=D + dist(this,M.Throu)(从这个节点到抛出消息节点的距离,这里就是dist(A,E)),并且更新D + dist(this,M.Throu)和M.Throu,生成新的消息。
  • 如果不是第一个消息,则如果新的总距离D + dist(this,M.Throu)小于存储在该节点中的距离,则存储距离取新的总距离D + dist(this,M.Throu),并抛出一个新的消息去更新D与D + dist(this,M.Throu)和M.Throu本身。文字描述晦涩难懂,后面会有简单明了示意图。

对于起点S接收到的每个消息M,S考虑具有最小距离D的那个消息,然后,S就可以知道应该怎么走,才能尽快到达E了。

举一个从E到S的消息传播的例子(蓝色箭头为传播方向),如下图(图中只列出部分信息)。如图所示,每一个节点T都挑出从T到节点E的最短路径,再抛出信息给其他节点,最后,S将会收到信息9和10,再考虑消息中附带的距离,分析哪条路径最好。

消息传播示意
消息传播示意

如何使用测试程序

测试程序的界面非常简单。你可以绘制墙(选中Draw walls后鼠标左键拖动即可绘制矩形墙)。之后,取消选中Draw walls,然后,就可以设置开始点(右键单击)和结束点(左键单击)。也可以点击Simulation进行距离为2000的自动测试来验证程序。最后,如果想重新绘制墙壁,可以点击Clear清除墙壁,再重新绘图。

测试程序界面
测试程序界面

嗨,我的老伙计,希望你能喜欢它,并看在上帝的面子上给我一些好的建议。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 介绍
  • 想法
  • 使用path库
  • 优化
  • 委托和路径查找算法
  • 如何使用测试程序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档