最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于写了个A*算法的WebGL 3D呈现,算法基于开源 的javascript实现,其实作者也有个不错的2D例子实现 ,只不过觉得所有A*算法的可视化实现都是平面的不够酷,另外还有不少参数需要调节控制,还是值得好好搞个全面的Demo,先上张2D和3D例子的对照图。
实现代码比较容易一百多行,不过算法核心在astar.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系统下呈现和算法都挺流畅,,当然这个小例子数据量也不大,本质其实还是2D的最短路径算法,并非真正意义的3D空间最短路径,但还是足够解决很多实际应用问题了。
阅读(2611) | 评论(0) | 转发(0) |