(window.webpackJsonp=window.webpackJsonp||[]).push([[74],{122:function(e,t,i){"use strict";i.r(t),i.d(t,"frontMatter",(function(){return c})),i.d(t,"metadata",(function(){return o})),i.d(t,"rightToc",(function(){return d})),i.d(t,"default",(function(){return l}));var a=i(2),n=i(6),s=(i(0),i(131)),r=(i(132),i(133),i(134)),c={title:"Pathfinding"},o={unversionedId:"examples/space/pathfinding",id:"examples/space/pathfinding",isDocsHomePage:!1,title:"Pathfinding",description:"- click to interact",source:"@site/docs\\examples\\space\\pathfinding.md",slug:"/examples/space/pathfinding",permalink:"/docs/examples/space/pathfinding",version:"current",sidebar:"docs",previous:{title:"Random distribution",permalink:"/docs/examples/space/random-dist"},next:{title:"Perlin Noise",permalink:"/docs/examples/space/perlin"}},d=[{value:"Breadth-first search",id:"breadth-first-search",children:[]},{value:"Dijkstra",id:"dijkstra",children:[]},{value:"A-Star",id:"a-star",children:[]},{value:"A-Star octile manhattan",id:"a-star-octile-manhattan",children:[]},{value:"A-Star octile euclidean",id:"a-star-octile-euclidean",children:[]},{value:"A-Star with optimistic heuristics",id:"a-star-with-optimistic-heuristics",children:[]},{value:"A-Star with pessimistic heuristics",id:"a-star-with-pessimistic-heuristics",children:[]}],h={rightToc:d};function l(e){var t=e.components,i=Object(n.a)(e,["components"]);return Object(s.b)("wrapper",Object(a.a)({},h,i,{components:t,mdxType:"MDXLayout"}),Object(s.b)("ul",null,Object(s.b)("li",{parentName:"ul"},Object(s.b)("strong",{parentName:"li"},"click to interact")),Object(s.b)("li",{parentName:"ul"},"source: ",Object(s.b)("inlineCode",{parentName:"li"},"examples/src/04-space/pathfinding.ts"))),Object(s.b)("h3",{id:"breadth-first-search"},"Breadth-first search"),Object(s.b)(r.a,{name:"Pathfinding",algorithm:"BREADTH_FIRST",mdxType:"APHCanvas"}),Object(s.b)("h3",{id:"dijkstra"},"Dijkstra"),Object(s.b)(r.a,{name:"Pathfinding",algorithm:"DIJKSTRA",mdxType:"APHCanvas"}),Object(s.b)("h3",{id:"a-star"},"A-Star"),Object(s.b)("ul",null,Object(s.b)("li",{parentName:"ul"},"algorithm:")),Object(s.b)("pre",null,Object(s.b)("code",Object(a.a)({parentName:"pre"},{className:"language-javascript"}),"let f be a priority of a node\nlet g be a cost from the origin to the current node\nlet h be an estimated cost from the current node to the target\nlet n1 be the first node\nlet n2 be the target node\nlet F be a priority queue\n\n1. create queue F\n2. insert n1 into F\n3. until F is empty\n    a) let q be a node of the lowest priority f\n    b) take q from F\n    c) for each neighbour s of q\n        if s = n2, finish\n        \n        let new_cost be q.g + estimation(s, q)\n        if(new_cost >= s.g) goto c)\n        \n        s.g = q.g + estimation(s, q)\n        s.h = estimation(s, n2)\n        \n        s.f = s.g + s.h\n        \n        if there is another node s in the queue F which is of a lower priority than s.f, goto c)\n        \n        put s into F, setting the priority to s.f\n        goto c)\n    end\n    goto 3\n")),Object(s.b)(r.a,{name:"Pathfinding",algorithm:"ASTAR",mdxType:"APHCanvas"}),Object(s.b)("h3",{id:"a-star-octile-manhattan"},"A-Star octile manhattan"),Object(s.b)(r.a,{name:"Pathfinding",mapType:"OCTILE",distanceMeasurement:"MANHATTAN",mdxType:"APHCanvas"}),Object(s.b)("h3",{id:"a-star-octile-euclidean"},"A-Star octile euclidean"),Object(s.b)(r.a,{name:"Pathfinding",mapType:"OCTILE",distanceMeasurement:"EUCLIDEAN",mdxType:"APHCanvas"}),Object(s.b)("h3",{id:"a-star-with-optimistic-heuristics"},"A-Star with optimistic heuristics"),Object(s.b)(r.a,{name:"Pathfinding",mapType:"OCTILE",heuristics:"VERY_OPTIMISTIC",mdxType:"APHCanvas"}),Object(s.b)("h3",{id:"a-star-with-pessimistic-heuristics"},"A-Star with pessimistic heuristics"),Object(s.b)(r.a,{name:"Pathfinding",mapType:"OCTILE",heuristics:"VERY_PESSIMISTIC",mdxType:"APHCanvas"}))}l.isMDXComponent=!0}}]);