Powargrid
  • Home
  • Blog
  • Buy
  • Demo
  • Media
  • Press
  • The Daily Blobbie
  • Blobbie Meme Maker
  • Forums

Our Skirmish AI is a Space Elevator

25/4/2014

0 Comments

 
Picture
Michiel told you about the development of our Skirmish AI here and here. In this post, I'll take a look from a higher vantage point. Climbing an actual space elevator would help me do that, but with a distinct lack of such devices on this little planet of ours, I'll have take that look in a non-literal way.

In "The Science of Discworld", Terry Pratchett, Ian Stewart and Jack Cohen used the space elevator* as an analogy for any process or technology that lifts a system to a new level of operation. So in that vein, the printing press, the internet and RNA are all space elevators. Being big Pratchett fans, this added use for the term space elevator stuck with Michiel and me.
Picture
So why is our Skirmish AI a space elevator in that sense? It started out as a nice first experiment in building an AI that could play Powargrid at a basic level. But since working on an AI is fun**, we happily kept adding bits of logic to it. And at one point the Skirmish AI became a computer opponent that was no longer trivial to beat, which was cool. It was at this point that we developed what you could call a Powargrid sub-hobby: watching AI versus AI matches on a skirmish map. This is also what inspired us to have an AI battle as the background for the main menu in Powargrid.
Before we got to the point where the Skirmish AI became good, we'd been working on the first three missions of the campaign. Each of those missions had a simple AI to take care of the enemy turns, so they were playable in a rudimentary way. But with our new best friend the Skirmish AI, I could suddenly drop an actual opponent into any level I designed. So I could simply think of an interesting layout for the game grid, combine it with a setup for the player and enemy bases that I thought would provide a nice challenge and then immediately test it.
And believe you me when I say that's a big step up from thinking of a mission in my head, sketching it out on paper and then asking Michiel to painstakingly code it into reality before testing whether the mission is actually any fun. This was certainly a new level of operation for mission design, so we feel that our Skirmish AI qualifies as a space elevator in the Pratchett-Stewart-Cohen sense of the word :).
Some of those missions are already in our playable alpha and others are lined up for use in later missions. And we have more mission concepts we think are fun to play, but we had to pick and choose in order to keep the campaign at an interesting length (and to be able to ever to finish this game ;).
For most missions, we do write a subclass for the AI, to handle specific aspects like Swap attacking the dam in 'Dam It' and Ford attacking the temple wall in 'Welcome to the Jungle'. An interesting case came up in 'Piece of Paradise', where you have two opponents in one team. Since team members can't damage each other's buildings, there is a possibility that one AI blocks the other. This takes the fun out of the mission, so we had to prevent that from happening. The best approach from a level design standpoint turned out to be simply have each AI leave a path for the other AI. I defined a this path but then found out that I couldn't feed a set of forbidden tiles into our pathfinder. So I called in Michiel's help and we ended up changing the Skirmish AI to accommodate these forbidden tiles. We usually shy away from changing the Skirmish AI, but it was clearly the best way to implement this. The change is also general enough that we may use it in more missions.
Picture
The tiles where yellow has built along the water are forbidden for the green AI.
The reason we shy away from changing things in the Skirmish AI is that it may affect other missions. We're quite happy with the difficulty level of the campaign, and we wouldn't want to throw it off balance by further optimizations to the AI. By now, we only change the Skirmish AI if we're sure it won't get any meaner or if it behaves stupid or silly in a non-human way. We'll probably have to branch the Skirmish AI in the future, since there are certainly things we'd still like to improve. A really nice improvement would be to teach the AI to be smarter about claiming territory by making use of bottlenecks in the play field, but that's going to be a tough nut to crack.
The last thing I'd like to say about this subject (for now) is that we plan to create an interface through which you can build your own Powargrid AI. We think it's huge fun to do so. It's not too hard to build an AI that plays the game in a (semi) sensible manner and seeing it get better with every tweak keeps you hungry for more improvements. The only risk I see is that if others do build AIs for Powargrid, the time Michiel and I spend just watching AI battles will see a significant increase. Which would eat into Powargrid development time. But I think that's a risk we're willing to take ;).
Well, that was that. We hope you enjoyed our little series on AI building. I think we'll have more to say on this subject in the future. In the meantime, be sure to let us know if you'd like to know more!

- Willem -

* A space elevator is a really interesting concept that would make bringing stuff up into space orders of magnitude cheaper than it is now (in energy and likely also in money).
** We once participated in an AI building contest for Open TTD, where we built a very mean AI together with our good friends Otto and Marnix.
0 Comments

Is this thing on?

23/4/2014

0 Comments

 
Just a quick test to see if this shows up both on Twitter and our new Facebook page. Also, have a picture of the mission we're currently working on!
Picture
0 Comments

Trailer Thrashing

20/4/2014

0 Comments

 
When Steam Greenlight came online back in 2012, we decided we wanted Powargrid on there, mostly to see what kind of feedback we would get. We already had our website with the playable alpha, we could easily take some screenshots and it wasn't that hard to write something about Powargrid. So we figured we basically had everything we needed. Except for a trailer. And since we din't want our Greenlight page to go live without a trailer, I set out to make one from scratch. I succeeded, and we were very happy with the end result. We had everything we needed, so we put up our Greenlight page (you can find it here, if you want to give us a thumbs up).
This was the result of my efforts back then:
But that trailer is a year and a half old now. Which means it's pretty dated. Powargrid looks better, feels better and runs smoother than it did back then, so it was about time to replace it with something new. I set out to remake the trailer with new video material, while keeping the basic setup the same, since we still like that. The music (by Wrathgame Studios) is great and the switches between different video fragments are fitted to it. It was just a case of recording some new videos with the new Powargrid looks. Shouldn't take that long, should it?
Well, I was wrong. I'd forgotten that recording a piece of video I'm really happy with takes time. From the small and silly things like forgetting to move my cursor off screen after clicking 'end turn' all the way up to the aesthetics of the structures you see on the game grid (by the player and the AI). That second example means looking at the game in a totally different way than what I'm used to. When all was said and done, each video fragment had taken me at least three tries to achieve the quality I was aiming for.
After the video portion was taken care of, I still needed to take a look at the text fragments. While I still like the 'Recruit 429841' joke from the first version, put in at the time because Powargrid hadn't been reviewed yet, we now have actual quotes we could use. Especially useful was a Twitter conversation with Alpha Beta Gamer, from which we could take 'A great new take on the turn based strategy genre'. This quote does triple duty; first and foremost by being a positive comment on our game. Second, it makes explicit that Powargrid is a turn based strategy game. This is too obvious to outright mention in the trailer, but having this quote makes sure that there is no question about it. Third, it indicates that Powargrid does something different from other turn-based strategy games, which we think is one of the strengths of our game but also is something we would hesitate to put in the trailer ourselves. Needless to say, we are enormously happy with what Alpha Beta Gamer has written about Powargrid :D.
After discussing the video fragments and texts with Michiel, I made the final tweaks this week and uploaded the trailer to Youtube. We loved the frame Youtube suggested for the video, so we used that :).

We hope you like the new Powargrid trailer:
- Willem -
0 Comments

#screenshotsaturday

19/4/2014

0 Comments

 
Picture
We just got included in the Indiecade #screenshotsaturday Showcase! And on top of that, we got a bunch of awesome replies on Twitter. Thanks everyone, you've got us grinning like mad :-D
0 Comments

Powargrid AI part 2: tactics

13/4/2014

0 Comments

 
I'm sorry Dave, I'm afraid I can't do that.
Welcome back to our series (part 1 here) on building the Powargrid AI! Michiel here again, and this time I'll look at the general tactics the AI uses. Our generic AI quickly became known as the "skirmish" AI, since it should be able to play a nice game of Powargrid on the skirmish maps. No mess, no fuss - just you against them, in a no-holds-barred fight to the last power plant.

We also created several specialized AIs for the
various campaign missions, and Willem will tell you more about those in the next part of the series.

I already mentioned the basic steps the AI goes through:
  • defend its own power plants
  • advance towards the opponent
  • attack whatever is in its way
  • finally, blow up the opponent's power plants
Every turn, it'll loop through these and decide what to do. There's a few simple knobs we can tweak to influence how aggressive or defensive it is. For example, a defensive AI will defend first, then, if it has any power left over, it will attack. An offensive AI will do things the other way around.
Picture
This is it! Well, this and another 1000 lines of code.
This core logic has stayed mostly unchanged, but we've tweaked the internals of each step over a period of several months, slowly making it smarter and meaner. At first, we had to give the AI a large head start (starting it off with more power plants than the player) but as it improved, we were having a hard time keeping up! Now,the AI will give you a good fight even if evenly matched. Three power plants against your two is hard, and we've not been able to beat the current version if you give it four power plants. There's a setting to give it five, if you're feeling particularly brave ;-)
Picture
Yeah, good luck with that. Let me know if you win!
After going through its main loop, there's some housekeeping to be done: maybe it should build another power plant, or build some substations to store any leftover power.

Decision making

What to attack? Where to build a new power plant? Which weapons to charge? Those are all decisions the AI has to make. We've decided on a simple approach for all of these: make a list of things, then assign them a score based on how good they are.

For example, if we're figuring out which weapons to charge:
  • Can it hit a power plant? +1000 points! Does that power plant only have one hitpoint left? Add another 1000!
  • Is it in our way, according to our pathfinding? That's 150 points.
  • Is it a weapon? Can it hit one of our power plants? 200 points. It can't? Still scary, 10 points.
  • Anything else? Well OK, have 5 points for being the wrong colour.
These numbers were determined by rigorous science I mean exquisite math well actually mucking with it until it looked good. Hey, we're not the only ones!
Then, just sort everything by their total score, and work your way down the list, charging each weapon which has more than the minimum score (or we run out of power).
One of the moves in the game, overcharging your power plants, had us pondering for a while. Overcharge, in case you haven't played the game yet (why not? go ahead, I'll wait!), boosts a power plant's output, but also damages it each turn, and you can't turn it off, so it's a a choice not to make lightly.

The AI will use it in two cases: defensively, if it's about to lose a power plant, it'll overcharge it to get some extra juice out of it. Offensively, it will overcharge a power plant only if it has more power plants than the opponent, and it could reach a strategically valuable tile but doesn't quite have enough power to get there. Again, simple rules, but the AI still manages to surprise us with a sudden charge every now and then.

Randomness

A* is great, but it is a deterministic algorithm: if you give it the same inputs, it'll give you the same results every time. In a game, this is generally not what you want. Especially in a grid based game, it's very obvious: even though "up, up, right" is equivalent to "right, up, up" and "up, right, up" in terms of getting where you want to go, the AI would have a fixed preference for one option.

To remedy that, we add a small random amount to every cost we calculate for A*. Not enough to make it choose a suboptimal path, but just random enough so that it'll make slightly different choices every time. And the effect is huge: if you look at the red and blue AIs fighting each other behind the main menu (tip: press F10 to hide the menu for a better look at the action), you'll notice that no two games are the same. In fact, we've been unable to predict which one will win, even though they are both running the same algorithms in every game they play! All because of a tiny, tiny bit of randomness.
The difference between the AI and a human is still quite visible, though. The AI is very good at math but lacks the high level overview a human player has. It doesn't see "obvious" moves where a single power line would block off and defend a large section of the board, for example. It also doesn't realize that if it had built a tower one tile away, it would be able to hit two targets at once. On the other hand, I regularly have it happen to me that I think it's left me an opening, I rush forward, and it turns out I don't have enough power to actually get there. Which it already knew, of course.

Campaign missions

So after a while, we had built a pretty decent, generic AI - put it on the field and it'll come for you! However, the campaign missions need a bit more flavour than just having differently coloured pieces rushing at you headlong, so each campaign mission is additionally scripted to make your opponents more interesting. As you play the campaign, you may notice the first couple of moves are always the same. That's the first couple of turns of the mission script being run. You can't really call that AI - it's just us deciding what we want it to do, specifically.
Picture
DO THIS BECAUSE REASONS
In addition, the AI needs to know about mission objectives. For example, in the "Dam It!" mission, it'll only attack the dam, not your power plants. In "Welcome to the Jungle", the red blobbies are trying to blast their way into some ancient ruins, while trying to keep you out of their valley, and you'll have to learn some new tricks to make it there in time!
Picture
However, in later missions, once the game's afoot, we can generally just check for some specific conditions, and then just turn it over to the generic AI. This also allows us to quickly test out missions. After designing the initial layout of the grid, we can just throw in one or more AIs and quickly get a feel for how it'll play. Willem would like to tell you more about that process, so I'll leave that to him, in a future blog post!
0 Comments

Powargrid AI part 1: intro and pathfinding

9/4/2014

0 Comments

 
I'm sorry Dave, I'm afraid I can't do that.
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.

Picture
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:

  • defend your own power plants
  • advance towards the opponent
  • attack whatever is in your way
  • finally, blow up their power plants
Before you can shoot something, though, you need to get in range, and that's what I want to talk about in this first post: pathfinding.

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!
Picture
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.
Picture
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.

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!
0 Comments

Lunch at the Garden

4/4/2014

0 Comments

 
Last Wednesday, we got the chance to demo Powargrid at the Dutch Game Garden (DGG) network lunch. The first time we've done something of the sort, so we were very curious how that would work out. Well, we've had a lot of fun there. There were only a few moments where no one was playing Powargrid and most of the time, a lot of people were looking on as well. The demo stand that DGG provided had an extra monitor at the back, so there were people all around us :).
Picture
The DGG let us use one of their very professional demo stands. Oh, and we have t-shirts with our logo :).
A lot of people told us they liked Powargrid, and those who played the game seemed to be enjoying themselves. It's hard to describe how cool it is if that's the reaction to a game you've spent almost three years on (and counting). It feels pretty amazing to say the least.
And on top of that we got feedback and tips from people who make a living building games. It varied from making things clearer for the players (for instance by showing firing range when you mouse over a weapon) to intuitive behavior we hadn't counted on (for instance dragging buildings on to the game grid instead of clicking the button) to improving the look and feel of the game (for instance by always having something moving on the screen). So we've now added a ton of stuff to our to do list that should make Powargrid that much better :).
On the business / marketing side of things, we set out to get a feel for what a reasonable retail price could be for Powargrid. This has been called the most difficult question in indie gaming and there is no way to be sure beforehand what the best price for your indie game is. We were certainly not disappointed, since we didn't just get the gut-feeling answers we were looking for, but we also spoke to some people with experience in selling games through Steam. This will help us a lot when we will eventually set the retail price. We also got some more insight in what journalists would like to see on our press page, such as something about a release date, even if it's just that the date is for now unknown.
So all in all, it was very much a fun and useful lunch at the Garden. We'll certainly visit the DGG again!
0 Comments

    Author

    We're Michiel and Willem. Hi!
    This blog is about the development of Powargrid and our experiences in doing so.

    Archives

    June 2017
    May 2017
    November 2016
    October 2016
    September 2016
    July 2016
    May 2016
    April 2016
    March 2016
    February 2016
    January 2016
    October 2015
    September 2015
    August 2015
    July 2015
    June 2015
    May 2015
    March 2015
    January 2015
    December 2014
    November 2014
    October 2014
    September 2014
    July 2014
    June 2014
    May 2014
    April 2014
    March 2014
    February 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    September 2012
    August 2012

    Categories

    All
    Game Design
    Marketing
    Progress
    Slacking
    Tech

    RSS Feed

© Wee Free Studio | Steam | Twitter | Facebook | RSS feed | Press | Contact