212 lines
4.4 KiB
TypeScript
212 lines
4.4 KiB
TypeScript
/**
|
|
* 導航網格類 左上角為原點(0,0)
|
|
* @author BrightLi
|
|
* @since 2020/4/18
|
|
*/
|
|
|
|
import Node from "./Node";
|
|
import AStar from "./AStar"
|
|
|
|
export default class Grid
|
|
{
|
|
private _startNode:Node; //起點
|
|
private _endNode:Node; //終點
|
|
private _nodes:Array<Array<Node>>; //Node數組
|
|
private _width:number; //網格列數
|
|
private _height:number; //網格行數
|
|
private _astar:AStar;
|
|
|
|
// 構造函數
|
|
public constructor(width:number, height:number) {
|
|
this._width = width;
|
|
this._height = height;
|
|
this._nodes = [];
|
|
var x:number,y:number;
|
|
for(x=0;x<width;x++){
|
|
this._nodes[x] = [];
|
|
for(y=0;y<height;y++){
|
|
this._nodes[x][y] = new Node(x,y);
|
|
}
|
|
}
|
|
this._astar=new AStar();
|
|
}
|
|
// 獲得節點
|
|
public getNodeAt(x:number , y:number):Node{
|
|
var result=this._nodes[x][y];
|
|
// result.reset();
|
|
return result;
|
|
}
|
|
// 是否可以行走
|
|
public isWallableAt(x:number,y:number):boolean{
|
|
return this.isInside(x,y) && this._nodes[x][y].walkable;
|
|
}
|
|
// 設置坐標是否可以行走
|
|
public setWalkableAt(x:number, y:number, value:boolean){
|
|
this._nodes[x][y].walkable = value;
|
|
}
|
|
// 設置起點
|
|
public setStartNode(x:number,y:number){
|
|
this._startNode=new Node(x,y);
|
|
}
|
|
// 設置終點
|
|
public setEndNode(x:number,y:number){
|
|
this._endNode=new Node(x,y);
|
|
}
|
|
// 尋路
|
|
public findPath():Array<Node>{
|
|
return this._astar.findPath(this);
|
|
}
|
|
// 網格寬度
|
|
public get width(){
|
|
return this._width;
|
|
}
|
|
// 網格高度
|
|
public get height(){
|
|
return this._height;
|
|
}
|
|
// 獲得起點
|
|
public get startNode(){
|
|
return this._startNode;
|
|
}
|
|
// 獲得終點
|
|
public get endNode(){
|
|
return this._endNode;
|
|
}
|
|
// 坐標點是否在網格內
|
|
public isInside(x:number,y:number):boolean{
|
|
return (x>=0 && x<this._width) && (y>=0 && y<this._height);
|
|
}
|
|
// 相鄰節點 Always:0,Never:1,IfAtMostOneObstancle:2,OnlyWhenNoObstacels:3,
|
|
public getNeighbors(node:Node,diagonallMovement:number):Array<Node>
|
|
{
|
|
var x=node.x,
|
|
y=node.y,
|
|
neighbors=Array<Node>(),
|
|
//上下左右
|
|
s0=false,s1=false,
|
|
s2=false,s3=false,
|
|
//斜方向
|
|
d0=false,d1=false,
|
|
d2=false,d3=false,
|
|
nodes=this._nodes;
|
|
// 上
|
|
if(this.isWallableAt(x,y-1)){
|
|
neighbors.push(nodes[x][y-1]);
|
|
s0=true;
|
|
}
|
|
// 右
|
|
if(this.isWallableAt(x+1,y)){
|
|
neighbors.push(nodes[x+1][y]);
|
|
s1=true;
|
|
}
|
|
// 下
|
|
if(this.isWallableAt(x,y+1)){
|
|
neighbors.push(nodes[x][y+1]);
|
|
s2=true;
|
|
}
|
|
// 左
|
|
if(this.isWallableAt(x-1,y)){
|
|
neighbors.push(nodes[x-1][y]);
|
|
s3=true;
|
|
}
|
|
if(diagonallMovement==1){
|
|
return neighbors;
|
|
}
|
|
if(diagonallMovement==3){
|
|
d0=s3 && s0;
|
|
d1=s0 && s1;
|
|
d2=s1 && s2;
|
|
d3=s2 && s3;
|
|
}else if(diagonallMovement==2){
|
|
d0=s3 || s0;
|
|
d1=s0 || s1;
|
|
d2=s1 || s2;
|
|
d3=s2 || s3;
|
|
}else if(diagonallMovement==0){
|
|
d0=true;
|
|
d1=true;
|
|
d2=true;
|
|
d3=true;
|
|
}
|
|
// 左上
|
|
if(d0 && this.isWallableAt(x-1,y-1)){
|
|
neighbors.push(nodes[x-1][y-1]);
|
|
}
|
|
// 右上
|
|
if(d1 && this.isWallableAt(x+1,y-1)){
|
|
neighbors.push(nodes[x+1][y+1]);
|
|
}
|
|
// 右下
|
|
if(d2 && this.isWallableAt(x+1,y+1)){
|
|
neighbors.push(nodes[x+1][y+1]);
|
|
}
|
|
// 左下
|
|
if(d2 && this.isWallableAt(x-1,y+1)){
|
|
neighbors.push(nodes[x-1][y+1]);
|
|
}
|
|
return neighbors;
|
|
}
|
|
// 圓滑路徑
|
|
public smoothenPath(path:Array<Node>){
|
|
var len=path.length,
|
|
x0=path[0].x,
|
|
y0=path[0].y,
|
|
x1=path[path.length-1].x,
|
|
y1=path[path.length-1].y,
|
|
sx:number,sy:number,
|
|
ex:number,ey:number,
|
|
newPath:Array<Node>,
|
|
i:number,j:number,coord:Node,line:Array<Node>,testCoord:Node,blocked:boolean;
|
|
sx=x0;
|
|
sy=y0;
|
|
newPath=[new Node(sx,sy)];
|
|
for(i=2;i<path.length;++i){
|
|
coord=path[i];
|
|
ex=coord.x;
|
|
ey=coord.y;
|
|
line=this.interpolate(sx,sy,ex,ey);
|
|
blocked=false;
|
|
for(j=1;j<line.length;++j){
|
|
testCoord=line[j];
|
|
if(!this.isWallableAt(testCoord.x,testCoord.y)){
|
|
blocked=true;
|
|
break;
|
|
}
|
|
}
|
|
if(blocked){
|
|
var lastValidCoord=path[i-1];
|
|
newPath.push(lastValidCoord);
|
|
sx=lastValidCoord.x;
|
|
sy=lastValidCoord.y;
|
|
}
|
|
}
|
|
newPath.push(new Node(x1,y1));
|
|
return newPath;
|
|
}
|
|
|
|
private interpolate(x0:number,y0:number,x1:number,y1:number){
|
|
var line:Array<Node>=[],
|
|
sx:number,sy:number,dx:number,dy:number,err:number,e2:number;
|
|
dx=Math.abs(x1-x0);
|
|
dy=Math.abs(y1-y0);
|
|
sx=(x0<x1) ?1:-1;
|
|
sy=(y0<y1) ?1:-1;
|
|
err=dx-dy;
|
|
while(true){
|
|
line.push(new Node(x0,y0));
|
|
if(x0==x1 && y0==y1){
|
|
break;
|
|
}
|
|
e2=2*err;
|
|
if(e2>-dy){
|
|
err=err-dy;
|
|
x0=x0+sx;
|
|
}
|
|
if(e2<dx){
|
|
err=err+dx;
|
|
y0=y0+sy;
|
|
}
|
|
}
|
|
return line;
|
|
}
|
|
} |