Hi there! Michiel here, with the first post in a short series on the Powargrid AI (Artificial Intelligence) - the algorithms that control the computer players.
The AI is what you'll be playing against in the single player campaign and the skirmish mode.
In this first post, I'll give you a quick overview, and then wander off (if you'll pardon the pun) into pathfinding.
The AI is what you'll be playing against in the single player campaign and the skirmish mode.
In this first post, I'll give you a quick overview, and then wander off (if you'll pardon the pun) into pathfinding.
In blue: you, our heroic protagonist. In green, Zealot Zomg, who is actually just a set of algorithms. In yellow, Chairman Swap, who is also algorithms.
So what's the goal of an AI? At first glance, it seems simple enough - it should play Powargrid, and try to win! However, an AI that's mercilessly good is actually not what you want in a game. The ultimate goal is to make sure the player has fun playing against it!
Our plan was to throw a simple "placeholder" AI together, then figure out how to do it properly. What actually happened was that we just kept improving that initial prototype. We'd sit back with a beer and figure out what rules, tactics, patterns and heuristics we'd been using when playing ourselves, then try to teach them to the computer.
The basic behaviours are pretty simple:
The basic behaviours are pretty simple:
- defend your own power plants
- advance towards the opponent
- attack whatever is in your way
- finally, blow up their power plants
Pathfinding
Pathfinding is figuring out how to get from A to B. In Powargrid, A is usually wherever your buildings are, and B is the spots where you can shoot at those juicy, juicy powerplants of your opponent. People are great at pathfinding - we can take one look at a game board and see exactly where to go thanks to our massively parallel visual system.
Unfortunately, a computer is basically looking at the board through a tube that's one tile across. Suddenly, just figuring out where to go is hard - try it!
The granddaddy of pathfinding is an algorithm called A* (A-star). It's one of my favourite algorithms! I'll try (and fail) to be brief, since there's loads of good reading already available online. Amit Patel of Red Blob Games has an awesome series on pathfinding in general and A* in particular. It's a must read for anyone in game dev, and there's much more great stuff there!
I'll try to sum up A* in a few sentences, though, and how it applies to Powargrid.
A* works on any grid - it just needs to be told which points are connected to which others. In Powargrid, that's just the tiles of the playfield and their neighbours.
To find a path, you give it a list of tiles you want to go, and which tiles to start from. If we're trying to attack another player, we can start from any tile we already built on, and we're looking to reach any tile from which we can shoot at their power plants.
Then, for every tile it currently knows, A* looks at its neighbours and estimates how far each might be from the goal. In our case, that estimate is easy! It's just how many tiles the target is away, horizontally and vertically (this is called the Manhattan distance because it's like measuring distance in city blocks). It then continues finding a path by looking at the best estimates first, which makes it much faster than just looking at everything. And it still guarantees you it'll find the shortest possible path!
Unfortunately, a computer is basically looking at the board through a tube that's one tile across. Suddenly, just figuring out where to go is hard - try it!
The granddaddy of pathfinding is an algorithm called A* (A-star). It's one of my favourite algorithms! I'll try (and fail) to be brief, since there's loads of good reading already available online. Amit Patel of Red Blob Games has an awesome series on pathfinding in general and A* in particular. It's a must read for anyone in game dev, and there's much more great stuff there!
I'll try to sum up A* in a few sentences, though, and how it applies to Powargrid.
A* works on any grid - it just needs to be told which points are connected to which others. In Powargrid, that's just the tiles of the playfield and their neighbours.
To find a path, you give it a list of tiles you want to go, and which tiles to start from. If we're trying to attack another player, we can start from any tile we already built on, and we're looking to reach any tile from which we can shoot at their power plants.
Then, for every tile it currently knows, A* looks at its neighbours and estimates how far each might be from the goal. In our case, that estimate is easy! It's just how many tiles the target is away, horizontally and vertically (this is called the Manhattan distance because it's like measuring distance in city blocks). It then continues finding a path by looking at the best estimates first, which makes it much faster than just looking at everything. And it still guarantees you it'll find the shortest possible path!
Straight line distance (green) vs Manhattan distance (the other three)
However, you can't always take the shortest path. In Powargrid, enemy pieces will block the way, and the grid is not always a neat rectangle.
This is not a rectangle. This is a jungle.
To find the best path, you tell A* the cost of traveling from one tile to another. This is where the wonderful versatility of the algorithm comes from: you can make up any cost you like, and define what the "best path" actually means.
In Powargrid, we tell A* your own tiles are cheap - you already own them! Empty tiles are a little more expensive, since you'll have to spend power to actually build something on them. Tiles occupied by an opponent are much more expensive, because you'll have to build and charge weapons to blast through them. The costs are 1 point for your own tiles, 3 for empty tiles, and 20 for enemy tiles. That means the AI will make a 7 tile detour if it can avoid going through one of your buildings.
These simple rules will make the AI build around your buildings, unless the path gets too long. Then it'll just plop down a tower and shoot you inna face.
Defending also uses pathfinding, but the other way around: the AI knows how much power you'll have next turn, and figures out where you'll be able to go. If that includes places where it would like you not to be, it'll claim those tiles itself.
In Powargrid, we tell A* your own tiles are cheap - you already own them! Empty tiles are a little more expensive, since you'll have to spend power to actually build something on them. Tiles occupied by an opponent are much more expensive, because you'll have to build and charge weapons to blast through them. The costs are 1 point for your own tiles, 3 for empty tiles, and 20 for enemy tiles. That means the AI will make a 7 tile detour if it can avoid going through one of your buildings.
These simple rules will make the AI build around your buildings, unless the path gets too long. Then it'll just plop down a tower and shoot you inna face.
Defending also uses pathfinding, but the other way around: the AI knows how much power you'll have next turn, and figures out where you'll be able to go. If that includes places where it would like you not to be, it'll claim those tiles itself.
Next time
That "short detour into pathfinding" I had in mind actually turned out rather longer than I expected. I'll end part 1 here, and continue the story in the next part. See you soon!
RSS Feed