{"version":3,"sources":["jsdelivr-header.js","/npm/pathfinding@0.4.18/src/core/Node.js","/npm/pathfinding@0.4.18/src/core/DiagonalMovement.js","/npm/pathfinding@0.4.18/src/core/Grid.js","/npm/pathfinding@0.4.18/src/core/Util.js","/npm/pathfinding@0.4.18/src/core/Heuristic.js","/npm/pathfinding@0.4.18/src/finders/AStarFinder.js","/npm/pathfinding@0.4.18/src/finders/BestFirstFinder.js","/npm/pathfinding@0.4.18/src/finders/BreadthFirstFinder.js","/npm/pathfinding@0.4.18/src/finders/DijkstraFinder.js","/npm/pathfinding@0.4.18/src/finders/BiAStarFinder.js","/npm/pathfinding@0.4.18/src/finders/BiBestFirstFinder.js","/npm/pathfinding@0.4.18/src/finders/BiBreadthFirstFinder.js","/npm/pathfinding@0.4.18/src/finders/BiDijkstraFinder.js","/npm/pathfinding@0.4.18/src/finders/IDAStarFinder.js","/npm/pathfinding@0.4.18/src/finders/JumpPointFinderBase.js","/npm/pathfinding@0.4.18/src/finders/JPFNeverMoveDiagonally.js","/npm/pathfinding@0.4.18/src/finders/JPFAlwaysMoveDiagonally.js","/npm/pathfinding@0.4.18/src/finders/JPFMoveDiagonallyIfNoObstacles.js","/npm/pathfinding@0.4.18/src/finders/JPFMoveDiagonallyIfAtMostOneObstacle.js","/npm/pathfinding@0.4.18/src/finders/JumpPointFinder.js","/npm/pathfinding@0.4.18/src/PathFinding.js","/npm/pathfinding@0.4.18/index.js"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,kLCGA,SAAS,EAAK,EAAG,EAAG,EAAU,CAK1B,KAAK,EAAI,EAKT,KAAK,EAAI,EAKT,KAAK,SAAY,IAAa,OAAY,GAAO,CACrD,CAEA,OAAA,EAAiB,8CC3BjB,IAAI,EAAmB,CACnB,OAAQ,EACR,MAAO,EACP,oBAAqB,EACrB,oBAAqB,CACzB,EAEA,OAAA,EAAiB,+CCPjB,IAAI,EAAO,EAAA,EACP,EAAmB,EAAA,EAUvB,SAAS,EAAK,EAAiB,EAAQ,EAAQ,CAC3C,IAAI,EAEA,OAAO,GAAoB,SAC3B,EAAQ,GAER,EAAS,EAAgB,OACzB,EAAQ,EAAgB,CAAC,EAAE,OAC3B,EAAS,GAOb,KAAK,MAAQ,EAKb,KAAK,OAAS,EAKd,KAAK,MAAQ,KAAK,YAAY,EAAO,EAAQ,CAAM,CACvD,CAWA,OAAA,EAAK,UAAU,YAAc,SAAS,EAAO,EAAQ,EAAQ,CACzD,IAAI,EAAG,EACH,EAAQ,IAAI,MAAM,CAAM,EAE5B,IAAK,EAAI,EAAG,EAAI,EAAQ,EAAE,EAEtB,IADA,EAAM,CAAC,EAAI,IAAI,MAAM,CAAK,EACrB,EAAI,EAAG,EAAI,EAAO,EAAE,EACrB,EAAM,CAAC,EAAE,CAAC,EAAI,IAAI,EAAK,EAAG,CAAC,EAKnC,GAAI,IAAW,OACX,OAAO,EAGX,GAAI,EAAO,SAAW,GAAU,EAAO,CAAC,EAAE,SAAW,EACjD,MAAM,IAAI,MAAM,0BAA0B,EAG9C,IAAK,EAAI,EAAG,EAAI,EAAQ,EAAE,EACtB,IAAK,EAAI,EAAG,EAAI,EAAO,EAAE,EACjB,EAAO,CAAC,EAAE,CAAC,IAGX,EAAM,CAAC,EAAE,CAAC,EAAE,SAAW,IAKnC,OAAO,CACX,EAGA,EAAK,UAAU,UAAY,SAAS,EAAG,EAAG,CACtC,OAAO,KAAK,MAAM,CAAC,EAAE,CAAC,CAC1B,EAUA,EAAK,UAAU,aAAe,SAAS,EAAG,EAAG,CACzC,OAAO,KAAK,SAAS,EAAG,CAAC,GAAK,KAAK,MAAM,CAAC,EAAE,CAAC,EAAE,QACnD,EAYA,EAAK,UAAU,SAAW,SAAS,EAAG,EAAG,CACrC,OAAQ,GAAK,GAAK,EAAI,KAAK,OAAW,GAAK,GAAK,EAAI,KAAK,MAC7D,EAUA,EAAK,UAAU,cAAgB,SAAS,EAAG,EAAG,EAAU,CACpD,KAAK,MAAM,CAAC,EAAE,CAAC,EAAE,SAAW,CAChC,EAqBA,EAAK,UAAU,aAAe,SAAS,EAAM,EAAkB,CAC3D,IAAI,EAAI,EAAK,EACT,EAAI,EAAK,EACT,EAAY,CAAA,EACZ,EAAK,GAAO,EAAK,GACjB,EAAK,GAAO,EAAK,GACjB,EAAK,GAAO,EAAK,GACjB,EAAK,GAAO,EAAK,GACjB,EAAQ,KAAK,MAuBjB,GApBI,KAAK,aAAa,EAAG,EAAI,CAAC,IAC1B,EAAU,KAAK,EAAM,EAAI,CAAC,EAAE,CAAC,CAAC,EAC9B,EAAK,IAGL,KAAK,aAAa,EAAI,EAAG,CAAC,IAC1B,EAAU,KAAK,EAAM,CAAC,EAAE,EAAI,CAAC,CAAC,EAC9B,EAAK,IAGL,KAAK,aAAa,EAAG,EAAI,CAAC,IAC1B,EAAU,KAAK,EAAM,EAAI,CAAC,EAAE,CAAC,CAAC,EAC9B,EAAK,IAGL,KAAK,aAAa,EAAI,EAAG,CAAC,IAC1B,EAAU,KAAK,EAAM,CAAC,EAAE,EAAI,CAAC,CAAC,EAC9B,EAAK,IAGL,IAAqB,EAAiB,MACtC,OAAO,EAGX,GAAI,IAAqB,EAAiB,oBACtC,EAAK,GAAM,EACX,EAAK,GAAM,EACX,EAAK,GAAM,EACX,EAAK,GAAM,UACJ,IAAqB,EAAiB,oBAC7C,EAAK,GAAM,EACX,EAAK,GAAM,EACX,EAAK,GAAM,EACX,EAAK,GAAM,UACJ,IAAqB,EAAiB,OAC7C,EAAK,GACL,EAAK,GACL,EAAK,GACL,EAAK,OAEL,OAAM,IAAI,MAAM,qCAAqC,EAIzD,OAAI,GAAM,KAAK,aAAa,EAAI,EAAG,EAAI,CAAC,GACpC,EAAU,KAAK,EAAM,EAAI,CAAC,EAAE,EAAI,CAAC,CAAC,EAGlC,GAAM,KAAK,aAAa,EAAI,EAAG,EAAI,CAAC,GACpC,EAAU,KAAK,EAAM,EAAI,CAAC,EAAE,EAAI,CAAC,CAAC,EAGlC,GAAM,KAAK,aAAa,EAAI,EAAG,EAAI,CAAC,GACpC,EAAU,KAAK,EAAM,EAAI,CAAC,EAAE,EAAI,CAAC,CAAC,EAGlC,GAAM,KAAK,aAAa,EAAI,EAAG,EAAI,CAAC,GACpC,EAAU,KAAK,EAAM,EAAI,CAAC,EAAE,EAAI,CAAC,CAAC,EAG/B,CACX,EAOA,EAAK,UAAU,MAAQ,UAAW,CAC9B,IAAI,EAAG,EAEH,EAAQ,KAAK,MACb,EAAS,KAAK,OACd,EAAY,KAAK,MAEjB,EAAU,IAAI,EAAK,EAAO,CAAM,EAChC,EAAW,IAAI,MAAM,CAAM,EAE/B,IAAK,EAAI,EAAG,EAAI,EAAQ,EAAE,EAEtB,IADA,EAAS,CAAC,EAAI,IAAI,MAAM,CAAK,EACxB,EAAI,EAAG,EAAI,EAAO,EAAE,EACrB,EAAS,CAAC,EAAE,CAAC,EAAI,IAAI,EAAK,EAAG,EAAG,EAAU,CAAC,EAAE,CAAC,EAAE,QAAQ,EAIhE,OAAA,EAAQ,MAAQ,EAET,CACX,EAEA,EAAiB,iDC9OjB,SAAS,EAAU,EAAM,CAErB,QADI,EAAO,CAAC,CAAC,EAAK,EAAG,EAAK,CAAC,CAAC,EACrB,EAAK,QACR,EAAO,EAAK,OACZ,EAAK,KAAK,CAAC,EAAK,EAAG,EAAK,CAAC,CAAC,EAE9B,OAAO,EAAK,QAAO,CACvB,CACA,EAAA,UAAoB,EAQpB,SAAS,EAAY,EAAO,EAAO,CAC/B,IAAI,EAAQ,EAAU,CAAK,EACvB,EAAQ,EAAU,CAAK,EAC3B,OAAO,EAAM,OAAO,EAAM,QAAO,CAAE,CACvC,CACA,EAAA,YAAsB,EAOtB,SAAS,EAAW,EAAM,CACtB,IAAI,EAAG,EAAM,EAAG,EAAG,EAAG,EAAI,EAC1B,IAAK,EAAI,EAAG,EAAI,EAAK,OAAQ,EAAE,EAC3B,EAAI,EAAK,EAAI,CAAC,EACd,EAAI,EAAK,CAAC,EACV,EAAK,EAAE,CAAC,EAAI,EAAE,CAAC,EACf,EAAK,EAAE,CAAC,EAAI,EAAE,CAAC,EACf,GAAO,KAAK,KAAK,EAAK,EAAK,EAAK,CAAE,EAEtC,OAAO,CACX,CACA,EAAA,WAAqB,EAarB,SAAS,EAAY,EAAI,EAAI,EAAI,EAAI,CACjC,IAAI,EAAM,KAAK,IACX,EAAO,CAAA,EACP,EAAI,EAAI,EAAI,EAAI,EAAK,EAUzB,IARA,EAAK,EAAI,EAAK,CAAE,EAChB,EAAK,EAAI,EAAK,CAAE,EAEhB,EAAM,EAAK,EAAM,EAAI,GACrB,EAAM,EAAK,EAAM,EAAI,GAErB,EAAM,EAAK,EAGP,EAAK,KAAK,CAAC,EAAI,CAAE,CAAC,EAEd,EAAA,IAAO,GAAM,IAAO,IAIxB,EAAK,EAAI,EACL,EAAK,CAAC,IACN,EAAM,EAAM,EACZ,EAAK,EAAK,GAEV,EAAK,IACL,EAAM,EAAM,EACZ,EAAK,EAAK,GAIlB,OAAO,CACX,CACA,EAAA,YAAsB,EAStB,SAAS,EAAW,EAAM,CACtB,IAAI,EAAW,CAAA,EACX,EAAM,EAAK,OACX,EAAQ,EACR,EACA,EACA,EAAG,EAEP,GAAI,EAAM,EACN,OAAO,EAGX,IAAK,EAAI,EAAG,EAAI,EAAM,EAAG,EAAE,EAMvB,IALA,EAAS,EAAK,CAAC,EACf,EAAS,EAAK,EAAI,CAAC,EAEnB,EAAe,EAAY,EAAO,CAAC,EAAG,EAAO,CAAC,EAAG,EAAO,CAAC,EAAG,EAAO,CAAC,CAAC,EACrE,EAAkB,EAAa,OAC1B,EAAI,EAAG,EAAI,EAAkB,EAAG,EAAE,EACnC,EAAS,KAAK,EAAa,CAAC,CAAC,EAGrC,OAAA,EAAS,KAAK,EAAK,EAAM,CAAC,CAAC,EAEpB,CACX,CACA,EAAA,WAAqB,EASrB,SAAS,EAAa,EAAM,EAAM,CAC9B,IAAI,EAAM,EAAK,OACX,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,EAAM,CAAC,EAAE,CAAC,EACpB,EAAK,EAAK,EAAM,CAAC,EAAE,CAAC,EACpB,EAAI,EACJ,EAAI,EACJ,EACA,EAAG,EAAG,EAAO,EAAM,EAAW,EAMlC,IAJA,EAAK,EACL,EAAK,EACL,EAAU,CAAC,CAAC,EAAI,CAAE,CAAC,EAEd,EAAI,EAAG,EAAI,EAAK,EAAE,EAAG,CAOtB,IANA,EAAQ,EAAK,CAAC,EACd,EAAK,EAAM,CAAC,EACZ,EAAK,EAAM,CAAC,EACZ,EAAO,EAAY,EAAI,EAAI,EAAI,CAAE,EAEjC,EAAU,GACL,EAAI,EAAG,EAAI,EAAK,OAAQ,EAAE,EAG3B,GAFA,EAAY,EAAK,CAAC,EAEd,CAAC,EAAK,aAAa,EAAU,CAAC,EAAG,EAAU,CAAC,CAAC,EAAG,CAChD,EAAU,GACV,KAChB,CAEY,IACA,eAAiB,EAAK,EAAI,CAAC,EAC3B,EAAQ,KAAK,cAAc,EAC3B,EAAK,eAAe,CAAC,EACrB,EAAK,eAAe,CAAC,EAEjC,CACI,OAAA,EAAQ,KAAK,CAAC,EAAI,CAAE,CAAC,EAEd,CACX,CACA,EAAA,aAAuB,EASvB,SAAS,EAAa,EAAM,CAGxB,GAAG,EAAK,OAAS,EACb,OAAO,EAGX,IAAI,EAAa,CAAA,EACb,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAI,EACJ,EAAK,EACL,EAAI,EAUR,IAPA,EAAK,KAAK,KAAK,EAAG,EAAK,EAAG,CAAE,EAC5B,GAAM,EACN,GAAM,EAGN,EAAW,KAAK,CAAC,EAAG,CAAE,CAAC,EAEnB,EAAI,EAAG,EAAI,EAAK,OAAQ,IAGxB,EAAK,EACL,EAAK,EAGL,EAAM,EACN,EAAM,EAGN,EAAK,EAAK,CAAC,EAAE,CAAC,EACd,EAAK,EAAK,CAAC,EAAE,CAAC,EAGd,EAAK,EAAK,EACV,EAAK,EAAK,EAGV,EAAK,KAAK,KAAK,EAAG,EAAK,EAAG,CAAE,EAC5B,GAAM,EACN,GAAM,GAGD,IAAO,GAAO,IAAO,IACtB,EAAW,KAAK,CAAC,EAAG,CAAE,CAAC,EAK/B,OAAA,EAAW,KAAK,CAAC,EAAG,CAAE,CAAC,EAEhB,CACX,CACA,OAAA,EAAA,aAAuB,2CCjPvB,EAAiB,CAQf,UAAW,SAAS,EAAI,EAAI,CACxB,OAAO,EAAK,CAClB,EAQE,UAAW,SAAS,EAAI,EAAI,CACxB,OAAO,KAAK,KAAK,EAAK,EAAK,EAAK,CAAE,CACxC,EAQE,OAAQ,SAAS,EAAI,EAAI,CACrB,IAAI,EAAI,KAAK,MAAQ,EACrB,OAAQ,EAAK,EAAM,EAAI,EAAK,EAAK,EAAI,EAAK,CAChD,EAQE,UAAW,SAAS,EAAI,EAAI,CACxB,OAAO,KAAK,IAAI,EAAI,CAAE,CAC5B,gDC7CA,IAAI,EAAa,EACb,EAAa,EAAA,EACb,EAAa,EAAA,EACb,EAAmB,EAAA,EAgBvB,SAAS,EAAY,EAAK,CACtB,EAAM,GAAO,CAAA,EACb,KAAK,cAAgB,EAAI,cACzB,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,UAAY,EAAI,WAAa,EAAU,UAC5C,KAAK,OAAS,EAAI,QAAU,EAC5B,KAAK,iBAAmB,EAAI,iBAEvB,KAAK,mBACD,KAAK,cAGF,KAAK,iBACL,KAAK,iBAAmB,EAAiB,oBAEzC,KAAK,iBAAmB,EAAiB,oBAL7C,KAAK,iBAAmB,EAAiB,OAY7C,KAAK,mBAAqB,EAAiB,MAC3C,KAAK,UAAY,EAAI,WAAa,EAAU,UAE5C,KAAK,UAAY,EAAI,WAAa,EAAU,MAEpD,CAOA,OAAA,EAAY,UAAU,SAAW,SAAS,EAAQ,EAAQ,EAAM,EAAM,EAAM,CACxE,IAAI,EAAW,IAAI,EAAK,SAAS,EAAO,EAAO,CACvC,OAAO,EAAM,EAAI,EAAM,CACnC,CAAS,EACD,EAAY,EAAK,UAAU,EAAQ,CAAM,EACzC,EAAU,EAAK,UAAU,EAAM,CAAI,EACnC,EAAY,KAAK,UACjB,EAAmB,KAAK,iBACxB,EAAS,KAAK,OACd,EAAM,KAAK,IAAK,EAAQ,KAAK,MAC7B,EAAM,EAAW,EAAU,EAAG,EAAG,EAAG,EAAG,EAW3C,IARA,EAAU,EAAI,EACd,EAAU,EAAI,EAGd,EAAS,KAAK,CAAS,EACvB,EAAU,OAAS,GAGZ,CAAC,EAAS,MAAK,GAAI,CAMtB,GAJA,EAAO,EAAS,IAAG,EACnB,EAAK,OAAS,GAGV,IAAS,EACT,OAAO,EAAK,UAAU,CAAO,EAKjC,IADA,EAAY,EAAK,aAAa,EAAM,CAAgB,EAC/C,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EACvC,EAAW,EAAU,CAAC,EAElB,CAAA,EAAS,SAIb,EAAI,EAAS,EACb,EAAI,EAAS,EAIb,EAAK,EAAK,GAAM,EAAI,EAAK,IAAM,GAAK,EAAI,EAAK,IAAM,EAAK,EAAI,IAIxD,CAAC,EAAS,QAAU,EAAK,EAAS,KAClC,EAAS,EAAI,EACb,EAAS,EAAI,EAAS,GAAK,EAAS,EAAU,EAAI,EAAI,CAAI,EAAG,EAAI,EAAI,CAAI,CAAC,EAC1E,EAAS,EAAI,EAAS,EAAI,EAAS,EACnC,EAAS,OAAS,EAEb,EAAS,OAOV,EAAS,WAAW,CAAQ,GAN5B,EAAS,KAAK,CAAQ,EACtB,EAAS,OAAS,KAStC,CAGI,MAAO,CAAA,CACX,EAEA,EAAiB,+CC7HjB,IAAI,EAAc,EAAA,EAelB,SAAS,EAAgB,EAAK,CAC1B,EAAY,KAAK,KAAM,CAAG,EAE1B,IAAI,EAAO,KAAK,UAChB,KAAK,UAAY,SAAS,EAAI,EAAI,CAC9B,OAAO,EAAK,EAAI,CAAE,EAAI,GAC9B,CACA,CAEA,OAAA,EAAgB,UAAY,IAAI,EAChC,EAAgB,UAAU,YAAc,EAExC,EAAiB,+CC3BjB,IAAI,EAAO,EAAA,EACP,EAAmB,EAAA,EAYvB,SAAS,EAAmB,EAAK,CAC7B,EAAM,GAAO,CAAA,EACb,KAAK,cAAgB,EAAI,cACzB,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,iBAAmB,EAAI,iBAEvB,KAAK,mBACD,KAAK,cAGF,KAAK,iBACL,KAAK,iBAAmB,EAAiB,oBAEzC,KAAK,iBAAmB,EAAiB,oBAL7C,KAAK,iBAAmB,EAAiB,MASrD,CAOA,OAAA,EAAmB,UAAU,SAAW,SAAS,EAAQ,EAAQ,EAAM,EAAM,EAAM,CAC/E,IAAI,EAAW,CAAA,EACX,EAAmB,KAAK,iBACxB,EAAY,EAAK,UAAU,EAAQ,CAAM,EACzC,EAAU,EAAK,UAAU,EAAM,CAAI,EACnC,EAAW,EAAU,EAAM,EAAG,EAOlC,IAJA,EAAS,KAAK,CAAS,EACvB,EAAU,OAAS,GAGZ,EAAS,QAAQ,CAMpB,GAJA,EAAO,EAAS,MAAK,EACrB,EAAK,OAAS,GAGV,IAAS,EACT,OAAO,EAAK,UAAU,CAAO,EAIjC,IADA,EAAY,EAAK,aAAa,EAAM,CAAgB,EAC/C,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EACvC,EAAW,EAAU,CAAC,EAGlB,EAAA,EAAS,QAAU,EAAS,UAIhC,EAAS,KAAK,CAAQ,EACtB,EAAS,OAAS,GAClB,EAAS,OAAS,EAE9B,CAGI,MAAO,CAAA,CACX,EAEA,EAAiB,+CC9EjB,IAAI,EAAc,EAAA,EAalB,SAAS,EAAe,EAAK,CACzB,EAAY,KAAK,KAAM,CAAG,EAC1B,KAAK,UAAY,SAAS,EAAI,EAAI,CAC9B,MAAO,EACf,CACA,CAEA,OAAA,EAAe,UAAY,IAAI,EAC/B,EAAe,UAAU,YAAc,EAEvC,EAAiB,8CCvBjB,IAAI,EAAa,EACb,EAAa,EAAA,EACb,EAAa,EAAA,EACb,EAAmB,EAAA,EAiBvB,SAAS,EAAc,EAAK,CACxB,EAAM,GAAO,CAAA,EACb,KAAK,cAAgB,EAAI,cACzB,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,UAAY,EAAI,WAAa,EAAU,UAC5C,KAAK,OAAS,EAAI,QAAU,EAEvB,KAAK,mBACD,KAAK,cAGF,KAAK,iBACL,KAAK,iBAAmB,EAAiB,oBAEzC,KAAK,iBAAmB,EAAiB,oBAL7C,KAAK,iBAAmB,EAAiB,OAY7C,KAAK,mBAAqB,EAAiB,MAC3C,KAAK,UAAY,EAAI,WAAa,EAAU,UAE5C,KAAK,UAAY,EAAI,WAAa,EAAU,MAEpD,CAOA,OAAA,EAAc,UAAU,SAAW,SAAS,EAAQ,EAAQ,EAAM,EAAM,EAAM,CAC1E,IAAI,EAAM,SAAS,GAAO,GAAO,CACzB,OAAO,GAAM,EAAI,GAAM,CACnC,EACQ,EAAgB,IAAI,EAAK,CAAG,EAC5B,EAAc,IAAI,EAAK,CAAG,EAC1B,EAAY,EAAK,UAAU,EAAQ,CAAM,EACzC,EAAU,EAAK,UAAU,EAAM,CAAI,EACnC,EAAY,KAAK,UACjB,EAAmB,KAAK,iBACxB,EAAS,KAAK,OACd,EAAM,KAAK,IAAK,EAAQ,KAAK,MAC7B,EAAM,EAAW,EAAU,EAAG,EAAG,EAAG,EAAG,EACvC,EAAW,EAAG,EAAS,EAiB3B,IAbA,EAAU,EAAI,EACd,EAAU,EAAI,EACd,EAAc,KAAK,CAAS,EAC5B,EAAU,OAAS,EAInB,EAAQ,EAAI,EACZ,EAAQ,EAAI,EACZ,EAAY,KAAK,CAAO,EACxB,EAAQ,OAAS,EAGV,CAAC,EAAc,MAAK,GAAM,CAAC,EAAY,MAAK,GAAI,CAQnD,IALA,EAAO,EAAc,IAAG,EACxB,EAAK,OAAS,GAGd,EAAY,EAAK,aAAa,EAAM,CAAgB,EAC/C,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EAGvC,GAFA,EAAW,EAAU,CAAC,EAElB,CAAA,EAAS,OAGb,IAAI,EAAS,SAAW,EACpB,OAAO,EAAK,YAAY,EAAM,CAAQ,EAG1C,EAAI,EAAS,EACb,EAAI,EAAS,EAIb,EAAK,EAAK,GAAM,EAAI,EAAK,IAAM,GAAK,EAAI,EAAK,IAAM,EAAK,EAAI,IAIxD,CAAC,EAAS,QAAU,EAAK,EAAS,KAClC,EAAS,EAAI,EACb,EAAS,EAAI,EAAS,GAClB,EAAS,EAAU,EAAI,EAAI,CAAI,EAAG,EAAI,EAAI,CAAI,CAAC,EACnD,EAAS,EAAI,EAAS,EAAI,EAAS,EACnC,EAAS,OAAS,EAEb,EAAS,OAOV,EAAc,WAAW,CAAQ,GANjC,EAAc,KAAK,CAAQ,EAC3B,EAAS,OAAS,IAiB9B,IALA,EAAO,EAAY,IAAG,EACtB,EAAK,OAAS,GAGd,EAAY,EAAK,aAAa,EAAM,CAAgB,EAC/C,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EAGvC,GAFA,EAAW,EAAU,CAAC,EAElB,CAAA,EAAS,OAGb,IAAI,EAAS,SAAW,EACpB,OAAO,EAAK,YAAY,EAAU,CAAI,EAG1C,EAAI,EAAS,EACb,EAAI,EAAS,EAIb,EAAK,EAAK,GAAM,EAAI,EAAK,IAAM,GAAK,EAAI,EAAK,IAAM,EAAK,EAAI,IAIxD,CAAC,EAAS,QAAU,EAAK,EAAS,KAClC,EAAS,EAAI,EACb,EAAS,EAAI,EAAS,GAClB,EAAS,EAAU,EAAI,EAAI,CAAM,EAAG,EAAI,EAAI,CAAM,CAAC,EACvD,EAAS,EAAI,EAAS,EAAI,EAAS,EACnC,EAAS,OAAS,EAEb,EAAS,OAOV,EAAY,WAAW,CAAQ,GAN/B,EAAY,KAAK,CAAQ,EACzB,EAAS,OAAS,IAStC,CAGI,MAAO,CAAA,CACX,EAEA,EAAiB,+CCpLjB,IAAI,EAAgB,EAAA,EAepB,SAAS,EAAkB,EAAK,CAC5B,EAAc,KAAK,KAAM,CAAG,EAE5B,IAAI,EAAO,KAAK,UAChB,KAAK,UAAY,SAAS,EAAI,EAAI,CAC9B,OAAO,EAAK,EAAI,CAAE,EAAI,GAC9B,CACA,CAEA,OAAA,EAAkB,UAAY,IAAI,EAClC,EAAkB,UAAU,YAAc,EAE1C,EAAiB,+CC3BjB,IAAI,EAAO,EAAA,EACP,EAAmB,EAAA,EAYvB,SAAS,EAAqB,EAAK,CAC/B,EAAM,GAAO,CAAA,EACb,KAAK,cAAgB,EAAI,cACzB,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,iBAAmB,EAAI,iBAEvB,KAAK,mBACD,KAAK,cAGF,KAAK,iBACL,KAAK,iBAAmB,EAAiB,oBAEzC,KAAK,iBAAmB,EAAiB,oBAL7C,KAAK,iBAAmB,EAAiB,MASrD,CAQA,OAAA,EAAqB,UAAU,SAAW,SAAS,EAAQ,EAAQ,EAAM,EAAM,EAAM,CACjF,IAAI,EAAY,EAAK,UAAU,EAAQ,CAAM,EACzC,EAAU,EAAK,UAAU,EAAM,CAAI,EACnC,EAAgB,CAAA,EAAI,EAAc,CAAA,EAClC,EAAW,EAAU,EACrB,EAAmB,KAAK,iBACxB,EAAW,EAAG,EAAS,EACvB,EAAG,EAYP,IATA,EAAc,KAAK,CAAS,EAC5B,EAAU,OAAS,GACnB,EAAU,GAAK,EAEf,EAAY,KAAK,CAAO,EACxB,EAAQ,OAAS,GACjB,EAAQ,GAAK,EAGN,EAAc,QAAU,EAAY,QAAQ,CAQ/C,IAJA,EAAO,EAAc,MAAK,EAC1B,EAAK,OAAS,GAEd,EAAY,EAAK,aAAa,EAAM,CAAgB,EAC/C,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EAGvC,GAFA,EAAW,EAAU,CAAC,EAElB,CAAA,EAAS,OAGb,IAAI,EAAS,OAAQ,CAGjB,GAAI,EAAS,KAAO,EAChB,OAAO,EAAK,YAAY,EAAM,CAAQ,EAE1C,QAChB,CACY,EAAc,KAAK,CAAQ,EAC3B,EAAS,OAAS,EAClB,EAAS,OAAS,GAClB,EAAS,GAAK,EASlB,IAJA,EAAO,EAAY,MAAK,EACxB,EAAK,OAAS,GAEd,EAAY,EAAK,aAAa,EAAM,CAAgB,EAC/C,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EAGvC,GAFA,EAAW,EAAU,CAAC,EAElB,CAAA,EAAS,OAGb,IAAI,EAAS,OAAQ,CACjB,GAAI,EAAS,KAAO,EAChB,OAAO,EAAK,YAAY,EAAU,CAAI,EAE1C,QAChB,CACY,EAAY,KAAK,CAAQ,EACzB,EAAS,OAAS,EAClB,EAAS,OAAS,GAClB,EAAS,GAAK,EAE1B,CAGI,MAAO,CAAA,CACX,EAEA,EAAiB,+CClHjB,IAAI,EAAgB,EAAA,EAapB,SAAS,EAAiB,EAAK,CAC3B,EAAc,KAAK,KAAM,CAAG,EAC5B,KAAK,UAAY,SAAS,EAAI,EAAI,CAC9B,MAAO,EACf,CACA,CAEA,OAAA,EAAiB,UAAY,IAAI,EACjC,EAAiB,UAAU,YAAc,EAEzC,EAAiB,+CCvBA,EAAA,EACjB,IAAI,EAAa,EAAA,EACb,EAAa,EAAA,EACb,EAAmB,EAAA,EA8BvB,SAAS,EAAc,EAAK,CACxB,EAAM,GAAO,CAAA,EACb,KAAK,cAAgB,EAAI,cACzB,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,iBAAmB,EAAI,iBAC5B,KAAK,UAAY,EAAI,WAAa,EAAU,UAC5C,KAAK,OAAS,EAAI,QAAU,EAC5B,KAAK,eAAiB,EAAI,gBAAkB,GAC5C,KAAK,UAAY,EAAI,WAAa,IAE7B,KAAK,mBACD,KAAK,cAGF,KAAK,iBACL,KAAK,iBAAmB,EAAiB,oBAEzC,KAAK,iBAAmB,EAAiB,oBAL7C,KAAK,iBAAmB,EAAiB,OAY7C,KAAK,mBAAqB,EAAiB,MAC3C,KAAK,UAAY,EAAI,WAAa,EAAU,UAE5C,KAAK,UAAY,EAAI,WAAa,EAAU,MAEpD,CASA,OAAA,EAAc,UAAU,SAAW,SAAS,EAAQ,EAAQ,EAAM,EAAM,EAAM,CAK1E,IAAI,EAAY,IAAI,KAAI,EAAG,QAAO,EAG9B,EAAI,SAAS,EAAG,EAAG,CACnB,OAAO,KAAK,UAAU,KAAK,IAAI,EAAE,EAAI,EAAE,CAAC,EAAG,KAAK,IAAI,EAAE,EAAI,EAAE,CAAC,CAAC,CACtE,EAAM,KAAK,IAAI,EAGP,EAAO,SAAS,EAAG,EAAG,CACtB,OAAQ,EAAE,IAAM,EAAE,GAAK,EAAE,IAAM,EAAE,EAAK,EAAI,KAAK,KACvD,EAcQ,EAAS,SAAS,EAAM,EAAG,EAAQ,EAAO,EAAO,CAIjD,GAAI,KAAK,UAAY,GACjB,IAAI,KAAI,EAAG,QAAO,EAAK,EAAY,KAAK,UAAY,IAEpD,MAAO,KAGX,IAAI,EAAI,EAAI,EAAE,EAAM,CAAG,EAAI,KAAK,OAGhC,GAAI,EAAI,EACJ,OAAO,EAGX,GAAI,GAAQ,EACR,OAAA,EAAM,CAAK,EAAI,CAAC,EAAK,EAAG,EAAK,CAAC,EACvB,EAGX,IAAI,EAAK,EAAG,EAAG,EAEX,EAAa,EAAK,aAAa,EAAM,KAAK,gBAAgB,EAU9D,IAAK,EAAI,EAAG,EAAM,IAAU,EAAY,EAAW,CAAC,EAAG,EAAE,EAAG,CAcxD,GAZI,KAAK,iBAGL,EAAU,YAAc,EAAU,YAAc,GAAK,EAElD,EAAU,SAAW,KACpB,EAAU,OAAS,KAI3B,EAAI,EAAO,EAAW,EAAI,EAAK,EAAM,CAAS,EAAG,EAAQ,EAAO,EAAQ,CAAC,EAErE,aAAa,EACb,OAAA,EAAM,CAAK,EAAI,CAAC,EAAK,EAAG,EAAK,CAAC,EAIvB,EAIP,KAAK,gBAAmB,EAAE,EAAU,cAAiB,IACrD,EAAU,OAAS,IAGnB,EAAI,IACJ,EAAM,EAEtB,CAEQ,OAAO,CAEf,EAAM,KAAK,IAAI,EAGP,EAAQ,EAAK,UAAU,EAAQ,CAAM,EACrC,EAAQ,EAAK,UAAU,EAAM,CAAI,EAIjC,EAAS,EAAE,EAAO,CAAG,EAErB,EAAG,EAAO,EAGd,IAAK,EAAI,GAAS,EAAE,EAAG,CAQnB,GANA,EAAQ,CAAA,EAGR,EAAI,EAAO,EAAO,EAAG,EAAQ,EAAO,CAAC,EAGjC,IAAM,IACN,MAAO,CAAA,EAKX,GAAI,aAAa,EACb,OAAO,EAKX,EAAS,CACjB,CAGI,MAAO,CAAA,CACX,EAEA,EAAiB,8CC7MjB,IAAI,EAAa,EACb,EAAa,EAAA,EACb,EAAa,EAAA,EACM,EAAA,EAQvB,SAAS,EAAoB,EAAK,CAC9B,EAAM,GAAO,CAAA,EACb,KAAK,UAAY,EAAI,WAAa,EAAU,UAC5C,KAAK,mBAAqB,EAAI,oBAAsB,EACxD,CAOA,OAAA,EAAoB,UAAU,SAAW,SAAS,EAAQ,EAAQ,EAAM,EAAM,EAAM,CAChF,IAAI,EAAW,KAAK,SAAW,IAAI,EAAK,SAAS,EAAO,EAAO,CACvD,OAAO,EAAM,EAAI,EAAM,CACnC,CAAS,EACD,EAAY,KAAK,UAAY,EAAK,UAAU,EAAQ,CAAM,EAC1D,EAAU,KAAK,QAAU,EAAK,UAAU,EAAM,CAAI,EAAG,EAczD,IAZA,KAAK,KAAO,EAIZ,EAAU,EAAI,EACd,EAAU,EAAI,EAGd,EAAS,KAAK,CAAS,EACvB,EAAU,OAAS,GAGZ,CAAC,EAAS,MAAK,GAAI,CAKtB,GAHA,EAAO,EAAS,IAAG,EACnB,EAAK,OAAS,GAEV,IAAS,EACT,OAAO,EAAK,WAAW,EAAK,UAAU,CAAO,CAAC,EAGlD,KAAK,oBAAoB,CAAI,CACrC,CAGI,MAAO,CAAA,CACX,EAQA,EAAoB,UAAU,oBAAsB,SAAS,EAAM,CAC/D,IAAI,EAAO,KAAK,KACZ,EAAY,KAAK,UACjB,EAAW,KAAK,SAChB,EAAO,KAAK,QAAQ,EACpB,EAAO,KAAK,QAAQ,EACpB,EAAW,EACX,EAAW,EAAG,EACd,EAAI,EAAK,EAAG,EAAI,EAAK,EACrB,EAAI,EAAY,EAAG,EAAI,EACvB,EAAM,KAAK,IAGf,IADA,EAAY,KAAK,eAAe,CAAI,EAChC,EAAI,EAAG,EAAI,EAAU,OAAQ,EAAI,EAAG,EAAE,EAGtC,GAFA,EAAW,EAAU,CAAC,EACtB,EAAY,KAAK,MAAM,EAAS,CAAC,EAAG,EAAS,CAAC,EAAG,EAAG,CAAC,EACjD,EAAW,CAMX,GAJA,EAAK,EAAU,CAAC,EAChB,EAAK,EAAU,CAAC,EAChB,EAAW,EAAK,UAAU,EAAI,CAAE,EAE5B,EAAS,OACT,SAIJ,EAAI,EAAU,OAAO,EAAI,EAAK,CAAC,EAAG,EAAI,EAAK,CAAC,CAAC,EAC7C,EAAK,EAAK,EAAI,GAEV,CAAC,EAAS,QAAU,EAAK,EAAS,KAClC,EAAS,EAAI,EACb,EAAS,EAAI,EAAS,GAAK,EAAU,EAAI,EAAK,CAAI,EAAG,EAAI,EAAK,CAAI,CAAC,EACnE,EAAS,EAAI,EAAS,EAAI,EAAS,EACnC,EAAS,OAAS,EAEb,EAAS,OAIV,EAAS,WAAW,CAAQ,GAH5B,EAAS,KAAK,CAAQ,EACtB,EAAS,OAAS,IAKtC,CAEA,EAEA,EAAiB,iDC9GjB,IAAI,EAAsB,EAAA,EACtB,EAAmB,EAAA,EAMvB,SAAS,EAAuB,EAAK,CACjC,EAAoB,KAAK,KAAM,CAAG,CACtC,CAEA,OAAA,EAAuB,UAAY,IAAI,EACvC,EAAuB,UAAU,YAAc,EAS/C,EAAuB,UAAU,MAAQ,SAAS,EAAG,EAAG,EAAI,EAAI,CAC5D,IAAI,EAAO,KAAK,KACZ,EAAK,EAAI,EAAI,EAAK,EAAI,EAE1B,GAAI,CAAC,EAAK,aAAa,EAAG,CAAC,EACvB,OAAO,KAOX,GAJG,KAAK,qBAAuB,KAC3B,EAAK,UAAU,EAAG,CAAC,EAAE,OAAS,IAG9B,EAAK,UAAU,EAAG,CAAC,IAAM,KAAK,QAC9B,MAAO,CAAC,EAAG,CAAC,EAGhB,GAAI,IAAO,GACP,GAAK,EAAK,aAAa,EAAG,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,GAC/D,EAAK,aAAa,EAAG,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,EAChE,MAAO,CAAC,EAAG,CAAC,UAGX,IAAO,EAAG,CACf,GAAK,EAAK,aAAa,EAAI,EAAG,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAC/D,EAAK,aAAa,EAAI,EAAG,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,EAChE,MAAO,CAAC,EAAG,CAAC,EAGhB,GAAI,KAAK,MAAM,EAAI,EAAG,EAAG,EAAG,CAAC,GAAK,KAAK,MAAM,EAAI,EAAG,EAAG,EAAG,CAAC,EACvD,MAAO,CAAC,EAAG,CAAC,CAExB,KAEQ,OAAM,IAAI,MAAM,oDAAoD,EAGxE,OAAO,KAAK,MAAM,EAAI,EAAI,EAAI,EAAI,EAAG,CAAC,CAC1C,EAQA,EAAuB,UAAU,eAAiB,SAAS,EAAM,CAC7D,IAAI,EAAS,EAAK,OACd,EAAI,EAAK,EAAG,EAAI,EAAK,EACrB,EAAO,KAAK,KACZ,EAAI,EAAY,EAAI,EACpB,EAAY,CAAA,EAAI,EAAe,EAAc,EAAG,EAGpD,GAAI,EACA,EAAK,EAAO,EACZ,EAAK,EAAO,EAEZ,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAC5C,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAExC,IAAO,GACH,EAAK,aAAa,EAAG,EAAI,CAAC,GAC1B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAC,CAAC,EAEzB,EAAK,aAAa,EAAG,EAAI,CAAC,GAC1B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAC,CAAC,EAEzB,EAAK,aAAa,EAAI,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,GAGzB,IAAO,IACR,EAAK,aAAa,EAAI,EAAG,CAAC,GAC1B,EAAU,KAAK,CAAC,EAAI,EAAG,CAAC,CAAC,EAEzB,EAAK,aAAa,EAAI,EAAG,CAAC,GAC1B,EAAU,KAAK,CAAC,EAAI,EAAG,CAAC,CAAC,EAEzB,EAAK,aAAa,EAAG,EAAI,CAAE,GAC3B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,OAOlC,KADA,EAAgB,EAAK,aAAa,EAAM,EAAiB,KAAK,EACzD,EAAI,EAAG,EAAI,EAAc,OAAQ,EAAI,EAAG,EAAE,EAC3C,EAAe,EAAc,CAAC,EAC9B,EAAU,KAAK,CAAC,EAAa,EAAG,EAAa,CAAC,CAAC,EAIvD,OAAO,CACX,EAEA,GAAiB,kDCpHjB,IAAI,EAAsB,EAAA,EACtB,EAAmB,EAAA,EAMvB,SAAS,EAAwB,EAAK,CAClC,EAAoB,KAAK,KAAM,CAAG,CACtC,CAEA,OAAA,EAAwB,UAAY,IAAI,EACxC,EAAwB,UAAU,YAAc,EAShD,EAAwB,UAAU,MAAQ,SAAS,EAAG,EAAG,EAAI,EAAI,CAC7D,IAAI,EAAO,KAAK,KACZ,EAAK,EAAI,EAAI,EAAK,EAAI,EAE1B,GAAI,CAAC,EAAK,aAAa,EAAG,CAAC,EACvB,OAAO,KAOX,GAJG,KAAK,qBAAuB,KAC3B,EAAK,UAAU,EAAG,CAAC,EAAE,OAAS,IAG9B,EAAK,UAAU,EAAG,CAAC,IAAM,KAAK,QAC9B,MAAO,CAAC,EAAG,CAAC,EAKhB,GAAI,IAAO,GAAK,IAAO,EAAG,CACtB,GAAK,EAAK,aAAa,EAAI,EAAI,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAI,EAAI,CAAC,GACjE,EAAK,aAAa,EAAI,EAAI,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAG,EAAI,CAAE,EAClE,MAAO,CAAC,EAAG,CAAC,EAGhB,GAAI,KAAK,MAAM,EAAI,EAAI,EAAG,EAAG,CAAC,GAAK,KAAK,MAAM,EAAG,EAAI,EAAI,EAAG,CAAC,EACzD,MAAO,CAAC,EAAG,CAAC,CAExB,SAGY,IAAO,GACP,GAAI,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAG,EAAI,CAAC,GAC/D,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAG,EAAI,CAAC,EAC/D,MAAO,CAAC,EAAG,CAAC,UAIZ,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,CAAC,GAC/D,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,CAAC,EAC/D,MAAO,CAAC,EAAG,CAAC,EAKxB,OAAO,KAAK,MAAM,EAAI,EAAI,EAAI,EAAI,EAAG,CAAC,CAC1C,EAQA,EAAwB,UAAU,eAAiB,SAAS,EAAM,CAC9D,IAAI,EAAS,EAAK,OACd,EAAI,EAAK,EAAG,EAAI,EAAK,EACrB,EAAO,KAAK,KACZ,EAAI,EAAY,EAAI,EACpB,EAAY,CAAA,EAAI,EAAe,EAAc,EAAG,EAGpD,GAAI,EACA,EAAK,EAAO,EACZ,EAAK,EAAO,EAEZ,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAC5C,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAGxC,IAAO,GAAK,IAAO,GACf,EAAK,aAAa,EAAG,EAAI,CAAE,GAC3B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,EAE1B,EAAK,aAAa,EAAI,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,EAE1B,EAAK,aAAa,EAAI,EAAI,EAAI,CAAE,GAChC,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,EAE9B,EAAK,aAAa,EAAI,EAAI,CAAC,GAC5B,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,EAE9B,EAAK,aAAa,EAAG,EAAI,CAAE,GAC5B,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,GAKhC,IAAO,GACF,EAAK,aAAa,EAAG,EAAI,CAAE,GAC3B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,EAEzB,EAAK,aAAa,EAAI,EAAG,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAG,EAAI,CAAE,CAAC,EAE7B,EAAK,aAAa,EAAI,EAAG,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAG,EAAI,CAAE,CAAC,IAI9B,EAAK,aAAa,EAAI,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,EAEzB,EAAK,aAAa,EAAG,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAC,CAAC,EAE7B,EAAK,aAAa,EAAG,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAC,CAAC,OAQ1C,KADA,EAAgB,EAAK,aAAa,EAAM,EAAiB,MAAM,EAC1D,EAAI,EAAG,EAAI,EAAc,OAAQ,EAAI,EAAG,EAAE,EAC3C,EAAe,EAAc,CAAC,EAC9B,EAAU,KAAK,CAAC,EAAa,EAAG,EAAa,CAAC,CAAC,EAIvD,OAAO,CACX,EAEA,GAAiB,kDCjJjB,IAAI,EAAsB,EAAA,EACtB,EAAmB,EAAA,EAMvB,SAAS,EAA+B,EAAK,CACzC,EAAoB,KAAK,KAAM,CAAG,CACtC,CAEA,OAAA,EAA+B,UAAY,IAAI,EAC/C,EAA+B,UAAU,YAAc,EASvD,EAA+B,UAAU,MAAQ,SAAS,EAAG,EAAG,EAAI,EAAI,CACpE,IAAI,EAAO,KAAK,KACZ,EAAK,EAAI,EAAI,EAAK,EAAI,EAE1B,GAAI,CAAC,EAAK,aAAa,EAAG,CAAC,EACvB,OAAO,KAOX,GAJG,KAAK,qBAAuB,KAC3B,EAAK,UAAU,EAAG,CAAC,EAAE,OAAS,IAG9B,EAAK,UAAU,EAAG,CAAC,IAAM,KAAK,QAC9B,MAAO,CAAC,EAAG,CAAC,EAKhB,GAAI,IAAO,GAAK,IAAO,GAMnB,GAAI,KAAK,MAAM,EAAI,EAAI,EAAG,EAAG,CAAC,GAAK,KAAK,MAAM,EAAG,EAAI,EAAI,EAAG,CAAC,EACzD,MAAO,CAAC,EAAG,CAAC,UAKZ,IAAO,GACP,GAAK,EAAK,aAAa,EAAG,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,GAC/D,EAAK,aAAa,EAAG,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,EAChE,MAAO,CAAC,EAAG,CAAC,UAGX,IAAO,IACP,EAAK,aAAa,EAAI,EAAG,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAC/D,EAAK,aAAa,EAAI,EAAG,CAAC,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAChE,MAAO,CAAC,EAAG,CAAC,EAWxB,OAAI,EAAK,aAAa,EAAI,EAAI,CAAC,GAAK,EAAK,aAAa,EAAG,EAAI,CAAE,EACpD,KAAK,MAAM,EAAI,EAAI,EAAI,EAAI,EAAG,CAAC,EAE/B,IAEf,EAQA,EAA+B,UAAU,eAAiB,SAAS,EAAM,CACrE,IAAI,EAAS,EAAK,OACd,EAAI,EAAK,EAAG,EAAI,EAAK,EACrB,EAAO,KAAK,KACZ,EAAI,EAAY,EAAI,EACpB,EAAY,CAAA,EAAI,EAAe,EAAc,EAAG,EAGpD,GAAI,EAQA,GAPA,EAAK,EAAO,EACZ,EAAK,EAAO,EAEZ,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAC5C,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAGxC,IAAO,GAAK,IAAO,EACf,EAAK,aAAa,EAAG,EAAI,CAAE,GAC3B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,EAE1B,EAAK,aAAa,EAAI,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,EAE1B,EAAK,aAAa,EAAG,EAAI,CAAE,GAAK,EAAK,aAAa,EAAI,EAAI,CAAC,GAC3D,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,MAIlC,CACD,IAAI,EACJ,GAAI,IAAO,EAAG,CACV,EAAiB,EAAK,aAAa,EAAI,EAAI,CAAC,EAC5C,IAAI,EAAgB,EAAK,aAAa,EAAG,EAAI,CAAC,EAC1C,EAAmB,EAAK,aAAa,EAAG,EAAI,CAAC,EAE7C,IACA,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,EACtB,GACA,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAC,CAAC,EAE9B,GACA,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAC,CAAC,GAGlC,GACA,EAAU,KAAK,CAAC,EAAG,EAAI,CAAC,CAAC,EAEzB,GACA,EAAU,KAAK,CAAC,EAAG,EAAI,CAAC,CAAC,CAE7C,SACqB,IAAO,EAAG,CACf,EAAiB,EAAK,aAAa,EAAG,EAAI,CAAE,EAC5C,IAAI,EAAkB,EAAK,aAAa,EAAI,EAAG,CAAC,EAC5C,EAAiB,EAAK,aAAa,EAAI,EAAG,CAAC,EAE3C,IACA,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,EACtB,GACA,EAAU,KAAK,CAAC,EAAI,EAAG,EAAI,CAAE,CAAC,EAE9B,GACA,EAAU,KAAK,CAAC,EAAI,EAAG,EAAI,CAAE,CAAC,GAGlC,GACA,EAAU,KAAK,CAAC,EAAI,EAAG,CAAC,CAAC,EAEzB,GACA,EAAU,KAAK,CAAC,EAAI,EAAG,CAAC,CAAC,CAE7C,CACA,KAKQ,KADA,EAAgB,EAAK,aAAa,EAAM,EAAiB,mBAAmB,EACvE,EAAI,EAAG,EAAI,EAAc,OAAQ,EAAI,EAAG,EAAE,EAC3C,EAAe,EAAc,CAAC,EAC9B,EAAU,KAAK,CAAC,EAAa,EAAG,EAAa,CAAC,CAAC,EAIvD,OAAO,CACX,EAEA,GAAiB,kDC1KjB,IAAI,EAAsB,EAAA,EACtB,EAAmB,EAAA,EAMvB,SAAS,EAAqC,EAAK,CAC/C,EAAoB,KAAK,KAAM,CAAG,CACtC,CAEA,OAAA,EAAqC,UAAY,IAAI,EACrD,EAAqC,UAAU,YAAc,EAS7D,EAAqC,UAAU,MAAQ,SAAS,EAAG,EAAG,EAAI,EAAI,CAC1E,IAAI,EAAO,KAAK,KACZ,EAAK,EAAI,EAAI,EAAK,EAAI,EAE1B,GAAI,CAAC,EAAK,aAAa,EAAG,CAAC,EACvB,OAAO,KAOX,GAJG,KAAK,qBAAuB,KAC3B,EAAK,UAAU,EAAG,CAAC,EAAE,OAAS,IAG9B,EAAK,UAAU,EAAG,CAAC,IAAM,KAAK,QAC9B,MAAO,CAAC,EAAG,CAAC,EAKhB,GAAI,IAAO,GAAK,IAAO,EAAG,CACtB,GAAK,EAAK,aAAa,EAAI,EAAI,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAI,EAAI,CAAC,GACjE,EAAK,aAAa,EAAI,EAAI,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAG,EAAI,CAAE,EAClE,MAAO,CAAC,EAAG,CAAC,EAGhB,GAAI,KAAK,MAAM,EAAI,EAAI,EAAG,EAAG,CAAC,GAAK,KAAK,MAAM,EAAG,EAAI,EAAI,EAAG,CAAC,EACzD,MAAO,CAAC,EAAG,CAAC,CAExB,SAGY,IAAO,GACP,GAAI,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAG,EAAI,CAAC,GAC/D,EAAK,aAAa,EAAI,EAAI,EAAI,CAAC,GAAK,CAAC,EAAK,aAAa,EAAG,EAAI,CAAC,EAC/D,MAAO,CAAC,EAAG,CAAC,UAIZ,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,CAAC,GAC/D,EAAK,aAAa,EAAI,EAAG,EAAI,CAAE,GAAK,CAAC,EAAK,aAAa,EAAI,EAAG,CAAC,EAC/D,MAAO,CAAC,EAAG,CAAC,EAOxB,OAAI,EAAK,aAAa,EAAI,EAAI,CAAC,GAAK,EAAK,aAAa,EAAG,EAAI,CAAE,EACpD,KAAK,MAAM,EAAI,EAAI,EAAI,EAAI,EAAG,CAAC,EAE/B,IAEf,EAQA,EAAqC,UAAU,eAAiB,SAAS,EAAM,CAC3E,IAAI,EAAS,EAAK,OACd,EAAI,EAAK,EAAG,EAAI,EAAK,EACrB,EAAO,KAAK,KACZ,EAAI,EAAY,EAAI,EACpB,EAAY,CAAA,EAAI,EAAe,EAAc,EAAG,EAGpD,GAAI,EACA,EAAK,EAAO,EACZ,EAAK,EAAO,EAEZ,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAC5C,GAAM,EAAI,GAAM,KAAK,IAAI,KAAK,IAAI,EAAI,CAAE,EAAG,CAAC,EAGxC,IAAO,GAAK,IAAO,GACf,EAAK,aAAa,EAAG,EAAI,CAAE,GAC3B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,EAE1B,EAAK,aAAa,EAAI,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,GAE1B,EAAK,aAAa,EAAG,EAAI,CAAE,GAAK,EAAK,aAAa,EAAI,EAAI,CAAC,IAC3D,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,EAE/B,CAAC,EAAK,aAAa,EAAI,EAAI,CAAC,GAAK,EAAK,aAAa,EAAG,EAAI,CAAE,GAC5D,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,EAE/B,CAAC,EAAK,aAAa,EAAG,EAAI,CAAE,GAAK,EAAK,aAAa,EAAI,EAAI,CAAC,GAC5D,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAE,CAAC,GAKhC,IAAO,EACF,EAAK,aAAa,EAAG,EAAI,CAAE,IAC3B,EAAU,KAAK,CAAC,EAAG,EAAI,CAAE,CAAC,EACrB,EAAK,aAAa,EAAI,EAAG,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAG,EAAI,CAAE,CAAC,EAE7B,EAAK,aAAa,EAAI,EAAG,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAG,EAAI,CAAE,CAAC,GAKlC,EAAK,aAAa,EAAI,EAAI,CAAC,IAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,CAAC,CAAC,EACrB,EAAK,aAAa,EAAG,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAC,CAAC,EAE7B,EAAK,aAAa,EAAG,EAAI,CAAC,GAC3B,EAAU,KAAK,CAAC,EAAI,EAAI,EAAI,CAAC,CAAC,OAS9C,KADA,EAAgB,EAAK,aAAa,EAAM,EAAiB,mBAAmB,EACvE,EAAI,EAAG,EAAI,EAAc,OAAQ,EAAI,EAAG,EAAE,EAC3C,EAAe,EAAc,CAAC,EAC9B,EAAU,KAAK,CAAC,EAAa,EAAG,EAAa,CAAC,CAAC,EAIvD,OAAO,CACX,EAEA,GAAiB,kDCvJjB,IAAI,EAAmB,EAAA,EACnB,EAAyB,GAAA,EACzB,EAA0B,GAAA,EAC1B,EAAiC,GAAA,EACjC,EAAuC,GAAA,EAU3C,SAAS,EAAgB,EAAK,CAE1B,OADA,EAAM,GAAO,CAAA,EACT,EAAI,mBAAqB,EAAiB,MACnC,IAAI,EAAuB,CAAG,EAC9B,EAAI,mBAAqB,EAAiB,OAC1C,IAAI,EAAwB,CAAG,EAC/B,EAAI,mBAAqB,EAAiB,oBAC1C,IAAI,EAA+B,CAAG,EAEtC,IAAI,EAAqC,CAAG,CAE3D,CAEA,OAAA,GAAiB,8CC9BjB,GAAiB,CACb,KAA8B,EAC9B,KAA8B,EAAA,EAC9B,KAA8B,GAAA,EAC9B,KAA8B,EAAA,EAC9B,iBAA8B,EAAA,EAC9B,UAA8B,EAAA,EAC9B,YAA8B,EAAA,EAC9B,gBAA8B,GAAA,EAC9B,mBAA8B,GAAA,EAC9B,eAA8B,GAAA,EAC9B,cAA8B,EAAA,EAC9B,kBAA8B,GAAA,EAC9B,qBAA8B,GAAA,EAC9B,iBAA8B,GAAA,EAC9B,cAA8B,GAAA,EAC9B,gBAA8B,GAAA,gDChBlC,GAAiB,GAAA","file":"/npm/pathfinding@0.4.18/index.js/+esm","sourceRoot":"","sourcesContent":["/**\n * Bundled by jsDelivr using Rollup v4.62.2 and esbuild v0.28.1.\n * Original file: /npm/pathfinding@0.4.18/index.js\n *\n * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files\n */\n","/**\r\n * A node in grid. \r\n * This class holds some basic information about a node and custom \r\n * attributes may be added, depending on the algorithms' needs.\r\n * @constructor\r\n * @param {number} x - The x coordinate of the node on the grid.\r\n * @param {number} y - The y coordinate of the node on the grid.\r\n * @param {boolean} [walkable] - Whether this node is walkable.\r\n */\r\nfunction Node(x, y, walkable) {\r\n /**\r\n * The x coordinate of the node on the grid.\r\n * @type number\r\n */\r\n this.x = x;\r\n /**\r\n * The y coordinate of the node on the grid.\r\n * @type number\r\n */\r\n this.y = y;\r\n /**\r\n * Whether this node can be walked through.\r\n * @type boolean\r\n */\r\n this.walkable = (walkable === undefined ? true : walkable);\r\n}\r\n\r\nmodule.exports = Node;\r\n","var DiagonalMovement = {\r\n Always: 1,\r\n Never: 2,\r\n IfAtMostOneObstacle: 3,\r\n OnlyWhenNoObstacles: 4\r\n};\r\n\r\nmodule.exports = DiagonalMovement;","var Node = require('./Node');\r\nvar DiagonalMovement = require('./DiagonalMovement');\r\n\r\n/**\r\n * The Grid class, which serves as the encapsulation of the layout of the nodes.\r\n * @constructor\r\n * @param {number|Array>} width_or_matrix Number of columns of the grid, or matrix\r\n * @param {number} height Number of rows of the grid.\r\n * @param {Array>} [matrix] - A 0-1 matrix\r\n * representing the walkable status of the nodes(0 or false for walkable).\r\n * If the matrix is not supplied, all the nodes will be walkable. */\r\nfunction Grid(width_or_matrix, height, matrix) {\r\n var width;\r\n\r\n if (typeof width_or_matrix !== 'object') {\r\n width = width_or_matrix;\r\n } else {\r\n height = width_or_matrix.length;\r\n width = width_or_matrix[0].length;\r\n matrix = width_or_matrix;\r\n }\r\n\r\n /**\r\n * The number of columns of the grid.\r\n * @type number\r\n */\r\n this.width = width;\r\n /**\r\n * The number of rows of the grid.\r\n * @type number\r\n */\r\n this.height = height;\r\n\r\n /**\r\n * A 2D array of nodes.\r\n */\r\n this.nodes = this._buildNodes(width, height, matrix);\r\n}\r\n\r\n/**\r\n * Build and return the nodes.\r\n * @private\r\n * @param {number} width\r\n * @param {number} height\r\n * @param {Array>} [matrix] - A 0-1 matrix representing\r\n * the walkable status of the nodes.\r\n * @see Grid\r\n */\r\nGrid.prototype._buildNodes = function(width, height, matrix) {\r\n var i, j,\r\n nodes = new Array(height);\r\n\r\n for (i = 0; i < height; ++i) {\r\n nodes[i] = new Array(width);\r\n for (j = 0; j < width; ++j) {\r\n nodes[i][j] = new Node(j, i);\r\n }\r\n }\r\n\r\n\r\n if (matrix === undefined) {\r\n return nodes;\r\n }\r\n\r\n if (matrix.length !== height || matrix[0].length !== width) {\r\n throw new Error('Matrix size does not fit');\r\n }\r\n\r\n for (i = 0; i < height; ++i) {\r\n for (j = 0; j < width; ++j) {\r\n if (matrix[i][j]) {\r\n // 0, false, null will be walkable\r\n // while others will be un-walkable\r\n nodes[i][j].walkable = false;\r\n }\r\n }\r\n }\r\n\r\n return nodes;\r\n};\r\n\r\n\r\nGrid.prototype.getNodeAt = function(x, y) {\r\n return this.nodes[y][x];\r\n};\r\n\r\n\r\n/**\r\n * Determine whether the node at the given position is walkable.\r\n * (Also returns false if the position is outside the grid.)\r\n * @param {number} x - The x coordinate of the node.\r\n * @param {number} y - The y coordinate of the node.\r\n * @return {boolean} - The walkability of the node.\r\n */\r\nGrid.prototype.isWalkableAt = function(x, y) {\r\n return this.isInside(x, y) && this.nodes[y][x].walkable;\r\n};\r\n\r\n\r\n/**\r\n * Determine whether the position is inside the grid.\r\n * XXX: `grid.isInside(x, y)` is wierd to read.\r\n * It should be `(x, y) is inside grid`, but I failed to find a better\r\n * name for this method.\r\n * @param {number} x\r\n * @param {number} y\r\n * @return {boolean}\r\n */\r\nGrid.prototype.isInside = function(x, y) {\r\n return (x >= 0 && x < this.width) && (y >= 0 && y < this.height);\r\n};\r\n\r\n\r\n/**\r\n * Set whether the node on the given position is walkable.\r\n * NOTE: throws exception if the coordinate is not inside the grid.\r\n * @param {number} x - The x coordinate of the node.\r\n * @param {number} y - The y coordinate of the node.\r\n * @param {boolean} walkable - Whether the position is walkable.\r\n */\r\nGrid.prototype.setWalkableAt = function(x, y, walkable) {\r\n this.nodes[y][x].walkable = walkable;\r\n};\r\n\r\n\r\n/**\r\n * Get the neighbors of the given node.\r\n *\r\n * offsets diagonalOffsets:\r\n * +---+---+---+ +---+---+---+\r\n * | | 0 | | | 0 | | 1 |\r\n * +---+---+---+ +---+---+---+\r\n * | 3 | | 1 | | | | |\r\n * +---+---+---+ +---+---+---+\r\n * | | 2 | | | 3 | | 2 |\r\n * +---+---+---+ +---+---+---+\r\n *\r\n * When allowDiagonal is true, if offsets[i] is valid, then\r\n * diagonalOffsets[i] and\r\n * diagonalOffsets[(i + 1) % 4] is valid.\r\n * @param {Node} node\r\n * @param {DiagonalMovement} diagonalMovement\r\n */\r\nGrid.prototype.getNeighbors = function(node, diagonalMovement) {\r\n var x = node.x,\r\n y = node.y,\r\n neighbors = [],\r\n s0 = false, d0 = false,\r\n s1 = false, d1 = false,\r\n s2 = false, d2 = false,\r\n s3 = false, d3 = false,\r\n nodes = this.nodes;\r\n\r\n // ↑\r\n if (this.isWalkableAt(x, y - 1)) {\r\n neighbors.push(nodes[y - 1][x]);\r\n s0 = true;\r\n }\r\n // →\r\n if (this.isWalkableAt(x + 1, y)) {\r\n neighbors.push(nodes[y][x + 1]);\r\n s1 = true;\r\n }\r\n // ↓\r\n if (this.isWalkableAt(x, y + 1)) {\r\n neighbors.push(nodes[y + 1][x]);\r\n s2 = true;\r\n }\r\n // ←\r\n if (this.isWalkableAt(x - 1, y)) {\r\n neighbors.push(nodes[y][x - 1]);\r\n s3 = true;\r\n }\r\n\r\n if (diagonalMovement === DiagonalMovement.Never) {\r\n return neighbors;\r\n }\r\n\r\n if (diagonalMovement === DiagonalMovement.OnlyWhenNoObstacles) {\r\n d0 = s3 && s0;\r\n d1 = s0 && s1;\r\n d2 = s1 && s2;\r\n d3 = s2 && s3;\r\n } else if (diagonalMovement === DiagonalMovement.IfAtMostOneObstacle) {\r\n d0 = s3 || s0;\r\n d1 = s0 || s1;\r\n d2 = s1 || s2;\r\n d3 = s2 || s3;\r\n } else if (diagonalMovement === DiagonalMovement.Always) {\r\n d0 = true;\r\n d1 = true;\r\n d2 = true;\r\n d3 = true;\r\n } else {\r\n throw new Error('Incorrect value of diagonalMovement');\r\n }\r\n\r\n // ↖\r\n if (d0 && this.isWalkableAt(x - 1, y - 1)) {\r\n neighbors.push(nodes[y - 1][x - 1]);\r\n }\r\n // ↗\r\n if (d1 && this.isWalkableAt(x + 1, y - 1)) {\r\n neighbors.push(nodes[y - 1][x + 1]);\r\n }\r\n // ↘\r\n if (d2 && this.isWalkableAt(x + 1, y + 1)) {\r\n neighbors.push(nodes[y + 1][x + 1]);\r\n }\r\n // ↙\r\n if (d3 && this.isWalkableAt(x - 1, y + 1)) {\r\n neighbors.push(nodes[y + 1][x - 1]);\r\n }\r\n\r\n return neighbors;\r\n};\r\n\r\n\r\n/**\r\n * Get a clone of this grid.\r\n * @return {Grid} Cloned grid.\r\n */\r\nGrid.prototype.clone = function() {\r\n var i, j,\r\n\r\n width = this.width,\r\n height = this.height,\r\n thisNodes = this.nodes,\r\n\r\n newGrid = new Grid(width, height),\r\n newNodes = new Array(height);\r\n\r\n for (i = 0; i < height; ++i) {\r\n newNodes[i] = new Array(width);\r\n for (j = 0; j < width; ++j) {\r\n newNodes[i][j] = new Node(j, i, thisNodes[i][j].walkable);\r\n }\r\n }\r\n\r\n newGrid.nodes = newNodes;\r\n\r\n return newGrid;\r\n};\r\n\r\nmodule.exports = Grid;\r\n","/**\r\n * Backtrace according to the parent records and return the path.\r\n * (including both start and end nodes)\r\n * @param {Node} node End node\r\n * @return {Array>} the path\r\n */\r\nfunction backtrace(node) {\r\n var path = [[node.x, node.y]];\r\n while (node.parent) {\r\n node = node.parent;\r\n path.push([node.x, node.y]);\r\n }\r\n return path.reverse();\r\n}\r\nexports.backtrace = backtrace;\r\n\r\n/**\r\n * Backtrace from start and end node, and return the path.\r\n * (including both start and end nodes)\r\n * @param {Node}\r\n * @param {Node}\r\n */\r\nfunction biBacktrace(nodeA, nodeB) {\r\n var pathA = backtrace(nodeA),\r\n pathB = backtrace(nodeB);\r\n return pathA.concat(pathB.reverse());\r\n}\r\nexports.biBacktrace = biBacktrace;\r\n\r\n/**\r\n * Compute the length of the path.\r\n * @param {Array>} path The path\r\n * @return {number} The length of the path\r\n */\r\nfunction pathLength(path) {\r\n var i, sum = 0, a, b, dx, dy;\r\n for (i = 1; i < path.length; ++i) {\r\n a = path[i - 1];\r\n b = path[i];\r\n dx = a[0] - b[0];\r\n dy = a[1] - b[1];\r\n sum += Math.sqrt(dx * dx + dy * dy);\r\n }\r\n return sum;\r\n}\r\nexports.pathLength = pathLength;\r\n\r\n\r\n/**\r\n * Given the start and end coordinates, return all the coordinates lying\r\n * on the line formed by these coordinates, based on Bresenham's algorithm.\r\n * http://en.wikipedia.org/wiki/Bresenham's_line_algorithm#Simplification\r\n * @param {number} x0 Start x coordinate\r\n * @param {number} y0 Start y coordinate\r\n * @param {number} x1 End x coordinate\r\n * @param {number} y1 End y coordinate\r\n * @return {Array>} The coordinates on the line\r\n */\r\nfunction interpolate(x0, y0, x1, y1) {\r\n var abs = Math.abs,\r\n line = [],\r\n sx, sy, dx, dy, err, e2;\r\n\r\n dx = abs(x1 - x0);\r\n dy = abs(y1 - y0);\r\n\r\n sx = (x0 < x1) ? 1 : -1;\r\n sy = (y0 < y1) ? 1 : -1;\r\n\r\n err = dx - dy;\r\n\r\n while (true) {\r\n line.push([x0, y0]);\r\n\r\n if (x0 === x1 && y0 === y1) {\r\n break;\r\n }\r\n \r\n e2 = 2 * err;\r\n if (e2 > -dy) {\r\n err = err - dy;\r\n x0 = x0 + sx;\r\n }\r\n if (e2 < dx) {\r\n err = err + dx;\r\n y0 = y0 + sy;\r\n }\r\n }\r\n\r\n return line;\r\n}\r\nexports.interpolate = interpolate;\r\n\r\n\r\n/**\r\n * Given a compressed path, return a new path that has all the segments\r\n * in it interpolated.\r\n * @param {Array>} path The path\r\n * @return {Array>} expanded path\r\n */\r\nfunction expandPath(path) {\r\n var expanded = [],\r\n len = path.length,\r\n coord0, coord1,\r\n interpolated,\r\n interpolatedLen,\r\n i, j;\r\n\r\n if (len < 2) {\r\n return expanded;\r\n }\r\n\r\n for (i = 0; i < len - 1; ++i) {\r\n coord0 = path[i];\r\n coord1 = path[i + 1];\r\n\r\n interpolated = interpolate(coord0[0], coord0[1], coord1[0], coord1[1]);\r\n interpolatedLen = interpolated.length;\r\n for (j = 0; j < interpolatedLen - 1; ++j) {\r\n expanded.push(interpolated[j]);\r\n }\r\n }\r\n expanded.push(path[len - 1]);\r\n\r\n return expanded;\r\n}\r\nexports.expandPath = expandPath;\r\n\r\n\r\n/**\r\n * Smoothen the give path.\r\n * The original path will not be modified; a new path will be returned.\r\n * @param {PF.Grid} grid\r\n * @param {Array>} path The path\r\n */\r\nfunction smoothenPath(grid, path) {\r\n var len = path.length,\r\n x0 = path[0][0], // path start x\r\n y0 = path[0][1], // path start y\r\n x1 = path[len - 1][0], // path end x\r\n y1 = path[len - 1][1], // path end y\r\n sx, sy, // current start coordinate\r\n ex, ey, // current end coordinate\r\n newPath,\r\n i, j, coord, line, testCoord, blocked;\r\n\r\n sx = x0;\r\n sy = y0;\r\n newPath = [[sx, sy]];\r\n\r\n for (i = 2; i < len; ++i) {\r\n coord = path[i];\r\n ex = coord[0];\r\n ey = coord[1];\r\n line = interpolate(sx, sy, ex, ey);\r\n\r\n blocked = false;\r\n for (j = 1; j < line.length; ++j) {\r\n testCoord = line[j];\r\n\r\n if (!grid.isWalkableAt(testCoord[0], testCoord[1])) {\r\n blocked = true;\r\n break;\r\n }\r\n }\r\n if (blocked) {\r\n lastValidCoord = path[i - 1];\r\n newPath.push(lastValidCoord);\r\n sx = lastValidCoord[0];\r\n sy = lastValidCoord[1];\r\n }\r\n }\r\n newPath.push([x1, y1]);\r\n\r\n return newPath;\r\n}\r\nexports.smoothenPath = smoothenPath;\r\n\r\n\r\n/**\r\n * Compress a path, remove redundant nodes without altering the shape\r\n * The original path is not modified\r\n * @param {Array>} path The path\r\n * @return {Array>} The compressed path\r\n */\r\nfunction compressPath(path) {\r\n\r\n // nothing to compress\r\n if(path.length < 3) {\r\n return path;\r\n }\r\n\r\n var compressed = [],\r\n sx = path[0][0], // start x\r\n sy = path[0][1], // start y\r\n px = path[1][0], // second point x\r\n py = path[1][1], // second point y\r\n dx = px - sx, // direction between the two points\r\n dy = py - sy, // direction between the two points\r\n lx, ly,\r\n ldx, ldy,\r\n sq, i;\r\n\r\n // normalize the direction\r\n sq = Math.sqrt(dx*dx + dy*dy);\r\n dx /= sq;\r\n dy /= sq;\r\n\r\n // start the new path\r\n compressed.push([sx,sy]);\r\n\r\n for(i = 2; i < path.length; i++) {\r\n\r\n // store the last point\r\n lx = px;\r\n ly = py;\r\n\r\n // store the last direction\r\n ldx = dx;\r\n ldy = dy;\r\n\r\n // next point\r\n px = path[i][0];\r\n py = path[i][1];\r\n\r\n // next direction\r\n dx = px - lx;\r\n dy = py - ly;\r\n\r\n // normalize\r\n sq = Math.sqrt(dx*dx + dy*dy);\r\n dx /= sq;\r\n dy /= sq;\r\n\r\n // if the direction has changed, store the point\r\n if ( dx !== ldx || dy !== ldy ) {\r\n compressed.push([lx,ly]);\r\n }\r\n }\r\n\r\n // store the last point\r\n compressed.push([px,py]);\r\n\r\n return compressed;\r\n}\r\nexports.compressPath = compressPath;\r\n","/**\r\n * @namespace PF.Heuristic\r\n * @description A collection of heuristic functions.\r\n */\r\nmodule.exports = {\r\n\r\n /**\r\n * Manhattan distance.\r\n * @param {number} dx - Difference in x.\r\n * @param {number} dy - Difference in y.\r\n * @return {number} dx + dy\r\n */\r\n manhattan: function(dx, dy) {\r\n return dx + dy;\r\n },\r\n\r\n /**\r\n * Euclidean distance.\r\n * @param {number} dx - Difference in x.\r\n * @param {number} dy - Difference in y.\r\n * @return {number} sqrt(dx * dx + dy * dy)\r\n */\r\n euclidean: function(dx, dy) {\r\n return Math.sqrt(dx * dx + dy * dy);\r\n },\r\n\r\n /**\r\n * Octile distance.\r\n * @param {number} dx - Difference in x.\r\n * @param {number} dy - Difference in y.\r\n * @return {number} sqrt(dx * dx + dy * dy) for grids\r\n */\r\n octile: function(dx, dy) {\r\n var F = Math.SQRT2 - 1;\r\n return (dx < dy) ? F * dx + dy : F * dy + dx;\r\n },\r\n\r\n /**\r\n * Chebyshev distance.\r\n * @param {number} dx - Difference in x.\r\n * @param {number} dy - Difference in y.\r\n * @return {number} max(dx, dy)\r\n */\r\n chebyshev: function(dx, dy) {\r\n return Math.max(dx, dy);\r\n }\r\n\r\n};\r\n","var Heap = require('heap');\r\nvar Util = require('../core/Util');\r\nvar Heuristic = require('../core/Heuristic');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * A* path-finder. Based upon https://github.com/bgrins/javascript-astar\r\n * @constructor\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching \r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n * @param {number} opt.weight Weight to apply to the heuristic to allow for\r\n * suboptimal paths, in order to speed up the search.\r\n */\r\nfunction AStarFinder(opt) {\r\n opt = opt || {};\r\n this.allowDiagonal = opt.allowDiagonal;\r\n this.dontCrossCorners = opt.dontCrossCorners;\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n this.weight = opt.weight || 1;\r\n this.diagonalMovement = opt.diagonalMovement;\r\n\r\n if (!this.diagonalMovement) {\r\n if (!this.allowDiagonal) {\r\n this.diagonalMovement = DiagonalMovement.Never;\r\n } else {\r\n if (this.dontCrossCorners) {\r\n this.diagonalMovement = DiagonalMovement.OnlyWhenNoObstacles;\r\n } else {\r\n this.diagonalMovement = DiagonalMovement.IfAtMostOneObstacle;\r\n }\r\n }\r\n }\r\n\r\n // When diagonal movement is allowed the manhattan heuristic is not\r\n //admissible. It should be octile instead\r\n if (this.diagonalMovement === DiagonalMovement.Never) {\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n } else {\r\n this.heuristic = opt.heuristic || Heuristic.octile;\r\n }\r\n}\r\n\r\n/**\r\n * Find and return the the path.\r\n * @return {Array>} The path, including both start and\r\n * end positions.\r\n */\r\nAStarFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {\r\n var openList = new Heap(function(nodeA, nodeB) {\r\n return nodeA.f - nodeB.f;\r\n }),\r\n startNode = grid.getNodeAt(startX, startY),\r\n endNode = grid.getNodeAt(endX, endY),\r\n heuristic = this.heuristic,\r\n diagonalMovement = this.diagonalMovement,\r\n weight = this.weight,\r\n abs = Math.abs, SQRT2 = Math.SQRT2,\r\n node, neighbors, neighbor, i, l, x, y, ng;\r\n\r\n // set the `g` and `f` value of the start node to be 0\r\n startNode.g = 0;\r\n startNode.f = 0;\r\n\r\n // push the start node into the open list\r\n openList.push(startNode);\r\n startNode.opened = true;\r\n\r\n // while the open list is not empty\r\n while (!openList.empty()) {\r\n // pop the position of node which has the minimum `f` value.\r\n node = openList.pop();\r\n node.closed = true;\r\n\r\n // if reached the end position, construct the path and return it\r\n if (node === endNode) {\r\n return Util.backtrace(endNode);\r\n }\r\n\r\n // get neigbours of the current node\r\n neighbors = grid.getNeighbors(node, diagonalMovement);\r\n for (i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n\r\n if (neighbor.closed) {\r\n continue;\r\n }\r\n\r\n x = neighbor.x;\r\n y = neighbor.y;\r\n\r\n // get the distance between current node and the neighbor\r\n // and calculate the next g score\r\n ng = node.g + ((x - node.x === 0 || y - node.y === 0) ? 1 : SQRT2);\r\n\r\n // check if the neighbor has not been inspected yet, or\r\n // can be reached with smaller cost from the current node\r\n if (!neighbor.opened || ng < neighbor.g) {\r\n neighbor.g = ng;\r\n neighbor.h = neighbor.h || weight * heuristic(abs(x - endX), abs(y - endY));\r\n neighbor.f = neighbor.g + neighbor.h;\r\n neighbor.parent = node;\r\n\r\n if (!neighbor.opened) {\r\n openList.push(neighbor);\r\n neighbor.opened = true;\r\n } else {\r\n // the neighbor can be reached with smaller cost.\r\n // Since its f value has been updated, we have to\r\n // update its position in the open list\r\n openList.updateItem(neighbor);\r\n }\r\n }\r\n } // end for each neighbor\r\n } // end while not open list empty\r\n\r\n // fail to find the path\r\n return [];\r\n};\r\n\r\nmodule.exports = AStarFinder;\r\n","var AStarFinder = require('./AStarFinder');\r\n\r\n/**\r\n * Best-First-Search path-finder.\r\n * @constructor\r\n * @extends AStarFinder\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n */\r\nfunction BestFirstFinder(opt) {\r\n AStarFinder.call(this, opt);\r\n\r\n var orig = this.heuristic;\r\n this.heuristic = function(dx, dy) {\r\n return orig(dx, dy) * 1000000;\r\n };\r\n}\r\n\r\nBestFirstFinder.prototype = new AStarFinder();\r\nBestFirstFinder.prototype.constructor = BestFirstFinder;\r\n\r\nmodule.exports = BestFirstFinder;\r\n","var Util = require('../core/Util');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Breadth-First-Search path finder.\r\n * @constructor\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n */\r\nfunction BreadthFirstFinder(opt) {\r\n opt = opt || {};\r\n this.allowDiagonal = opt.allowDiagonal;\r\n this.dontCrossCorners = opt.dontCrossCorners;\r\n this.diagonalMovement = opt.diagonalMovement;\r\n\r\n if (!this.diagonalMovement) {\r\n if (!this.allowDiagonal) {\r\n this.diagonalMovement = DiagonalMovement.Never;\r\n } else {\r\n if (this.dontCrossCorners) {\r\n this.diagonalMovement = DiagonalMovement.OnlyWhenNoObstacles;\r\n } else {\r\n this.diagonalMovement = DiagonalMovement.IfAtMostOneObstacle;\r\n }\r\n }\r\n }\r\n}\r\n\r\n/**\r\n * Find and return the the path.\r\n * @return {Array>} The path, including both start and\r\n * end positions.\r\n */\r\nBreadthFirstFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {\r\n var openList = [],\r\n diagonalMovement = this.diagonalMovement,\r\n startNode = grid.getNodeAt(startX, startY),\r\n endNode = grid.getNodeAt(endX, endY),\r\n neighbors, neighbor, node, i, l;\r\n\r\n // push the start pos into the queue\r\n openList.push(startNode);\r\n startNode.opened = true;\r\n\r\n // while the queue is not empty\r\n while (openList.length) {\r\n // take the front node from the queue\r\n node = openList.shift();\r\n node.closed = true;\r\n\r\n // reached the end position\r\n if (node === endNode) {\r\n return Util.backtrace(endNode);\r\n }\r\n\r\n neighbors = grid.getNeighbors(node, diagonalMovement);\r\n for (i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n\r\n // skip this neighbor if it has been inspected before\r\n if (neighbor.closed || neighbor.opened) {\r\n continue;\r\n }\r\n\r\n openList.push(neighbor);\r\n neighbor.opened = true;\r\n neighbor.parent = node;\r\n }\r\n }\r\n \r\n // fail to find the path\r\n return [];\r\n};\r\n\r\nmodule.exports = BreadthFirstFinder;\r\n","var AStarFinder = require('./AStarFinder');\r\n\r\n/**\r\n * Dijkstra path-finder.\r\n * @constructor\r\n * @extends AStarFinder\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n */\r\nfunction DijkstraFinder(opt) {\r\n AStarFinder.call(this, opt);\r\n this.heuristic = function(dx, dy) {\r\n return 0;\r\n };\r\n}\r\n\r\nDijkstraFinder.prototype = new AStarFinder();\r\nDijkstraFinder.prototype.constructor = DijkstraFinder;\r\n\r\nmodule.exports = DijkstraFinder;\r\n","var Heap = require('heap');\r\nvar Util = require('../core/Util');\r\nvar Heuristic = require('../core/Heuristic');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * A* path-finder.\r\n * based upon https://github.com/bgrins/javascript-astar\r\n * @constructor\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n * @param {number} opt.weight Weight to apply to the heuristic to allow for\r\n * suboptimal paths, in order to speed up the search.\r\n */\r\nfunction BiAStarFinder(opt) {\r\n opt = opt || {};\r\n this.allowDiagonal = opt.allowDiagonal;\r\n this.dontCrossCorners = opt.dontCrossCorners;\r\n this.diagonalMovement = opt.diagonalMovement;\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n this.weight = opt.weight || 1;\r\n\r\n if (!this.diagonalMovement) {\r\n if (!this.allowDiagonal) {\r\n this.diagonalMovement = DiagonalMovement.Never;\r\n } else {\r\n if (this.dontCrossCorners) {\r\n this.diagonalMovement = DiagonalMovement.OnlyWhenNoObstacles;\r\n } else {\r\n this.diagonalMovement = DiagonalMovement.IfAtMostOneObstacle;\r\n }\r\n }\r\n }\r\n\r\n //When diagonal movement is allowed the manhattan heuristic is not admissible\r\n //It should be octile instead\r\n if (this.diagonalMovement === DiagonalMovement.Never) {\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n } else {\r\n this.heuristic = opt.heuristic || Heuristic.octile;\r\n }\r\n}\r\n\r\n/**\r\n * Find and return the the path.\r\n * @return {Array>} The path, including both start and\r\n * end positions.\r\n */\r\nBiAStarFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {\r\n var cmp = function(nodeA, nodeB) {\r\n return nodeA.f - nodeB.f;\r\n },\r\n startOpenList = new Heap(cmp),\r\n endOpenList = new Heap(cmp),\r\n startNode = grid.getNodeAt(startX, startY),\r\n endNode = grid.getNodeAt(endX, endY),\r\n heuristic = this.heuristic,\r\n diagonalMovement = this.diagonalMovement,\r\n weight = this.weight,\r\n abs = Math.abs, SQRT2 = Math.SQRT2,\r\n node, neighbors, neighbor, i, l, x, y, ng,\r\n BY_START = 1, BY_END = 2;\r\n\r\n // set the `g` and `f` value of the start node to be 0\r\n // and push it into the start open list\r\n startNode.g = 0;\r\n startNode.f = 0;\r\n startOpenList.push(startNode);\r\n startNode.opened = BY_START;\r\n\r\n // set the `g` and `f` value of the end node to be 0\r\n // and push it into the open open list\r\n endNode.g = 0;\r\n endNode.f = 0;\r\n endOpenList.push(endNode);\r\n endNode.opened = BY_END;\r\n\r\n // while both the open lists are not empty\r\n while (!startOpenList.empty() && !endOpenList.empty()) {\r\n\r\n // pop the position of start node which has the minimum `f` value.\r\n node = startOpenList.pop();\r\n node.closed = true;\r\n\r\n // get neigbours of the current node\r\n neighbors = grid.getNeighbors(node, diagonalMovement);\r\n for (i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n\r\n if (neighbor.closed) {\r\n continue;\r\n }\r\n if (neighbor.opened === BY_END) {\r\n return Util.biBacktrace(node, neighbor);\r\n }\r\n\r\n x = neighbor.x;\r\n y = neighbor.y;\r\n\r\n // get the distance between current node and the neighbor\r\n // and calculate the next g score\r\n ng = node.g + ((x - node.x === 0 || y - node.y === 0) ? 1 : SQRT2);\r\n\r\n // check if the neighbor has not been inspected yet, or\r\n // can be reached with smaller cost from the current node\r\n if (!neighbor.opened || ng < neighbor.g) {\r\n neighbor.g = ng;\r\n neighbor.h = neighbor.h ||\r\n weight * heuristic(abs(x - endX), abs(y - endY));\r\n neighbor.f = neighbor.g + neighbor.h;\r\n neighbor.parent = node;\r\n\r\n if (!neighbor.opened) {\r\n startOpenList.push(neighbor);\r\n neighbor.opened = BY_START;\r\n } else {\r\n // the neighbor can be reached with smaller cost.\r\n // Since its f value has been updated, we have to\r\n // update its position in the open list\r\n startOpenList.updateItem(neighbor);\r\n }\r\n }\r\n } // end for each neighbor\r\n\r\n\r\n // pop the position of end node which has the minimum `f` value.\r\n node = endOpenList.pop();\r\n node.closed = true;\r\n\r\n // get neigbours of the current node\r\n neighbors = grid.getNeighbors(node, diagonalMovement);\r\n for (i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n\r\n if (neighbor.closed) {\r\n continue;\r\n }\r\n if (neighbor.opened === BY_START) {\r\n return Util.biBacktrace(neighbor, node);\r\n }\r\n\r\n x = neighbor.x;\r\n y = neighbor.y;\r\n\r\n // get the distance between current node and the neighbor\r\n // and calculate the next g score\r\n ng = node.g + ((x - node.x === 0 || y - node.y === 0) ? 1 : SQRT2);\r\n\r\n // check if the neighbor has not been inspected yet, or\r\n // can be reached with smaller cost from the current node\r\n if (!neighbor.opened || ng < neighbor.g) {\r\n neighbor.g = ng;\r\n neighbor.h = neighbor.h ||\r\n weight * heuristic(abs(x - startX), abs(y - startY));\r\n neighbor.f = neighbor.g + neighbor.h;\r\n neighbor.parent = node;\r\n\r\n if (!neighbor.opened) {\r\n endOpenList.push(neighbor);\r\n neighbor.opened = BY_END;\r\n } else {\r\n // the neighbor can be reached with smaller cost.\r\n // Since its f value has been updated, we have to\r\n // update its position in the open list\r\n endOpenList.updateItem(neighbor);\r\n }\r\n }\r\n } // end for each neighbor\r\n } // end while not open list empty\r\n\r\n // fail to find the path\r\n return [];\r\n};\r\n\r\nmodule.exports = BiAStarFinder;\r\n","var BiAStarFinder = require('./BiAStarFinder');\r\n\r\n/**\r\n * Bi-direcitional Best-First-Search path-finder.\r\n * @constructor\r\n * @extends BiAStarFinder\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n */\r\nfunction BiBestFirstFinder(opt) {\r\n BiAStarFinder.call(this, opt);\r\n\r\n var orig = this.heuristic;\r\n this.heuristic = function(dx, dy) {\r\n return orig(dx, dy) * 1000000;\r\n };\r\n}\r\n\r\nBiBestFirstFinder.prototype = new BiAStarFinder();\r\nBiBestFirstFinder.prototype.constructor = BiBestFirstFinder;\r\n\r\nmodule.exports = BiBestFirstFinder;\r\n","var Util = require('../core/Util');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Bi-directional Breadth-First-Search path finder.\r\n * @constructor\r\n * @param {object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n */\r\nfunction BiBreadthFirstFinder(opt) {\r\n opt = opt || {};\r\n this.allowDiagonal = opt.allowDiagonal;\r\n this.dontCrossCorners = opt.dontCrossCorners;\r\n this.diagonalMovement = opt.diagonalMovement;\r\n\r\n if (!this.diagonalMovement) {\r\n if (!this.allowDiagonal) {\r\n this.diagonalMovement = DiagonalMovement.Never;\r\n } else {\r\n if (this.dontCrossCorners) {\r\n this.diagonalMovement = DiagonalMovement.OnlyWhenNoObstacles;\r\n } else {\r\n this.diagonalMovement = DiagonalMovement.IfAtMostOneObstacle;\r\n }\r\n }\r\n }\r\n}\r\n\r\n\r\n/**\r\n * Find and return the the path.\r\n * @return {Array>} The path, including both start and\r\n * end positions.\r\n */\r\nBiBreadthFirstFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {\r\n var startNode = grid.getNodeAt(startX, startY),\r\n endNode = grid.getNodeAt(endX, endY),\r\n startOpenList = [], endOpenList = [],\r\n neighbors, neighbor, node,\r\n diagonalMovement = this.diagonalMovement,\r\n BY_START = 0, BY_END = 1,\r\n i, l;\r\n\r\n // push the start and end nodes into the queues\r\n startOpenList.push(startNode);\r\n startNode.opened = true;\r\n startNode.by = BY_START;\r\n\r\n endOpenList.push(endNode);\r\n endNode.opened = true;\r\n endNode.by = BY_END;\r\n\r\n // while both the queues are not empty\r\n while (startOpenList.length && endOpenList.length) {\r\n\r\n // expand start open list\r\n\r\n node = startOpenList.shift();\r\n node.closed = true;\r\n\r\n neighbors = grid.getNeighbors(node, diagonalMovement);\r\n for (i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n\r\n if (neighbor.closed) {\r\n continue;\r\n }\r\n if (neighbor.opened) {\r\n // if this node has been inspected by the reversed search,\r\n // then a path is found.\r\n if (neighbor.by === BY_END) {\r\n return Util.biBacktrace(node, neighbor);\r\n }\r\n continue;\r\n }\r\n startOpenList.push(neighbor);\r\n neighbor.parent = node;\r\n neighbor.opened = true;\r\n neighbor.by = BY_START;\r\n }\r\n\r\n // expand end open list\r\n\r\n node = endOpenList.shift();\r\n node.closed = true;\r\n\r\n neighbors = grid.getNeighbors(node, diagonalMovement);\r\n for (i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n\r\n if (neighbor.closed) {\r\n continue;\r\n }\r\n if (neighbor.opened) {\r\n if (neighbor.by === BY_START) {\r\n return Util.biBacktrace(neighbor, node);\r\n }\r\n continue;\r\n }\r\n endOpenList.push(neighbor);\r\n neighbor.parent = node;\r\n neighbor.opened = true;\r\n neighbor.by = BY_END;\r\n }\r\n }\r\n\r\n // fail to find the path\r\n return [];\r\n};\r\n\r\nmodule.exports = BiBreadthFirstFinder;\r\n","var BiAStarFinder = require('./BiAStarFinder');\r\n\r\n/**\r\n * Bi-directional Dijkstra path-finder.\r\n * @constructor\r\n * @extends BiAStarFinder\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n */\r\nfunction BiDijkstraFinder(opt) {\r\n BiAStarFinder.call(this, opt);\r\n this.heuristic = function(dx, dy) {\r\n return 0;\r\n };\r\n}\r\n\r\nBiDijkstraFinder.prototype = new BiAStarFinder();\r\nBiDijkstraFinder.prototype.constructor = BiDijkstraFinder;\r\n\r\nmodule.exports = BiDijkstraFinder;\r\n","var Util = require('../core/Util');\r\nvar Heuristic = require('../core/Heuristic');\r\nvar Node = require('../core/Node');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Iterative Deeping A Star (IDA*) path-finder.\r\n *\r\n * Recursion based on:\r\n * http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html\r\n *\r\n * Path retracing based on:\r\n * V. Nageshwara Rao, Vipin Kumar and K. Ramesh\r\n * \"A Parallel Implementation of Iterative-Deeping-A*\", January 1987.\r\n * ftp://ftp.cs.utexas.edu/.snapshot/hourly.1/pub/AI-Lab/tech-reports/UT-AI-TR-87-46.pdf\r\n *\r\n * @author Gerard Meier (www.gerardmeier.com)\r\n *\r\n * @constructor\r\n * @param {Object} opt\r\n * @param {boolean} opt.allowDiagonal Whether diagonal movement is allowed.\r\n * Deprecated, use diagonalMovement instead.\r\n * @param {boolean} opt.dontCrossCorners Disallow diagonal movement touching\r\n * block corners. Deprecated, use diagonalMovement instead.\r\n * @param {DiagonalMovement} opt.diagonalMovement Allowed diagonal movement.\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n * @param {number} opt.weight Weight to apply to the heuristic to allow for\r\n * suboptimal paths, in order to speed up the search.\r\n * @param {boolean} opt.trackRecursion Whether to track recursion for\r\n * statistical purposes.\r\n * @param {number} opt.timeLimit Maximum execution time. Use <= 0 for infinite.\r\n */\r\nfunction IDAStarFinder(opt) {\r\n opt = opt || {};\r\n this.allowDiagonal = opt.allowDiagonal;\r\n this.dontCrossCorners = opt.dontCrossCorners;\r\n this.diagonalMovement = opt.diagonalMovement;\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n this.weight = opt.weight || 1;\r\n this.trackRecursion = opt.trackRecursion || false;\r\n this.timeLimit = opt.timeLimit || Infinity; // Default: no time limit.\r\n\r\n if (!this.diagonalMovement) {\r\n if (!this.allowDiagonal) {\r\n this.diagonalMovement = DiagonalMovement.Never;\r\n } else {\r\n if (this.dontCrossCorners) {\r\n this.diagonalMovement = DiagonalMovement.OnlyWhenNoObstacles;\r\n } else {\r\n this.diagonalMovement = DiagonalMovement.IfAtMostOneObstacle;\r\n }\r\n }\r\n }\r\n\r\n // When diagonal movement is allowed the manhattan heuristic is not\r\n // admissible, it should be octile instead\r\n if (this.diagonalMovement === DiagonalMovement.Never) {\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n } else {\r\n this.heuristic = opt.heuristic || Heuristic.octile;\r\n }\r\n}\r\n\r\n/**\r\n * Find and return the the path. When an empty array is returned, either\r\n * no path is possible, or the maximum execution time is reached.\r\n *\r\n * @return {Array>} The path, including both start and\r\n * end positions.\r\n */\r\nIDAStarFinder.prototype.findPath = function(startX, startY, endX, endY, grid) {\r\n // Used for statistics:\r\n var nodesVisited = 0;\r\n\r\n // Execution time limitation:\r\n var startTime = new Date().getTime();\r\n\r\n // Heuristic helper:\r\n var h = function(a, b) {\r\n return this.heuristic(Math.abs(b.x - a.x), Math.abs(b.y - a.y));\r\n }.bind(this);\r\n\r\n // Step cost from a to b:\r\n var cost = function(a, b) {\r\n return (a.x === b.x || a.y === b.y) ? 1 : Math.SQRT2;\r\n };\r\n\r\n /**\r\n * IDA* search implementation.\r\n *\r\n * @param {Node} The node currently expanding from.\r\n * @param {number} Cost to reach the given node.\r\n * @param {number} Maximum search depth (cut-off value).\r\n * @param {Array>} The found route.\r\n * @param {number} Recursion depth.\r\n *\r\n * @return {Object} either a number with the new optimal cut-off depth,\r\n * or a valid node instance, in which case a path was found.\r\n */\r\n var search = function(node, g, cutoff, route, depth) {\r\n nodesVisited++;\r\n\r\n // Enforce timelimit:\r\n if (this.timeLimit > 0 &&\r\n new Date().getTime() - startTime > this.timeLimit * 1000) {\r\n // Enforced as \"path-not-found\".\r\n return Infinity;\r\n }\r\n\r\n var f = g + h(node, end) * this.weight;\r\n\r\n // We've searched too deep for this iteration.\r\n if (f > cutoff) {\r\n return f;\r\n }\r\n\r\n if (node == end) {\r\n route[depth] = [node.x, node.y];\r\n return node;\r\n }\r\n\r\n var min, t, k, neighbour;\r\n\r\n var neighbours = grid.getNeighbors(node, this.diagonalMovement);\r\n\r\n // Sort the neighbours, gives nicer paths. But, this deviates\r\n // from the original algorithm - so I left it out.\r\n //neighbours.sort(function(a, b){\r\n // return h(a, end) - h(b, end);\r\n //});\r\n\r\n \r\n /*jshint -W084 *///Disable warning: Expected a conditional expression and instead saw an assignment\r\n for (k = 0, min = Infinity; neighbour = neighbours[k]; ++k) {\r\n /*jshint +W084 *///Enable warning: Expected a conditional expression and instead saw an assignment\r\n if (this.trackRecursion) {\r\n // Retain a copy for visualisation. Due to recursion, this\r\n // node may be part of other paths too.\r\n neighbour.retainCount = neighbour.retainCount + 1 || 1;\r\n\r\n if(neighbour.tested !== true) {\r\n neighbour.tested = true;\r\n }\r\n }\r\n\r\n t = search(neighbour, g + cost(node, neighbour), cutoff, route, depth + 1);\r\n\r\n if (t instanceof Node) {\r\n route[depth] = [node.x, node.y];\r\n\r\n // For a typical A* linked list, this would work:\r\n // neighbour.parent = node;\r\n return t;\r\n }\r\n\r\n // Decrement count, then determine whether it's actually closed.\r\n if (this.trackRecursion && (--neighbour.retainCount) === 0) {\r\n neighbour.tested = false;\r\n }\r\n\r\n if (t < min) {\r\n min = t;\r\n }\r\n }\r\n\r\n return min;\r\n\r\n }.bind(this);\r\n\r\n // Node instance lookups:\r\n var start = grid.getNodeAt(startX, startY);\r\n var end = grid.getNodeAt(endX, endY);\r\n\r\n // Initial search depth, given the typical heuristic contraints,\r\n // there should be no cheaper route possible.\r\n var cutOff = h(start, end);\r\n\r\n var j, route, t;\r\n\r\n // With an overflow protection.\r\n for (j = 0; true; ++j) {\r\n\r\n route = [];\r\n\r\n // Search till cut-off depth:\r\n t = search(start, 0, cutOff, route, 0);\r\n\r\n // Route not possible, or not found in time limit.\r\n if (t === Infinity) {\r\n return [];\r\n }\r\n\r\n // If t is a node, it's also the end node. Route is now\r\n // populated with a valid path to the end node.\r\n if (t instanceof Node) {\r\n return route;\r\n }\r\n\r\n // Try again, this time with a deeper cut-off. The t score\r\n // is the closest we got to the end node.\r\n cutOff = t;\r\n }\r\n\r\n // This _should_ never to be reached.\r\n return [];\r\n};\r\n\r\nmodule.exports = IDAStarFinder;\r\n","/**\r\n * @author imor / https://github.com/imor\r\n */\r\nvar Heap = require('heap');\r\nvar Util = require('../core/Util');\r\nvar Heuristic = require('../core/Heuristic');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Base class for the Jump Point Search algorithm\r\n * @param {object} opt\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n */\r\nfunction JumpPointFinderBase(opt) {\r\n opt = opt || {};\r\n this.heuristic = opt.heuristic || Heuristic.manhattan;\r\n this.trackJumpRecursion = opt.trackJumpRecursion || false;\r\n}\r\n\r\n/**\r\n * Find and return the path.\r\n * @return {Array>} The path, including both start and\r\n * end positions.\r\n */\r\nJumpPointFinderBase.prototype.findPath = function(startX, startY, endX, endY, grid) {\r\n var openList = this.openList = new Heap(function(nodeA, nodeB) {\r\n return nodeA.f - nodeB.f;\r\n }),\r\n startNode = this.startNode = grid.getNodeAt(startX, startY),\r\n endNode = this.endNode = grid.getNodeAt(endX, endY), node;\r\n\r\n this.grid = grid;\r\n\r\n\r\n // set the `g` and `f` value of the start node to be 0\r\n startNode.g = 0;\r\n startNode.f = 0;\r\n\r\n // push the start node into the open list\r\n openList.push(startNode);\r\n startNode.opened = true;\r\n\r\n // while the open list is not empty\r\n while (!openList.empty()) {\r\n // pop the position of node which has the minimum `f` value.\r\n node = openList.pop();\r\n node.closed = true;\r\n\r\n if (node === endNode) {\r\n return Util.expandPath(Util.backtrace(endNode));\r\n }\r\n\r\n this._identifySuccessors(node);\r\n }\r\n\r\n // fail to find the path\r\n return [];\r\n};\r\n\r\n/**\r\n * Identify successors for the given node. Runs a jump point search in the\r\n * direction of each available neighbor, adding any points found to the open\r\n * list.\r\n * @protected\r\n */\r\nJumpPointFinderBase.prototype._identifySuccessors = function(node) {\r\n var grid = this.grid,\r\n heuristic = this.heuristic,\r\n openList = this.openList,\r\n endX = this.endNode.x,\r\n endY = this.endNode.y,\r\n neighbors, neighbor,\r\n jumpPoint, i, l,\r\n x = node.x, y = node.y,\r\n jx, jy, dx, dy, d, ng, jumpNode,\r\n abs = Math.abs, max = Math.max;\r\n\r\n neighbors = this._findNeighbors(node);\r\n for(i = 0, l = neighbors.length; i < l; ++i) {\r\n neighbor = neighbors[i];\r\n jumpPoint = this._jump(neighbor[0], neighbor[1], x, y);\r\n if (jumpPoint) {\r\n\r\n jx = jumpPoint[0];\r\n jy = jumpPoint[1];\r\n jumpNode = grid.getNodeAt(jx, jy);\r\n\r\n if (jumpNode.closed) {\r\n continue;\r\n }\r\n\r\n // include distance, as parent may not be immediately adjacent:\r\n d = Heuristic.octile(abs(jx - x), abs(jy - y));\r\n ng = node.g + d; // next `g` value\r\n\r\n if (!jumpNode.opened || ng < jumpNode.g) {\r\n jumpNode.g = ng;\r\n jumpNode.h = jumpNode.h || heuristic(abs(jx - endX), abs(jy - endY));\r\n jumpNode.f = jumpNode.g + jumpNode.h;\r\n jumpNode.parent = node;\r\n\r\n if (!jumpNode.opened) {\r\n openList.push(jumpNode);\r\n jumpNode.opened = true;\r\n } else {\r\n openList.updateItem(jumpNode);\r\n }\r\n }\r\n }\r\n }\r\n};\r\n\r\nmodule.exports = JumpPointFinderBase;\r\n","/**\r\n * @author imor / https://github.com/imor\r\n */\r\nvar JumpPointFinderBase = require('./JumpPointFinderBase');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Path finder using the Jump Point Search algorithm allowing only horizontal\r\n * or vertical movements.\r\n */\r\nfunction JPFNeverMoveDiagonally(opt) {\r\n JumpPointFinderBase.call(this, opt);\r\n}\r\n\r\nJPFNeverMoveDiagonally.prototype = new JumpPointFinderBase();\r\nJPFNeverMoveDiagonally.prototype.constructor = JPFNeverMoveDiagonally;\r\n\r\n/**\r\n * Search recursively in the direction (parent -> child), stopping only when a\r\n * jump point is found.\r\n * @protected\r\n * @return {Array>} The x, y coordinate of the jump point\r\n * found, or null if not found\r\n */\r\nJPFNeverMoveDiagonally.prototype._jump = function(x, y, px, py) {\r\n var grid = this.grid,\r\n dx = x - px, dy = y - py;\r\n\r\n if (!grid.isWalkableAt(x, y)) {\r\n return null;\r\n }\r\n\r\n if(this.trackJumpRecursion === true) {\r\n grid.getNodeAt(x, y).tested = true;\r\n }\r\n\r\n if (grid.getNodeAt(x, y) === this.endNode) {\r\n return [x, y];\r\n }\r\n\r\n if (dx !== 0) {\r\n if ((grid.isWalkableAt(x, y - 1) && !grid.isWalkableAt(x - dx, y - 1)) ||\r\n (grid.isWalkableAt(x, y + 1) && !grid.isWalkableAt(x - dx, y + 1))) {\r\n return [x, y];\r\n }\r\n }\r\n else if (dy !== 0) {\r\n if ((grid.isWalkableAt(x - 1, y) && !grid.isWalkableAt(x - 1, y - dy)) ||\r\n (grid.isWalkableAt(x + 1, y) && !grid.isWalkableAt(x + 1, y - dy))) {\r\n return [x, y];\r\n }\r\n //When moving vertically, must check for horizontal jump points\r\n if (this._jump(x + 1, y, x, y) || this._jump(x - 1, y, x, y)) {\r\n return [x, y];\r\n }\r\n }\r\n else {\r\n throw new Error(\"Only horizontal and vertical movements are allowed\");\r\n }\r\n\r\n return this._jump(x + dx, y + dy, x, y);\r\n};\r\n\r\n/**\r\n * Find the neighbors for the given node. If the node has a parent,\r\n * prune the neighbors based on the jump point search algorithm, otherwise\r\n * return all available neighbors.\r\n * @return {Array>} The neighbors found.\r\n */\r\nJPFNeverMoveDiagonally.prototype._findNeighbors = function(node) {\r\n var parent = node.parent,\r\n x = node.x, y = node.y,\r\n grid = this.grid,\r\n px, py, nx, ny, dx, dy,\r\n neighbors = [], neighborNodes, neighborNode, i, l;\r\n\r\n // directed pruning: can ignore most neighbors, unless forced.\r\n if (parent) {\r\n px = parent.x;\r\n py = parent.y;\r\n // get the normalized direction of travel\r\n dx = (x - px) / Math.max(Math.abs(x - px), 1);\r\n dy = (y - py) / Math.max(Math.abs(y - py), 1);\r\n\r\n if (dx !== 0) {\r\n if (grid.isWalkableAt(x, y - 1)) {\r\n neighbors.push([x, y - 1]);\r\n }\r\n if (grid.isWalkableAt(x, y + 1)) {\r\n neighbors.push([x, y + 1]);\r\n }\r\n if (grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y]);\r\n }\r\n }\r\n else if (dy !== 0) {\r\n if (grid.isWalkableAt(x - 1, y)) {\r\n neighbors.push([x - 1, y]);\r\n }\r\n if (grid.isWalkableAt(x + 1, y)) {\r\n neighbors.push([x + 1, y]);\r\n }\r\n if (grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x, y + dy]);\r\n }\r\n }\r\n }\r\n // return all neighbors\r\n else {\r\n neighborNodes = grid.getNeighbors(node, DiagonalMovement.Never);\r\n for (i = 0, l = neighborNodes.length; i < l; ++i) {\r\n neighborNode = neighborNodes[i];\r\n neighbors.push([neighborNode.x, neighborNode.y]);\r\n }\r\n }\r\n\r\n return neighbors;\r\n};\r\n\r\nmodule.exports = JPFNeverMoveDiagonally;\r\n","/**\r\n * @author imor / https://github.com/imor\r\n */\r\nvar JumpPointFinderBase = require('./JumpPointFinderBase');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Path finder using the Jump Point Search algorithm which always moves\r\n * diagonally irrespective of the number of obstacles.\r\n */\r\nfunction JPFAlwaysMoveDiagonally(opt) {\r\n JumpPointFinderBase.call(this, opt);\r\n}\r\n\r\nJPFAlwaysMoveDiagonally.prototype = new JumpPointFinderBase();\r\nJPFAlwaysMoveDiagonally.prototype.constructor = JPFAlwaysMoveDiagonally;\r\n\r\n/**\r\n * Search recursively in the direction (parent -> child), stopping only when a\r\n * jump point is found.\r\n * @protected\r\n * @return {Array>} The x, y coordinate of the jump point\r\n * found, or null if not found\r\n */\r\nJPFAlwaysMoveDiagonally.prototype._jump = function(x, y, px, py) {\r\n var grid = this.grid,\r\n dx = x - px, dy = y - py;\r\n\r\n if (!grid.isWalkableAt(x, y)) {\r\n return null;\r\n }\r\n\r\n if(this.trackJumpRecursion === true) {\r\n grid.getNodeAt(x, y).tested = true;\r\n }\r\n\r\n if (grid.getNodeAt(x, y) === this.endNode) {\r\n return [x, y];\r\n }\r\n\r\n // check for forced neighbors\r\n // along the diagonal\r\n if (dx !== 0 && dy !== 0) {\r\n if ((grid.isWalkableAt(x - dx, y + dy) && !grid.isWalkableAt(x - dx, y)) ||\r\n (grid.isWalkableAt(x + dx, y - dy) && !grid.isWalkableAt(x, y - dy))) {\r\n return [x, y];\r\n }\r\n // when moving diagonally, must check for vertical/horizontal jump points\r\n if (this._jump(x + dx, y, x, y) || this._jump(x, y + dy, x, y)) {\r\n return [x, y];\r\n }\r\n }\r\n // horizontally/vertically\r\n else {\r\n if( dx !== 0 ) { // moving along x\r\n if((grid.isWalkableAt(x + dx, y + 1) && !grid.isWalkableAt(x, y + 1)) ||\r\n (grid.isWalkableAt(x + dx, y - 1) && !grid.isWalkableAt(x, y - 1))) {\r\n return [x, y];\r\n }\r\n }\r\n else {\r\n if((grid.isWalkableAt(x + 1, y + dy) && !grid.isWalkableAt(x + 1, y)) ||\r\n (grid.isWalkableAt(x - 1, y + dy) && !grid.isWalkableAt(x - 1, y))) {\r\n return [x, y];\r\n }\r\n }\r\n }\r\n\r\n return this._jump(x + dx, y + dy, x, y);\r\n};\r\n\r\n/**\r\n * Find the neighbors for the given node. If the node has a parent,\r\n * prune the neighbors based on the jump point search algorithm, otherwise\r\n * return all available neighbors.\r\n * @return {Array>} The neighbors found.\r\n */\r\nJPFAlwaysMoveDiagonally.prototype._findNeighbors = function(node) {\r\n var parent = node.parent,\r\n x = node.x, y = node.y,\r\n grid = this.grid,\r\n px, py, nx, ny, dx, dy,\r\n neighbors = [], neighborNodes, neighborNode, i, l;\r\n\r\n // directed pruning: can ignore most neighbors, unless forced.\r\n if (parent) {\r\n px = parent.x;\r\n py = parent.y;\r\n // get the normalized direction of travel\r\n dx = (x - px) / Math.max(Math.abs(x - px), 1);\r\n dy = (y - py) / Math.max(Math.abs(y - py), 1);\r\n\r\n // search diagonally\r\n if (dx !== 0 && dy !== 0) {\r\n if (grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x, y + dy]);\r\n }\r\n if (grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y]);\r\n }\r\n if (grid.isWalkableAt(x + dx, y + dy)) {\r\n neighbors.push([x + dx, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x - dx, y)) {\r\n neighbors.push([x - dx, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x, y - dy)) {\r\n neighbors.push([x + dx, y - dy]);\r\n }\r\n }\r\n // search horizontally/vertically\r\n else {\r\n if(dx === 0) {\r\n if (grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x + 1, y)) {\r\n neighbors.push([x + 1, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x - 1, y)) {\r\n neighbors.push([x - 1, y + dy]);\r\n }\r\n }\r\n else {\r\n if (grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y]);\r\n }\r\n if (!grid.isWalkableAt(x, y + 1)) {\r\n neighbors.push([x + dx, y + 1]);\r\n }\r\n if (!grid.isWalkableAt(x, y - 1)) {\r\n neighbors.push([x + dx, y - 1]);\r\n }\r\n }\r\n }\r\n }\r\n // return all neighbors\r\n else {\r\n neighborNodes = grid.getNeighbors(node, DiagonalMovement.Always);\r\n for (i = 0, l = neighborNodes.length; i < l; ++i) {\r\n neighborNode = neighborNodes[i];\r\n neighbors.push([neighborNode.x, neighborNode.y]);\r\n }\r\n }\r\n\r\n return neighbors;\r\n};\r\n\r\nmodule.exports = JPFAlwaysMoveDiagonally;\r\n","/**\r\n * @author imor / https://github.com/imor\r\n */\r\nvar JumpPointFinderBase = require('./JumpPointFinderBase');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Path finder using the Jump Point Search algorithm which moves\r\n * diagonally only when there are no obstacles.\r\n */\r\nfunction JPFMoveDiagonallyIfNoObstacles(opt) {\r\n JumpPointFinderBase.call(this, opt);\r\n}\r\n\r\nJPFMoveDiagonallyIfNoObstacles.prototype = new JumpPointFinderBase();\r\nJPFMoveDiagonallyIfNoObstacles.prototype.constructor = JPFMoveDiagonallyIfNoObstacles;\r\n\r\n/**\r\n * Search recursively in the direction (parent -> child), stopping only when a\r\n * jump point is found.\r\n * @protected\r\n * @return {Array>} The x, y coordinate of the jump point\r\n * found, or null if not found\r\n */\r\nJPFMoveDiagonallyIfNoObstacles.prototype._jump = function(x, y, px, py) {\r\n var grid = this.grid,\r\n dx = x - px, dy = y - py;\r\n\r\n if (!grid.isWalkableAt(x, y)) {\r\n return null;\r\n }\r\n\r\n if(this.trackJumpRecursion === true) {\r\n grid.getNodeAt(x, y).tested = true;\r\n }\r\n\r\n if (grid.getNodeAt(x, y) === this.endNode) {\r\n return [x, y];\r\n }\r\n\r\n // check for forced neighbors\r\n // along the diagonal\r\n if (dx !== 0 && dy !== 0) {\r\n // if ((grid.isWalkableAt(x - dx, y + dy) && !grid.isWalkableAt(x - dx, y)) ||\r\n // (grid.isWalkableAt(x + dx, y - dy) && !grid.isWalkableAt(x, y - dy))) {\r\n // return [x, y];\r\n // }\r\n // when moving diagonally, must check for vertical/horizontal jump points\r\n if (this._jump(x + dx, y, x, y) || this._jump(x, y + dy, x, y)) {\r\n return [x, y];\r\n }\r\n }\r\n // horizontally/vertically\r\n else {\r\n if (dx !== 0) {\r\n if ((grid.isWalkableAt(x, y - 1) && !grid.isWalkableAt(x - dx, y - 1)) ||\r\n (grid.isWalkableAt(x, y + 1) && !grid.isWalkableAt(x - dx, y + 1))) {\r\n return [x, y];\r\n }\r\n }\r\n else if (dy !== 0) {\r\n if ((grid.isWalkableAt(x - 1, y) && !grid.isWalkableAt(x - 1, y - dy)) ||\r\n (grid.isWalkableAt(x + 1, y) && !grid.isWalkableAt(x + 1, y - dy))) {\r\n return [x, y];\r\n }\r\n // When moving vertically, must check for horizontal jump points\r\n // if (this._jump(x + 1, y, x, y) || this._jump(x - 1, y, x, y)) {\r\n // return [x, y];\r\n // }\r\n }\r\n }\r\n\r\n // moving diagonally, must make sure one of the vertical/horizontal\r\n // neighbors is open to allow the path\r\n if (grid.isWalkableAt(x + dx, y) && grid.isWalkableAt(x, y + dy)) {\r\n return this._jump(x + dx, y + dy, x, y);\r\n } else {\r\n return null;\r\n }\r\n};\r\n\r\n/**\r\n * Find the neighbors for the given node. If the node has a parent,\r\n * prune the neighbors based on the jump point search algorithm, otherwise\r\n * return all available neighbors.\r\n * @return {Array>} The neighbors found.\r\n */\r\nJPFMoveDiagonallyIfNoObstacles.prototype._findNeighbors = function(node) {\r\n var parent = node.parent,\r\n x = node.x, y = node.y,\r\n grid = this.grid,\r\n px, py, nx, ny, dx, dy,\r\n neighbors = [], neighborNodes, neighborNode, i, l;\r\n\r\n // directed pruning: can ignore most neighbors, unless forced.\r\n if (parent) {\r\n px = parent.x;\r\n py = parent.y;\r\n // get the normalized direction of travel\r\n dx = (x - px) / Math.max(Math.abs(x - px), 1);\r\n dy = (y - py) / Math.max(Math.abs(y - py), 1);\r\n\r\n // search diagonally\r\n if (dx !== 0 && dy !== 0) {\r\n if (grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x, y + dy]);\r\n }\r\n if (grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y]);\r\n }\r\n if (grid.isWalkableAt(x, y + dy) && grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y + dy]);\r\n }\r\n }\r\n // search horizontally/vertically\r\n else {\r\n var isNextWalkable;\r\n if (dx !== 0) {\r\n isNextWalkable = grid.isWalkableAt(x + dx, y);\r\n var isTopWalkable = grid.isWalkableAt(x, y + 1);\r\n var isBottomWalkable = grid.isWalkableAt(x, y - 1);\r\n\r\n if (isNextWalkable) {\r\n neighbors.push([x + dx, y]);\r\n if (isTopWalkable) {\r\n neighbors.push([x + dx, y + 1]);\r\n }\r\n if (isBottomWalkable) {\r\n neighbors.push([x + dx, y - 1]);\r\n }\r\n }\r\n if (isTopWalkable) {\r\n neighbors.push([x, y + 1]);\r\n }\r\n if (isBottomWalkable) {\r\n neighbors.push([x, y - 1]);\r\n }\r\n }\r\n else if (dy !== 0) {\r\n isNextWalkable = grid.isWalkableAt(x, y + dy);\r\n var isRightWalkable = grid.isWalkableAt(x + 1, y);\r\n var isLeftWalkable = grid.isWalkableAt(x - 1, y);\r\n\r\n if (isNextWalkable) {\r\n neighbors.push([x, y + dy]);\r\n if (isRightWalkable) {\r\n neighbors.push([x + 1, y + dy]);\r\n }\r\n if (isLeftWalkable) {\r\n neighbors.push([x - 1, y + dy]);\r\n }\r\n }\r\n if (isRightWalkable) {\r\n neighbors.push([x + 1, y]);\r\n }\r\n if (isLeftWalkable) {\r\n neighbors.push([x - 1, y]);\r\n }\r\n }\r\n }\r\n }\r\n // return all neighbors\r\n else {\r\n neighborNodes = grid.getNeighbors(node, DiagonalMovement.OnlyWhenNoObstacles);\r\n for (i = 0, l = neighborNodes.length; i < l; ++i) {\r\n neighborNode = neighborNodes[i];\r\n neighbors.push([neighborNode.x, neighborNode.y]);\r\n }\r\n }\r\n\r\n return neighbors;\r\n};\r\n\r\nmodule.exports = JPFMoveDiagonallyIfNoObstacles;\r\n","/**\r\n * @author imor / https://github.com/imor\r\n */\r\nvar JumpPointFinderBase = require('./JumpPointFinderBase');\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\n\r\n/**\r\n * Path finder using the Jump Point Search algorithm which moves\r\n * diagonally only when there is at most one obstacle.\r\n */\r\nfunction JPFMoveDiagonallyIfAtMostOneObstacle(opt) {\r\n JumpPointFinderBase.call(this, opt);\r\n}\r\n\r\nJPFMoveDiagonallyIfAtMostOneObstacle.prototype = new JumpPointFinderBase();\r\nJPFMoveDiagonallyIfAtMostOneObstacle.prototype.constructor = JPFMoveDiagonallyIfAtMostOneObstacle;\r\n\r\n/**\r\n * Search recursively in the direction (parent -> child), stopping only when a\r\n * jump point is found.\r\n * @protected\r\n * @return {Array>} The x, y coordinate of the jump point\r\n * found, or null if not found\r\n */\r\nJPFMoveDiagonallyIfAtMostOneObstacle.prototype._jump = function(x, y, px, py) {\r\n var grid = this.grid,\r\n dx = x - px, dy = y - py;\r\n\r\n if (!grid.isWalkableAt(x, y)) {\r\n return null;\r\n }\r\n\r\n if(this.trackJumpRecursion === true) {\r\n grid.getNodeAt(x, y).tested = true;\r\n }\r\n\r\n if (grid.getNodeAt(x, y) === this.endNode) {\r\n return [x, y];\r\n }\r\n\r\n // check for forced neighbors\r\n // along the diagonal\r\n if (dx !== 0 && dy !== 0) {\r\n if ((grid.isWalkableAt(x - dx, y + dy) && !grid.isWalkableAt(x - dx, y)) ||\r\n (grid.isWalkableAt(x + dx, y - dy) && !grid.isWalkableAt(x, y - dy))) {\r\n return [x, y];\r\n }\r\n // when moving diagonally, must check for vertical/horizontal jump points\r\n if (this._jump(x + dx, y, x, y) || this._jump(x, y + dy, x, y)) {\r\n return [x, y];\r\n }\r\n }\r\n // horizontally/vertically\r\n else {\r\n if( dx !== 0 ) { // moving along x\r\n if((grid.isWalkableAt(x + dx, y + 1) && !grid.isWalkableAt(x, y + 1)) ||\r\n (grid.isWalkableAt(x + dx, y - 1) && !grid.isWalkableAt(x, y - 1))) {\r\n return [x, y];\r\n }\r\n }\r\n else {\r\n if((grid.isWalkableAt(x + 1, y + dy) && !grid.isWalkableAt(x + 1, y)) ||\r\n (grid.isWalkableAt(x - 1, y + dy) && !grid.isWalkableAt(x - 1, y))) {\r\n return [x, y];\r\n }\r\n }\r\n }\r\n\r\n // moving diagonally, must make sure one of the vertical/horizontal\r\n // neighbors is open to allow the path\r\n if (grid.isWalkableAt(x + dx, y) || grid.isWalkableAt(x, y + dy)) {\r\n return this._jump(x + dx, y + dy, x, y);\r\n } else {\r\n return null;\r\n }\r\n};\r\n\r\n/**\r\n * Find the neighbors for the given node. If the node has a parent,\r\n * prune the neighbors based on the jump point search algorithm, otherwise\r\n * return all available neighbors.\r\n * @return {Array>} The neighbors found.\r\n */\r\nJPFMoveDiagonallyIfAtMostOneObstacle.prototype._findNeighbors = function(node) {\r\n var parent = node.parent,\r\n x = node.x, y = node.y,\r\n grid = this.grid,\r\n px, py, nx, ny, dx, dy,\r\n neighbors = [], neighborNodes, neighborNode, i, l;\r\n\r\n // directed pruning: can ignore most neighbors, unless forced.\r\n if (parent) {\r\n px = parent.x;\r\n py = parent.y;\r\n // get the normalized direction of travel\r\n dx = (x - px) / Math.max(Math.abs(x - px), 1);\r\n dy = (y - py) / Math.max(Math.abs(y - py), 1);\r\n\r\n // search diagonally\r\n if (dx !== 0 && dy !== 0) {\r\n if (grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x, y + dy]);\r\n }\r\n if (grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y]);\r\n }\r\n if (grid.isWalkableAt(x, y + dy) || grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x - dx, y) && grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x - dx, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x, y - dy) && grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y - dy]);\r\n }\r\n }\r\n // search horizontally/vertically\r\n else {\r\n if(dx === 0) {\r\n if (grid.isWalkableAt(x, y + dy)) {\r\n neighbors.push([x, y + dy]);\r\n if (!grid.isWalkableAt(x + 1, y)) {\r\n neighbors.push([x + 1, y + dy]);\r\n }\r\n if (!grid.isWalkableAt(x - 1, y)) {\r\n neighbors.push([x - 1, y + dy]);\r\n }\r\n }\r\n }\r\n else {\r\n if (grid.isWalkableAt(x + dx, y)) {\r\n neighbors.push([x + dx, y]);\r\n if (!grid.isWalkableAt(x, y + 1)) {\r\n neighbors.push([x + dx, y + 1]);\r\n }\r\n if (!grid.isWalkableAt(x, y - 1)) {\r\n neighbors.push([x + dx, y - 1]);\r\n }\r\n }\r\n }\r\n }\r\n }\r\n // return all neighbors\r\n else {\r\n neighborNodes = grid.getNeighbors(node, DiagonalMovement.IfAtMostOneObstacle);\r\n for (i = 0, l = neighborNodes.length; i < l; ++i) {\r\n neighborNode = neighborNodes[i];\r\n neighbors.push([neighborNode.x, neighborNode.y]);\r\n }\r\n }\r\n\r\n return neighbors;\r\n};\r\n\r\nmodule.exports = JPFMoveDiagonallyIfAtMostOneObstacle;\r\n","/**\r\n * @author aniero / https://github.com/aniero\r\n */\r\nvar DiagonalMovement = require('../core/DiagonalMovement');\r\nvar JPFNeverMoveDiagonally = require('./JPFNeverMoveDiagonally');\r\nvar JPFAlwaysMoveDiagonally = require('./JPFAlwaysMoveDiagonally');\r\nvar JPFMoveDiagonallyIfNoObstacles = require('./JPFMoveDiagonallyIfNoObstacles');\r\nvar JPFMoveDiagonallyIfAtMostOneObstacle = require('./JPFMoveDiagonallyIfAtMostOneObstacle');\r\n\r\n/**\r\n * Path finder using the Jump Point Search algorithm\r\n * @param {Object} opt\r\n * @param {function} opt.heuristic Heuristic function to estimate the distance\r\n * (defaults to manhattan).\r\n * @param {DiagonalMovement} opt.diagonalMovement Condition under which diagonal\r\n * movement will be allowed.\r\n */\r\nfunction JumpPointFinder(opt) {\r\n opt = opt || {};\r\n if (opt.diagonalMovement === DiagonalMovement.Never) {\r\n return new JPFNeverMoveDiagonally(opt);\r\n } else if (opt.diagonalMovement === DiagonalMovement.Always) {\r\n return new JPFAlwaysMoveDiagonally(opt);\r\n } else if (opt.diagonalMovement === DiagonalMovement.OnlyWhenNoObstacles) {\r\n return new JPFMoveDiagonallyIfNoObstacles(opt);\r\n } else {\r\n return new JPFMoveDiagonallyIfAtMostOneObstacle(opt);\r\n }\r\n}\r\n\r\nmodule.exports = JumpPointFinder;\r\n","module.exports = {\r\n 'Heap' : require('heap'),\r\n 'Node' : require('./core/Node'),\r\n 'Grid' : require('./core/Grid'),\r\n 'Util' : require('./core/Util'),\r\n 'DiagonalMovement' : require('./core/DiagonalMovement'),\r\n 'Heuristic' : require('./core/Heuristic'),\r\n 'AStarFinder' : require('./finders/AStarFinder'),\r\n 'BestFirstFinder' : require('./finders/BestFirstFinder'),\r\n 'BreadthFirstFinder' : require('./finders/BreadthFirstFinder'),\r\n 'DijkstraFinder' : require('./finders/DijkstraFinder'),\r\n 'BiAStarFinder' : require('./finders/BiAStarFinder'),\r\n 'BiBestFirstFinder' : require('./finders/BiBestFirstFinder'),\r\n 'BiBreadthFirstFinder' : require('./finders/BiBreadthFirstFinder'),\r\n 'BiDijkstraFinder' : require('./finders/BiDijkstraFinder'),\r\n 'IDAStarFinder' : require('./finders/IDAStarFinder'),\r\n 'JumpPointFinder' : require('./finders/JumpPointFinder'),\r\n};\r\n","module.exports = require('./src/PathFinding');\r\n"]}