bit-gamer.net

Developer Blog: Making the AI Work

Posted on 11th Aug 2010 at 10:31 by Mode 7 with 10 comments

This week I'll hand over to Frozen Synapse's Lead Designer, Ian Hardingham, who has just had a breakthrough with creating Frozen Synapse's pathfinding engine... - Paul Taylor

I'm pleased with myself today.

The pathfinding in FS has always been atrocious – experienced players pretty much have to use shift all the time to bypass it. It’s a pain in the ass. Here’s a great example of it going wrong, below.

Developer Blog: Making the AI Work Developer Blog: Interface Design
Artificial Intelligence is no match for Natural Stupidity

The reason pathfinding sucks so much is that my algorithm for it is terrible – it splits the levels up into a grid, each square about the size of a unit. It then checks each square for obstacles. It’s a really innaccurate representation of the level.

This weekend I was reading up on advanced pathfinding stuff, and considering using some kind of Navmesh with movement polygons. Then I was hit by a flash of inspiration – the only thing that matters in FS is corners. If you ever want to make a path in FS, you only ever use the corners to get there – the only points I need in my nav-graph are the corners! Here’s my code for identifying the corners in action...

Developer Blog: Making the AI Work Developer Blog: Interface Design
The new pathfinding engine in action

As you’ll know if you’ve written A* before, the algorithm needs to know how all the navigation nodes are connected. Here’s the same level with that info included...

Developer Blog: Making the AI Work Developer Blog: Interface Design
Now with navigation nodes included

The nav-graph for that level is pretty simple though – here’s a more normal one, just so you know how complex things can be for the AI in Frozen Synapse...

Developer Blog: Making the AI Work Developer Blog: Interface Design
This is how the AI in Frozen Synapse sees levels

Yikes. Lucky computers are fast at this sort of thing! Here’s the same level that the initial algorithm got wrong, but with the new algo I knocked up this morning...

Developer Blog: Making the AI Work Developer Blog: Interface Design
The AI is now only one step away from developing SkyNet

Perfect. I am now a happy developer.

Now, back to the Q&A - if you have any questions you'd like to pit to us then just drop them in the comments and we'll address them next week!

Q: As a frothing fan of Frozen Synapse who, unfortunately, has almost no friends who play PC games, what can I do to help promote this game? - Wazzle

A: Thanks very much for offering to help! And we're glad about the frothing.

There are three major things fans can do to help us spread the word, the first of which is simply to recommend the game to friends We know a lot of people have done this and we greatly appreciate it!

Second, you can blog, tweet, post or talk about the game on the internet. Make sure all of your internet friends and acquaintances know about the game. Even just one personal blog post can make a huge difference in terms of spreading the word about the game.

After that, why not mail major sites and blogs about it? If you can see that your favourite site hasn't covered the game yet, please do send them a short polite email asking them to check it out. We still haven't managed to get any coverage on some of the big US sites, like Kotaku and Destructoid, so if you're active in those communities that could be a big help.

Q: [Regarding Mode7's post about testing] Would computer science students really be classed as 'newbies'? They're all likely to be gamers. I suppose it's easier because you don't have to explain basics, and they'll have more ideas of what to expect units to do, but surely you'd garner more from actual non-gamers? - delriogw

A: By newbies, I simply meant, "people who have never played the game before".

We always show our games to non-gamers during development and see how they react, but the information you get from people who are actually likely to be buying your game versus people way outside your intended demographic is always much more practically useful. A few testers happened to be big strategy game fans, and that was completely invaluable; equally some other people weren't really into the genre, but were still "gamers", so that provided another different slant.

Having said all that, taking our game to Nottingham Gamecity and showing it to the general public (people who, literally, wandered in off the street) was another completely different experience and also very handy.

Paul Taylor is the Joint Managing Director of Mode 7 Games, makers of Frozen Synapse, an upcoming PC strategy game.

10 Comments

Discuss in the forums Reply
geekboyUK 11th August 2010, 22:43 Quote
Cool - this is exactly how I did my pathfinding in my final year degree project! It was a simulator for people evacuating a building to measure bottle-necks in floorplan design... in other words the closest I could get to writing a game for a degree project.

Looks like a very similar method - take corner of each object, pushed out by half width of a 'person' then build net of possible next corners.... then use the net in A* ;)
stoff3r 12th August 2010, 22:21 Quote
Navigating by corners is a good idea, but how does it improve to just using smaller size squares. Surely the computer can calculate the least amount of squares to the destination?

With cpu's getting more cores and even virtual cores, is it useful for the AI-npc's to have one core each in such games?

How far are we off having the AI seeing in real time and analysing what he sees, in 3d for instance.

Does your game has more complex geometry like windows or stairs etc? And can the visuals be tweaked to other color-schemes? The default could get old pretty fast, and as bit-tech said in beta-testing, it wasn't really that readable.

Sorry for the bombardment of questions, just got really interested :D
CardJoe 13th August 2010, 08:49 Quote
Quote:
Originally Posted by stoff3r

Does your game has more complex geometry like windows or stairs etc?

I know that Frozen Synapse at least includes obstacles of different heights, allowing for window gaps and cover. You can see them in the pictures above - light blue is a low height object, which players are exposed if they stand behind unless they crouch.
Coldon 13th August 2010, 09:47 Quote
so you are simply using a waypoint based system, albeit the waypoint's are getting auto generated. Grid-based pathfinding is the least effort and the path quality is excellent.

I'm more than sure you would have had better results with a grid-based approach using an optimized A* (priority queue based), theta A* or fringe search.

Seeing as you can now navigate via corners, if you wish to move to a location that isn't a corner, I'm assuming you first have to find the nearest corner, navigate to it and then move to the final location? That is an awful amount of unnecessary work and your path lengths will end up being grossly suboptimal.

you also say that using a grid to approximate the game environment is really inaccurate, that's simply not true, short of using a near-optimal navigation mesh, grid based pathfinding offers nearly the same amount of accuracy, with the added benefit that grid based navigational map updates cost O(1) where as with a navigational mesh this will trigger a whole new subdivision and recombination routine.

Pretty much most of the modern pathfinding research is based upon grid-based navigational maps. I can link you to several papers that might prove useful in the future if you are interested.
Omroth 14th August 2010, 18:01 Quote
Hi Coldon.

"your path lengths will end up being grossly suboptimal"

This approach produces 100% optimal path lengths in every single situation.

I'm willing to accept that this approach might not be the fastest, however I'm not entirely sure how even an adjusted-grid-based system (which is required as FS' levels are vector, not grid based) would produce the optimal path without an expensive post-step to work out which parts of the grid path could be turned into diagonal movement.

I agree that the recalculation of the nav-mesh is expensive, but FS only ever has to regenerate once per turn and the recalculation takes < 1 second so it's not really a problem. In general, if I find a solution which makes 100% perfect paths in an acceptable time I don't feel the need to further optimise.
Coldon 15th August 2010, 13:41 Quote
To what are you comparing your path length optimality? If you do calculate the paths according to the nearest corner and then do the initial/final movement step to/from it, I cannot see how your paths would be optimal, perhaps you will get at best within 90% optimality but not fully optimal.

even if you level data is vector based a single grid map of the level can be generated and scaled as needed, now I'm not saying you should use grid maps, if your level data isn't dynamic then navmeshes are the way to go. Its jsut I have yet to see a single game using navmeshes in a dynamic environment, relic uses grid maps in DOW and COH.

<1 is a bit worrying, in your case, it seems the game is turn based so that's okay, but if it was real time, that time is unacceptable, for example bioware buts a 3ms constraint on pathfinding searches, so having a single component taking a massive amount of time is usually unacceptable.

I guess I am nitpicking a bit, and at the end of the day, your technique works and that's whats important.
Omroth 15th August 2010, 18:20 Quote
Can you give me a situation where you don't think it would produce an optimal result? Again - I am perfectly willing to accept I'm wrong on this one, but I haven't seen a single instance of a non-optimal route so far.

We are talking about the same meaning of "path length" yes - as in, the actual distance the unit has to travel on the path.

Ian
Coldon 15th August 2010, 22:10 Quote
http://i64.photobucket.com/albums/h185/coldon/example.jpg

in the above example the green dot being the goal, the light blue path uses the closest corner, while the dark blue is the shortest path. Obviously the light blue section is a lot longer than the dark blue. What you can do in your algorithm is, as you explore a node (pop off open list), do a line of sight check to the goal and if its successful, then you have the final path.

So you will terminate the A* search not when the closest corner found but rather when a line of sight check passes. This again is all conjecture based on my understanding of how you are doing your pathfinding, i could be making a wrong assumption somewhere along the line.
Omroth 15th August 2010, 22:48 Quote
Ah, I definitely didn't make this clear, and my apologies.

For my first step, I add the initial starting position (not a corner) as an actual node, as in I add it with all of the visible nav-nodes.

For the final step, I stop A* when I get to a node which can *see* the end node (not the closest to the end node)... is it possible that that may choose un-optimal result? I'll investigate.
Coldon 15th August 2010, 23:16 Quote
no, that sounds perfectly solid, paths generated in that way should be optimal in regards to the navigational geometry present. Thanks for clearing that up! I was pretty sure that I was missing something ;)

I think that for your current use, your selected algorithm is perfect. Though if you make the environment dynamic at a later stage, it may be necessary to use a different underlying navigational geometry.

Great work so far and best of luck in future. If you ever want to discuss pathfinding algorithms, give me a shout, I've spent the last 2 years researching realtime pathfinding in dynamic environments for my thesis.
Log in

You are not logged in, please login with your forum account below. If you don't already have an account please register to start contributing.



Discuss in the forums
Styx: Master of Shadows Review

Styx: Master of Shadows Review

31st October 2014

The Evil Within Review

The Evil Within Review

21st October 2014

Wasteland 2 Review

Wasteland 2 Review

17th October 2014