Red Brick Games

Archive for the ‘RTS maps’ Category

Making the A.I. fortify bottlenecks - part 3

Tuesday, August 26th, 2008

Fortifying bottlenecks is now working!

I’ve got all the basics working. Each A.I.-controlled base now:

examines the terrain around the base,
analyzes it into passages and junctions,
stores the passages and junctions into a Boost graph object,
culls passages that are dead ends (i.e. passages that don’t lead to danger)
semi-randomly picks a frontier among the remaining passage(s),
evaluates the frontier of passages for its merit,
repeats steps 5.-6. until a “high-merit” frontier is found; and finally
builds towers to fortify that frontier

It works beautifully. I’ve been trying to take some screenshots that show it in action (somewhat tricky to do):

- - - -

Here’s a purple base (far left) facing off against an orange base (right). The orange squares show the orange base’s defensive frontier:

pardon all the debugging text!

You can see the orange base keeps its defensive frontier just out-of-range of Purple’s towers. (The one tower in the middle is Orange’s, not Purple’s).

- - - -

A screenshot from later in the game. Notice that purple has moved his line of towers forward. The A.I. dynamically adjusts its defensive frontier as conditions change in the game, and has a tendency to “push” a line of towers forward, just like a real RTS player often does.

- - - -

Another screenshot, showing the nodes and edges of the Orange base’s defensive graph. The graph reflects the topology of the terrain, though you have to squint to see that.

- - - -

Here, the thick green squares represent the green player’s defensive frontier. The A.I. did a great job in this case - the chosen frontier is (almost) the narrowest point of the entrance onto Green’s plateau. In other words, the A.I. correctly picked the best location.

Picking an optimal defensive location may be obvious and easy to a human player, but getting the A.I. to do it is hard! Sometime, I’d like to post screenshots from other RTS games — AAA ones at that — that don’t choose defensive spots this well! If you’re a long-time RTS player, I’m sure you know what I’m talking about.

- - - -

Another nice defensive line, guarding the approach to a red base.

- - - -

Here’s a screenshot from the greatest game of Orcs vs. Martians I’ve played to date. The random map was fantastic, every A.I. player played well, the defensive frontiers were great, and a huge drawn-out battle developed in the valley at the center-top of the screen.

click for full-size

As you can see, the blue A.I. went a little hog-wild with his defensive towers. Earlier, there was an enemy to his lower-left, which is why all those blue towers are there.

- - - -

The A.I. charging into the “valley of death”.

click for full-size

The reason why so many towers are everywhere, is that the defensive frontier(s) moved several times, so the A.I. kept building new lines of towers.

There’s still some work left to do on this feature. For example, preventing the A.I. from over-fortifying beyond what the A.I. really needs. But all the basics are implemented, and the feature is working great :-)

I feel like this feature really adds to the quality of the gameplay. The A.I. now fights with towers, not just troops! The A.I. can try to push you back using mostly towers, like human players do. Also, I’ve noticed that pitched battles develop much more frequently now. I LOVE pitched battles, with the sieging of some strategic map location, that requires one side to come up with a breakthrough, in either technology or tactics.

So, a big step forward!

The next step is to make the A.I. fortify bases cooperatively. Right now, each base thinks and fortifies independently. That causes a certain amount of unnecessary fortification, i.e. between friendly bases. It’d be more efficient for multiple bases to think together and choose a common frontier that surrounds all friendly bases, assuming they’re close enough. Such a “cooperative” defense frontier could even encompass bases of different players. Even bases of both human and A.I. players.

…Which has some pretty neat implications. Picture yourself located on the front lines in a game, struggling to stay alive…and your A.I. ally(s) come up and start helping you to fortify your base! How often does that happen in an RTS game? Usually, A.I. allies act as though you don’t exist, or worse! With cooperative defense, your A.I. allies would proactively come help you, if they perceive your defenses to be the weakest link. How cool would that be.

Ah…

Can you tell I’m happy about this :-)

Posted in RTS maps, A.I., Gameplay | No Comments »

Making the A.I. fortify bottlenecks - part 2

Tuesday, July 29th, 2008

The A.I. work on placing towers at natural bottlenecks in the terrain is coming along pretty well. I implemented a quick, “dumb” algorithm to try it out. Its effect on gameplay is pretty favorable - that is, when the “dumb” algorithm works. Which is not very often.

I’ve been thinking about this problem some more. Finding ideal defensive bottlenecks, at which to build fortifications, is pretty hard to do.

I shouldn’t be surprised; now that I think about it, not a single RTS game I’ve ever played has had A.I. that did this very well. Maybe there are some out there, but I haven’t played them. Usually, the A.I. would just build a huge rectangular wall around each base. In those cases, the A.I. obviously wasn’t analyzing the terrain for optimal defense locations at all. Case in point: remember Age of Empires 2? Yes…then you know what I’m talking about :)

I want Orcs vs. Martians to do better than that.

Technicals

Ok, so here’s an update to my algorithmic approach.

To simplify the implementation, I’ve thrown away that first step I mentioned about finding terrain bottlenecks for the entire world. I think I can still find very-nearly-optimal bottlenecks around a particular base without it (and the resulting alg will likely be faster, too).

Next, the frontier-walk, the one that starts from the base to be defended, needs to be made smarter.

My current thinking is that the frontier-walk needs to keep track of individual sub-frontiers, within the main frontier. I see this as being absolutely key to solving this problem. Each sub-frontier represents a “passage”, or an “entrance”, to the base. Initially, as you walk away from the base, there’s just the single frontier. But as the frontier collides with cliff walls, water, or other un-walkable tiles, it splits into these sub-frontiers, which then “walk” down the passages independently.

The sub-frontiers are necessary, because you need to analyze separately each passage that leaves the base. Why? Because many of those so-called “passages” will dead-end! Those passage don’t need to be defended, and shouldn’t count towards the “cost” of the frontier. Defending them would waste resources (and look dumb in the game), and counting their cost could make the algorithm pick a sub-ideal frontier.

After walking the passages, and finding each passage’s narrowest point, then roughly speaking, you’ve got the solution. The ideal defensive frontier is: the collection of narrowest gaps, on each passage that leaves the initial base.

…of course, it’s actually a little more complicated than that. Passages will often re-combine with each other, as they lead away from the base. So, as the passages branch out from the base, they don’t form a simple tree structure. They really form a directed acyclic graph (DAG).

The output of walking the passages will be this DAG. Each node in the DAG represents a sub-passage, and each sub-passage has its own narrowest gap.

And to really find the ideal defensive frontier, the DAG needs to be depth-traversed and analyzed, rather than just examining the immediate passages that leave the base. That’s because the ideal frontier may be further down the passages, after the passages branch and merge several times.

And, the “ideal” frontier is not only about narrowest gaps. If the A.I. is playing to win, it also wants to control as much territory as possible. So you’re also trying to maximize the amount of land area, that lies behind the defensive frontier.

So roughly speaking, in Orcs vs. Martians’s case, the merit of any particular defensive frontier is:

decreased by size of the frontier (i.e. its length)
increased by the land area behind the frontier
decreased by the average distance to the frontier (because workers have to travel to/from the frontier, to build/repair towers)

The exact formula for which, I’m still working out.

- - - - -

If I implement all of the above, Orcs vs. Martians will have some fantastic tower-building, defensive A.I.!

Implementation challenges:

what exactly constitutes a “passage”? If there’s a single unwalkable tile in the middle of a passage, does that briefly split the passage into two passages?
how to detect when a frontiers splits, fast?
how to detect when sub-frontiers merge back together, fast?

All of this has to run in near-real-time.

Posted in RTS maps, A.I., Gameplay | No Comments »

More A.I.

Friday, July 18th, 2008

Big news on the A.I. front - I’ve figured out (most of) an algorithm that will place A.I. towers near bottlenecks in the terrain. w00t! Currently, A.I. players only place towers randomly, around their bases. If A.I. players could recognize natural bottlenecks in the terrain, and concentrate their defenses there, they would play much more effectively.

“Bottlenecks” being things like a ramp up to a high mesa, or an entrance to a box canyon, or a land bridge connecting a peninsula to a continent, or a fjord proving access to an island.

The alg isn’t implemented yet - haven’t even started - but it’ll involve extruding all the natural obstacles in the terrain (i.e., blowing them up like a balloon), and the places where the extrusions first bump into each other, identify where the bottlenecks are. Then, it’ll do a frontier-walk, starting from the A.I. player’s base. The first bottlenecks that the frontier-walk reaches, are the bottlenecks that the A.I. player should fortify.

Still working out the details, but I’m pretty sure it’ll work. I got the extrusion idea from forums I read long ago, of all things, about Quake 2 (!) I’m pretty sure that’s where I’m remembering the idea from — though it seems odd that a game like Quake 2 would need to know anything about bottlenecks in its maps? Maybe it was needed for bot A.I. Then the frontier walk idea is mine, to identify which bottlenecks are relevant to a given base.

One really cool thing about this algorithm is, by varying how the frontier walk starts, the algorithm may even be able to identify bottlenecks around a player’s entire empire/territory — not just around individual bases — so the A.I. doesn’t waste too many towers fortifying bottlenecks between its own bases.

Posted in RTS maps, A.I. | No Comments »

Run away, run away!

Tuesday, February 12th, 2008

(a reference to Monty Python’s The Holy Grail)

Ok, I flinch. That task about making the A.I. reason based on its personal view of the world, is a little too big to do right now. I still want to do it, but I’m also still debating how, and I hesitate to bite off a task that big at this particular moment.

One reason for my hesitation is, I feel like Orcs vs. Martians is still suffering from a few not-fully-defined gameplay rules. There are still several unanswered questions. Things such as:

if you go to build a building, and there are trees in the way, what happens?
or similarly, if some of your own units are standing in the way of the building site, what happens?
what if those units instead belong to an allied player?
should there be a distinction between raw resources, and finished resources? (where only finished resources, produced at bases, may be used to build with)
should immature trees be harvest-able? if they are, should harvesting them (i.e. saplings) produce fewer resources?

I’d like to nail down questions like those so that the gameplay is fully defined, before tackling the big A.I. personal-view-of-the-world task.

My tentative answers to the above:

trees that get built on, simply disappear. The only problem is, this rule could be somewhat abused. A player could go around, starting new bases and then canceling them, thereby wiping out whole groves of trees. Hmm…
your units automatically move out of the way
allied units similarly move out of the way. An odd side effect of this is, it effectively allows you to move another player’s units. But I don’t think there’ll be any terribly negative consequences from this, and from my gaming experience, it’ll be very convenient. (enemy units, of course, won’t move)
yes. Workers will be required to go pick up “building materials” at a base; they won’t be able to harvest resources from trees or ore and then go directly to build a building. The game already works this way more or less. This rule is a little confusing though, as one tester pointed out, so I need to figure out how to make it clearer to the player…
to keep things simple, no. The easiest answer is to simply prohibit harvesting trees that haven’t yet grown to full-size.

- - -

Posted in RTS maps, A.I. | No Comments »

Screenshots and The End of a Tunnel

Thursday, September 13th, 2007

Here are a few recent screenshots of Orcs vs. Martians, in action.

Here I’m helping Purple, an allied computer player, defend his base against an attack by the Red computer player. (I’m the human Cyan player.)

The defense succeeds, and Purple immediately launches his own counter-attack. I follow in. We manage to reach Red’s base, though since Purple took the lead, he lost all but two units in the attack.

I end the game. Here’s the the end-game screen in its latest incarnation, with nested tab controls.

Here’s the end-game screen again, this time with the Replay sub-window open. (this allows you to watch a replay immediately at the end of the game.)

How about that new layout to the end-game screen? I’m liking it better than earlier layouts. And I still have a few more changes planned.

I also like that particular map, shown in the replay. The random map generator is doing a pretty good job of making interesting maps, with plenty of bottlenecks, fjords, and naturally defensible locations.

That map also happens to be my stress-test case: it has the max # of players (9), max map size (90×90), and max # of resources. I’ve been doing profiling and optimization lately to get this test case to be playable.

Development, in general, on OVM is moving ahead…I definitely feel I’ve reached the “beginning of the end” of this project. The tasks still left on my to-do list are generally about graphics improvements, A.I., speed and memory optimization, internet testing, and some optional game play elements. And…game balancing. I’m a little concerned about that last task, game balancing, because I have no real prior experience with it. Don’t know how much time / effort it’ll require.

At any rate, it feels good to see the light at the end of the tunnel on this project. Hopefully, that light’s not a mirage.

Technicals
Currently, my stress test scenario generates up to about 1300 RTSUnit objects (server-side only; not counting client objects). At that point, I get around 4-5 frames per second in rendering performance. Also, Windows’ Task Manager shows the game to be eating up about 400MB RAM in-memory, with another 400MB in swap space.

Them is my current stats.

I’ve just started investigating what’s causing so much memory consumption - 800+ MB is an awful lot. Maybe/probably it’s all those RTSUnits? I wonder how big those things are? They ARE derived from the Player class, after all, which I would guess is a pretty heavy class.

If the RTSUnits are in fact the culprit, I might try a radical idea: changing RTSUnit to be derived from ShapeBase, instead of from Player. Now THAT would be an ambitious undertaking! But if it’s feasible, it might yield a much lighter-weight RTSUnit.

Ultimately, I want to support up to about 2000 RTSUnits. That would allow for 9 players to have about 100 units each, plus about 1000 trees + ore deposits on the map.

Posted in General, Torque, RTS maps | No Comments »

July and August

Thursday, August 30th, 2007

Development progress for July and August:

units now walk apart
When several units overlap because they’re standing too close, they now automatically walk apart.
made the end-game replay show roads
As they get paved.
improved the end-game graphs
Among other things, the time axis is now labeled in minutes:seconds.
improved the appearance of player colors on the 3D models
Mo’ better lookin’. Conquer the world, spread your colors.
made the AI send workers in pairs when building new bases
So they get built faster.
allowed players to specify “random” for their color
In the game setup screen. This is a surprisingly enjoyable feature. Sometimes it’s the little things…
made the unit portraits show the units correctly posed, colored with the player’s color, and holding their weapon
w00t! This was a fair-sized technical challenge, because the portraits are not bitmaps loaded from disk, they’re generated in-memory each time the game runs. Originally, I wasn’t at all sure I could get Torque to do this. Especially the part about the weapons. Torque really shines this way: though buggy sometimes, though undocumented in many places, Torque almost always gives me the tools to do what I need to do.
allowed user to specify random maps’ maximum elevation and median elevation
Allows more precise control over the random maps. The median elevation is the elevation at which half of all elevation points are lower, and half are higher. For example you can set the median near the maximum, and the resulting map will have near-uniform plateaus that plunge into deep lake valleys. Pretty neat.
added post-processing to random maps
…to increase the amount of playable land. Before, sometimes large parts of the map would be unreachable and thus unplayable. Now, there’s an algorithm that inserts little connecting ramps between unconnected regions. So far in testing, the algorithm consistently gets nearly 100% of the walkable land to be playable. (this issue/task had been on my to-do list for forever and was a source of some anxiety, so I’m glad to see it finally done. random maps have been a lot of work)
off-screen attacks now cause an alert sound, an alert popup in the main GUI, and pings on the minimap
The popups on the main GUI are awesomely helpful! I plan to add more info to make them even better.
fixed a bug where unit animations occasionally missed an action
Like an axe swing, etc.
showed players who are teammates adjacent to each other
In the details window.
showed team numbers next to players’ names
So you don’t need to remember who’s on whose team.
workers now switch to different tools to do different tasks
Axes for chopping, pickaxes for mining, hammers for building, etc.
resources carried by workers are now shown as piles of logs
Held in their hands. Got rid of the backpack placeholder.
units now rotate
E.g. as they change walking direction, or as they turn to face things that they act on.
implemented an auto-explore feature!
Just hit the “Explore” button (or “X” hotkey), and the unit will auto-explore land that is covered by the fog of war! No further user action necessary — though you may not like the path your unit takes. This is another feature designed to reduce micromanagement and make the game more enjoyable. I first saw this feature in Empire Earth 2, and really liked it there. (actually, that’s the only place I’ve seen it)
made unit-level retreating easier
Now, units that are moving will only stop to engage targets “in front of” them, and not stop for targets behind. Before, units would stop for any target within range (unless you used the specific “rush” command). Playtesting revealed that the old way was very frustrating when you were trying retreat from a losing battle. The new way feels considerably more intuitive.
allowed the game window to be as large as the virtual desktop
Helpful if you’ve got a laptop driving a larger secondary display. Before, Torque limited the window size to be smaller than the primary display. Probably because Torque was originally written back when secondary displays were rare as hens’ teeth.