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 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:
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. (pg 3, fig 4)
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 interfered 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.
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.
To 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.
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.
This continuation writeup also includes support for N-gon navmesh by including makeshift triangulation through N-gon (non-tri) navmesh regions.
for each agent:
determine if in within current triangle bounds, otherwise determine if still in current region bounds
Info to store (for agent):
Info to store (for agent or/and for behaviour? storing in agent means more duplication but more flexibility):
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.
Start of development:
Tracing 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
Typically, 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)
For horde of enemies, typically this isn’t needed and a mass flowfield would do just fine with 24/7 flowfield behaviour.
The 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.
However, 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.
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.
Below 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.
Question 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.
Neverthless, 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)
On 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.
What’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).
NOTE: 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.
Then, 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..)
Also 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.
Current WIP (Desktop PCs only) Demo can be found in:
Hold 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.
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.
Simplified 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.
Additionally, 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).
As it stands now, it’s pretty good/functional even without the spinning vectors coded in yet (to handle sharp cornering).
Got 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.
Surprisingly, even without collision detection between agents, the flocking seperation behaviour works pretty good in minimising collisions of agents among one another.
You 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.
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]
borderEdge: a normal vector to separate main corridor
diagonalEdge: a normal vector to split quad main corridor into 2 triangles
Main corridor n-gon connects 2 portals. It’s either a Tri or Quad.
Dictionary[ID Key]= (Transitional) Flowfield
Multiple 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).
LRU Cache array of ids required to ensure Dictionary[ID Key] of Flowfields do not become overbloated.
(ID Key: From region starting portal edge to destination edge to all incident portals to destination)
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.