基于WebGL 的3D呈现A* Search Algorithm

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

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

function init() { 
 w = 40; m = 20; d = w * m / 2; 
 gridRows = []; 
 dm = new ht.DataModel(); 
 g3d = new ht.graph3d.Graph3dView(dm); 
 g3d.setGridVisible(true);
 g3d.setGridColor('#BBBBBB');
 g3d.setGridSize(m);
 g3d.setGridGap(w); 
 g3d.addToDOM(); 
 g3d.sm().setSelectionMode('none'); 
 anim = startBall = endBall = null; 
 g3d.getView().addEventListener(ht.Default.isTouchable ? 'touchstart' : 'mousedown', function(e){ 
 if(!anim){
 var p = g3d.getHitPosition(e);
 var x = Math.floor((p[0] + d)/ w);
 var y = Math.floor((p[2] + d)/ w);
 var endBall = dm.getDataByTag("cell_" + x + "_" + y);
 if(endBall && endBall.s('batch') !== 'wall'){ 
 if(startBall.a('x') === x && startBall.a('y') === y){
 return;
 } 
 var g = new Graph(gridRows, { 
 diagonal: formPane.v('diagonal') 
 });
 var start = g.grid[startBall.a('x')][startBall.a('y')];
 var end = g.grid[x][y];
 var result = astar.search(g, start, end, {
 closest: formPane.v('closest') 
 }); 
 if(!result.length){
 return;
 }
 x = result[result.length-1].x;
 y = result[result.length-1].y;
 endBall = dm.getDataByTag("cell_" + x + "_" + y);
 endBall.s('3d.visible', true);
 startBall.s('3d.visible', false);
 formPane.setDisabled(true);
 anim = ht.Default.startAnim({
 duration: 700,
 finishFunc: function(){ 
 for(var i=0; i<result.length; i++){
 var ball = dm.getDataByTag("cell_" + result[i].x + "_" + result[i].y);
 ball.s({
 '3d.visible': false,
 'shape3d.opacity': 1,
 'shape3d.transparent': false
 }); 
 startBall.p3(-d+w*x+w/2, w/2, -d+w*y+w/2);
 startBall.a({x: x, y: y});
 startBall.s('3d.visible', true);
 }
 anim = null;
 formPane.setDisabled(false);
 },
 action: function(v){
 var index = Math.round(v*result.length);
 for(var i=0; i<index; i++){
 var ball = dm.getDataByTag("cell_" + result[i].x + "_" + result[i].y);
 ball.s({
 '3d.visible': true,
 'shape3d.opacity': i/index*0.3 + 0.7,
 'shape3d.transparent': true
 }); 
 }
 }
 }); 
 }
 } 
 }, false); 
 createFormPane();
 createGrid(); 
} 
function createGrid(){
 dm.clear(); 
 var ball;
 gridRows.length = 0;
 for(var x = 0; x < m; x++) {
 var nodeRow = [];
 gridRows.push(nodeRow);
 for(var y = 0; y < m; y++) { 
 var isWall = Math.floor(Math.random()*(1/formPane.v('frequency')));
 if(isWall === 0){
 nodeRow.push(0);
 createNode(x, y).s({
 'batch': 'wall',
 'all.color': '#9CA69D'
 });
 }else{
 nodeRow.push(1);
 ball = createNode(x, y).s({
 'shape3d': 'sphere', 
 'shape3d.color': '#FF703F',
 '3d.visible': false
 });
 } 
 } 
 }
 if(!ball){
 createGrid();
 return;
 } 
 startBall = createNode(ball.a('x'), ball.a('y'), 'start').s({
 'shape3d': 'sphere', 
 'shape3d.color': '#FF703F' 
 }); 
 shape = new ht.Shape();
 shape.setPoints(new ht.List([
 {x: -d, y: d},
 {x: d, y: d},
 {x: d, y: -d},
 {x: -d, y: -d},
 {x: -d, y: d}
 ]));
 shape.setThickness(4);
 shape.setTall(w);
 shape.setElevation(w/2);
 shape.setClosePath(true);
 shape.s({
 'all.color': 'rgba(187, 187, 187, 0.8)', 
 'all.transparent': true, 
 'all.reverse.cull': true
 });
 dm.add(shape); 
}
function createNode(x, y, tag){
 var node = new ht.Node();
 tag = tag || "cell_" + x + "_" + y; 
 node.setTag(tag); 
 node.a({ x: x, y: y });
 node.s3(w*0.9, w*0.9, w*0.9);
 node.p3(-d+w*x+w/2, w/2, -d+w*y+w/2);
 node.s({
 'all.reverse.cull': true,
 'shape3d.reverse.cull': true
 });
 dm.add(node);
 return node;
} 
function createFormPane() { 
 formPane = new ht.widget.FormPane();
 formPane.setWidth(230);
 formPane.setHeight(70);
 formPane.getView().className = 'formpane';
 document.body.appendChild(formPane.getView()); 
 formPane.addRow(['Wall Frequency', {
 id: 'frequency',
 slider: {
 min: 0,
 max: 0.8,
 value: 0.1, 
 onValueChanged: function(){
 createGrid();
 }
 }
 }], [100, 0.1]); 
 formPane.addRow([
 {
 id: 'closest',
 checkBox: {
 label: 'Try Closest'
 }
 },
 {
 id: 'diagonal',
 checkBox: {
 label: 'Allow Diagonal'
 } 
 }
 ], [0.1, 0.1]);
}

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