Chinaunix首页 | 论坛 | 博客
  • 博客访问: 748261
  • 博文数量: 109
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1987
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-15 22:39
个人简介

HT for Web 3D. HT for modern web and mobile app development. www.hightopo.com

文章分类

全部博文(109)

文章存档

2018年(28)

2017年(21)

2016年(10)

2015年(28)

2014年(19)

2013年(3)

我的朋友

分类: HTML5

2015-11-18 01:40:20

IMG_1486


http://www.hightopo.com/demo/astar/astar.html

最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于HT for Web写了个A*算法的WebGL 3D呈现,算法基于开源 https://github.com/bgrins/javascript-astar 的javascript实现,其实作者也有个不错的2D例子实现 http://www.briangrinstead.com/files/astar/ ,只不过觉得所有A*算法的可视化实现都是平面的不够酷,另外还有不少参数需要调节控制,还是值得好好搞个全面的Demo,先上张2D和3D例子的对照图。

Screen Shot 2014-11-24 at 5.36.33 PM

实现代码比较容易一百多行,不过算法核心在astar.js了,界面核心在ht.js里面了,我只需要构建网格信息,只需监听用户点击,然后调用astar.js进行最短路径计算,将结果通过动画的方式呈现出走动的过程,所有代码如下:

点击(此处)折叠或打开

  1. function init() {
  2.     w = 40; m = 20; d = w * m / 2;
  3.     gridRows = [];
  4.     dm = new ht.DataModel();
  5.     g3d = new ht.graph3d.Graph3dView(dm);
  6.     g3d.setGridVisible(true);
  7.     g3d.setGridColor('#BBBBBB');
  8.     g3d.setGridSize(m);
  9.     g3d.setGridGap(w);
  10.     g3d.addToDOM();
  11.     g3d.sm().setSelectionMode('none');
  12.     anim = startBall = endBall = null;
  13.     g3d.getView().addEventListener(ht.Default.isTouchable ? 'touchstart' : 'mousedown', function(e){
  14.         if(!anim){
  15.             var p = g3d.getHitPosition(e);
  16.             var x = Math.floor((p[0] + d)/ w);
  17.             var y = Math.floor((p[2] + d)/ w);
  18.             var endBall = dm.getDataByTag("cell_" + x + "_" + y);
  19.             if(endBall && endBall.s('batch') !== 'wall'){
  20.                 if(startBall.a('x') === x && startBall.a('y') === y){
  21.                     return;
  22.                 }
  23.                 var g = new Graph(gridRows, {
  24.                     diagonal: formPane.v('diagonal')
  25.                 });
  26.                 var start = g.grid[startBall.a('x')][startBall.a('y')];
  27.                 var end = g.grid[x][y];
  28.                 var result = astar.search(g, start, end, {
  29.                     closest: formPane.v('closest')
  30.                 });
  31.                 if(!result.length){
  32.                     return;
  33.                 }
  34.                 x = result[result.length-1].x;
  35.                 y = result[result.length-1].y;
  36.                 endBall = dm.getDataByTag("cell_" + x + "_" + y);
  37.                 endBall.s('3d.visible', true);
  38.                 startBall.s('3d.visible', false);
  39.                 formPane.setDisabled(true);
  40.                 anim = ht.Default.startAnim({
  41.                     duration: 700,
  42.                     finishFunc: function(){
  43.                         for(var i=0; i<result.length; i++){
  44.                             var ball = dm.getDataByTag("cell_" + result[i].x + "_" + result[i].y);
  45.                             ball.s({
  46.                                 '3d.visible': false,
  47.                                 'shape3d.opacity': 1,
  48.                                 'shape3d.transparent': false
  49.                             });
  50.                             startBall.p3(-d+w*x+w/2, w/2, -d+w*y+w/2);
  51.                             startBall.a({x: x, y: y});
  52.                             startBall.s('3d.visible', true);
  53.                         }
  54.                         anim = null;
  55.                         formPane.setDisabled(false);
  56.                     },
  57.                     action: function(v){
  58.                         var index = Math.round(v*result.length);
  59.                         for(var i=0; i<index; i++){
  60.                             var ball = dm.getDataByTag("cell_" + result[i].x + "_" + result[i].y);
  61.                             ball.s({
  62.                                 '3d.visible': true,
  63.                                 'shape3d.opacity': i/index*0.3 + 0.7,
  64.                                 'shape3d.transparent': true
  65.                             });
  66.                         }
  67.                     }
  68.                 });
  69.             }
  70.         }
  71.     }, false);
  72.     createFormPane();
  73.     createGrid();
  74. }
  75. function createGrid(){
  76.     dm.clear();
  77.     var ball;
  78.     gridRows.length = 0;
  79.     for(var x = 0; x < m; x++) {
  80.         var nodeRow = [];
  81.         gridRows.push(nodeRow);
  82.         for(var y = 0; y < m; y++) {
  83.             var isWall = Math.floor(Math.random()*(1/formPane.v('frequency')));
  84.             if(isWall === 0){
  85.                 nodeRow.push(0);
  86.                 createNode(x, y).s({
  87.                     'batch': 'wall',
  88.                     'all.color': '#9CA69D'
  89.                 });
  90.             }else{
  91.                 nodeRow.push(1);
  92.                 ball = createNode(x, y).s({
  93.                     'shape3d': 'sphere',
  94.                     'shape3d.color': '#FF703F',
  95.                     '3d.visible': false
  96.                 });
  97.             }
  98.         }
  99.     }
  100.     if(!ball){
  101.         createGrid();
  102.         return;
  103.     }
  104.     startBall = createNode(ball.a('x'), ball.a('y'), 'start').s({
  105.         'shape3d': 'sphere',
  106.         'shape3d.color': '#FF703F'
  107.     });

  108.     shape = new ht.Shape();
  109.     shape.setPoints(new ht.List([
  110.         {x: -d, y: d},
  111.         {x: d, y: d},
  112.         {x: d, y: -d},
  113.         {x: -d, y: -d},
  114.         {x: -d, y: d}
  115.     ]));
  116.     shape.setThickness(4);
  117.     shape.setTall(w);
  118.     shape.setElevation(w/2);
  119.     shape.setClosePath(true);
  120.     shape.s({
  121.         'all.color': 'rgba(187, 187, 187, 0.8)',
  122.         'all.transparent': true,
  123.         'all.reverse.cull': true
  124.     });
  125.     dm.add(shape);
  126. }
  127. function createNode(x, y, tag){
  128.     var node = new ht.Node();
  129.     tag = tag || "cell_" + x + "_" + y;
  130.     node.setTag(tag);
  131.     node.a({ x: x, y: y });
  132.     node.s3(w*0.9, w*0.9, w*0.9);
  133.     node.p3(-d+w*x+w/2, w/2, -d+w*y+w/2);
  134.     node.s({
  135.         'all.reverse.cull': true,
  136.         'shape3d.reverse.cull': true
  137.     });
  138.     dm.add(node);
  139.     return node;
  140. }
  141. function createFormPane() {
  142.     formPane = new ht.widget.FormPane();
  143.     formPane.setWidth(230);
  144.     formPane.setHeight(70);
  145.     formPane.getView().className = 'formpane';
  146.     document.body.appendChild(formPane.getView());
  147.     formPane.addRow(['Wall Frequency', {
  148.         id: 'frequency',
  149.         slider: {
  150.             min: 0,
  151.             max: 0.8,
  152.             value: 0.1,
  153.             onValueChanged: function(){
  154.                 createGrid();
  155.             }
  156.         }
  157.     }], [100, 0.1]);
  158.     formPane.addRow([
  159.         {
  160.             id: 'closest',
  161.             checkBox: {
  162.                 label: 'Try Closest'
  163.             }
  164.         },
  165.         {
  166.             id: 'diagonal',
  167.             checkBox: {
  168.                 label: 'Allow Diagonal'
  169.             }
  170.         }
  171.     ], [0.1, 0.1]);
  172. }

只从iOS8支持WebGL后在移动终端上测试3D应用比当前的大部分Android平板舒服多了,以上的例子在iOS系统下呈现和算法都挺流畅,http://v.youku.com/v_show/id_XODMzOTU1Njcy.html,当然这个小例子数据量也不大,本质其实还是2D的最短路径算法,并非真正意义的3D空间最短路径,但还是足够解决很多实际应用问题了。

http://www.hightopo.com/demo/astar/astar.html

Screen Shot 2014-11-24 at 5.09.13 PM


阅读(1873) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册