It's all in your head, Part 19

The only place you'll ever hear the truth
User avatar
Chris
Introversion Staff
Introversion Staff
Posts: 1172
Joined: Sat Nov 25, 2000 7:28 pm
Location: Cambridge, UK
Contact:

It's all in your head, Part 19

Postby Chris » Tue May 04, 2010 6:51 pm

Work continues towards the Subversion "Vertical Slice" - a fully playable single location, with all graphics, sound, interface etc built to a reasonable quality level. We've made some big leaps forwards since Christmas, and i've been sitting people down in front of the game and watching them play it. Everything takes a long time in this project, and i'm not entirely sure why. Even something simple like allowing the user to plant a bug on a cctv camera has turned out to be a massive job, with interface redesigns and heavy rethinking on how the player interacts with the world. I'm overthinking everything, always looking ahead to situations that won't become problems for months, trying to design and implement everything correctly first time. This is usually a bad idea. Iterative improvement and replacement often gets you to a better solution faster than aiming for the perfect solution first time. And even if you write a system and then totally replace it, you still learn a huge amount - writing a system wrongly is often the best way to learn how to do it right.

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.

Image

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

Image
User avatar
Xocrates
level5
level5
Posts: 5262
Joined: Wed Dec 13, 2006 11:34 pm

Postby Xocrates » Tue May 04, 2010 7:03 pm

Woo! Update! With Pictures! And Video!!!

Finally there is something tangible enough for me to be excited about :D
Romanu
level1
level1
Posts: 22
Joined: Sun Jan 04, 2009 1:15 pm
Location: Brighton, United Kingdom
Contact:

Postby Romanu » Tue May 04, 2010 7:14 pm

That's awesome! Thanks for the update. Where's the video from the Bafta's also god-damnit!
User avatar
faemir
level1
level1
Posts: 20
Joined: Sun Apr 01, 2007 9:41 pm

Postby faemir » Tue May 04, 2010 7:16 pm

Very interesting hearing about the path-finding. I can't say that it ever bothered me in Darwinia the old way too, but I suppose it was sufficient enough back then.
MikeTheWookiee
level4
level4
Posts: 657
Joined: Wed Mar 07, 2007 11:58 pm
Location: Kashyyyk / Cambridge (commuting)

Postby MikeTheWookiee » Tue May 04, 2010 7:36 pm

That video is lovely. Chris, these blogs really are wonderful in that we can see how the game is accumulating from the interminable city-generation stages to now, where we appear to have some sort of game coming together. If it ends up only 10% as good as we all hope it'll be then it should become a stone-cold classic.

Bet you a pint that this
I basically don't need to worry about navigation again.
comes back to haunt you though! :)
Skah T
level0
Posts: 1
Joined: Tue May 04, 2010 7:55 pm

Re: It's all in your head, Part 19

Postby Skah T » Tue May 04, 2010 8:12 pm

Chris wrote: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).


I'm guessing your "blurring" routine will be (or is already) smarter than what you are describing here in order to account for any line-of-sight issues. Like hidden bombs, snipers hiding behind objects, etc. I wouldn't want an agent to be tipped off that I'm hiding just around the corner :)

Another neat option is to have multiple heat maps for different senses. A sight map could be defeated with a flash grenade. A sound map would propagate through doors and walls. Even a smell map might let you detect the smoke before the fire. :)
User avatar
NukeLord
level4
level4
Posts: 525
Joined: Fri Nov 03, 2006 2:08 pm

Postby NukeLord » Tue May 04, 2010 8:19 pm

Wow! Really interesting video. I'm really looking foward to this, very excited! :D
martin
level5
level5
Posts: 3210
Joined: Fri Nov 19, 2004 8:37 pm

Postby martin » Tue May 04, 2010 8:22 pm

A long time since the last update, but definitely worth it!

That heat map idea is pretty cool, as someone above me said that technique can be extended for all sorts of things. Which would mean you can have large crowds reacting realistically, which is always cool!
GENERATION 22:The first time you see this, copy it into your sig on any forum and add 1 to the generation. Social experiment.
Xeon06
level1
level1
Posts: 16
Joined: Sun Aug 13, 2006 12:46 am

Postby Xeon06 » Tue May 04, 2010 8:35 pm

God, this is so awesome. I'd pre-order it now for 100$! I'm also a game programmer and I find these technical blogs extremely interesting. My games always use the approach of looping through all entities for each entities, that heat map idea is genius.

Just watched the video, this is incredible! Reminds me of the old Mission Impossible TV show. Were these rooms and buildings procedurally generated like the cities from earlier blog posts?
Weatherproof
level1
level1
Posts: 22
Joined: Thu Jul 17, 2008 5:18 pm

Postby Weatherproof » Tue May 04, 2010 9:33 pm

Wow!! I must have said "Oh my God!!" about 5 different times while watching that video!
Also, great talk about the process of developing a pathfinding system, it was a great read!
Keep up the good work and I can't wait for the next update! :D
User avatar
Wasgood
level5
level5
Posts: 1082
Joined: Sat Sep 02, 2006 11:44 am

Postby Wasgood » Wed May 05, 2010 2:22 am

/me twitches
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Postby xander » Wed May 05, 2010 3:01 am

Okay, this may be a really, really stupid question, but googling A* related stuff does not really answer it: for several of the paths calculated (nearly all that I saw?), near the end of the path there is a little ``wiggle.'' What is that all about?

Also, and this may be really nit-picky (and may not even be right), but the bathrooms seem off to me. Most of the public restrooms that I have seen around here are built such that all of the toilets are along a common wall (like this diagram):

Code: Select all

+------+------+
|    oO|Oo    |
|      |      |
|    oO|Oo    |
|      |      |
+  ----|----- +


I assume that this is done so that fewer pipes have to be run. Again, this may not be true everywhere, but it seems to be the rule around these here parts.

xander
User avatar
elexis
level5
level5
Posts: 1466
Joined: Fri Aug 24, 2007 6:11 am
Location: Australia
Contact:

Postby elexis » Wed May 05, 2010 3:30 am

Don't know about the A* thing, but the male/female toilets are definetely not on a common wall here, although vertically (ie between levels) all the toilets line up.
User avatar
Ace Rimmer
level5
level5
Posts: 10803
Joined: Thu Dec 07, 2006 9:46 pm
Location: The Multiverse

Postby Ace Rimmer » Wed May 05, 2010 4:10 am

Awesome video. I will definitely be playing Subversion.

Regarding toilets, perhaps it's an American thing? I agree that they typically seem to be on a common wall unless separated by another structure (e.g. elevators/lifts).
Smoke me a kipper, I'll be back for breakfast...
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Postby xander » Wed May 05, 2010 4:13 am

elexis wrote:Don't know about the A* thing, but the male/female toilets are definetely not on a common wall here, although vertically (ie between levels) all the toilets line up.

It may just be an American thing. What about the rotation of the toilets? Should they at least be rotated so that the tanks are all on the same wall?

xander

Return to “Introversion Blog”

Who is online

Users browsing this forum: No registered users and 11 guests