Sign up for free to use this document yourself.
  • Handling flowfields with navmeshes

  • Typical gridded flowfield reference:

    https://howtorts.github.io/

  • What about non-gridded? (navmesh)

    Integrating http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.875&rep=rep1&type=pdf for handling multiple agent positions

    THe above link only shows an example of moving a single robot across a tri-navmesh. But what happens if you are moving multiple robots to a single position? The flowfield needs to account for multiple locations finally converging to that final location, which the article fails to address.

    Below is a proposed approach to implemting this in a performant manner that may also involve only calculating such flow field vectors on demand only, depending on where entities start from:


    Node Flow:
    Flow field that represents the flow field directions through every node towards a given destination within navmesh. Each navmesh “node” is a navmesh triangle polygon region and has a single direction being chosen (towards a neighboring node), to get “closer” to it’s final destination. This forms a series of portal edges are formed to produce various corridors (whether parallel or converging) towards target destination.

    Continuous Flowfield vectors in navmesh :

    Flow field vectors are calculated/stored/cached under portal edges of navmesh. ( portal edges are one directional, ie. one sided, and thus imply which node it’s headed to ) . So , a hash of key [portal edge id)] to an array of 2 vectors for its left/right vertices accordingly. Some vectors are “special” and contain rotating/trisplitting functionality as described in the article in order to smoothly navigate around corners.

    When entity enters a new node along it’s flowfield path, check:

    Does entity’s last saved portal edge contain a vertex that also belongs to last prev portal edge ( it enterered from) in the new node?

    If No, save the next earliest portal edge (from last saved portal edge onwards along flowfield direction) that meets this condition.


    All entities store it’s own reference to previous portal edge ( where it came from) , next(New) portal edge ( where it’s headed to), and last saved portal edge. This ensures a continuity of motion by relying on the any last used vertex vectors for the current triangular node its standing on, along its own path motion.

    Assertion: ( hopefully i am right. Can someone proof me wrong on this??) As long as the agent moves through each navmesh region along its stipulated flowfield path , incidentally, one vertex vector will always be picked from the last saved portal) , another vertex vector from the previous immediate neighbor portal it came from, and a new vertex vector on the new portal edge up ahead. At max only 1 new vertex vector needs to be calculated/cached for each tri node being passed though on the new portal edge if it hasn’t been calculated before.


    Possible enhancement for crowd control:

    Periodically, agents might check how crowded portals are and if it’s too crowded, determine an alternate flowfield corridoor path through navmesh along the portal graph. Additional costs can be assigned to edge portals depending on how crowded it gets. It might mean a break in continuity in motion for such cases, so these agents reset their edge portal references to start moving from scratch if they do change their path corridor.


    Global storage vector cache to support multiple flowfield paths to multitole destinations

    To universalise the cache to support multiple destinations and arbitrary routes, etc. Rather than store vectors of flowfield with just [portalEdgeId] alone as the key, add additional suffix series [portalEdgeId + incident portslEdgeIds…], ie. next subsequent incident portal edges along some flowfield path to match partial flowfield paths across a given sequence of portals starting from a given portal edge.

  • Managing flowfields for navmesh (gridless flowfields).

    This continuation writeup also includes support for N-gon navmesh by including makeshift triangulation through N-gon (non-tri) navmesh regions.

    Requirements for navmesh:

    • All common vertices at edges must be welded to uniqiely identify matching vertices by strict equality of instances.
    • precompute normals for all edge regions (or do this on demand when generating flowfield for agent) to quickly determine if in current region bounds for agent
    • portal edges requires a unique ID for navmesh (may do this on demand) to store string-concatanated keys if using Transitional flowfields.

    for each agent:
    determine if in within current triangle bounds, otherwise determine if still in current region bounds

    Info to store (for agent):

    • prevEdge, lastSavedEdge reference. ALso store prevEdgeFlowfield and lastSavedEdgeFlowfield reference in case not using persitant flowfield.
    • currentFlowfield
    • currentNavmeshRegion
    • currentTriangle (might be a currentRegion(if triangle region) or triangle fan …hmmm)

    Info to store (for agent or/and for behaviour? storing in agent means more duplication but more flexibility):

    • BFS/DFS/AStar/Dijkstra reference for path determination to final destination node
    • persitant flowfield vs transitional flowfield mode flag
    • final destination point
    • navmesh reference
    • callback function for agent (method may return a new BFS/DFS/AStar/Dijkstra reference) in the event agent finds himself outside available navmesh path, a new one can be provided (or the same updated one). If null/undefined is returned or callback isn’t provided, agent will attempt to head back to currentRegion (via closest edge).

    Agent needs to take into account if his next destination portal leads to final destination node (or if agent is already in final destination node), and adjust vectors accordingly in relation to final destination point for final destination node. This is particularly important if final destination point is moving per frame.

    Persistant flowfield:

    Works well for BFS/DFS/Astar/Dijkstra to common destination node.

    A global Flowfield that only works in relation to a single common destination node.

    // to destination portal edge
    Dictionary[From Region starting portal edge] = Triangulation (if required)

    Dictionary[Edge] = [vector for left vertex, vector for right vertex]

    Triangulation:
    borderEdge: a normal vector to seperate main coridoor
    diagonalEdge: a normal vector to split quad main coridoor into 2 triangles
    Main corridoor n-gon connects 2 portals. It’s either a Tri or Quad.

    • Indicates single main corriddoor border edge (left or right) for tri cordioor, or 2 main coridoor border edges (left and right) for quad coridoor with diagonalEdge
    • Contains any fan edges if required
    • fanEdge: a linkless standalone HalfEdge with Vertex, Normal in relation to assumed vertices within non-tri region context on left/right of main corridoor

    Transitional Flowfields:

    Dictionary[ID Key]= (Transitional) Flowfield
    Multiple flowfields to unknown final destination. Each Flowfield containing vectors for only a single region corridoor and incident portals to destination portal after it (in sequence).

    LRU Cache array of ids required to ensure Dictinoary[ID Key] of Flowfields do not become overbloated.

    Each flowfield:

    (ID Key: From region starting portal edge to destination edge to all incident portals to destination)

    • Triangulation (if required) for current region (localTriangulation)
    • New vertex vectors only stored in relation to current region’s starting/destination edge portals
      ID key must be uniquely generated/referenced for each flowfield. This means iterating along some given path until no more incdent portal is found in order to properly derive ID. Anytime an agent visits a new region along it’s given path, it will have to determine a new ID key flowfield to use for the current path the agent uses. Consider caching these ID keys (based off new region’s id), as a makeshift Dictionary[region] cache within the respective BFS/DFS/Astar/Dijkstra reference so multiple agents that share the same path reference to common destination need not recalculate ID key.

    Dictionary[Edge] = [vector for left vertex, vector for right vertex]


    Convention of flowfield key if defining from start: Always pick first longest region edge portal (that isn’t destination portal) as starting portal.

{"cards":[{"_id":"5b16245da3f28fda0f000060","treeId":"5b162471a3f28fda0f00005e","seq":18473149,"position":1,"parentId":null,"content":"# Handling flowfields with navmeshes"},{"_id":"5ab9e2306469987211000052","treeId":"5b162471a3f28fda0f00005e","seq":18514038,"position":0.5,"parentId":"5b16245da3f28fda0f000060","content":"### Typical gridded flowfield reference:\n\nhttps://howtorts.github.io/"},{"_id":"5b16242aa3f28fda0f000061","treeId":"5b162471a3f28fda0f00005e","seq":18514039,"position":1,"parentId":"5b16245da3f28fda0f000060","content":"### What about non-gridded? (navmesh)\n\nIntegrating http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.875&rep=rep1&type=pdf for handling multiple agent positions\n\nTHe above link only shows an example of moving a single robot across a tri-navmesh. But what happens if you are moving multiple robots to a single position? The flowfield needs to account for multiple locations finally converging to that final location, which the article fails to address.\n\nBelow is a proposed approach to implemting this in a performant manner that may also involve only calculating such flow field vectors on demand only, depending on where entities start from:\n\n______________\n\nNode Flow:\nFlow field that represents the flow field directions through every node towards a given destination within navmesh. Each navmesh \"node\" is a navmesh triangle polygon region and has a single direction being chosen (towards a neighboring node), to get \"closer\" to it's final destination. This forms a series of portal edges are formed to produce various corridors (whether parallel or converging) towards target destination.\n\nContinuous Flowfield vectors in navmesh :\n\n Flow field vectors are calculated/stored/cached under portal edges of navmesh. ( portal edges are one directional, ie. one sided, and thus imply which node it's headed to ) . So , a hash of key [portal edge id)] to an array of 2 vectors for its left/right vertices accordingly. Some vectors are \"special\" and contain rotating/trisplitting functionality as described in the article in order to smoothly navigate around corners. \n\n When entity enters a new node along it's flowfield path, check: \n\nDoes entity's last saved portal edge contain a vertex that also belongs to last prev portal edge ( it enterered from) in the new node?\n\nIf No, save the next earliest portal edge (from last saved portal edge onwards along flowfield direction) that meets this condition.\n\n----\n\nAll entities store it's own reference to previous portal edge ( where it came from) , next(New) portal edge ( where it's headed to), and last saved portal edge. This ensures a continuity of motion by relying on the any last used vertex vectors for the current triangular node its standing on, along its own path motion. \n\nAssertion: ( hopefully i am right. Can someone proof me wrong on this??) As long as the agent moves through each navmesh region along its stipulated flowfield path , incidentally, one vertex vector will always be picked from the last saved portal) , another vertex vector from the previous immediate neighbor portal it came from, and a new vertex vector on the new portal edge up ahead. At max only 1 new vertex vector needs to be calculated/cached for each tri node being passed though on the new portal edge if it hasn't been calculated before.\n\n----\n\n### Possible enhancement for crowd control:\n\nPeriodically, agents might check how crowded portals are and if it's too crowded, determine an alternate flowfield corridoor path through navmesh along the portal graph. Additional costs can be assigned to edge portals depending on how crowded it gets. It might mean a break in continuity in motion for such cases, so these agents reset their edge portal references to start moving from scratch if they do change their path corridor.\n\n-----\n\n### Global storage vector cache to support multiple flowfield paths to multitole destinations \n\nTo universalise the cache to support multiple destinations and arbitrary routes, etc. Rather than store vectors of flowfield with just [portalEdgeId] alone as the key, add additional suffix series [portalEdgeId + incident portslEdgeIds...], ie. next subsequent incident portal edges along some flowfield path to match partial flowfield paths across a given sequence of portals starting from a given portal edge.\n"},{"_id":"5aba331e646998721100004f","treeId":"5b162471a3f28fda0f00005e","seq":18518486,"position":1,"parentId":"5b16242aa3f28fda0f000061","content":"## Managing flowfields for navmesh (gridless flowfields).\n\nThis continuation writeup also includes support for N-gon navmesh by including makeshift triangulation through N-gon (non-tri) navmesh regions.\n\n### Requirements for navmesh:\n- All common vertices at edges must be welded to uniqiely identify matching vertices by strict equality of instances.\n- precompute normals for all edge regions (or do this on demand when generating flowfield for agent) to quickly determine if in current region bounds for agent\n- portal edges requires a unique ID for navmesh (may do this on demand) to store string-concatanated keys if using Transitional flowfields.\n\n\nNavmeshFlowfieldBehaviour:\n-------\nfor each agent:\ndetermine if in within current triangle bounds, otherwise determine if still in current region bounds\n\nInfo to store (for agent):\n- prevEdge, lastSavedEdge reference. ALso store prevEdgeFlowfield and lastSavedEdgeFlowfield reference in case not using persitant flowfield.\n- currentFlowfield\n- currentNavmeshRegion\n- currentTriangle (might be a currentRegion(if triangle region) or triangle fan ...hmmm)\n\nInfo to store (for agent or/and for behaviour? storing in agent means more duplication but more flexibility):\n- BFS/DFS/AStar/Dijkstra reference for path determination to final destination node\n- persitant flowfield vs transitional flowfield mode flag\n- final destination point\n- navmesh reference\n- callback function for agent (method may return a new BFS/DFS/AStar/Dijkstra reference) in the event agent finds himself outside available navmesh path, a new one can be provided (or the same updated one). If null/undefined is returned or callback isn't provided, agent will attempt to head back to currentRegion (via closest edge).\n\nAgent needs to take into account if his next destination portal leads to final destination node (or if agent is already in final destination node), and adjust vectors accordingly in relation to final destination point for final destination node. This is particularly important if final destination point is moving per frame.\n\n\nPersistant flowfield:\n-------------------\nWorks well for BFS/DFS/Astar/Dijkstra to common destination node.\n\nA global Flowfield that only works in relation to a single common destination node.\n\n// to destination portal edge\nDictionary[From Region starting portal edge] = Triangulation (if required)\n\nDictionary[Edge] = [vector for left vertex, vector for right vertex]\n\nTriangulation:\nborderEdge: a normal vector to seperate main coridoor\ndiagonalEdge: a normal vector to split quad main coridoor into 2 triangles\nMain corridoor n-gon connects 2 portals. It's either a Tri or Quad.\n\n- Indicates single main corriddoor border edge (left or right) for tri cordioor, or 2 main coridoor border edges (left and right) for quad coridoor with diagonalEdge \n- Contains any fan edges if required\n- fanEdge: a linkless standalone HalfEdge with Vertex, Normal in relation to assumed vertices within non-tri region context on left/right of main corridoor \n\n\nTransitional Flowfields: \n--------------------------\nDictionary[ID Key]= (Transitional) Flowfield\nMultiple flowfields to unknown final destination. Each Flowfield containing vectors for only a single region corridoor and incident portals to destination portal after it (in sequence).\n\nLRU Cache array of ids required to ensure Dictinoary[ID Key] of Flowfields do not become overbloated.\n\nEach flowfield:\n\n(ID Key: From region starting portal edge to destination edge to all incident portals to destination)\n- Triangulation (if required) for current region (localTriangulation)\n- New vertex vectors only stored in relation to current region's starting/destination edge portals\nID key must be uniquely generated/referenced for each flowfield. This means iterating along some given path until no more incdent portal is found in order to properly derive ID. Anytime an agent visits a new region along it's given path, it will have to determine a new ID key flowfield to use for the current path the agent uses. Consider caching these ID keys (based off new region's id), as a makeshift Dictionary[region] cache within the respective BFS/DFS/Astar/Dijkstra reference so multiple agents that share the same path reference to common destination need not recalculate ID key.\n\nDictionary[Edge] = [vector for left vertex, vector for right vertex]\n\n\n______________\n\nConvention of flowfield key if defining from start: Always pick first longest region edge portal (that isn't destination portal) as starting portal.\n\n"}],"tree":{"_id":"5b162471a3f28fda0f00005e","name":"HowToGridlessRTS","publicUrl":"how-to-gridless-rts"}}