Compromise-free pathfinding on a navigation mesh

Michael L. Cui, Daniel D. Harabor, Alban Grastien

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    Abstract

    We want to compute geometric shortest paths in a collection of convex traversable polygons, also known as a navigation mesh. Simple to compute and easy to update, navigation meshes are widely used for pathfinding in computer games. When the mesh is static, shortest path problems can be solved exactly and very fast but only after a costly preprocessing step. When the mesh is dynamic, practitioners turn to online methods which typically compute only approximately shortest paths. In this work we present a new pathfinding algorithm which is compromise-free; i.e., it is simultaneously fast, online and optimal. Our method, Polyanya, extends and generalises Anya; a recent and related interval-based search technique developed for computing geometric shortest paths in grids. We show how that algorithm can be modified to support search over arbitrary sets of convex polygons and then evaluate its performance on a range of realistic and synthetic benchmark problems.

    Original languageEnglish
    Title of host publication IJCAI 2017
    Subtitle of host publication26th International Joint Conference on Artificial Intelligence
    EditorsCarles Sierra
    Place of PublicationPalo Alto CA USA
    PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
    Pages496-502
    Number of pages7
    ISBN (Electronic)9780999241103
    ISBN (Print)9780999241103
    Publication statusPublished - 2017
    EventInternational Joint Conference on Artificial Intelligence 2017 - Melbourne, Australia
    Duration: 19 Aug 201725 Aug 2017
    Conference number: 26th
    https://ijcai-17.org/

    Conference

    ConferenceInternational Joint Conference on Artificial Intelligence 2017
    Abbreviated titleIJCAI 2017
    CountryAustralia
    CityMelbourne
    Period19/08/1725/08/17
    Internet address

    Cite this

    Cui, M. L., Harabor, D. D., & Grastien, A. (2017). Compromise-free pathfinding on a navigation mesh. In C. Sierra (Ed.), IJCAI 2017: 26th International Joint Conference on Artificial Intelligence (pp. 496-502). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI).
    Cui, Michael L. ; Harabor, Daniel D. ; Grastien, Alban. / Compromise-free pathfinding on a navigation mesh. IJCAI 2017: 26th International Joint Conference on Artificial Intelligence. editor / Carles Sierra. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2017. pp. 496-502
    @inproceedings{e81dff93193447a2af54042c9387ba1a,
    title = "Compromise-free pathfinding on a navigation mesh",
    abstract = "We want to compute geometric shortest paths in a collection of convex traversable polygons, also known as a navigation mesh. Simple to compute and easy to update, navigation meshes are widely used for pathfinding in computer games. When the mesh is static, shortest path problems can be solved exactly and very fast but only after a costly preprocessing step. When the mesh is dynamic, practitioners turn to online methods which typically compute only approximately shortest paths. In this work we present a new pathfinding algorithm which is compromise-free; i.e., it is simultaneously fast, online and optimal. Our method, Polyanya, extends and generalises Anya; a recent and related interval-based search technique developed for computing geometric shortest paths in grids. We show how that algorithm can be modified to support search over arbitrary sets of convex polygons and then evaluate its performance on a range of realistic and synthetic benchmark problems.",
    author = "Cui, {Michael L.} and Harabor, {Daniel D.} and Alban Grastien",
    year = "2017",
    language = "English",
    isbn = "9780999241103",
    pages = "496--502",
    editor = "Carles Sierra",
    booktitle = "IJCAI 2017",
    publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
    address = "United States",

    }

    Cui, ML, Harabor, DD & Grastien, A 2017, Compromise-free pathfinding on a navigation mesh. in C Sierra (ed.), IJCAI 2017: 26th International Joint Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 496-502, International Joint Conference on Artificial Intelligence 2017, Melbourne, Australia, 19/08/17.

    Compromise-free pathfinding on a navigation mesh. / Cui, Michael L.; Harabor, Daniel D.; Grastien, Alban.

    IJCAI 2017: 26th International Joint Conference on Artificial Intelligence. ed. / Carles Sierra. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2017. p. 496-502.

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    TY - GEN

    T1 - Compromise-free pathfinding on a navigation mesh

    AU - Cui, Michael L.

    AU - Harabor, Daniel D.

    AU - Grastien, Alban

    PY - 2017

    Y1 - 2017

    N2 - We want to compute geometric shortest paths in a collection of convex traversable polygons, also known as a navigation mesh. Simple to compute and easy to update, navigation meshes are widely used for pathfinding in computer games. When the mesh is static, shortest path problems can be solved exactly and very fast but only after a costly preprocessing step. When the mesh is dynamic, practitioners turn to online methods which typically compute only approximately shortest paths. In this work we present a new pathfinding algorithm which is compromise-free; i.e., it is simultaneously fast, online and optimal. Our method, Polyanya, extends and generalises Anya; a recent and related interval-based search technique developed for computing geometric shortest paths in grids. We show how that algorithm can be modified to support search over arbitrary sets of convex polygons and then evaluate its performance on a range of realistic and synthetic benchmark problems.

    AB - We want to compute geometric shortest paths in a collection of convex traversable polygons, also known as a navigation mesh. Simple to compute and easy to update, navigation meshes are widely used for pathfinding in computer games. When the mesh is static, shortest path problems can be solved exactly and very fast but only after a costly preprocessing step. When the mesh is dynamic, practitioners turn to online methods which typically compute only approximately shortest paths. In this work we present a new pathfinding algorithm which is compromise-free; i.e., it is simultaneously fast, online and optimal. Our method, Polyanya, extends and generalises Anya; a recent and related interval-based search technique developed for computing geometric shortest paths in grids. We show how that algorithm can be modified to support search over arbitrary sets of convex polygons and then evaluate its performance on a range of realistic and synthetic benchmark problems.

    UR - http://www.scopus.com/inward/record.url?scp=85031899853&partnerID=8YFLogxK

    M3 - Conference Paper

    SN - 9780999241103

    SP - 496

    EP - 502

    BT - IJCAI 2017

    A2 - Sierra, Carles

    PB - Association for the Advancement of Artificial Intelligence (AAAI)

    CY - Palo Alto CA USA

    ER -

    Cui ML, Harabor DD, Grastien A. Compromise-free pathfinding on a navigation mesh. In Sierra C, editor, IJCAI 2017: 26th International Joint Conference on Artificial Intelligence. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2017. p. 496-502