Path finding has been a great example of this. I've written two pathfinding systems in my life : one for the static world map of Defcon, and another for the numerous maps in Multiwinia. Both games used a pretty crude method which I was never entirely happy with, solving route-planning the same way the internet routes messages between distant routers, and for Subversion I knew i'd have to solve it properly. Despite that prior experience, it still took me three attempts to get it right.
First attempt : Basically the same system as Defcon and Multiwinia, with navigation "Flags" dotted around the world, connected to their neighbours if there was a walkable path between them. Often resulted in characters getting stuck in corners or in rooms that didn't contain a flag, and always produced routes that looked terrible, often involving sudden sharp changes in direction in the middle of an open room.
Second attempt : I wrote a system to generate a Nav Mesh based on the geometry of the world, and then used the A* route planning algorithm across that. This allows extremely efficient route planning (minimal memory usage, and very fast). However the process to generate the nav mesh is very expensive (takes a long time), and is prone to errors - doorways and small openings are often incorrectly marked as blocked, because their edges don't quite line up in 3d space. In addition, although it's possible to support dynamic scenery and obstacles, it's seriously complex to do so.
It might seem like a waste of time to be doing this job over and over again, but it's really not. Once i'd finished the Second Attempt and realised it was never going to be reliable enough, I immediately hit on the Right Way To Do It, and implemented the whole thing in about 4 hours.
Third and Final attempt : The world is rasterized onto a 2d grid. Walls produce solid grid cells that cannot be walked through. Navigation uses A* across the grid. It does use a lot of memory and there's a practical limit on how large the world can be, but it's perfect for Subversion. It can support dynamic scenery such as using shape-charge explosives to blow a hole in a wall (you simply change the relevant cells in the 2d grid), and it can support dynamic obstacles by simply rasterising them onto the same grid. Best of all, producing the 2d grid is extremely fast and error tolerant - I basically don't need to worry about navigation again.
Another issue is that generating a route, even using A*, can be quite slow - especially when no route exists, because A* has to search the entire world before it can be sure there is definitely no route. This can manifest itself as pauses in the game - ie the game freezes for a fraction of a second. It's quite noticeable, and can ruin an otherwise smooth frame rate. Using A* across a rasterized 2d grid can be done over a long period of time - several seconds if you don't mind waiting. If twenty people all decide to route plan somewhere all at the same time, this is a huge help, because you can smooth that calculation burden out over many seconds so the player doesn't notice it. The trick then is to hide this using gameplay/behaviour tricks, because you don't want the NPCs looking indecisive. Ultimately it comes down to priority - my agents in game will route plan as fast as possible, because I expect them to respond quickly to me. But an NPC sat at a desk who decides to visit the toilets - he starts planning his route but remains sitting. Several seconds later his route has been completed, and only then does he get up and start walking. Using this basic method, hundreds of NPCs can be routing around the world without affecting the smooth frame rate.
Here's a video of Subversion in action, focusing on the route planning system as it stands now. A lot of new features have been going into Subversion since Christmas, hopefully you can see some of them in this new video. The location this time is a Bank Vault, and you've basically got to rob it without using any weapons. There's still a huge amount unfinished here - the interfaces exist only at the most basic level, and it's still pretty cumbersome to play. Eventually i'll do a strong pass over the game interface and solve all of that, but for now it's functional.
It was only after I finished with the route planning that I realised what a great method this 2d grid is in general. It can be applied to virtually any complex system in game, and often takes a horrifically complex and largely unsolvable 3d space problem, and reduces it down to a much more manageable 2d grid based problem. AI events are a great example : in Multiwinia and Darwinia every single unit in-game was searching its surroundings for threats in 3d space. Literally every Darwinian would look in a 100m circle around himself for grenades, airstrikes, fire, virii, and enemy soldiers. If they saw something they'd run away from it. This is hugely expensive, and when thousands of Darwinians are battling each other there's a lot of wasted CPU time.
This entire method can be replaced with a 2d grid "heat map". The basic idea is that a threat such as a grenade "colours in" its cell in the 2d grid bright red, to mean "extremely dangerous". This 2d grid is then blurred as if you've opened it up in photoshop and applied a large pixel blur to the image. That 2d bright spot becomes a glowing area of red, with a clear gradient getting brighter as you approach the centre point. AI agents can therefore just look at their own cell for danger, and if they find it they can run away easily. This kind of system scales extremely well, with virtually zero CPU use for hundreds of NPCs responding to dangers at once. It also works well for dangers that have unusual shapes, such as Fire (which might cover a large area - that entire area just gets colours in bright red, and the blurring takes care of the rest).
- Introversion Staff
- Posts: 1138
- Joined: Sat Nov 25, 2000 7:28 pm
- Location: Cambridge, UK