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.
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...
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...
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...
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...
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.
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.
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...
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...
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...
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...
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 ReplyLooks 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* ;)
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
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.
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.
"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.
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.
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
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.
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.
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.