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
Step one; make it not look stupid!
- World divided into chunks, loaded at any time, with high latency
- Open world
- Huge environment, hundreds of characters, complex situations, long distance pathing.
- 360, PS3, possibly others – all different.
- Dynamic environment
- Things moving all the time – physics
- Varied agents
- Massive amounts of variety in actions – vehicles etc.
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
- 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.
- 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
- 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.
- 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?
- 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 🙂
- Carried around with the object
- Objects need not be convex
Dynamic layers sit on top of the static data
Part 2: Pathfinding
- 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)
- 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)
- Stuck detection, coping with bad data, good error reporting. No crashing, graceful recovery, and need to be consistent framerate.
- 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)
- 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 needed
- Craig Renolds’ steering behaviours used (with changes)
- 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
- 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
- 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