search

Glidias / yuka

JavaScript library for developing Game AI.
https://mugen87.github.io/yuka/
MIT License
0 stars 0 forks source link

WIP: Navmesh Flowfield behaviour #1

Closed Glidias closed 3 years ago

Glidias commented 5 years ago

image

Tracing out the main flow vectors. Seems correct. Will do further checks to confirm. There were some cases with shorter lengthed 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

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.

Glidias commented 5 years ago

image

The basic vector flowfield movement behaviour across fully triangulated navmesh coriridoor 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.

Glidias commented 5 years ago

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 my methods to handing Ngon navmeshes with regards to the flowfields and triangulation that isn't covered in the citeseer article.

image

image

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, my method uses a main corridor with a destination portal and some given "entrance" portal., and if outside the main corridoor, 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 , 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 scehemes 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: This method from the citeseer article is no longer used... And a simpler Arrival flowfield method is used instead as described in the latter post. image

Then, test the behaviour 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 phsysics 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: //playcanv.as/b/q88u213Y/ 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.

Glidias commented 5 years ago

Made a demo link to be mobile-friendly and performant on 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.

//playcanv.as/b/EZzcIMBY/

A simple "Arrival" flowfield approach method

image

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.

Addiionally, 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).

What's next?

As it stands now, it's pretty good/functional even without the spinning vectors coded in yet (to handle sharp cornering).

Perhaps, 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 effeiecient javascript 2d physics engine is worth considering.

Glidias commented 5 years ago

https://playcanv.as/b/rmA7brGq/

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.

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.