These are my notes from Streaming Open World Pathfinding, Quinn Dunki. Very interesting, and some unique ways to cut down the processing time to make it fast and cheap. Find the slides on her site.

These mainly mirror the slides in progression, with some additional stuff (if it does seem similar 🙂 ). The questions start near the end, for some extra info.

Streaming open world pathfinding – Saboteur

Pathfinding basics:

Step one; make it not look stupid!

Challenges

• Streaming
  • World divided into chunks, loaded at any time, with high latency
• Open world
  • Huge environment, hundreds of characters, complex situations, long distance pathing.
• Multiplatform
  • 360, PS3, possibly others – all different.
• Dynamic environment
  • Things moving all the time – physics
• Varied agents
  • Massive amounts of variety in actions – vehicles etc.

Pre-plan

Long distance + cheap = Static?
But need some kind of dynamic layer – physics stuff changes the world.
Streaming needs to chop up the data too.

Part 1: The Data

Not enough time to polish 9KM of area – good code to deal with the data we have.

• Static layer
  • Need AI representation of world
  • Havok? – too spendy (phantoms and other queries are too expensive)
  • Cellmaps/Navmeshs? – too labour expensive since needs manual work (no known perfect software version)
  • Need simple data, robust code

Solution: Fences

• Pseudo 2D – cheap raycasts etc.
• 100x cheaper then havok
• Generated automatically and modifiable
• Fancy tool – worth every hour spent on it. Spend one hour, save 10 hours (in the project the are more limited by design (level/game) and art)
  • Adds barriers around things which get in the way

Labels for 3d (3d is still required!)

• Interiors, multiple floors, stairs, etc.
  • Good: picks appropriate label. Bad: Cost of checking which label we should be using
  • Bad: It doubles a lot of your raycasts (a cliff; can go down, but not up a cliff)
• Next time: just use Y components? (for heights etc.)

Need also cover and other information on the graph.

Graph generation

• Nodes at object extents – standard
• Connection algorithm – not so standard. Different sized agents – vehicles, etc. . Assumed it was for people (which are 95% of them) and do the rest specially. No reason to do a big generic system for it

Connection algorithm

• Lots of testing/prototyping but no whitepaper 🙂
• Connect each fence internally. Get the connections that matter – only need one main connection between spaces.
• Points of closest approach – cardinally
• Fully connect overlapping – use N^2 tests – fences can overlap and stuff.
• Connect by proximity – clears up problems of not using N^2 to get all connections
• Fully connect stitch nodes

Does it work?

• Good: Low density of data – fast to search
• Bad: Low fidelity paths – needs smoothing! (Going along a path on the sides of a road instead the middle for instance)
  • But okay, smoothing cheaper then searching.

Data subdivision

• Stream blocks – 200m2 – static fence data, physical data, etc. etc.
• Static fences overlap blocks. For this, it’s replicated for both – no huge cost there.
• Stitch nodes around borders – basically, at edges of a block, the points need to be connected to each other – stitches the two blocks together.

Export process – building the data

• SMED – Saboteur Map Editor
  • Export anything that doesn’t change in the game, to remove loading
• Iteration, iteration, iteration

That’s all great – what if something moves?
Dynamic layer

• Can’t modify the data that is there (else why export it in the first place if we can do it all in real time?)
• Add on top dynamic fences (based of Full Spectrum Warrior which added nav meshes)

Dynamic fence generation

• Done in SMED – one per havok object.
• For 99.9% of objects, they are square, so it is dead easy.

What happens when it tips over?

• Project bounding box down
• Vertices create point cloud
• sort points in cloud CCW
• Eliminate concave angles

Good approximation, but in some odd cases it goes wrong – big L shape things. But nothing can walk into the object 🙂

Dynamic graphs

• Carried around with the object
• Objects need not be convex

Dynamic layers sit on top of the static data

Part 2: Pathfinding

Static:

• A* – if it ain’t broke
• Devil is in the details – hundreds of agents, crowds, and other cases.

Where to begin and end?

• Find nodes near our extrema, quickly!

Cellmaps – too labour intensive

Quadtree – too slow to modify

Old school – grid

• Each grid square keeps nodes in it.
• Simple concentric ring search. Exponentially expensive!
• Have as many nodes as possible – but this is at odds with the less data approach

A* path on static graph

• Fast, looks like crap (the walking on the side of the road)
• Smoothing
  • Visible points tightening, although some cases it fails, but meh, can work fine in most cases.

Smoothing cannot eliminate nodes (IE: don’t as a cost saving, people walking around don’t do hitting code anyway)

Streaming static data

• Wait for it to load. Might be 10 frames or more!
• Paths spanning stream blocks
• Try to look busy – start walking? Try walking in general direction (but can look STUPID if it takes a while for the data – try other things, look busy)

What happens when a crate is in the way?

• Should go around it!
• dynamic fenes detected as we walk (ray tracing, fast!)
• Subpath around it
  • dynamic mingraph tells us how to get around it
  • brute force for extrema – lot amount of nodes to check, so still fast
  • Stitch into current path – keep walking. Form of lazy evaluation. Can’t modify the data which is very expensive!
• What if the crate moves?
  • Who cares?
  • If it hits me, we go ragdoll anyway.
  • Special cases; cars and suchlike.

Too simple; what about a pile of crates?

• Close group of fences form clumps
• A clump becomes one object. Combined objects graph used for the search if we need to go around this (ray tracing to notice it’s in the way)
• Clumps update periodically
  • Why not do it when things change? It doesn’t work perfectly.
  • So do every clump
• For the graph around clumps, do some simple checking for the outside A* points (same code as for when objects tip over)

Robustness

• Stuck detection, coping with bad data, good error reporting. No crashing, graceful recovery, and need to be consistent framerate.

Handling failure

• Retry a few times
• Try and look busy while doing this (animations)
  • escape from fences
• Give up andlook angry – be aware, feedback, annoyed (eg; cars piled up in the way)

Optimization

• Pathfinding – A*, extrema, smoothing
• Clump updating can be done on different threads, load balancing on multiple CPU’s, and is the easiest part of the AI to do this.
• Raycasts and ms budgets – no need for doing it over frames (it’s that fast)
• Grid – extrema node finding, fence searching, label lookup and other bits.

Path following

• Path following needed
• Craig Renolds’ steering behaviours used (with changes)

Crowd avoidance

• Find people within ellipse
• Steering forces
• Stop if would otherwise steer oddly -people stop in real life!
• Personal space – the facing of the target (don’t walk into their eyes)
• Choose a side to avoid them on

Acceleration and deceleration in corners, at destinations

• No collision between characters
  • It’s too expensive, and with great avoidance is not needed!

LOD on path following

• Level 1: No crowd avoidance
• 2: No steering, linear interpolation
• 3 – Timed teleportation

Dynamic data invalidating a static path?

• assumption is there is always around the dynamic
• As long as the AI reacts it’s fine, and happens only with huge player involvement

Hierarchical pathfinding?

• Mixed feelings – hard to make them look good with sparse data

What if the distance is too far and we can’t path it all

• 1.5KM distances loaded at once (200x200M blocks), so usually not a problem
• People can exist outside streamblocks, use teleports and special rules for missions

Middleware?

• Not really checked it, decided to handle themselves since they have lots of middleware and there are problems integration

How do you address cover?

• Fence data used for it

AI breaking blocking objects?

• Nazi’s can’t be too clever (bumbling fools)
• Things can break however, just not done.

When taking cover behind objects, some might be too small.

• Uses raycasting, since it doesn’t need to be sorted that often