A*寻路在线编辑器 + A*库

在线编辑器地址

拖入地图背景

修改蜂窝格子大小 生成静态地图数据

添加障碍

点击 添加障碍 后 按住 alt键盘 加 鼠标拖拽 快速建立障碍地形或者墙体

选择终点和起点

空格键 + 鼠标 拖拽地图

查看寻路细节

优化路径点数 寻路返回的实际路点列表 仅拐角部分

模拟寻路

修改寻路 k 值权重

>当k=0时,f(n)= h(n) ,最佳优先算法;以距离目标最近为导向
 当k=1时,f(n)= g(n) ,迪杰斯特拉算法;以距离自己最近为导向
 当k=0.5时,f(n)=g(n)+h(n) ,A星算法; 以距离自己最近 + 距离目标最近 为导向
  
 无障碍物时,最佳优先算法的步骤和结果路径都是最优的
 有障碍物时,采用A*算法

在这里插入图片描述

下载并保存地图json数据

{
    "timestamp": 1661536249564,
    "mapWidth": 2048,
    "mapHeight": 2048,
    "outerRadius": 30,
    "k": 0.5,
    "roadDataArr":[...]
}

json地图数据
timestamp 生成的时间戳
mapWidth&mapHeight 地图大小
outerRadius 格子外径
k 寻路优先权重值
roadDataArr 地图格子节点静态数据

下载a*寻路核心库


使用A*库

import Coord = astar.Coord;
import HoneycombSeeker = astar.HoneycombSeeker;
import MapData = astar.MapData;
import RoadNode = astar.RoadNode;

		
	//mapData就是下载的地图json反序列化后的object对象
	//JSON.parse(mapJsonTextContent);
	//至于  mapJsonTextContent 是你加载 map_data.json的文本内容 
	// 你可以使用 cc.load 来加载 
	// 也可以使用 Laya.loader 来加载
	// 当然你如果是纯html 也可以用 fetch
  	let seeker = new HoneycombSeeker(mapData);
    let startNode = seeker.GetRoadNodeByPosition(startPoint[0], startPoint[1]);
    let targetNode = seeker.GetRoadNodeByPosition(targetPoint[0], targetPoint[1]);
     if (!targetNode || !startNode) {
            alert(`开始节点和结束节点位置不对\nstartPoint:${startPoint[0]},${startPoint[1]}\ntargetPoint:${targetPoint[0]},${targetPoint[1]}\nmapData:${mapData.roadDataArr[0].length},${mapData.roadDataArr.length}`);
            return;
        }

   let paths = seeker.SeekPath(startNode, targetNode);

你需要根据情况 对最后一个至多个节点位置进行优化
即: 寻路路径 p0->p1->p2->p3->p4->p5
当移动到p4时 他的下一个目标位置应该时 mouseMapPos位置 鼠标对应的地图位置

关于大地图的处理

你可以在编辑器中将整张大地图用来处理生成碰撞地形格子数据 然后使用切图工具 将图片切成大小相同的底图
在游戏内实时去计算玩家的位置和屏幕的视角范围 去实时添加和移除地图块 来优化大地图的性能开销

另外单张地图的格子数量上限时 4096 x 4096 理论上已经够用了
当你超过4096的需求时 会自动帮你计算成 4096需要的蜂窝格子大小

==如果你有其它特殊需求 可以csdn留言或者联系我的邮箱 我会及时处理==

isysprey@foxmail.com

关于寻路的性能问题

该寻路算法采用的 高低位 存储x,y 使用map的方式去查找访问 高效轻量

        get key(): number {
            //这个值可以根据实际情况来调整 
            //12位的最大存储值是4096  x,y不能超过4096 
            //你可以上调但要保证不能溢出 也可以根据实际情况 下调  
            return this.x << 12 | this.y;
        }
        /**
         * 可以通过key来反推出x,y坐标值
         * 静态方法
         * @param key 
         * @returns 
         */
        public static key2Coord(key: number) {
            return new Coord(key >> 12 & 0xfff, key & 0xfff);
        }

同时在回溯路径的过程中 对路径点数计算优化
实际寻路路点数量 = 拐角数 + 2 ( 起点 和 终点)

已对数组和对象进行高度复用 同时也需要约束开发者
返回的节点仅供读取访问数据 不可赋值

是否支持es5?

支持

打包库的目标版本就是 es5 且向上兼容

尚未优化的点

  • 当寻路被打断 第二次寻路的目标位置 与 第一次寻路的目标位置 距离较近时 可以选择从尾部查找 一次排序找到 距离下次位置较近的点 ( 可以设置一个阈值 低于这个阈值的时候 从当前点开始寻路 到 新的目标点 ) 这样之前的路点就不需要重新计算
  • 寻路终点优化 对寻路节点附加偏移值 路点真实位置 = 路点中心位置 + 路点偏移
    默认 路点偏移 x,y,z都是0 终点前的几个位置 通过鼠标对应地图的位置
    做对应的插 值计算偏移
11赞

发布成插件卖钱

这东西又不稀罕 。。 就是提供一个方便 免的有些同学去新地方上班 要重新写一套 之类的
打包成一个库 方便使用

2赞

老板格局大

mark一个

大佬能不能写个JPS寻路

感谢大佬 :+1:

感谢大佬!

a * 库下载不了

astar_lib.zip (52.5 KB)

麻烦发布成插件卖钱,网页的东西一个都不敢用,哪天说没就没了