Skip to content

Instantly share code, notes, and snippets.

@manthrax
Created June 27, 2022 01:09
Show Gist options
  • Save manthrax/44a94e21f7227eb504d14ff1faf8d1b5 to your computer and use it in GitHub Desktop.
Save manthrax/44a94e21f7227eb504d14ff1faf8d1b5 to your computer and use it in GitHub Desktop.
let binsert = (items,item)=>{
let low = 0;
let high = items.length;
while (low < high) {
const mid = (low + high) >> 1;
((item.cost - items[mid].cost) > 0) ? (high = mid) : (low = mid + 1);
}
items.splice(low, 0, item);
}
let {min, max, abs, sqrt,random} = Math;
export class MStar {
constructor({nodes, edges}) {
let npush = (n,nb)=>(nodes[n].n || (nodes[n].n = [])).push(nb)
edges.forEach(e=>npush(e.a, e.b) | npush(e.b, e.a))
let ndist = (a,b)=>{
let na = nodes[a];
let nb = nodes[b];
return ((nb.x - na.x)**2)+((nb.y - na.y)**2);
//return sqrt((nb.x - na.x)**2)+((nb.y - na.y)**2);
//let sd = abs(nb.x - na.x)+abs(nb.y - na.y);
}
this.search = (start,end)=>{
let pq = []
return {
pqueue: [],
visited: {},
start,
end,
progress:true,
frustration:0,
step() {
let v = this.visited;
let q = this.pqueue;
if (!q.length)
binsert(q, {
s: -1,
i: start,
cost: ndist(start, end)
})
let p = this.pqueue.pop();
this.progress = (this.p && (this.p.i==p.s))?true:false;
(this.progress&&(this.frustration=0))||(this.frustration++);
this.p=p;
if (p.i == end)
return p;
let n = nodes[p.i]
//console.log(n);
let g,h;
n.n&&n.n.forEach(nbi=>(!v[nbi]) && (!nodes[nbi].blocked) && binsert(q, v[nbi]={
sp:p,
s: p.i,
i: nbi,
g:g=ndist(p.i,nbi)+(p.g||0),
h:h=ndist(nbi,end),
cost:g+h
}))
v[p.i] = p;
if((!this.pqueue.length)||nodes[start].blocked||nodes[end].blocked)return v[start];
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment