{"cards":[{"_id":"5b16245da3f28fda0f000060","treeId":"5b162471a3f28fda0f00005e","seq":22532263,"position":1,"parentId":null,"content":"# Handling flowfields with navmeshes (The plan)"},{"_id":"5ab9e2306469987211000052","treeId":"5b162471a3f28fda0f00005e","seq":18514038,"position":0.5,"parentId":"5b16245da3f28fda0f000060","content":"### Typical gridded flowfield reference:\n\nhttps://howtorts.github.io/"},{"_id":"3a89a645ee7bd63a62000078","treeId":"5b162471a3f28fda0f00005e","seq":22532310,"position":0.625,"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\n\n"},{"_id":"3a89a770ee7bd63a62000077","treeId":"5b162471a3f28fda0f00005e","seq":22532311,"position":0.75,"parentId":"5b16245da3f28fda0f000060","content":"Below is a proposed approach to implanting 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\nNode Flow:\n\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. (pg 3, fig 4)\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 interfered 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\n"},{"_id":"3a89a342ee7bd63a6200007a","treeId":"5b162471a3f28fda0f00005e","seq":22532307,"position":1,"parentId":"3a89a770ee7bd63a62000077","content":"----\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"},{"_id":"5b16242aa3f28fda0f000061","treeId":"5b162471a3f28fda0f00005e","seq":22532302,"position":1,"parentId":"5b16245da3f28fda0f000060","content":"### 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"},{"_id":"5aba331e646998721100004f","treeId":"5b162471a3f28fda0f00005e","seq":22532318,"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"},{"_id":"3a898df8ee7bd63a6200007d","treeId":"5b162471a3f28fda0f00005e","seq":22532322,"position":1,"parentId":"5aba331e646998721100004f","content":"\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 separate main corridor\ndiagonalEdge: a normal vector to split quad main corridor into 2 triangles\nMain corridor n-gon connects 2 portals. It's either a Tri or Quad.\n\n- Indicates single main corridor border edge (left or right) for tri corridor, or 2 main corridor border edges (left and right) for quad corridor 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 corridor \n"},{"_id":"3a898d7cee7bd63a6200007e","treeId":"5b162471a3f28fda0f00005e","seq":22532323,"position":2,"parentId":"5aba331e646998721100004f","content":"Transitional Flowfields: \n--------------------------\nDictionary[ID Key]= (Transitional) Flowfield\nMultiple flowfields to unknown final destination. Each Flowfield containing vectors for only a single region corridor and incident portals to destination portal after it (in sequence).\n\nLRU Cache array of ids required to ensure Dictionary[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 incident 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."},{"_id":"3a89a458ee7bd63a62000079","treeId":"5b162471a3f28fda0f00005e","seq":22532313,"position":2,"parentId":"5b16245da3f28fda0f000060","content":"\n### Global storage vector cache to support multiple flowfield paths to multiple destinations \n\nTo universalize 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 portalEdgeIds...], 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":"3a89eaa3ba255c7e8400006c","treeId":"5b162471a3f28fda0f00005e","seq":22532251,"position":2,"parentId":null,"content":"## Development Journal >>"},{"_id":"3a89e874ba255c7e8400006e","treeId":"5b162471a3f28fda0f00005e","seq":22532254,"position":2,"parentId":"3a89eaa3ba255c7e8400006c","content":"### Aug 22, 2019"},{"_id":"3a89ea53ba255c7e8400006d","treeId":"5b162471a3f28fda0f00005e","seq":22532279,"position":1,"parentId":"3a89e874ba255c7e8400006e","content":"___________________\nStart of development:\n\n\n\nTracing out the main flow vectors. Seems correct. Will do further checks to confirm. There were some cases with shorter length vectors (instead of proper unit length vectors) at sharp corners. ~Did i normalize correctly? Hmm....~ Okay, fixed. Had a `.y` typo instead of using `.z`\n\nTypically, one could manage this such that: If an agent can see the target directly, he'll seek directly towards it (disable navmesh flowfield behaviour disabled) and use direct Seek behaviour for himself (among other behaviours). However, if he incidentally bumps into a wall or loses sight of target (periodic check upon getting bumped away from path , or target found to have moved, etc.), then the navmesh flowfield behaviour can be enabled again (seek behaviour disabled) to help flow him towards target and avoid crashing into \"walls\" (ie. constrain within portal corridor)\n\nFor horde of enemies, typically this isn't needed and a mass flowfield would do just fine with 24/7 flowfield behaviour. "},{"_id":"3a89e223ba255c7e84000070","treeId":"5b162471a3f28fda0f00005e","seq":22532267,"position":3,"parentId":"3a89eaa3ba255c7e8400006c","content":"### Sept 3, 2019"},{"_id":"3a89e1f5ba255c7e84000071","treeId":"5b162471a3f28fda0f00005e","seq":22532280,"position":1,"parentId":"3a89e223ba255c7e84000070","content":"### \n\n\nThe basic vector flowfield movement behaviour across fully triangulated navmesh corridor works fine (based off the article in: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.875&rep=rep1&type=pdf). What's left is to deal with the final destination node vectors and spinning vectors at sharp corners for smoother navigation. \n\nHowever, basic flow vectors for the case when adapting it to a navmesh of n-gons , causes NaN vectors/positions to come up. Probably missed out something and need to check.\n"},{"_id":"3a89e0afba255c7e84000072","treeId":"5b162471a3f28fda0f00005e","seq":22532269,"position":4,"parentId":"3a89eaa3ba255c7e8400006c","content":"### Sept 6, 2019"},{"_id":"3a89e077ba255c7e84000073","treeId":"5b162471a3f28fda0f00005e","seq":22532293,"position":1,"parentId":"3a89e0afba255c7e84000072","content":"Okay, issue solved. The Ngon Navmesh appears to be working fine after adding in collinearity portal edge/edge-to-edge checks to avoid Zero length normals/zero-area/degenerate triangles, etc. from being calculated. \n\nBelow is an informational writeup on the some methods to handing Ngon navmeshes with regards to the flowfields and triangulation that isn't covered in the citeseer article.\n\n\n\n\n\nQuestion that was considered:: what makes a good form of triangulation for the non-tri N-gons with regards to their internal localised flowfields. Currently, the method uses a main corridor with a destination portal and some given \"entrance\" portal., and if outside the main corridor, fanned flow edges are used to guide the flow to that destination portal to the left/right ends of it. Both \"entrance portal\" edge and \"destination portal edge\" cannot be col-linear since it'd result in no main corridor lane, and in such a case, a different \"entrance\" portal is used to support that, typically the next longest edge other than the destination portal. In the end, decided best to stick to a conventional form of triangulation as of above (where from a given key \"destination\" portal only, one simply decides on a \"suitable\" \"entrance\" portal given the convention of picking the next available longest side in the list, regardless of the path taken to final destination) , thus, the \"downside\" to this is that it's very possible for many agents to enter a n-gon region portal from a fanned sector rather than along the main corridor channel towards the destination portal edge . However, this apparent \"downside\" (that may sound bad on paper) doesn't appear to actually result in bad movement and sometimes might somehow yield better results in some cases Also, by simply using the destination portal as a key, it will always result in one form of triangulation (and predefined set of localised flowfields) always given a target destination portal for a given non-tri n-gon region.\n\nNeverthless, whether choosing the \"entrance\" portal edge is based purely on destination portal edge only, or also requires a path-aware starting portal direction, this requires further testing to see if if there are any downsides/upsides to that, particularly with multiple agents where the \"path-agnostic/destination-portal only\" approach might be considered \"bad\", since they'll all be flocking along the fanned edge straight towards the left/right corner of the destination portal rather than along a main stipulated path corridor), resulting in a more \"corner\" hugging destination approach to movement. Nevertheless, traffic spatial checks could be adopted to use different flowfield schemes in such cases (eg. sweep into main lane instead of corner rush, etc.), or use alternate routes/exit portals to deemed lower-costing nodes to final destination . (ie. a destination portal edge with a cost threshold, traffic adding additional costs to the destination portal edge causing agents to pick a different localised flowfield exit)\n\nOn a sidenote, perhaps, picking the edge that would give the largest surface area makes for a \"good\" triangulation for a flowfield? Well, not too sure...because what makes a \"good\" flowfield triangulation for a given polygon needs some actual criteria to begin with.\n\n--------\n\nWhat's left/missing? Deal with the final destination region flowfield vectors (to arrive at exact final destination spot at last region) and spinning vectors at sharp corners (for smoother navigation).\n\nNOTE: The \"Arrival\" destination point method in page 3, (figure 3) from the citeseer article is no longer used... And a simpler Arrival flowfield method is used instead as described in the latter post.\n\n\n\nThen, test the behavior with a crowd of agents that also flock together and avoid colliding among one another as they move to destination across flowfields, while being clamped to navmesh border edges and the 3D environment. (Basically, expend the current behaviour in the demo to use multiple entities..)\n\nAlso including box2Dlike physics with custom y-axis altitude collision filter, that uses blocking navmesh border b2dedges and also b2dcircles for agents to avoid colliding among themselves.\n\nCurrent WIP (Desktop PCs only) Demo can be found in: ~~//playcanv.as/b/q88u213Y/~~\nHold Right mouse button to pan camera...left mouse button to rotate it. F key to set point in middle of screen to set flowfield towards destination."},{"_id":"3a89dab0ba255c7e84000074","treeId":"5b162471a3f28fda0f00005e","seq":22532273,"position":5,"parentId":"3a89eaa3ba255c7e8400006c","content":"### Sept 9, 2019"},{"_id":"3a89da54ba255c7e84000075","treeId":"5b162471a3f28fda0f00005e","seq":22532291,"position":1,"parentId":"3a89dab0ba255c7e84000074","content":"Made a demo link to be mobile-friendly and performant even on legacy smartphone devices. Right-mouse-button to pan camera, mouse wheel to zoom, and left mouse button to rotate camera. For touch, Pinch with 2 fingers to pan/zoom camera.\n\n~~//playcanv.as/b/EZzcIMBY/~~\n\n### A simple \"Arrival\" flowfield approach method\n\n\n\nSimplified the final destination flowfield approach to differ from the method mentioned in the citeseer article. Basically, I'd stick to the (previously mentioned) Ngon approach for splitting up the Ngon edges into fanned triangles leading to the destination point, . (with a flow vertex zero vector at final destination point) for each n-fan sector of the n-gon. But this is also applied to triangular navmesh regions as well to adopt the same method across the board. Also, since the final destination point is a zero vector, there is no need to proportionally stretch and scale vectors to target destination, since the agent will always approach to zero velocity as he gets closer to the zero vector flow vertex destination. Thus, the edge flow vectors can simply be normalised to unit length approaching towards the zero vector point...and will ensure the agent will always stop at the given destination.\n\nAdditionally, NavMeshFlowFieldBehaviour has basic arrival \"close-enough\" distance parameter to force the agent to a stop as long as he's close enough to target (including an arrival function callback trigger). \n\n______\n\n### What's next?\n\nAs it stands now, it's pretty good/functional even without the spinning vectors coded in yet (to handle sharp cornering). \n\nPerhaps, should go ahead testing the behaviour with multiple agent entities/flocking and using the built-in Playcanvas physics engine instead (ammoJS) (rather than integrating a 2d physics engine) to handle integrated inter-agent + navmesh collisions. Not sure how performant it will run on mobile though. If not, swapping out to a more efficient javascript 2d physics engine is worth considering."},{"_id":"3a89d663ba255c7e84000076","treeId":"5b162471a3f28fda0f00005e","seq":22532276,"position":6,"parentId":"3a89eaa3ba255c7e8400006c","content":"### Sept 10, 2019"},{"_id":"3a89d615ba255c7e84000077","treeId":"5b162471a3f28fda0f00005e","seq":22532289,"position":1,"parentId":"3a89d663ba255c7e84000076","content":"https://playcanv.as/b/rmA7brGq/\n\nGot a demo up for crowd with multiple agents and flocking on navmesh through flowfield. There is an unpublished editor scene that attempts to use AmmoJS 3D physics as well to prevent inter-agent collisions, which works well on desktop as far as performance is concerned, but is too laggy to use on mobile. The above link doesnt use any physics, just flocking and flowfield behaviours together with basic environmental collision clipping.\n\nSurprisingly, even without collision detection between agents, the flocking seperation behaviour works pretty good in minimising collisions of agents among one another.\n\nYou might encounter an issue with agent getting stuck on wooden junkplanks....but that's because the extruded navmesh edge collision geometry wasnt cleaned up in those areas and could easily be fixed later."}],"tree":{"_id":"5b162471a3f28fda0f00005e","name":"HowToGridlessRTS","publicUrl":"how-to-gridless-rts"}}