pathfind.js

"use strict";{function a(a,b){return a*c+b}function b(a){let b=d.get(a);return b||(b=new g,d.set(a,b)),b}const c=67108864,d=new Map;self.JobHandlers["PFCellData"]=function(a){const c=a["mapKey"],d=a["hcells"],e=a["vcells"],f=a["cellData"],g=a["diagonals"],h=b(c);h.Init(d,e,f,g)},self.JobHandlers["PFUpdateRegion"]=function(a){const c=a["mapKey"],d=a["cx1"],e=a["cy1"],f=a["lenx"],g=a["leny"],h=a["cellData"],i=b(c);i.UpdateRegion(d,e,f,g,h)},self.JobHandlers["PFSetDiagonals"]=function(a){const c=a["mapKey"],d=a["diagonals"],e=b(c);e.SetDiagonalsEnabled(d)},self.JobHandlers["PFResetAllCellData"]=function(){for(const a of d.values())a.Clear()},self.JobHandlers["PFFindPath"]=function(a){const c=a["mapKey"],d=a["cellX"],e=a["cellY"],f=a["destCellX"],g=a["destCellY"],h=b(c),i=performance.now(),j=h.FindPath(d,e,f,g);return{result:j}};let e=0;class f{constructor(a,b){this._parent=null,this._x=a||0,this._y=b||0,this._f=0,this._g=0,this._h=0,this._seq=e++}SetXY(a,b){this._x=a,this._y=b}DirectionTo(a){const b=this._x,c=this._y,d=a._x,e=a._y;if(b===d){if(e>c)return 6;if(e<c)return 2;if(c===e)return 8}else if(c===e){if(d>b)return 4;if(e<b)return 0}else{if(d<b&&e<c)return 1;if(d>b&&e<c)return 3;if(d<b&&e>c)return 7;if(d>b&&e>c)return 5}return 8}static Sort(c,a){const b=c._f,d=a._f;return b===d?c._seq-a._seq:b-d}}class g{constructor(){this._hcells=0,this._vcells=0,this._cells=null,this._openList=new RedBlackSet(f.Sort),this._openMap=new Map,this._closedSet=new Set,this._currentNode=null,this._targetX=0,this._targetY=0,this._diagonalsEnabled=!0}Init(a,b,c,d){this._hcells=a,this._vcells=b,this._cells=c,this._diagonalsEnabled=!!d}UpdateRegion(a,b,c,d,e){const f=this._cells;if(f)for(let d=0;d<c;++d)f[a+d].set(e[d],b)}Clear(){this._cells=null}_ClearIntermediateData(){this._openList.Clear(),this._openMap.clear(),this._closedSet.clear(),this._currentNode=null,e=0}UpdateRegion(a,b,c,d,e){for(let f=0;f<c;++f)for(let c=0;c<d;++c)this._cells[a+f][b+c]=e[f][c]}SetDiagonalsEnabled(a){this._diagonalsEnabled=!!a}At(a,b){return 0>a||0>b||a>=this._hcells||b>=this._vcells?67108863:this._cells[a][b]}FindPath(a,b,c,d){var e=Math.max,f=Math.min,g=Math.floor;if(!this._cells)return null;a=g(a),b=g(b),c=g(c),d=g(d),this._targetX=c,this._targetY=d;const h=f(a,c),i=e(a,c),j=f(b,d),k=e(b,d);if(0>h||0>j||i>=this._hcells||k>=this._vcells)return null;if(this._diagonalsEnabled){let a=!0;for(let b=h;b<=i;++b)for(let c=j;c<=k;++c)if(0!==this._cells[b][c]){a=!1,b=i+1;break}if(a)return[{x:c,y:d}]}return this._AStarFindPath(a,b)}_AStarFindPath(b,c){const d=this._diagonalsEnabled,e=this._openList,g=this._openMap,h=this._closedSet,i=new f(b,c);for(e.Add(i),g.set(a(b,c),i);!e.IsEmpty();){const b=e.Shift(),c=a(b._x,b._y);if(g.delete(c),h.add(c),b._x===this._targetX&&b._y===this._targetY)return this._ClearIntermediateData(),this._GetResultPath(b);this._currentNode=b;const f=b._x,i=b._y,j=67108863===this.At(f-1,i),k=67108863===this.At(f,i-1),l=67108863===this.At(f+1,i),m=67108863===this.At(f,i+1);j||this._AddCellToOpenList(f-1,i,10),!d||j||k||67108863===this.At(f-1,i-1)||this._AddCellToOpenList(f-1,i-1,14),k||this._AddCellToOpenList(f,i-1,10),!d||k||l||67108863===this.At(f+1,i-1)||this._AddCellToOpenList(f+1,i-1,14),l||this._AddCellToOpenList(f+1,i,10),!d||l||m||67108863===this.At(f+1,i+1)||this._AddCellToOpenList(f+1,i+1,14),m||this._AddCellToOpenList(f,i+1,10),!d||m||j||67108863===this.At(f-1,i+1)||this._AddCellToOpenList(f-1,i+1,14)}return this._ClearIntermediateData(),null}_AddCellToOpenList(b,d,e){const f=a(b,d);if(!this._closedSet.has(f)){const a=this.At(b,d),g=this._openMap.get(f);return g?void(this._currentNode._g+e+a<g._g&&this._UpdateNodeInOpenList(g,e,a)):void this._AddNewNodeToOpenList(b,d,e,a)}}_UpdateNodeInOpenList(a,b,c){const d=this._openList,e=this._currentNode;d.Remove(a),a._parent=e,a._g=e._g+b+c,a._h=this._EstimateH(a._x,a._y),a._f=a._g+a._h,d.Add(a)}_AddNewNodeToOpenList(b,d,e,g){const i=new f(b,d),c=this._EstimateH(b,d),h=this._currentNode._g+e+g;i._h=c,i._g=h,i._f=c+h,i._parent=this._currentNode,this._openMap.set(a(b,d),i),this._openList.Add(i)}_EstimateH(a,b){var c=Math.abs;const d=c(a-this._targetX),e=c(b-this._targetY);return 10*d+10*e}_GetResultPath(a){const b=[];for(let c=!1,d=8,e=-1,f=a;f;)0===b.length?(c=!0,f._parent&&(d=f.DirectionTo(f._parent),e=d)):f._parent?(e=f.DirectionTo(f._parent),c=e!==d):c=!1,c&&(b.push({x:f._x,y:f._y}),d=e),f=f._parent;return b.reverse()}}}