{"version":3,"sources":["/home/runner/work/turf/turf/packages/turf-shortest-path/dist/cjs/index.cjs","../../index.ts","../../lib/javascript-astar.ts"],"names":[],"mappings":"AAAA;ACQA,kCAAqB;AACrB,uEAAsC;AACtC,0CAAyB;AACzB,uDAAwC;AACxC,iDAA4B;AAC5B,iDAA4B;AAC5B,4CAAkC;AAClC;AAGE;AACA;AACA;AACA;AACA;AACA;AAAA,wCACK;ADRP;AACA;AEVA,SAAS,MAAA,CAAO,IAAA,EAAgB;AAC9B,EAAA,IAAI,KAAA,EAAO,IAAA,EACT,KAAA,EAAO,CAAC,CAAA;AACV,EAAA,MAAA,CAAO,IAAA,CAAK,MAAA,EAAQ;AAClB,IAAA,IAAA,CAAK,OAAA,CAAQ,IAAI,CAAA;AACjB,IAAA,KAAA,EAAO,IAAA,CAAK,MAAA;AAAA,EACd;AACA,EAAA,OAAO,IAAA;AACT;AAEA,SAAS,OAAA,CAAA,EAAU;AACjB,EAAA,OAAO,IAAI,UAAA,CAAqB,QAAA,CAAU,IAAA,EAAM;AAC9C,IAAA,OAAO,IAAA,CAAK,CAAA;AAAA,EACd,CAAC,CAAA;AACH;AAMO,IAAI,MAAA,EAAQ;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAcjB,MAAA,EAAQ,QAAA,CACN,KAAA,EACA,KAAA,EACA,GAAA,EACA,QAAA,EAEI,CAAC,CAAA,EACL;AAhDJ,IAAA,IAAA,EAAA;AAiDI,IAAA,KAAA,CAAM,UAAA,CAAW,CAAA;AACjB,IAAA,QAAA,EAAU,QAAA,GAAW,CAAC,CAAA;AACtB,IAAA,IAAI,UAAA,EAAY,KAAA,CAAM,UAAA,CAAW,SAAA,EAC/B,QAAA,EAAA,CAAU,GAAA,EAAA,OAAA,CAAQ,OAAA,EAAA,GAAR,KAAA,EAAA,GAAA,EAAmB,KAAA;AAE/B,IAAA,IAAI,SAAA,EAAW,OAAA,CAAQ,CAAA,EACrB,YAAA,EAAc,KAAA;AAEhB,IAAA,KAAA,CAAM,EAAA,EAAI,SAAA,CAAU,KAAA,EAAO,GAAG,CAAA;AAE9B,IAAA,QAAA,CAAS,IAAA,CAAK,KAAK,CAAA;AAEnB,IAAA,MAAA,CAAO,QAAA,CAAS,IAAA,CAAK,EAAA,EAAI,CAAA,EAAG;AAE1B,MAAA,IAAI,YAAA,EAAc,QAAA,CAAS,GAAA,CAAI,CAAA;AAG/B,MAAA,GAAA,CAAI,YAAA,IAAgB,GAAA,EAAK;AACvB,QAAA,OAAO,MAAA,CAAO,WAAW,CAAA;AAAA,MAC3B;AAGA,MAAA,WAAA,CAAY,OAAA,EAAS,IAAA;AAGrB,MAAA,IAAI,UAAA,EAAY,KAAA,CAAM,SAAA,CAAU,WAAW,CAAA;AAE3C,MAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,GAAA,EAAK,SAAA,CAAU,MAAA,EAAQ,EAAA,EAAI,EAAA,EAAI,EAAE,CAAA,EAAG;AAClD,QAAA,IAAI,SAAA,EAAW,SAAA,CAAU,CAAC,CAAA;AAE1B,QAAA,GAAA,CAAI,QAAA,CAAS,OAAA,GAAU,QAAA,CAAS,MAAA,CAAO,CAAA,EAAG;AAExC,UAAA,QAAA;AAAA,QACF;AAIA,QAAA,IAAI,OAAA,EAAS,WAAA,CAAY,EAAA,EAAI,QAAA,CAAS,OAAA,CAAQ,WAAW,CAAA,EACvD,YAAA,EAAc,QAAA,CAAS,OAAA;AAEzB,QAAA,GAAA,CAAI,CAAC,YAAA,GAAe,OAAA,EAAS,QAAA,CAAS,CAAA,EAAG;AAEvC,UAAA,QAAA,CAAS,QAAA,EAAU,IAAA;AACnB,UAAA,QAAA,CAAS,OAAA,EAAS,WAAA;AAClB,UAAA,QAAA,CAAS,EAAA,EAAI,QAAA,CAAS,EAAA,GAAK,SAAA,CAAU,QAAA,EAAU,GAAG,CAAA;AAClD,UAAA,QAAA,CAAS,EAAA,EAAI,MAAA;AACb,UAAA,QAAA,CAAS,EAAA,EAAI,QAAA,CAAS,EAAA,EAAI,QAAA,CAAS,CAAA;AACnC,UAAA,KAAA,CAAM,SAAA,CAAU,QAAQ,CAAA;AACxB,UAAA,GAAA,CAAI,OAAA,EAAS;AAGX,YAAA,GAAA,CACE,QAAA,CAAS,EAAA,EAAI,WAAA,CAAY,EAAA,GACxB,QAAA,CAAS,EAAA,IAAM,WAAA,CAAY,EAAA,GAAK,QAAA,CAAS,EAAA,EAAI,WAAA,CAAY,CAAA,EAC1D;AACA,cAAA,YAAA,EAAc,QAAA;AAAA,YAChB;AAAA,UACF;AAEA,UAAA,GAAA,CAAI,CAAC,WAAA,EAAa;AAEhB,YAAA,QAAA,CAAS,IAAA,CAAK,QAAQ,CAAA;AAAA,UACxB,EAAA,KAAO;AAEL,YAAA,QAAA,CAAS,cAAA,CAAe,QAAQ,CAAA;AAAA,UAClC;AAAA,QACF;AAAA,MACF;AAAA,IACF;AAEA,IAAA,GAAA,CAAI,OAAA,EAAS;AACX,MAAA,OAAO,MAAA,CAAO,WAAW,CAAA;AAAA,IAC3B;AAGA,IAAA,OAAO,CAAC,CAAA;AAAA,EACV,CAAA;AAAA;AAAA,EAEA,UAAA,EAAY;AAAA,IACV,SAAA,EAAW,QAAA,CACT,IAAA,EACA,IAAA,EACA;AACA,MAAA,IAAI,GAAA,EAAK,IAAA,CAAK,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,IAAA,CAAK,CAAC,CAAA;AACjC,MAAA,IAAI,GAAA,EAAK,IAAA,CAAK,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,IAAA,CAAK,CAAC,CAAA;AACjC,MAAA,OAAO,GAAA,EAAK,EAAA;AAAA,IACd,CAAA;AAAA,IACA,QAAA,EAAU,QAAA,CACR,IAAA,EACA,IAAA,EACA;AACA,MAAA,IAAI,EAAA,EAAI,CAAA;AACR,MAAA,IAAI,GAAA,EAAK,IAAA,CAAK,IAAA,CAAK,CAAC,CAAA;AACpB,MAAA,IAAI,GAAA,EAAK,IAAA,CAAK,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,IAAA,CAAK,CAAC,CAAA;AACjC,MAAA,IAAI,GAAA,EAAK,IAAA,CAAK,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,IAAA,CAAK,CAAC,CAAA;AACjC,MAAA,OAAO,EAAA,EAAA,CAAK,GAAA,EAAK,EAAA,EAAA,EAAA,CAAO,GAAA,EAAK,EAAA,EAAI,CAAA,EAAA,EAAK,IAAA,CAAK,GAAA,CAAI,EAAA,EAAI,EAAE,CAAA;AAAA,IACvD;AAAA,EACF,CAAA;AAAA,EACA,SAAA,EAAW,QAAA,CAAU,IAAA,EAAgB;AACnC,IAAA,IAAA,CAAK,EAAA,EAAI,CAAA;AACT,IAAA,IAAA,CAAK,EAAA,EAAI,CAAA;AACT,IAAA,IAAA,CAAK,EAAA,EAAI,CAAA;AACT,IAAA,IAAA,CAAK,QAAA,EAAU,KAAA;AACf,IAAA,IAAA,CAAK,OAAA,EAAS,KAAA;AACd,IAAA,IAAA,CAAK,OAAA,EAAS,KAAA,CAAA;AAAA,EAChB;AACF,CAAA;AAWO,IAAM,MAAA,EAAN,MAAY;AAAA,EAMjB,WAAA,CAAY,MAAA,EAAoB,QAAA,EAAkC,CAAC,CAAA,EAAG;AALtE,IAAA,IAAA,CAAA,MAAA,EAAoB,CAAC,CAAA;AAErB,IAAA,IAAA,CAAA,KAAA,EAAqB,CAAC,CAAA;AACtB,IAAA,IAAA,CAAA,WAAA,EAAyB,CAAC,CAAA;AAGxB,IAAA,IAAA,CAAK,SAAA,EAAW,CAAC,CAAC,OAAA,CAAQ,QAAA;AAC1B,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,EAAA,EAAI,MAAA,CAAO,MAAA,EAAQ,CAAA,EAAA,EAAK;AACtC,MAAA,IAAA,CAAK,IAAA,CAAK,CAAC,EAAA,EAAI,CAAC,CAAA;AAEhB,MAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,IAAA,EAAM,MAAA,CAAO,CAAC,CAAA,EAAG,EAAA,EAAI,GAAA,CAAI,MAAA,EAAQ,CAAA,EAAA,EAAK;AACpD,QAAA,IAAI,KAAA,EAAO,IAAI,QAAA,CAAS,CAAA,EAAG,CAAA,EAAG,GAAA,CAAI,CAAC,CAAC,CAAA;AACpC,QAAA,IAAA,CAAK,IAAA,CAAK,CAAC,CAAA,CAAE,CAAC,EAAA,EAAI,IAAA;AAClB,QAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,IAAI,CAAA;AAAA,MACtB;AAAA,IACF;AACA,IAAA,IAAA,CAAK,IAAA,CAAK,CAAA;AAAA,EACZ;AAAA,EAEA,IAAA,CAAA,EAAO;AACL,IAAA,IAAA,CAAK,WAAA,EAAa,CAAC,CAAA;AACnB,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,EAAA,EAAI,IAAA,CAAK,KAAA,CAAM,MAAA,EAAQ,CAAA,EAAA,EAAK;AAC1C,MAAA,KAAA,CAAM,SAAA,CAAU,IAAA,CAAK,KAAA,CAAM,CAAC,CAAC,CAAA;AAAA,IAC/B;AAAA,EACF;AAAA,EAEA,UAAA,CAAA,EAAa;AACX,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,EAAA,EAAI,IAAA,CAAK,UAAA,CAAW,MAAA,EAAQ,CAAA,EAAA,EAAK;AAC/C,MAAA,KAAA,CAAM,SAAA,CAAU,IAAA,CAAK,UAAA,CAAW,CAAC,CAAC,CAAA;AAAA,IACpC;AACA,IAAA,IAAA,CAAK,WAAA,EAAa,CAAC,CAAA;AAAA,EACrB;AAAA,EAEA,SAAA,CAAU,IAAA,EAAgB;AACxB,IAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,IAAI,CAAA;AAAA,EAC3B;AAAA,EAEA,SAAA,CAAU,IAAA,EAAgB;AACxB,IAAA,IAAI,IAAA,EAAM,CAAC,CAAA,EACT,EAAA,EAAI,IAAA,CAAK,CAAA,EACT,EAAA,EAAI,IAAA,CAAK,CAAA,EACT,KAAA,EAAO,IAAA,CAAK,IAAA;AAGd,IAAA,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,CAAC,EAAA,GAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,CAAC,CAAA,EAAG;AACjC,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA;AAAA,IACzB;AAGA,IAAA,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,CAAC,EAAA,GAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,CAAC,CAAA,EAAG;AACjC,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA;AAAA,IACzB;AAGA,IAAA,GAAA,CAAI,IAAA,CAAK,CAAC,EAAA,GAAK,IAAA,CAAK,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAA,EAAG;AAC7B,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAC,CAAA;AAAA,IACzB;AAGA,IAAA,GAAA,CAAI,IAAA,CAAK,CAAC,EAAA,GAAK,IAAA,CAAK,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAA,EAAG;AAC7B,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAC,CAAA;AAAA,IACzB;AAEA,IAAA,GAAA,CAAI,IAAA,CAAK,QAAA,EAAU;AAEjB,MAAA,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,CAAC,EAAA,GAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAA,EAAG;AACrC,QAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAC,CAAA;AAAA,MAC7B;AAGA,MAAA,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,CAAC,EAAA,GAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAA,EAAG;AACrC,QAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAC,CAAA;AAAA,MAC7B;AAGA,MAAA,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,CAAC,EAAA,GAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAA,EAAG;AACrC,QAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAC,CAAA;AAAA,MAC7B;AAGA,MAAA,GAAA,CAAI,IAAA,CAAK,EAAA,EAAI,CAAC,EAAA,GAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAA,EAAG;AACrC,QAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,EAAA,EAAI,CAAC,CAAA,CAAE,EAAA,EAAI,CAAC,CAAC,CAAA;AAAA,MAC7B;AAAA,IACF;AAEA,IAAA,OAAO,GAAA;AAAA,EACT;AAAA,EAEA,QAAA,CAAA,EAAW;AACT,IAAA,IAAI,YAAA,EAAc,CAAC,CAAA,EACjB,MAAA,EAAQ,IAAA,CAAK,IAAA,EACb,QAAA,EACA,GAAA,EACA,CAAA,EACA,CAAA;AACF,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,IAAA,EAAM,KAAA,CAAM,MAAA,EAAQ,EAAA,EAAI,GAAA,EAAK,CAAA,EAAA,EAAK;AAChD,MAAA,SAAA,EAAW,CAAC,CAAA;AACZ,MAAA,IAAA,EAAM,KAAA,CAAM,CAAC,CAAA;AACb,MAAA,IAAA,CAAK,EAAA,EAAI,CAAA,EAAG,EAAA,EAAI,GAAA,CAAI,MAAA,EAAQ,EAAA,EAAI,CAAA,EAAG,CAAA,EAAA,EAAK;AACtC,QAAA,QAAA,CAAS,IAAA,CAAK,GAAA,CAAI,CAAC,CAAA,CAAE,MAAM,CAAA;AAAA,MAC7B;AACA,MAAA,WAAA,CAAY,IAAA,CAAK,QAAA,CAAS,IAAA,CAAK,GAAG,CAAC,CAAA;AAAA,IACrC;AACA,IAAA,OAAO,WAAA,CAAY,IAAA,CAAK,IAAI,CAAA;AAAA,EAC9B;AACF,CAAA;AAEO,IAAM,SAAA,EAAN,MAAe;AAAA,EAYpB,WAAA,CAAY,CAAA,EAAW,CAAA,EAAW,MAAA,EAAgB;AAPlD,IAAA,IAAA,CAAA,QAAA,EAAmB,KAAA;AAEnB,IAAA,IAAA,CAAA,EAAA,EAAY,CAAA;AACZ,IAAA,IAAA,CAAA,EAAA,EAAY,CAAA;AACZ,IAAA,IAAA,CAAA,EAAA,EAAY,CAAA;AACZ,IAAA,IAAA,CAAA,OAAA,EAAkB,KAAA;AAGhB,IAAA,IAAA,CAAK,EAAA,EAAI,CAAA;AACT,IAAA,IAAA,CAAK,EAAA,EAAI,CAAA;AACT,IAAA,IAAA,CAAK,OAAA,EAAS,MAAA;AAAA,EAChB;AAAA,EACA,QAAA,CAAA,EAAW;AACT,IAAA,OAAO,IAAA,EAAM,IAAA,CAAK,EAAA,EAAI,IAAA,EAAM,IAAA,CAAK,EAAA,EAAI,GAAA;AAAA,EACvC;AAAA,EAEA,OAAA,CAAQ,YAAA,EAAwB;AAE9B,IAAA,GAAA,CACE,aAAA,GACA,YAAA,CAAa,EAAA,IAAM,IAAA,CAAK,EAAA,GACxB,YAAA,CAAa,EAAA,IAAM,IAAA,CAAK,CAAA,EACxB;AACA,MAAA,OAAO,IAAA,CAAK,OAAA,EAAS,OAAA;AAAA,IACvB;AACA,IAAA,OAAO,IAAA,CAAK,MAAA;AAAA,EACd;AAAA,EAEA,MAAA,CAAA,EAAS;AACP,IAAA,OAAO,IAAA,CAAK,OAAA,IAAW,CAAA;AAAA,EACzB;AACF,CAAA;AAEA,IAAM,WAAA,EAAN,MAAoB;AAAA,EAIlB,WAAA,CAAY,aAAA,EAAiC;AAH7C,IAAA,IAAA,CAAA,QAAA,EAAe,CAAC,CAAA;AAId,IAAA,IAAA,CAAK,cAAA,EAAgB,aAAA;AAAA,EACvB;AAAA,EAEA,IAAA,CAAK,OAAA,EAAY;AAEf,IAAA,IAAA,CAAK,OAAA,CAAQ,IAAA,CAAK,OAAO,CAAA;AAGzB,IAAA,IAAA,CAAK,QAAA,CAAS,IAAA,CAAK,OAAA,CAAQ,OAAA,EAAS,CAAC,CAAA;AAAA,EACvC;AAAA,EAEA,GAAA,CAAA,EAAM;AAEJ,IAAA,IAAI,OAAA,EAAS,IAAA,CAAK,OAAA,CAAQ,CAAC,CAAA;AAE3B,IAAA,IAAI,IAAA,EAAM,IAAA,CAAK,OAAA,CAAQ,GAAA,CAAI,CAAA;AAG3B,IAAA,GAAA,CAAI,IAAA,CAAK,OAAA,CAAQ,OAAA,EAAS,CAAA,EAAG;AAC3B,MAAA,IAAA,CAAK,OAAA,CAAQ,CAAC,EAAA,EAAI,GAAA;AAClB,MAAA,IAAA,CAAK,QAAA,CAAS,CAAC,CAAA;AAAA,IACjB;AACA,IAAA,OAAO,MAAA;AAAA,EACT;AAAA,EAEA,MAAA,CAAO,IAAA,EAAS;AACd,IAAA,IAAI,EAAA,EAAI,IAAA,CAAK,OAAA,CAAQ,OAAA,CAAQ,IAAI,CAAA;AAIjC,IAAA,IAAI,IAAA,EAAM,IAAA,CAAK,OAAA,CAAQ,GAAA,CAAI,CAAA;AAE3B,IAAA,GAAA,CAAI,EAAA,IAAM,IAAA,CAAK,OAAA,CAAQ,OAAA,EAAS,CAAA,EAAG;AACjC,MAAA,IAAA,CAAK,OAAA,CAAQ,CAAC,EAAA,EAAI,GAAA;AAElB,MAAA,GAAA,CAAI,IAAA,CAAK,aAAA,CAAc,GAAG,EAAA,EAAI,IAAA,CAAK,aAAA,CAAc,IAAI,CAAA,EAAG;AACtD,QAAA,IAAA,CAAK,QAAA,CAAS,CAAC,CAAA;AAAA,MACjB,EAAA,KAAO;AACL,QAAA,IAAA,CAAK,QAAA,CAAS,CAAC,CAAA;AAAA,MACjB;AAAA,IACF;AAAA,EACF;AAAA,EAEA,IAAA,CAAA,EAAO;AACL,IAAA,OAAO,IAAA,CAAK,OAAA,CAAQ,MAAA;AAAA,EACtB;AAAA,EAEA,cAAA,CAAe,IAAA,EAAS;AACtB,IAAA,IAAA,CAAK,QAAA,CAAS,IAAA,CAAK,OAAA,CAAQ,OAAA,CAAQ,IAAI,CAAC,CAAA;AAAA,EAC1C;AAAA,EAEA,QAAA,CAAS,CAAA,EAAW;AAElB,IAAA,IAAI,QAAA,EAAU,IAAA,CAAK,OAAA,CAAQ,CAAC,CAAA;AAG5B,IAAA,MAAA,CAAO,EAAA,EAAI,CAAA,EAAG;AAEZ,MAAA,IAAI,QAAA,EAAA,CAAY,EAAA,EAAI,EAAA,GAAM,CAAA,EAAA,EAAK,CAAA,EAC7B,OAAA,EAAS,IAAA,CAAK,OAAA,CAAQ,OAAO,CAAA;AAE/B,MAAA,GAAA,CAAI,IAAA,CAAK,aAAA,CAAc,OAAO,EAAA,EAAI,IAAA,CAAK,aAAA,CAAc,MAAM,CAAA,EAAG;AAC5D,QAAA,IAAA,CAAK,OAAA,CAAQ,OAAO,EAAA,EAAI,OAAA;AACxB,QAAA,IAAA,CAAK,OAAA,CAAQ,CAAC,EAAA,EAAI,MAAA;AAElB,QAAA,EAAA,EAAI,OAAA;AAAA,MAEN,EAAA,KAAO;AACL,QAAA,KAAA;AAAA,MACF;AAAA,IACF;AAAA,EACF;AAAA,EAEA,QAAA,CAAS,CAAA,EAAW;AAElB,IAAA,IAAI,OAAA,EAAS,IAAA,CAAK,OAAA,CAAQ,MAAA,EACxB,QAAA,EAAU,IAAA,CAAK,OAAA,CAAQ,CAAC,CAAA,EACxB,UAAA,EAAY,IAAA,CAAK,aAAA,CAAc,OAAO,CAAA;AAExC,IAAA,MAAA,CAAO,IAAA,EAAM;AAEX,MAAA,IAAI,QAAA,EAAW,EAAA,EAAI,EAAA,GAAM,CAAA,EACvB,QAAA,EAAU,QAAA,EAAU,CAAA;AAEtB,MAAA,IAAI,KAAA,EAAO,IAAA,EACT,WAAA;AAEF,MAAA,GAAA,CAAI,QAAA,EAAU,MAAA,EAAQ;AAEpB,QAAA,IAAI,OAAA,EAAS,IAAA,CAAK,OAAA,CAAQ,OAAO,CAAA;AACjC,QAAA,YAAA,EAAc,IAAA,CAAK,aAAA,CAAc,MAAM,CAAA;AAGvC,QAAA,GAAA,CAAI,YAAA,EAAc,SAAA,EAAW;AAC3B,UAAA,KAAA,EAAO,OAAA;AAAA,QACT;AAAA,MACF;AAGA,MAAA,GAAA,CAAI,QAAA,EAAU,MAAA,EAAQ;AACpB,QAAA,IAAI,OAAA,EAAS,IAAA,CAAK,OAAA,CAAQ,OAAO,CAAA,EAC/B,YAAA,EAAc,IAAA,CAAK,aAAA,CAAc,MAAM,CAAA;AACzC,QAAA,GAAA,CAAI,YAAA,EAAA,CAAe,KAAA,IAAS,KAAA,EAAO,UAAA,EAAY,WAAA,CAAA,EAAe;AAC5D,UAAA,KAAA,EAAO,OAAA;AAAA,QACT;AAAA,MACF;AAGA,MAAA,GAAA,CAAI,KAAA,IAAS,IAAA,EAAM;AACjB,QAAA,IAAA,CAAK,OAAA,CAAQ,CAAC,EAAA,EAAI,IAAA,CAAK,OAAA,CAAQ,IAAI,CAAA;AACnC,QAAA,IAAA,CAAK,OAAA,CAAQ,IAAI,EAAA,EAAI,OAAA;AACrB,QAAA,EAAA,EAAI,IAAA;AAAA,MAEN,EAAA,KAAO;AACL,QAAA,KAAA;AAAA,MACF;AAAA,IACF;AAAA,EACF;AACF,CAAA;AFjJA;AACA;AChPA,SAAS,YAAA,CACP,KAAA,EACA,GAAA,EACA,QAAA,EAII,CAAC,CAAA,EACgB;AAErB,EAAA,QAAA,EAAU,QAAA,GAAW,CAAC,CAAA;AACtB,EAAA,GAAA,CAAI,CAAC,+BAAA,OAAgB,CAAA,EAAG,MAAM,IAAI,KAAA,CAAM,oBAAoB,CAAA;AAC5D,EAAA,IAAI,UAAA,EAAY,OAAA,CAAQ,UAAA,GAAa,wCAAA,CAAmB,CAAC,CAAA;AACzD,EAAA,IAAI,WAAA,EAAa,OAAA,CAAQ,WAAA,GAAc,GAAA;AAGvC,EAAA,GAAA,CAAI,CAAC,KAAA,EAAO,MAAM,IAAI,KAAA,CAAM,mBAAmB,CAAA;AAC/C,EAAA,GAAA,CAAI,CAAC,GAAA,EAAK,MAAM,IAAI,KAAA,CAAM,iBAAiB,CAAA;AAC3C,EAAA,GAAA,CAAI,WAAA,GAAA,CAAe,CAAC,+BAAA,UAAmB,EAAA,GAAK,WAAA,GAAc,CAAA,CAAA;AACxD,IAAA,MAAM,IAAI,KAAA,CAAM,qDAAqD,CAAA;AAGvE,EAAA,MAAM,WAAA,EAAa,iCAAA,KAAc,CAAA;AACjC,EAAA,MAAM,SAAA,EAAW,iCAAA,GAAY,CAAA;AAC7B,EAAA,MAAA,EAAQ,4BAAA,UAAgB,CAAA;AACxB,EAAA,IAAA,EAAM,4BAAA,QAAc,CAAA;AAGpB,EAAA,GAAA,CAAI,SAAA,CAAU,KAAA,IAAS,mBAAA,EAAqB;AAC1C,IAAA,GAAA,CAAI,SAAA,CAAU,QAAA,CAAS,OAAA,IAAW,CAAA,EAAG;AACnC,MAAA,OAAO,iCAAA,CAAY,UAAA,EAAY,QAAQ,CAAC,CAAA;AAAA,IAC1C;AAAA,EACF,EAAA,KAAA,GAAA,CACE,SAAA,CAAU,KAAA,IAAS,UAAA,GACnB,SAAA,CAAU,QAAA,CAAS,KAAA,IAAS,SAAA,EAC5B;AACA,IAAA,UAAA,EAAY,wCAAA,CAAmB,SAAS,CAAC,CAAA;AAAA,EAC3C,EAAA,KAAA,GAAA,CAAW,SAAA,CAAU,KAAA,IAAS,SAAA,EAAW;AACvC,IAAA,UAAA,EAAY,wCAAA,CAAmB,8BAAA,gCAAQ,SAAiB,CAAC,CAAC,CAAC,CAAA;AAAA,EAC7D,EAAA,KAAO;AACL,IAAA,MAAM,IAAI,KAAA,CAAM,mBAAmB,CAAA;AAAA,EACrC;AAGA,EAAA,MAAM,WAAA,EAA0C,SAAA;AAChD,EAAA,UAAA,CAAW,QAAA,CAAS,IAAA,CAAK,KAAK,CAAA;AAC9B,EAAA,UAAA,CAAW,QAAA,CAAS,IAAA,CAAK,GAAG,CAAA;AAC5B,EAAA,MAAM,IAAA,EAAM,wBAAA,4CAAK,sCAAM,wBAAY,UAAe,CAAC,CAAA,EAAG,IAAI,CAAC,CAAA;AAC3D,EAAA,MAAM,CAAC,IAAA,EAAM,KAAA,EAAO,IAAA,EAAM,KAAK,EAAA,EAAI,GAAA;AAEnC,EAAA,UAAA,CAAW,QAAA,CAAS,GAAA,CAAI,CAAA;AACxB,EAAA,UAAA,CAAW,QAAA,CAAS,GAAA,CAAI,CAAA;AAExB,EAAA,MAAM,oBAAA,EACJ,gCAAA,CAAU,IAAA,EAAM,KAAK,CAAA,EAAG,CAAC,IAAA,EAAM,KAAK,CAAA,EAAG,OAAO,EAAA,EAAI,UAAA;AACpD,EAAA,MAAM,UAAA,EAAA,CAAa,KAAA,EAAO,IAAA,EAAA,EAAQ,mBAAA;AAElC,EAAA,MAAM,iBAAA,EACJ,gCAAA,CAAU,IAAA,EAAM,KAAK,CAAA,EAAG,CAAC,IAAA,EAAM,KAAK,CAAA,EAAG,OAAO,EAAA,EAAI,UAAA;AACpD,EAAA,MAAM,WAAA,EAAA,CAAc,MAAA,EAAQ,KAAA,EAAA,EAAS,gBAAA;AAGrC,EAAA,MAAM,OAAA,EAAW,oBAAA,EAAsB,EAAA,EAAK,UAAA,EAAa,CAAA;AACzD,EAAA,MAAM,OAAA,EAAW,iBAAA,EAAmB,EAAA,EAAK,WAAA,EAAc,CAAA;AAIvD,EAAA,MAAM,YAAA,EAA0B,CAAC,CAAA;AACjC,EAAA,MAAM,OAAA,EAAqB,CAAC,CAAA;AAE5B,EAAA,IAAI,cAAA;AACJ,EAAA,IAAI,YAAA;AACJ,EAAA,IAAI,aAAA,EAAe,QAAA;AACnB,EAAA,IAAI,WAAA,EAAa,QAAA;AACjB,EAAA,IAAI,SAAA,EAAW,MAAA,EAAQ,MAAA;AACvB,EAAA,IAAI,EAAA,EAAI,CAAA;AACR,EAAA,MAAA,CAAO,SAAA,GAAY,KAAA,EAAO;AAExB,IAAA,MAAM,UAAA,EAAY,CAAC,CAAA;AACnB,IAAA,MAAM,eAAA,EAAiB,CAAC,CAAA;AACxB,IAAA,IAAI,SAAA,EAAW,KAAA,EAAO,MAAA;AACtB,IAAA,IAAI,EAAA,EAAI,CAAA;AACR,IAAA,MAAA,CAAO,SAAA,GAAY,IAAA,EAAM;AACvB,MAAA,MAAM,GAAA,EAAK,4BAAA,CAAO,QAAA,EAAU,QAAQ,CAAC,CAAA;AACrC,MAAA,MAAM,iBAAA,EAAmB,QAAA,CAAS,EAAA,EAAI,SAAS,CAAA;AAE/C,MAAA,SAAA,CAAU,IAAA,CAAK,iBAAA,EAAmB,EAAA,EAAI,CAAC,CAAA;AAGvC,MAAA,cAAA,CAAe,IAAA,CAAK,SAAA,EAAW,IAAA,EAAM,QAAQ,CAAA;AAE7C,MAAA,MAAM,UAAA,EAAY,gCAAA,EAAS,EAAI,KAAK,CAAA;AAEpC,MAAA,GAAA,CAAI,CAAC,iBAAA,GAAoB,UAAA,EAAY,YAAA,EAAc;AACjD,QAAA,aAAA,EAAe,SAAA;AACf,QAAA,eAAA,EAAiB,EAAE,CAAA,EAAG,CAAA,EAAG,CAAA,EAAG,EAAE,CAAA;AAAA,MAChC;AACA,MAAA,MAAM,QAAA,EAAU,gCAAA,EAAS,EAAI,GAAG,CAAA;AAEhC,MAAA,GAAA,CAAI,CAAC,iBAAA,GAAoB,QAAA,EAAU,UAAA,EAAY;AAC7C,QAAA,WAAA,EAAa,OAAA;AACb,QAAA,aAAA,EAAe,EAAE,CAAA,EAAG,CAAA,EAAG,CAAA,EAAG,EAAE,CAAA;AAAA,MAC9B;AACA,MAAA,SAAA,GAAY,SAAA;AACZ,MAAA,CAAA,EAAA;AAAA,IACF;AACA,IAAA,MAAA,CAAO,IAAA,CAAK,SAAS,CAAA;AACrB,IAAA,WAAA,CAAY,IAAA,CAAK,cAAc,CAAA;AAC/B,IAAA,SAAA,GAAY,UAAA;AACZ,IAAA,CAAA,EAAA;AAAA,EACF;AAKA,EAAA,MAAM,MAAA,EAAQ,IAAI,KAAA,CAAM,MAAA,EAAQ,EAAE,QAAA,EAAU,KAAK,CAAC,CAAA;AAClD,EAAA,MAAM,cAAA,EAAgB,KAAA,CAAM,IAAA,CAAK,cAAA,CAAgB,CAAC,CAAA,CAAE,cAAA,CAAgB,CAAC,CAAA;AACrE,EAAA,MAAM,YAAA,EAAc,KAAA,CAAM,IAAA,CAAK,YAAA,CAAc,CAAC,CAAA,CAAE,YAAA,CAAc,CAAC,CAAA;AAC/D,EAAA,MAAM,OAAA,EAAqB,KAAA,CAAM,MAAA,CAAO,KAAA,EAAO,aAAA,EAAe,WAAW,CAAA;AAEzE,EAAA,MAAM,KAAA,EAAO,CAAC,UAAU,CAAA;AACxB,EAAA,MAAA,CAAO,OAAA,CAAQ,QAAA,CAAU,KAAA,EAAO;AAC9B,IAAA,MAAM,OAAA,EAAS,WAAA,CAAY,KAAA,CAAM,CAAC,CAAA,CAAE,KAAA,CAAM,CAAC,CAAA,CAAE,KAAA,CAAM,GAAG,CAAA;AACtD,IAAA,IAAA,CAAK,IAAA,CAAK,CAAC,CAAC,MAAA,CAAO,CAAC,CAAA,EAAG,CAAC,MAAA,CAAO,CAAC,CAAC,CAAC,CAAA;AAAA,EACpC,CAAC,CAAA;AACD,EAAA,IAAA,CAAK,IAAA,CAAK,QAAQ,CAAA;AAalB,EAAA,OAAO,sCAAA,iCAAY,IAAe,CAAC,CAAA;AACrC;AAUA,SAAS,QAAA,CAAS,EAAA,EAAoB,QAAA,EAAsC;AAC1E,EAAA,IAAA,CAAA,IAAS,EAAA,EAAI,CAAA,EAAG,EAAA,EAAI,QAAA,CAAS,QAAA,CAAS,MAAA,EAAQ,CAAA,EAAA,EAAK;AACjD,IAAA,GAAA,CAAI,0DAAA,EAAsB,EAAI,QAAA,CAAS,QAAA,CAAS,CAAC,CAAC,CAAA,EAAG;AACnD,MAAA,OAAO,IAAA;AAAA,IACT;AAAA,EACF;AACA,EAAA,OAAO,KAAA;AACT;AAGA,IAAO,cAAA,EAAQ,YAAA;ADgLf;AACE;AACA;AACF,qEAAC","file":"/home/runner/work/turf/turf/packages/turf-shortest-path/dist/cjs/index.cjs","sourcesContent":[null,"import {\n Polygon,\n Feature,\n FeatureCollection,\n LineString,\n Geometry,\n Point,\n} from \"geojson\";\nimport { bbox } from \"@turf/bbox\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { distance } from \"@turf/distance\";\nimport { transformScale as scale } from \"@turf/transform-scale\";\nimport { cleanCoords } from \"@turf/clean-coords\";\nimport { bboxPolygon } from \"@turf/bbox-polygon\";\nimport { getCoord, getGeom } from \"@turf/invariant\";\nimport {\n Coord,\n Units,\n point,\n isNumber,\n lineString,\n isObject,\n featureCollection,\n feature,\n} from \"@turf/helpers\";\nimport { Graph, GridNode, astar } from \"./lib/javascript-astar.js\";\n\n/**\n * Returns the shortest {@link LineString|path} from {@link Point|start} to {@link Point|end} without colliding with\n * any {@link Feature} in obstacles {@link FeatureCollection}<{@link Polygon}>\n *\n * @function\n * @param {Coord} start point\n * @param {Coord} end point\n * @param {Object} [options={}] optional parameters\n * @param {Polygon|Feature|FeatureCollection} [options.obstacles] areas which path cannot travel\n * @param {Units} [options.units='kilometers'] unit in which resolution & minimum distance will be expressed in; Supports all valid Turf {@link https://turfjs.org/docs/api/types/Units Units}.\n * @param {number} [options.resolution=100] distance between matrix points on which the path will be calculated\n * @returns {Feature} shortest path between start and end\n * @example\n * var start = [-5, -6];\n * var end = [9, -6];\n * var options = {\n * obstacles: turf.polygon([[[0, -7], [5, -7], [5, -3], [0, -3], [0, -7]]]).geometry\n * };\n *\n * var path = turf.shortestPath(start, end, options);\n *\n * //addToMap\n * var addToMap = [start, end, options.obstacles, path];\n */\nfunction shortestPath(\n start: Coord,\n end: Coord,\n options: {\n obstacles?: Polygon | Feature | FeatureCollection;\n units?: Units;\n resolution?: number;\n } = {}\n): Feature {\n // Optional parameters\n options = options || {};\n if (!isObject(options)) throw new Error(\"options is invalid\");\n let obstacles = options.obstacles || featureCollection([]);\n let resolution = options.resolution || 100;\n\n // validation\n if (!start) throw new Error(\"start is required\");\n if (!end) throw new Error(\"end is required\");\n if (resolution && (!isNumber(resolution) || resolution <= 0))\n throw new Error(\"options.resolution must be a number, greater than 0\");\n\n // Normalize Inputs\n const startCoord = getCoord(start);\n const endCoord = getCoord(end);\n start = point(startCoord);\n end = point(endCoord);\n\n // Handle obstacles\n if (obstacles.type === \"FeatureCollection\") {\n if (obstacles.features.length === 0) {\n return lineString([startCoord, endCoord]);\n }\n } else if (\n obstacles.type === \"Feature\" &&\n obstacles.geometry.type === \"Polygon\"\n ) {\n obstacles = featureCollection([obstacles]);\n } else if (obstacles.type === \"Polygon\") {\n obstacles = featureCollection([feature(getGeom(obstacles))]);\n } else {\n throw new Error(\"invalid obstacles\");\n }\n\n // define path grid area\n const collection: FeatureCollection = obstacles;\n collection.features.push(start);\n collection.features.push(end);\n const box = bbox(scale(bboxPolygon(bbox(collection)), 1.15)); // extend 15%\n const [west, south, east, north] = box;\n\n collection.features.pop();\n collection.features.pop();\n\n const columnsWithFraction =\n distance([west, south], [east, south], options) / resolution;\n const cellWidth = (east - west) / columnsWithFraction;\n\n const rowsWithFraction =\n distance([west, south], [west, north], options) / resolution;\n const cellHeight = (north - south) / rowsWithFraction;\n\n // adjust origin of the grid\n const deltaX = ((columnsWithFraction % 1) * cellWidth) / 2;\n const deltaY = ((rowsWithFraction % 1) * cellHeight) / 2;\n\n // loop through points only once to speed up process\n // define matrix grid for A-star algorithm\n const pointMatrix: string[][] = [];\n const matrix: number[][] = [];\n\n let closestToStart: { x: number; y: number };\n let closestToEnd: { x: number; y: number };\n let minDistStart = Infinity;\n let minDistEnd = Infinity;\n let currentY = north - deltaY;\n let r = 0;\n while (currentY >= south) {\n // var currentY = south + deltaY;\n const matrixRow = [];\n const pointMatrixRow = [];\n let currentX = west + deltaX;\n let c = 0;\n while (currentX <= east) {\n const pt = point([currentX, currentY]);\n const isInsideObstacle = isInside(pt, obstacles);\n // feed obstacles matrix\n matrixRow.push(isInsideObstacle ? 0 : 1); // with javascript-astar\n // matrixRow.push(isInsideObstacle ? 1 : 0); // with astar-andrea\n // map point's coords\n pointMatrixRow.push(currentX + \"|\" + currentY);\n // set closest points\n const distStart = distance(pt, start);\n // if (distStart < minDistStart) {\n if (!isInsideObstacle && distStart < minDistStart) {\n minDistStart = distStart;\n closestToStart = { x: c, y: r };\n }\n const distEnd = distance(pt, end);\n // if (distEnd < minDistEnd) {\n if (!isInsideObstacle && distEnd < minDistEnd) {\n minDistEnd = distEnd;\n closestToEnd = { x: c, y: r };\n }\n currentX += cellWidth;\n c++;\n }\n matrix.push(matrixRow);\n pointMatrix.push(pointMatrixRow);\n currentY -= cellHeight;\n r++;\n }\n\n // find path on matrix grid\n\n // javascript-astar ----------------------\n const graph = new Graph(matrix, { diagonal: true });\n const startOnMatrix = graph.grid[closestToStart!.y][closestToStart!.x];\n const endOnMatrix = graph.grid[closestToEnd!.y][closestToEnd!.x];\n const result: GridNode[] = astar.search(graph, startOnMatrix, endOnMatrix);\n\n const path = [startCoord];\n result.forEach(function (coord) {\n const coords = pointMatrix[coord.x][coord.y].split(\"|\");\n path.push([+coords[0], +coords[1]]); // make sure coords are numbers\n });\n path.push(endCoord);\n // ---------------------------------------\n\n // astar-andrea ------------------------\n // var result = aStar(matrix, [closestToStart.x, closestToStart.y], [closestToEnd.x, closestToEnd.y], 'DiagonalFree');\n // var path = [start.geometry.coordinates];\n // result.forEach(function (coord) {\n // var coords = pointMatrix[coord[1]][coord[0]].split('|');\n // path.push([+coords[0], +coords[1]]); // make sure coords are numbers\n // });\n // path.push(end.geometry.coordinates);\n // ---------------------------------------\n\n return cleanCoords(lineString(path));\n}\n\n/**\n * Checks if Point is inside any of the Polygons\n *\n * @private\n * @param {Feature} pt to check\n * @param {FeatureCollection} polygons features\n * @returns {boolean} if inside or not\n */\nfunction isInside(pt: Feature, polygons: FeatureCollection) {\n for (let i = 0; i < polygons.features.length; i++) {\n if (booleanPointInPolygon(pt, polygons.features[i])) {\n return true;\n }\n }\n return false;\n}\n\nexport { shortestPath };\nexport default shortestPath;\n","// javascript-astar 0.4.1\n// http://github.com/bgrins/javascript-astar\n// Freely distributable under the MIT License.\n// Implements the astar search algorithm in javascript using a Binary Heap.\n// Includes Binary Heap (with modifications) from Marijn Haverbeke.\n// http://eloquentjavascript.net/appendix2.html\n\nfunction pathTo(node: GridNode) {\n var curr = node,\n path = [];\n while (curr.parent) {\n path.unshift(curr);\n curr = curr.parent;\n }\n return path;\n}\n\nfunction getHeap() {\n return new BinaryHeap(function (node) {\n return node.f;\n });\n}\n\n/**\n * Astar\n * @private\n */\nexport var astar = {\n /**\n * Perform an A* Search on a graph given a start and end node.\n *\n * @private\n * @memberof astar\n * @param {Graph} graph Graph\n * @param {GridNode} start Start\n * @param {GridNode} end End\n * @param {Object} [options] Options\n * @param {bool} [options.closest] Specifies whether to return the path to the closest node if the target is unreachable.\n * @param {Function} [options.heuristic] Heuristic function (see astar.heuristics).\n * @returns {Object} Search\n */\n search: function (\n graph: Graph,\n start: GridNode,\n end: GridNode,\n options: {\n closest?: boolean;\n } = {}\n ) {\n graph.cleanDirty();\n options = options || {};\n var heuristic = astar.heuristics.manhattan,\n closest = options.closest ?? false;\n\n var openHeap = getHeap(),\n closestNode = start; // set the start node to be the closest if required\n\n start.h = heuristic(start, end);\n\n openHeap.push(start);\n\n while (openHeap.size() > 0) {\n // Grab the lowest f(x) to process next. Heap keeps this sorted for us.\n var currentNode = openHeap.pop();\n\n // End case -- result has been found, return the traced path.\n if (currentNode === end) {\n return pathTo(currentNode);\n }\n\n // Normal case -- move currentNode from open to closed, process each of its neighbors.\n currentNode.closed = true;\n\n // Find all neighbors for the current node.\n var neighbors = graph.neighbors(currentNode);\n\n for (var i = 0, il = neighbors.length; i < il; ++i) {\n var neighbor = neighbors[i];\n\n if (neighbor.closed || neighbor.isWall()) {\n // Not a valid node to process, skip to next neighbor.\n continue;\n }\n\n // The g score is the shortest distance from start to current node.\n // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.\n var gScore = currentNode.g + neighbor.getCost(currentNode),\n beenVisited = neighbor.visited;\n\n if (!beenVisited || gScore < neighbor.g) {\n // Found an optimal (so far) path to this node. Take score for node to see how good it is.\n neighbor.visited = true;\n neighbor.parent = currentNode;\n neighbor.h = neighbor.h || heuristic(neighbor, end);\n neighbor.g = gScore;\n neighbor.f = neighbor.g + neighbor.h;\n graph.markDirty(neighbor);\n if (closest) {\n // If the neighbour is closer than the current closestNode or if it's equally close but has\n // a cheaper path than the current closest node then it becomes the closest node\n if (\n neighbor.h < closestNode.h ||\n (neighbor.h === closestNode.h && neighbor.g < closestNode.g)\n ) {\n closestNode = neighbor;\n }\n }\n\n if (!beenVisited) {\n // Pushing to heap will put it in proper place based on the 'f' value.\n openHeap.push(neighbor);\n } else {\n // Already seen the node, but since it has been rescored we need to reorder it in the heap\n openHeap.rescoreElement(neighbor);\n }\n }\n }\n }\n\n if (closest) {\n return pathTo(closestNode);\n }\n\n // No result was found - empty array signifies failure to find path.\n return [];\n },\n // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html\n heuristics: {\n manhattan: function (\n pos0: { x: number; y: number },\n pos1: { x: number; y: number }\n ) {\n var d1 = Math.abs(pos1.x - pos0.x);\n var d2 = Math.abs(pos1.y - pos0.y);\n return d1 + d2;\n },\n diagonal: function (\n pos0: { x: number; y: number },\n pos1: { x: number; y: number }\n ) {\n var D = 1;\n var D2 = Math.sqrt(2);\n var d1 = Math.abs(pos1.x - pos0.x);\n var d2 = Math.abs(pos1.y - pos0.y);\n return D * (d1 + d2) + (D2 - 2 * D) * Math.min(d1, d2);\n },\n },\n cleanNode: function (node: GridNode) {\n node.f = 0;\n node.g = 0;\n node.h = 0;\n node.visited = false;\n node.closed = false;\n node.parent = undefined;\n },\n};\n\n/**\n * A graph memory structure\n *\n * @private\n * @param {Array} gridIn 2D array of input weights\n * @param {Object} [options] Options\n * @param {boolean} [options.diagonal] Specifies whether diagonal moves are allowed\n * @returns {void} Graph\n */\nexport class Graph {\n nodes: GridNode[] = [];\n diagonal: boolean;\n grid: GridNode[][] = [];\n dirtyNodes: GridNode[] = [];\n\n constructor(gridIn: number[][], options: { diagonal?: boolean } = {}) {\n this.diagonal = !!options.diagonal;\n for (var x = 0; x < gridIn.length; x++) {\n this.grid[x] = [];\n\n for (var y = 0, row = gridIn[x]; y < row.length; y++) {\n var node = new GridNode(x, y, row[y]);\n this.grid[x][y] = node;\n this.nodes.push(node);\n }\n }\n this.init();\n }\n\n init() {\n this.dirtyNodes = [];\n for (var i = 0; i < this.nodes.length; i++) {\n astar.cleanNode(this.nodes[i]);\n }\n }\n\n cleanDirty() {\n for (var i = 0; i < this.dirtyNodes.length; i++) {\n astar.cleanNode(this.dirtyNodes[i]);\n }\n this.dirtyNodes = [];\n }\n\n markDirty(node: GridNode) {\n this.dirtyNodes.push(node);\n }\n\n neighbors(node: GridNode) {\n var ret = [],\n x = node.x,\n y = node.y,\n grid = this.grid;\n\n // West\n if (grid[x - 1] && grid[x - 1][y]) {\n ret.push(grid[x - 1][y]);\n }\n\n // East\n if (grid[x + 1] && grid[x + 1][y]) {\n ret.push(grid[x + 1][y]);\n }\n\n // South\n if (grid[x] && grid[x][y - 1]) {\n ret.push(grid[x][y - 1]);\n }\n\n // North\n if (grid[x] && grid[x][y + 1]) {\n ret.push(grid[x][y + 1]);\n }\n\n if (this.diagonal) {\n // Southwest\n if (grid[x - 1] && grid[x - 1][y - 1]) {\n ret.push(grid[x - 1][y - 1]);\n }\n\n // Southeast\n if (grid[x + 1] && grid[x + 1][y - 1]) {\n ret.push(grid[x + 1][y - 1]);\n }\n\n // Northwest\n if (grid[x - 1] && grid[x - 1][y + 1]) {\n ret.push(grid[x - 1][y + 1]);\n }\n\n // Northeast\n if (grid[x + 1] && grid[x + 1][y + 1]) {\n ret.push(grid[x + 1][y + 1]);\n }\n }\n\n return ret;\n }\n\n toString() {\n var graphString = [],\n nodes = this.grid, // when using grid\n rowDebug,\n row,\n y,\n l;\n for (var x = 0, len = nodes.length; x < len; x++) {\n rowDebug = [];\n row = nodes[x];\n for (y = 0, l = row.length; y < l; y++) {\n rowDebug.push(row[y].weight);\n }\n graphString.push(rowDebug.join(\" \"));\n }\n return graphString.join(\"\\n\");\n }\n}\n\nexport class GridNode {\n x: number;\n y: number;\n weight: number;\n\n visited: boolean = false;\n parent?: GridNode;\n h: number = 0;\n g: number = 0;\n f: number = 0;\n closed: boolean = false;\n\n constructor(x: number, y: number, weight: number) {\n this.x = x;\n this.y = y;\n this.weight = weight;\n }\n toString() {\n return \"[\" + this.x + \" \" + this.y + \"]\";\n }\n\n getCost(fromNeighbor: GridNode) {\n // Take diagonal weight into consideration.\n if (\n fromNeighbor &&\n fromNeighbor.x !== this.x &&\n fromNeighbor.y !== this.y\n ) {\n return this.weight * 1.41421;\n }\n return this.weight;\n }\n\n isWall() {\n return this.weight === 0;\n }\n}\n\nclass BinaryHeap {\n content: T[] = [];\n scoreFunction: (o: T) => number;\n\n constructor(scoreFunction: (o: T) => number) {\n this.scoreFunction = scoreFunction;\n }\n\n push(element: T) {\n // Add the new element to the end of the array.\n this.content.push(element);\n\n // Allow it to sink down.\n this.sinkDown(this.content.length - 1);\n }\n\n pop() {\n // Store the first element so we can return it later.\n var result = this.content[0];\n // Get the element at the end of the array.\n var end = this.content.pop();\n // If there are any elements left, put the end element at the\n // start, and let it bubble up.\n if (this.content.length > 0) {\n this.content[0] = end!;\n this.bubbleUp(0);\n }\n return result;\n }\n\n remove(node: T) {\n var i = this.content.indexOf(node);\n\n // When it is found, the process seen in 'pop' is repeated\n // to fill up the hole.\n var end = this.content.pop()!;\n\n if (i !== this.content.length - 1) {\n this.content[i] = end;\n\n if (this.scoreFunction(end) < this.scoreFunction(node)) {\n this.sinkDown(i);\n } else {\n this.bubbleUp(i);\n }\n }\n }\n\n size() {\n return this.content.length;\n }\n\n rescoreElement(node: T) {\n this.sinkDown(this.content.indexOf(node));\n }\n\n sinkDown(n: number) {\n // Fetch the element that has to be sunk.\n var element = this.content[n];\n\n // When at 0, an element can not sink any further.\n while (n > 0) {\n // Compute the parent element's index, and fetch it.\n var parentN = ((n + 1) >> 1) - 1,\n parent = this.content[parentN];\n // Swap the elements if the parent is greater.\n if (this.scoreFunction(element) < this.scoreFunction(parent)) {\n this.content[parentN] = element;\n this.content[n] = parent;\n // Update 'n' to continue at the new position.\n n = parentN;\n // Found a parent that is less, no need to sink any further.\n } else {\n break;\n }\n }\n }\n\n bubbleUp(n: number) {\n // Look up the target element and its score.\n var length = this.content.length,\n element = this.content[n],\n elemScore = this.scoreFunction(element);\n\n while (true) {\n // Compute the indices of the child elements.\n var child2N = (n + 1) << 1,\n child1N = child2N - 1;\n // This is used to store the new position of the element, if any.\n var swap = null,\n child1Score;\n // If the first child exists (is inside the array)...\n if (child1N < length) {\n // Look it up and compute its score.\n var child1 = this.content[child1N];\n child1Score = this.scoreFunction(child1);\n\n // If the score is less than our element's, we need to swap.\n if (child1Score < elemScore) {\n swap = child1N;\n }\n }\n\n // Do the same checks for the other child.\n if (child2N < length) {\n var child2 = this.content[child2N],\n child2Score = this.scoreFunction(child2);\n if (child2Score < (swap === null ? elemScore : child1Score)!) {\n swap = child2N;\n }\n }\n\n // If the element needs to be moved, swap it, and continue.\n if (swap !== null) {\n this.content[n] = this.content[swap];\n this.content[swap] = element;\n n = swap;\n // Otherwise, we are done.\n } else {\n break;\n }\n }\n }\n}\n"]}