Tuesday, November 30th, 2010
The levels produced by our generator look like this:
They are a bunch of pre-made rooms thrown onto a playmap and rotated and messed around with a bit, basically. It’s a good generator, and I’ve never had any complaints about the terrain itself (although I’ve had plenty about the unit placing!). Our levels are pretty unusual in how open they are, and I hope you can see that from the picture above – many windows have good coverage of a very large proportion of the map.
I’ve been meaning for some time to produce an alternative level generator, which produces maps which are tighter – maybe a bit more like a Counter Strike map than a Tribes map for example.
Almost a year ago the infamous Lyx produced what is by a long way my favorite human-designed map – we in fact ended up using it for our first demo to PC Gamer. Don’t tell him that though. This is the map:
(I call this “Lyx1″ – I don’t think he gave it a name himself).
As you can hopefully see, this is a much tighter map with some superb deathmatch-esque flow to it. There are three main “routes” between the left and the right, producing a very replayable, differentiated experience.
I sat down yesterday and said to myself: “I want to make a generator which makes maps like that.” So I sat down and tried it. (You may want to skip down to the bottom if you aren’t interested in stories about generative content algorithms).
I started off with an algorithm which I use in the existing generator, which goes something like this.
Start off with a blank slate of the right size, and pick a random corner – top left, top right, bottom left, or bottom right:
Create a randomly sized room-shaped block there:
Partition the rest of the area into two rectangles (the cyan and blue rectangles here):
Recursively repeat in those areas:
And stop when your boxes are getting too small for rooms. Running the algorithm gives something like this:
First off we add some walls. Now we have to make sure every room is accessible from everywhere in the map. To do that, we start off with the top left room, and make a doorway to each adjacent room. Then we go to those rooms and add doorways to any rooms adjacent to them. We also make sure to add a door to the outside somewhere. Running the algorithm produces this:
Most of the hard work has been done. Now we add a few more random doors and some windows around the place:
Finally, we add some boxes for cover. There probably aren’t quite enough boxes on this particular map, and the algorithm for putting boxes outside doesn’t produce very pretty results yet… but I’m almost there. The finished level:
I admit to having picked this map as it looks especially nice, but the truth is that the vast majority of maps generated are very effective. This kind of map produces quite a different FS experience, and I’m excited to get it out there. I think the multiplayer mode that will most benefit is Disputed, but I think it’ll be good for some old fashioned Extermination too.
Here are some other maps the algorithm has produced:
And, for anyone who’s interested in such things, here’s the settings object which gives some insight into which elements of the generator can be easily tweaked. Bin is going to be using these to make some heavily differentiated single player maps:
new ScriptObject(csSettingsStandard)
{
minZoneSide = 100;
maxZoneSide = 300;
stopZoneSide = 125; // stopZoneSide mst be more than minZoneSide
minGap = 60; // basically the smallest sided new area in the initial recursion
outsideWallWidth = 10;
insideWallWidth = 8;
minEdgeWidthForDoor = 60;
doorWidth = 30;
useMiddleDoors = false;
doorEdgeSpace = 20;
windowWidth = 32;
windowDif = 3;
doorZoneSize = 40;
outsideDoorChance = 0.5;
outsideWindowChance = 0.4;
extraDoorChance = 0.3;
windowChance = 0.43;
minRoomWidthForBox = 80;
chanceForBoxInRoom = 0.6;
minEdgeWidthForBox = 80;
minBoxSurroundingSpace = 30;
minOutsideBoxSurroundingSpace = 0;
minBoxWidth = 25;
maxBoxWidth = 110;
boxHackFromWall = 10;
boxWidthRectangleTriggerSize = 50;
boxWidthRectangleSize = 40;
chanceForMultipleBoxesInRoom = 0; // this code doesn’t work so leave this at 0
boxRightAtWallChance = 0.25;
roomSizeGuaranteesBox = 150;
outsideEdgeBoxChance = 0.1;
outsideBoxDepthRange = 60;
outsideBoxTooClose = 20;
maxOutsideBoxWidth = 50;
lightChance = 0.7;
};
Posted in News | 4 Comments »
Saturday, November 20th, 2010
Apologies for the downtime guys.
Ian
Posted in News | Comments Off
Saturday, November 20th, 2010
Server is currently down – I’m working on it.
Posted in News | Comments Off
Tuesday, November 16th, 2010
Very very excited to announce this. Here’s a post by Paul which has some stuff about SP in it too. It’s late here but I’ll post more about it soon.
Thank you so much for the support everyone.
Posted in News | Comments Off
Tuesday, November 2nd, 2010
First, I’m happy to announce that we’ll be releasing an interim beta later this week which will include the new AI for random single player matches. This release will not have any of our lovely new single player stuff – it just gives the new, vastly improved AI to what is in there now. (Including explosive units for you and the AI).
Ok, and now onto the main topic.
I’ve spent the last week working on our AI. The existing AI had every response from “this is terrible” (Paul and almost everyone) to “it’s so good it must be cheating” (the guys on Three Moves Ahead). I hadn’t touched the AI code in a year, and the first thing that I’d found was that the AI was actually broken – and always has been. And the perpetrator was death animations, of all things.
A while ago we added death animations. Beforehand, when a player died the player object was deleted. But with death animations we stopped deleting the player and just set an “Alive” flag to false. This was a pretty bad design decision actually, and everywhere in the code I had to go around checking whether a player was alive, when previously a player object existing meant that it was alive.
But I forgot to tell the AI code. All of my advanced testing algorithms weren’t aware when players died in AI simulations. The AI had no good metric for determining which of its plans were any good. So it just went with the first one it made.
Anyway. I’m now going to explain what our AI does, and how it works.
Early on in my design process, I decided that I needed to split the AI up into two modules. Module 1 (which I call the DoubleDummy module, in a nod to Bridge AI) needed to be able to beat any plan. So I could feed in a plan of my units doing x,y, and z; and the DoubleDummy module would give me an emeny plan which would beat it
Module 2, the “Hand Generator” module, would generate a lot of different things the AI’s opponent might do.
I’ll be brief on how the DoubleDummy module works. It splits the turn up into ten 0.5 second snapshots (ie one at time 0, one at 0.5, one at 1, etc), and for each snapshot it calculates all the areas within reach of your units which are either (a) dangerous (aimed at by an enemy who will beat you for example), (b) neutral (not in view of any enemies for example), or (b) “Green” – you will kill someone here (behind an enemy’s back for instance). I rate all the green areas in terms of how good they are, and then try and find a path to that area without being in danger.
The DoubleDummy algorithm can produce 1 or 100 plans, all different. That will be important later. DoubleDummy can also react to multiple enemy plans – finding the one Green spot against five different enemy plans.
So once I had got DoubleDummy working, I set about on the Hand Generator – creating plans which the enemy might do. And inspiration struck. I could use DoubleDummy to make these plans without doing any extra work. And here’s how:
Take a plan for Player 1 where his units do nothing – they stay where they are. Camp basically. But they just don’t move. This is easy to generate.
Use DoubleDummy to generate plans for Player 2 which will “beat” Player 1 doing nothing. Generate say the best 5.
Use DoubleDummy to generate plans for Player 1 which will “beat” each plan generated for Player 2.
Use DoubleDummy to generate plans for Player 2 which will beat Player 1′s reactions to Player 2′s reactions to Player 1 doing nothing…
(and don’t throw away earlier plan iterations – keep them in the mix)
Continue until you run out of time.
Not only is this a brilliantly elegant solution, it actually mirrors what humans do when they play FS. They generally imagine what the opponent is going to do, and try and beat it.
So we have say 30 plans for Player 1 and 30 for Player 2. We simulate all of them against all of them, giving them points for kills and penalties for losing units, along with some other bonuses for “interesting” play. The best Player 2 plan wins.
And it works. You guys will be able to take a look later this week, and I’m looking forward to your feedback. Right now it’s beating Bin regularly, which is a pretty good accolade…
Posted in News | 8 Comments »
