Any-Angle-Pathfinding, 用visualisations实现任意角度搜索的算法集合

分享于 

15分钟阅读

GitHub

  繁體 雙語
A collection of algorithms used for any-angle pathfinding with visualisations.
  • 源代码名称:Any-Angle-Pathfinding
  • 源代码网址:http://www.github.com/Ohohcakester/Any-Angle-Pathfinding
  • Any-Angle-Pathfinding源代码文档
  • Any-Angle-Pathfinding源代码下载
  • Git URL:
    git://www.github.com/Ohohcakester/Any-Angle-Pathfinding.git
    Git Clone代码到本地:
    git clone http://www.github.com/Ohohcakester/Any-Angle-Pathfinding
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/Ohohcakester/Any-Angle-Pathfinding
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    
    任意角度寻找

    用visualisations实现任意角度寻径算法的Collection。

    一些有用的论文,包括任何角度查找算法的比较:

    在这里,Anya的实现来自于这里的JGraphT,来自,它们是在各自的许可协议下。

    其它的都是

    特性

    实现算法的Visualisations:

    • 稀疏可见图算法
    • 可见性图算法类似,但( 还有最好的)的速度更快。
    • 需要预处理。
    • 在同一张纸上描述的边缘稀疏可见性图算法
    • 边缘稀疏可见性图算法
    • 安雅
    • Anya16
    • SG16: 在四叉树定义的可见性图形上加速A*搜索

    测试计算路径长度和运行时间的函数。

    用于生成栅格贴图的贴图生成器插件:

    • DefaultGenerator
      • 生成随机栅格贴图。可以为determinstic贴图生成设置随机种子。
    • AutomataGenerator
    • MazeMapGenerator
      • 利用kruskal算法的改进生成随机迷宫映射。
    • TiledMapGenerator
      • 从平铺一组现有地图生成贴图
    • UpscaledMapGenerator
      • 从现有地图的放大生成地图
      • 后置处理( 平滑) 是在元胞自动机迭代后进行
    • AffineMapTransformation
      • 对现有地图应用仿射变换 (scaling/rotation/shear) 生成新地图。

    映射也可以从文件中导入。 有关如何创建网格文件的详细信息,请参阅 uiandio/graphimporter。java注释。

    语言:需要 Java 8

    可视化:Java Swing

    依赖性:JUnit ( 在使用 Ant 构建脚本时不需要)

    生成的映射

    如果要加载现有的已经生成地图,可以在这里下载地图:

    使用它们,解压它们并将 mazedata/originalbenchmarks/ 目录放在存储库的root 中。

    大地图

    中比较比较大的图这些幻灯片和 this仅作为代码存储在StoredTestMazes ( 它们通过运行相应的生成代码来加载)。 用于测试的精确映射在 AlgoTest 中找到。 大地图来自这四个测试集: 英镑,英镑,"tiledmazes",英镑,英镑。

    为了方便,我还预先生成了上述地图。 它们在这里可用:

    使用 Apache Ant 构建

    若要生成和运行代码,请从基目录( 其中 build.xml 是) 运行以下命令。

    
    ant
    
    
    java -jar dist/AAP.jar -Xmx4096m
    
    
    
    

    要清理生成脚本中生成的文件,

     
    ant clean
    
    
    
     
    如何使用

    主要的类在 AnyAnglePathfinding.java. 中

    在 main() 中设置选择变量选择要运行的程序的哪个组件。 每个组件的详细信息在组件部分中给出。

    • [0] 可视化:生成算法的交互式可视化。
    • [1] AlgoTest: 对算法执行运行时间和路径长度测试。
    • [2] 实验:用于其他算法的测试。 ( 比如。检查算法的最优性)
    • [3] TestDataGenerator: 为/mazedata 目录生成测试数据。
    • [4] GridGraphVisualiser: 生成图形的可视化效果。 选择起点和终点坐标的便捷工具。
    • [5] TextOutputVisualiser: 从字符串生成算法的交互式可视化。
    • [6] AlgoTest.runWithArgs: 使用 命令行 参数运行测试

    通常,将在 loadMaze ( ) 中配置迷宫,并通过设置选择变量在 setDefaultAlgoFunction ( ) 中配置运行的算法。

    • loadMaze() 中一些重要的迷宫: ( 你可以更改相应的案例定义中的参数)
      • 选择 0: 随机迷宫
      • 选择 1: 指定种子的随机迷宫
      • 选择 58: Upscaled映射
      • 选择 59: 平铺贴图
      • 选择 60: 自动机映射( 动态截断)
      • 选择 63: 现有地图的仿射变换
      • 选择 66: 迷宫贴图
    组件

    我最常用的组件:

    • [0] 可视化
    • [4] GridGraphVisualiser
    • [6] AlgoTest.runWithArgs

    [0] 可视化

    用于生成算法树搜索的跟踪。

    初始视图将是蓝色的完整路径。 逐句通过帧以查看算法的跟踪。 通常,蓝色的圆被探索,红色的线是父。 起始点和目标点标记为圆。

    左/右:向后移动/向前移动一步。

    pgup/PgDown: 一次向后移动多个步骤。

    向上/向下:向后/向前移动一步,不会在最后一帧的第一帧周围循环。

    a/d 和s/w: 一次向后/向前移动多个步骤,不会从最后一帧转到第一帧。

    移动一步并同时拍摄屏幕截图。

    P: 与O 相同,但不在最后一帧的第一帧周围循环。

    L: 与P 相同,但一次跳跃多个步骤。

    [1] AlgoTest

    使用code中定义的测试套件,使用测试算法运行时

    要运行的测试在 main/Algotest.java的函数 AlgoTest.run() 中指定。 可以在那里编辑测试参数。

    
    String[] algoNames = new String[]{
    
    
    //Define algorithms to test here
    
    
    "Anya16",
    
    
    "BasicThetaStar",
    
    
    };
    
    
    
    String[] mapSetNames = new String[]{
    
    
    //Define the map sets to test on here
    
    
    "benchmarks",
    
    
    "automatadcmazes",
    
    
    };
    
    
    
    

    算法名称列表可以在 AlgoTest.getAlgo() 中找到,并且可以在 AlgoTest.testSequence 中找到映射集列表。

    以下映射集用于中的测试这些幻灯片:

    • 基准
    • benchmarksrandom
    • scaledmazes
    • tiledmazes
    • automatadcmazes
    • mazemaps

    [2] 实验

    用于在算法上运行各种实验的 检查 Experiment.run() 以获取详细信息

    Experiment.run() 函数有一系列注释出的实验。 当我需要测试某些算法的某些属性时,我通常只需要快速定义这些。

    一些更值得注意的实验示例:

    • testAlgorithmOptimality(): 将算法路径长度与一个已经知最优算法的算法进行比较。 对于快速查找算法的示例测试用例非常有用。

    [3] TestDataGenerator

    用于生成/导出网格到外部文件

    我不经常用这种方法。 ( 毕竟,我只需要生成测试数据一次)

    [4] GridGraphVisualiser

    用于预览地图视图的

    一个非常有用的工具它生成当前选定栅格地图的可视化效果。 按任何未使用的键将热键列表打印到控制台。 ( 比如。箭头键)

    使用左/右鼠标按钮放置起始/目标点( 分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别分别)。

    ( 当前) 热键列表:

    
    ESC: Close the window.
    
    
    9: Generates the path file from the currently selected points.
    
    
    0: Generates the maze analysis for the maze.
    
    
    A: Prints the maze analysis for the maze.
    
    
    P: Prints the path analysis for the current selected path.
    
    
    S: Generates a. map and a. scen file from the maze.
    
    
    Z: Switch mode: Automatically display path between points.
    
    
    X: Switch mode: Automatically display search tree between points.
    
    
    C: Switch mode: Disable path computation.
    
    
    V: Hold down for real-time pathfinding to mouse location
    
    
    
    

    这个工具的常用用途是找到一对好的开始/目标点,以便在英镑的[0] 可视化环境中。 我通常的工作流程:

    • 通过设置 choice 变量在 AnyAnglePathfinding.loadMaze() 中选择映射
    • 运行GridGraphVisualiser以生成地图的预览
    • Z 自动显示起始/目标点之间的最短路径( 由ENLSVGs供电)
    • 使用左/右鼠标按钮选择一对好的起始/目标点。
    • P 打印两个点的路径分析+ 坐标。
    • 复制这些坐标,并将它的用于 [0] 可视化

    [5] TextOutputVisualisation

    用于从字符串生成算法跟踪的

    我使用这个来查看在这个框架中未实现算法的算法跟踪。 ( 比如。在 C++ 中实现)。为这里,我在某个映射上运行算法,并插入print语句以打印算法跟踪。

    ( 比如,当它探索带有父( 2,4 )的( 5,8 ) 时,我打印出" 2 4 5 8")。 每行打印一个项目。

    跟踪以 # 字符结束。

    视图应按照时间顺序打印,以便显示器有意义。

    跟踪的每一行都是整数的序列,由空格隔开。

    跟踪中可以使用以下格式:

    • <x1> <y1> <x2> <y2> :从 (x1,y1)(x2,y2) 绘制一行
    • <x> <y>: 在 (x,y) 处绘制点
    • <y> <xLn> <xLd> <xRn> <xRd> <px> <py> :在行 y 上生成分数水平间隔,从 xLn/xLd ( 左边) 到 xRn/xRd ( 右边)。 也会在基点 (px, py) 中绘制直线。 用来跟踪 Anya。
    • <y> <xLn> <xLd> <xRn> <xRd> :与上面相同,但没有基点。

    ( 注意:这些是在函数 GridObjects.create() 中定义的)

    [6] AlgoTest.runWithArgs

    类似于 AlgoTest,但是我们从 命令行 运行测试参数。

    这些参数如下所示:

    • java -jar dist/AAP.jar <algorithmName> <mapSetName> <testType> <outputDirectory>

    用于运行测试的bash脚本示例:

    
    runtest() {
    
    
    java -jar dist/AAP.jar -Xmx4096m"$@"
    
    
    }
    
    
    
    runtest Anya16 benchmarks default output_benchmarks
    
    
    runtest BasicThetaStar benchmarks default output_benchmarks
    
    
    
    runtest Anya16 benchmarksrandom default output_benchmarksrandom
    
    
    runtest BasicThetaStar benchmarksrandom default output_benchmarksrandom
    
    
    
    

    算法名称列表可以在 AlgoTest.getAlgo() 中找到,并且映射集和测试类型的列表可以在 AlgoTest.testSequence 中找到。