路径查找器AI

首先放出测试程序和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节点时,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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

HashedWheelTimer算法详解

George Varghese 和 Tony Lauck 1996 年的论文:Hashed and Hierarchical Timing Wheels: da...

1531
来自专栏机器学习从入门到成神

Python3读取深度学习CIFAR-10数据集出现的若干问题解决

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1282
来自专栏专知

【干货】TensorFlow中那些鲜为人知却又极其实用的知识

TensorFlow的生态圈极其强大,覆盖了科研、工程中的各种流程,其中一些特别好用的模块和技巧可以使你的工作效率大幅度提升,也可以让你的产品变得非常稳定。本文...

1541
来自专栏Python爬虫与数据挖掘

浅谈网络爬虫中深度优先算法和简单代码实现

我们今天要学习的内容,主要是给大家普及一下深度优先算法的基本概念,详情内容如下。

521
来自专栏深度学习那些事儿

在pytorch中实现与TensorFlow类似的"same"方式padding

文章来自Oldpan博客:https://oldpan.me/archives/pytorch-same-padding-tflike

2.8K7
来自专栏码云1024

Tensorflow 搭建神经网络 (一)

本文为中国大学MOOC课程《人工智能实践:Tensorflow笔记》的笔记中搭建神经网络,总结搭建八股的部分

63615
来自专栏机器学习原理

深度学习(1)——tensorflow简介什么是TensorFlow?什么是数据流图?安装基本概念示例变量的更新操作

3803
来自专栏HansBug's Lab

算法模板——线段树7(骰子翻转问题)

实现功能:首先输入一个长度为N的序列,由1-4组成(1表示向前滚一下,2表示向后滚一下,3表示向左滚一下,4表示向右滚一下,骰子原始状态:上1前2左4右5后3下...

3865
来自专栏牛客网

百度云部门 C++面试

14)读套接口时候返回0,时候时候产生EAGIN。【EAGIN也不太清楚,知道又这个玩意,不知道具体的,应该直接说不知道】

1572
来自专栏QQ音乐技术团队的专栏

​关于M4A文件的随机访问

文章介绍了M4A文件的大概结构,详细解读了其中的Sample Table Box,并结合图例,详细讲解了如何使用它来完成M4A文件的随机访问。 本文属原创作品,...

3718

扫码关注云+社区

领取腾讯云代金券