AI 助理
备案控制台
开发者社区 人工智能 文章 正文

Threejs中使用astar(A*)算法寻路导航，Threejs寻路定位导航

2022-10-17 642
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Threejs中使用astar(A*)算法寻路导航，Threejs寻路定位导航

1，介绍

该示例使用的是 r95版本Three.js库。利用A*算法实现寻路、导航功能。添加坐标轴。

效果图如下：


2，主要说明

引入A*算法astar.js


<script type="text/javascript" src="libs/astar.js"></script>


初始化路网、障碍物，记录路网、障碍物位置信息


// 绘制路网
function initGround() {
  var geometry = new THREE.Geometry();
  geometry.vertices.push(new THREE.Vector3(0, 0, 0));
  geometry.vertices.push(new THREE.Vector3(length, 0, 0));
  for (var i = 0; i <= length / ws; i++) {
    var material = new THREE.LineBasicMaterial({
      color: 0x808080
    });
    var line = new THREE.Line(geometry, material);
    line.position.z = i * ws;
    scene.add(line);
    var line = new THREE.Line(geometry, material);
    line.position.x = i * ws;
    line.position.z = length;
    line.rotation.y = 90 * Math.PI / 180;
    scene.add(line);
  }
}
// 初始化障碍物
function initGrid() {
  for (var i = 0; i < length / ws; i++) {
    var nodeRow = [];
    for (var j = 0; j < length / ws; j++) {
      var salt = Math.random() * 7;
      if (salt > 2) {
        nodeRow.push(1);
      } else {
        nodeRow.push(0);
      }
      if (salt <= 2) {
        var cube = new THREE.Mesh(new THREE.CubeGeometry(1, 1, 1), new THREE.MeshBasicMaterial({
          color: 0xC0C0C0
        }));
        let x = ws * j + ws / 2;
        let z = ws * i + ws / 2;
        cube.position.set(x, 1.2, z);
        scene.add(cube);
        mesh.push(cube);
      }
    }
    graph.push(nodeRow);
  }
}

调用A*算法，传入路网和障碍物信息，返回计算结果。用返回计算结果绘制路径。


//计算路径
function caculatePath(resultArray) {
  var maps = new Graph(graph); // 地图
  var startX = parseInt(resultArray[0].position.z / ws);
  var startY = parseInt(resultArray[0].position.x / ws);
  var endX = parseInt(resultArray[1].position.z / ws);
  var endY = parseInt(resultArray[1].position.x / ws);
  var start = maps.grid[startX][startY];
  var end = maps.grid[endX][endY];
  result = astar.search(maps, start, end);
  if (result.length == 0) {
    alert("无可到达路径");
    cleanSphere();
    return;
  }
  var nArr = [{
    x: resultArray[0].position.x,
    z: resultArray[0].position.z,
    y: 1.2
  }];
  for (var i = 0; i < result.length; i++) {
    let d = {
      x: result[i].y * ws + ws / 2,
      y: 1.2,
      z: result[i].x * ws + ws / 2,
    }
    nArr.push(d);
  }
  initLine(nArr);
}


3，源码

<!DOCTYPE html>
<html>
  <head>
    <title>Threejs中使用astar(A*)算法寻路导航</title>
    <script type="text/javascript" src="libs/three.js"></script>
    <script type="text/javascript" src="libs/OrbitControls.js"></script>
    <script type="text/javascript" charset="UTF-8" src="libs/other/Tween.min.js"></script>
    <script type="text/javascript" src="libs/astar.js"></script>
    <style>
      body {
        margin: 0;
        overflow: hidden;
      }
    </style>
  </head>
  <body>
    <div id="dom"></div>
    <script type="text/javascript">
      var camera;
      var renderer;
      var clock = new THREE.Clock();
      var length = 36;
      var ws = 2;
      var graph = [];
      var mesh = [];
      var resultArray = new Array();
      var isCaculate = false;
      function init() {
        // 创建一个场景，它将包含我们所有的元素，如物体，相机和灯光。
        var scene = new THREE.Scene();
        var urls = [
          'assets/textures/cubemap/flowers/posx.jpg',
          'assets/textures/cubemap/flowers/negx.jpg',
          'assets/textures/cubemap/flowers/posy.jpg',
          'assets/textures/cubemap/flowers/negy.jpg',
          'assets/textures/cubemap/flowers/posz.jpg',
          'assets/textures/cubemap/flowers/negz.jpg'
        ];
        var cubeLoader = new THREE.CubeTextureLoader();
        scene.background = cubeLoader.load(urls);
        // 创建一个摄像机，它定义了我们正在看的地方
        camera = new THREE.PerspectiveCamera(40, window.innerWidth / window.innerHeight, 0.1, 1000);
        // 将摄像机对准场景的中心
        camera.position.x = 60;
        camera.position.y = 35;
        camera.position.z = 60;
        camera.lookAt({
          x: 0,
          y: 5,
          z: -20
        });
        var orbit = new THREE.OrbitControls(camera);
        orbit.target = camera.position;
        orbit.update();
        // 创建一个渲染器并设置大小，WebGLRenderer将会使用电脑显卡来渲染场景
        // initialize basic renderer
        renderer = new THREE.WebGLRenderer();
        renderer.setSize(window.innerWidth, window.innerHeight);
        // 将平面添加到场景中
        var plane = createPlaneGeometryBasicMaterial();
        scene.add(plane);
        // 在屏幕上显示坐标轴
        var axes = new THREE.AxesHelper(100);
        scene.add(axes);
        // var trackballControls = initTrackballControls(camera, renderer);
        scene.add(new THREE.AmbientLight(0x666666));
        var ambientLight = new THREE.AmbientLight("#ffffff", 1);
        scene.add(ambientLight);
        document.getElementById("dom").appendChild(renderer.domElement);
        initGround();
        initGrid();
        initGridArr();
        // 启动动画
        renderScene();
        // 创建一个地面
        function createPlaneGeometryBasicMaterial() {
          var textureLoader = new THREE.TextureLoader();
          var cubeMaterial = new THREE.MeshStandardMaterial({
            map: textureLoader.load("assets/textures/stone/cd.jpg"),
          });
          cubeMaterial.map.wrapS = THREE.RepeatWrapping;
          cubeMaterial.map.wrapT = THREE.RepeatWrapping;
          cubeMaterial.map.repeat.set(18, 18)
          // 创建地平面并设置大小
          var planeGeometry = new THREE.PlaneGeometry(500, 500);
          var plane = new THREE.Mesh(planeGeometry, cubeMaterial);
          // 设置平面位置并旋转
          plane.rotation.x = -0.5 * Math.PI;
          plane.position.x = 0;
          plane.position.z = 0;
          return plane;
        }
        // 初始化线路
        function initLine(pArr) {
          var points = [];
          var geometry = new THREE.Geometry();
          for (var i = 0; i < pArr.length; i++) {
            var randomX = pArr[i].x;
            var randomY = pArr[i].y;
            var randomZ = pArr[i].z;
            var vector = new THREE.Vector3(randomX, randomY, randomZ);
            geometry.vertices.push(vector);
            points.push(vector);
          }
          var material = new THREE.LineBasicMaterial({
            color: 0x0000FF
          });
          var line = new THREE.Line(geometry, material);
          scene.add(line);
          return points;
        }
        // 绘制路网
        function initGround() {
          var geometry = new THREE.Geometry();
          geometry.vertices.push(new THREE.Vector3(0, 0, 0));
          geometry.vertices.push(new THREE.Vector3(length, 0, 0));
          for (var i = 0; i <= length / ws; i++) {
            var material = new THREE.LineBasicMaterial({
              color: 0x808080
            });
            var line = new THREE.Line(geometry, material);
            line.position.z = i * ws;
            scene.add(line);
            var line = new THREE.Line(geometry, material);
            line.position.x = i * ws;
            line.position.z = length;
            line.rotation.y = 90 * Math.PI / 180;
            scene.add(line);
          }
        }
        // 初始化障碍物
        function initGrid() {
          for (var i = 0; i < length / ws; i++) {
            var nodeRow = [];
            for (var j = 0; j < length / ws; j++) {
              var salt = Math.random() * 7;
              if (salt > 2) {
                nodeRow.push(1);
              } else {
                nodeRow.push(0);
              }
              if (salt <= 2) {
                var cube = new THREE.Mesh(new THREE.CubeGeometry(1, 1, 1), new THREE.MeshBasicMaterial({
                  color: 0xC0C0C0
                }));
                let x = ws * j + ws / 2;
                let z = ws * i + ws / 2;
                cube.position.set(x, 1.2, z);
                scene.add(cube);
                mesh.push(cube);
              }
            }
            graph.push(nodeRow);
          }
        }
        function initGridArr() {
          for (var i = 0; i < length / ws; i++) {
            var nodeRow = [];
            for (var j = 0; j < length / ws; j++) {
              nodeRow.push(1);
            }
            graph.push(nodeRow);
          }
        }
        //计算路径
        function caculatePath(resultArray) {
          var maps = new Graph(graph); // 地图
          var startX = parseInt(resultArray[0].position.z / ws);
          var startY = parseInt(resultArray[0].position.x / ws);
          var endX = parseInt(resultArray[1].position.z / ws);
          var endY = parseInt(resultArray[1].position.x / ws);
          var start = maps.grid[startX][startY];
          var end = maps.grid[endX][endY];
          result = astar.search(maps, start, end);
          if (result.length == 0) {
            alert("无可到达路径");
            cleanSphere();
            return;
          }
          var nArr = [{
            x: resultArray[0].position.x,
            z: resultArray[0].position.z,
            y: 1.2
          }];
          for (var i = 0; i < result.length; i++) {
            let d = {
              x: result[i].y * ws + ws / 2,
              y: 1.2,
              z: result[i].x * ws + ws / 2,
            }
            nArr.push(d);
          }
          initLine(nArr);
        }
        //清除小球
        function cleanSphere() {
          let child = scene.children; //获取场景中的所有子对象
          for (var i = 0; i < child.length; i++) {
            if (child[i].geometry instanceof THREE.SphereGeometry) { //几何对象是球体几何
              scene.remove(child[i]); //从场景中移除
              i--;
            }
          }
          isCaculate = false;
        }
        //初始球体
        function initSphere(x, z) {
          if (isCaculate) {
            cleanSphere();
          }
          var geometry = new THREE.SphereGeometry(ws / 2, 30, 30); //球体几何
          var material = new THREE.MeshBasicMaterial({
            color: 0xffff00
          }); //网格基础材料
          if (resultArray.length == 0) {
            var sphere = new THREE.Mesh(geometry, material);
            sphere.position.x = x;
            sphere.position.y = 1;
            sphere.position.z = z;
            resultArray.push(sphere);
            scene.add(sphere);
          } else if (resultArray[0].position.x != x || resultArray[0].position.z != z) {
            var sphere = new THREE.Mesh(geometry, material);
            sphere.position.x = x;
            sphere.position.y = 1;
            sphere.position.z = z;
            resultArray.push(sphere);
            scene.add(sphere);
            caculatePath(resultArray);
            isCaculate = true;
            resultArray = new Array();
          }
        }
        // 拾取对象
        function pickupObjects(event) {
          // 点击屏幕创建一个向量
          var raycaster = new THREE.Raycaster();
          var vector = new THREE.Vector2((event.clientX / window.innerWidth) * 2 - 1, -(event.clientY / window
            .innerHeight) * 2 + 1);
          var fxl = new THREE.Vector3(0, 1, 0);
          var groundplane = new THREE.Plane(fxl, 0);
          raycaster.setFromCamera(vector, camera);
          var ray = raycaster.ray;
          let intersects = ray.intersectPlane(groundplane);
          let x = intersects.x;
          let z = intersects.z;
          if (x < 0 || z < 0 || length < z || length < x) {
            return;
          }
          var k, m;
          for (var i = 0; i < length; i += ws) {
            if (x >= i && x < i + ws) {
              k = i + ws / 2;
            }
          }
          for (var j = 0; j < length; j += ws) {
            if (z >= j && z < j + ws) {
              m = j + ws / 2;
            }
          }
          initSphere(k, m); //初始化球体
        }
        document.addEventListener('click', pickupObjects, false); //监听单击拾取对象初始化球体
        // 动画渲染
        var step = 5;
        function renderScene() {
          orbit.update();
          // 使用requestAnimationFrame函数进行渲染
          requestAnimationFrame(renderScene);
          renderer.render(scene, camera);
        }
        // 渲染的场景
        renderer.render(scene, camera);
      }
      window.onload = init;
      function onResize() {
        camera.aspect = window.innerWidth / window.innerHeight;
        camera.updateProjectionMatrix();
        renderer.setSize(window.innerWidth, window.innerHeight);
      }
      // 监听调整大小事件
      window.addEventListener('resize', onResize, false);
    </script>
  </body>
</html>
文章标签：
算法
关键词：
threejs算法
算法定位
算法astar
算法寻路
算法导航
zuoben
目录
相关文章
简简单单做算法
|
并行计算 监控 算法
通过matlab对比music,mvdr以及tdoa三种定位算法的性能
通过matlab对比music,mvdr以及tdoa三种定位算法的性能
简简单单做算法
260 0
baker_zhuang
|
1月前
|
算法 数据可视化 新制造
Threejs路径规划_基于A*算法案例完整版
这篇文章详细介绍了如何在Three.js中完整实现基于A*算法的路径规划案例，包括网格构建、路径寻找算法的实现以及路径可视化展示等方面的内容。
baker_zhuang
59 0
Threejs路径规划_基于A*算法案例完整版
baker_zhuang
|
1月前
|
存储 算法 机器人
Threejs路径规划_基于A*算法案例V2
这篇文章详细介绍了如何在Three.js中使用A*算法进行高效的路径规划，并通过三维物理电路的实例演示了路径计算和优化的过程。
baker_zhuang
58 0
萝卜丝丸子
|
3月前
|
算法
互动游戏解决遇到问题之基于射线投射寻路算法的问题如何解决
互动游戏解决遇到问题之基于射线投射寻路算法的问题如何解决
萝卜丝丸子
37 0
郑小健
|
4月前
|
机器学习/深度学习 搜索推荐 算法
利用机器学习算法增强IAA广告定位和预测：实现个性化广告投放以最大化收益
【7月更文第30天】在当今高度竞争的移动应用市场中，应用内广告（IAA）是许多开发者获取收入的重要途径之一。然而，传统的广告推送方式往往忽略了用户的个体差异性，导致广告效果不佳。通过运用机器学习技术，我们可以更准确地理解用户偏好，从而实现个性化的广告推送。
郑小健
294 0
东方睿赢
|
5月前
|
存储 算法 Java
Java查找算法概览：二分查找适用于有序数组，通过比较中间元素缩小搜索范围；哈希查找利用哈希函数快速定位，示例中使用HashMap存储键值对，支持多值关联。
【6月更文挑战第21天】Java查找算法概览：二分查找适用于有序数组，通过比较中间元素缩小搜索范围；哈希查找利用哈希函数快速定位，示例中使用HashMap存储键值对，支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。
东方睿赢
57 1
编程的平行世界
|
4月前
|
Dart 算法 数据可视化
用flutter实现五种寻路算法的可视化效果，快来看看！
半年前我写了一篇有关排序算法可视化的文章，挺有意思，还被张风捷特烈-张老师收录进了FlutterUnit，今天让我们再来做一个有关寻路算法的可视化效果吧！
编程的平行世界
34 0
简简单单做算法
|
6月前
|
机器学习/深度学习 算法 网络架构
基于yolov2深度学习网络的单人口罩佩戴检测和人脸定位算法matlab仿真
摘要：该内容展示了一个基于YOLOv2的单人口罩佩戴检测和人脸定位算法的应用。使用MATLAB2022A，YOLOv2通过Darknet-19网络和锚框技术检测图像中的口罩佩戴情况。核心代码段展示了如何处理图像，检测人脸并标注口罩区域。程序会实时显示检测结果，等待一段时间以优化显示流畅性。
简简单单做算法
71 0
叫我兔兔酱
|
6月前
|
算法 定位技术 图形学
unity3d寻路算法
unity3d寻路算法
叫我兔兔酱
143 8
电力程序小学童
|
6月前
|
运维 算法
基于改进遗传算法的配电网故障定位（matlab代码）
基于改进遗传算法的配电网故障定位（matlab代码）
电力程序小学童
65 0

热门文章

最新文章

  • 1
    [干货]基础机器学习算法
  • 2
    18 回归算法 - Softmax回归 - 信贷审批案例
  • 3
    【推荐算法】商品推荐_3041
  • 4
    泛型KMP算法
  • 5
    线性排序算法（1）
  • 6
    【算法】算法之美—Fire Net
  • 7
    A* + 弗洛伊德 算法 打造 360 向寻路 - [ActionScript3.0]
  • 8
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 9
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 10
    算法学习之顺序结构
  • 1
    算法金 | 深度学习图像增强方法总结
    140
  • 2
    基于内容的推荐系统算法详解
    193
  • 3
    基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
    67
  • 4
    强化学习系列：A3C算法解析
    207
  • 5
    AES（Advanced Encryption Standard）是一种广泛使用的对称密钥加密算法，由美国国家标准技术研究所（NIST）制定。
    98
  • 6
    计算机视觉：目标检测算法综述
    150
  • 7
    `scipy.optimize`模块提供了许多用于优化问题的函数和算法。这些算法可以用于找到函数的最小值、最大值、零点等。
    81
  • 8
    Python排序算法大PK：归并VS快速，谁才是你的效率之选？
    34
  • 9
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    40
  • 10
    深入剖析操作系统调度算法
    55

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云OSS设置跨域访问