Red Brick Games

Here’s a game design issue with which I’m currently wrestling.

• fact: terrain elevation is important in Orcs vs. Martians. High elevation gives bonuses to vision, attack range, and windmill productivity.
• fact: RTSs are usually played with the camera angled down.
• fact: it’s hard to see terrain elevation with the camera angled down!
• result: occasional frustration.

So I’m trying to think up some approach to help the player visualize terrain elevation better.

Should I draw equi-height contonur lines on the terrain, like you see on a surveyor’s map?

But that might be hard to implement. I’m using the Torque game engine, and I don’t think its terrain renderer could easily be modified to draw pencil-thin terrain countour lines…

In lieu of contour lines, should I draw contour “bands”? i.e., draw thick swaths of equi-height terrain, using an additional terrain texture?

Torque could do that pretty easily.

If I did that, should I draw terrain that way always? Or draw the bands only sometimes? i.e. like when planning a new building?

And if I used this additional texture to band the terrains, would it look confusing in regards to other textures? i.e., I already use different textures to denote

• walkable terrain,
• impassible terrain, and
• terrain flat enough to build on

If I threw yet another texture into the batch, would that just look confusing?

Hmm…

- - - - -

The HUD can now show all bases’ build queues, simultaneously!

What you’re looking at here is the hotkey groups, in the upper-right corner of the screen.

The last three hotkey groups (8, 9, and 0) are assigned to base buildings. Below each hotkey group is the respective base’s resources, and workers.

What’s new here is the 3rd little graphic below those: the current build order for the base.

The graphic shows the portrait of the unit being produced, the quantity in the queue, and even…a tiny green build-progress bar!

With this feature, it’s now possible to monitor production of all bases right on-screen, simultaneously. No more clicking around from base to base!

I think it’s pretty cool.

A second, smaller feature, is that the hotkey groups are now skinned with race-specific textures. The above screenshow shows the Martian skin.

The Orc skin is:

And the Human skin is:

Fortifying bottlenecks is now working!

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

1. examines the terrain around the base,
2. analyzes it into passages and junctions,
3. stores the passages and junctions into a Boost graph object,
4. culls passages that are dead ends (i.e. passages that don’t lead to danger)
5. semi-randomly picks a frontier among the remaining passage(s),
6. evaluates the frontier of passages for its merit,
7. repeats steps 5.-6. until a “high-merit” frontier is found; and finally
8. 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 :-)

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.

Recent progress on Orcs vs. Martians:

A.I. players now explore more

This fixes the blindness issue with maintaining a personal-view-of-the-world. Big “yay” there.

I actually had to do two different exploration algorithms: one to explore near the unit’s home base, in order to find new expansion base spots; the other to explore the entire map, in order to find enemies. Two different algorithms, for two different needs. The combination of the two seem to work pretty well; the A.I. is no longer dumb as dirt.

…In fact, they almost work too well. Despite the fact that the A.I. no longer cheats, the A.I. is once again finding my home base mighty quickly. Those meddlin’ explorers. Maybe I need to dumb down the exploration algorithms?

But it’s still kind of fun. If you can quickly build towers out a distance away from your base, and fend off the A.I.’s explorers, the A.I. takes considerably longer to figure out where you are. Muwahahaha!

Heavily armed, and no place to go

Stack-based unit modes now work

Finally.

One benefit of this feature is that all movement code is now factored out into its own stack element, making movement “smarter” for all modes. Whether a unit is harvesting, building, or just marching somewhere, the unit now intelligently re-paths around unexpected obstacles, no matter what its mode is.

End User License Agreement

Got that written.

To write it, I read the EULAs from about 10 other games, to familiarize myself with their contents and how much they varied from game to game. The verdict? They differ a lot in format and wording, but all contain pretty much the same stuff, or different subsets thereof.

Here’s an interesting question. Are EULAs themselves copyrighted? Instead of writing my own, could I have just copied a EULA from another game? or would that have been some kind of infringement in itself? No idea. Just to play it safe, I rolled my own.

Flattened never-explored terrain in the 3-D view (a fog-of-war feature)

This feature was another Big Thing to me, having been on my to-do list for nearly 2 years.

If you played one of the beta releases or are a long-time blog reader, you may remember this issue. The way I used to “hide” unexplored terrain in the 3-D view, was to color it black. But, you could still see the silhouettes of hills, and water showed up plainly. Those were big problems, because terrain elevation and water locations are key elements to the gameplay (elevation provides all kinds of bonus, and water makes trees grow faster). Being able to see those two things gave the player way more info than they should have had.

My solution? Dynamic terrain height alteration. Initially, all terrain that’s not explored is set to be one meter above sea level. That flattens all hills; and since it’s above sea level, the “false” terrain hides water that lies beneath it. (All terrain still starts out black, so you just see black.) As units explore and new terrain is revealed, the game “pops” the elevation of tiles to their true height. For hills, the terrain gets popped up, and for water, the terrain gets popped down. And of course the black is removed, painting the tiles with their correct textures.

It seems to work fairly well. At first, I was concerned about performance. Could Torque alter terrain heights fast enough for changing fog-of-war? In OVM, fog-of-war gets updated twice a second, so Torque is now modifying terrain heights at (up to) twice a second, for potentially dozens of tiles at a time. The verdict? I haven’t profiled it yet, but Torque seems to do it plenty fast. No noticeable slowdown. Wahoo!

Visually, I generally like the way it looks, though with… reservations. When exploring high areas, you’re constantly seeing artificial “canyons”, that aren’t really there. It’s definitely…different. See for yourself.

Here’s a unit exploring a hilltop, where fog of war covers the interior of the hill, creating an artificial “canyon”.

As the unit explores, the canyon fills in.

Also, when you spot enemy buildings, if you haven’t seen all terrain they sit on, the effect is…interesting.

Hmm.

My thoughts are, it all looks kind of neat, and visually it’s very striking. But it’s also distracting. Those artificial canyons really draw the eye to them, but since there’s nothing really there, I feel like it distracts the player too much.

I think this feature is going to need further fine-tuning.

Rally points are now visible

I used a little 3-D model of a banner, from the good folks at Frogames, to mark rally ponits. The banner is dynamically recolored in the player’s color:

The banner appears & disappears as you select & de-select the base building; pretty standard RTS fare. It also runs a nice animation of being blown in the wind.

…and

…and besides the above, there’s been lots more internal bug fixing, refactoring, renaming, optimization, pulling out of one’s hair, and what-not. All the usual trials and tribulations of software development.

In contrast to the aforementioned progress, A.I. has not gone so well. I made a serious effort to smarten-up the “unit-level” A.I., i.e. what units do on their own (mostly in regards to fighting) when the player isn’t actively directing them. But I haven’t been able to come up with algorithms to do it. It’s been pretty hard to do, despite the fact that I can pretty well visualize the behavior I want them to have. Bummer.

I also haven’t yet made much of an effort to smarten-up the high-level, strategic A.I., either.

And now for something completely different: a photo of NASA research aircraft. Just thought I’d include this since the aircraft look so cool :)

So the main benefit of squads is that they allow soldiers to march around in nifty-looking unit formations, right?

But in Orcs vs. Martians, I’m thinking squads can benefit workers, too.

Counterpoints

But first off - I can’t see squads benefiting most worker actions. Like when workers go to harvest resources - why would you want a squad there? If you tell several workers to harvest a tree, having them march in formation to the tree would just look dumb.

I don’t see squads benefiting the paving of roads, or repairing of buildings, either.

But the one use case is…

But there’s one big exception where worker squads of do look beneficial: building new bases.

In Orcs vs. Martians, building new bases is a fairly high-risk endeavor. Workers are required to carry resources (i.e. building materials) out to the building site. Unlike other RTSs, your stockpile of resources is not magically, omnipresently, available everywhere on the map! You have to carry resources to where you need them, just like in the real world.

So when you send workers out to build a new base, you’re not only risking the lives of your workers, you’re risking the resources that they carry. If those workers die, they drop their resources. To make matters worse, if they die too close to enemy territory, the enemy may retrieve the resources — thus benefiting from your loss.

So it makes sense to protect building parties.

A solution

So squads of workers start to look attractive here.

Why? First, it takes several workers (currently 4) to carry a sufficient quantity of resources to build a new base. You don’t want each worker to walk independently, in a long line out to the building site — that’s harder to manage and protect. Much better for workers to walk together, as a group.

Second, if there’s much risk at all of enemy attack, you’d want soldiers to escort the workers. Formations also then become attractive. Preferably, you’d like the vulnerable workers to travel on the inside of the formation, and the tougher soldiers to travel on the outside. In practice, these formations may not be big enough to have an “inside” and an “outside” strictly speaking, but 4 workers could be protected pretty well by 2 soldiers in front and 2 in the rear.

Squads to the rescue?

Squads provide a nice solution to both those issues.

Here’s the user experience I’m thinking of: the user multi-selects both workers and soldiers. The game detects the mix of different unit types, but shows only the “Worker” command palette. The user issues the command “build new base”. The workers converge on their current base, picking up resources to build with.

Here’s where squads come in. The game internally creates a squad for the workers, and waits until all workers have their requisite building materials. Only when they’re all ready, do they leave for the building site. This ensures they travel as a group.

The soldiers also get added to the squad. The already-existing logic of the squads puts the units in formation as they travel (assuming the user has turned on the formations option). The squad can also be made to detect the mix of unit types, and put the more vulnerable units (workers) on the inside, and the tougher units (soldiers) on the outside.

Problems solved!

Having worker squads will also be a boon to the game’s A.I. players. From playtesting, I can attest that A.I. builder-workers are currently too vulnerable; they’re too easily picked off. A.I. players sometimes lose a lot of resources while trying to set up new bases. (a problem observed in many other RTS games too, not just OVM!) This will help that.

Worker squads could also be used for other building types besides bases. They’re not really unique to bases; it’s just that bases are the most-frequent use case. Probably the criteria for whether to form a worker squad, or not, would be distance to the building site. So e.g. if you wanted to build some distant towers, you’d probably want to use workers squads for that case, too. The game could be made to examine walking distance, or some other criteria, and auto-detect when it’s best to organize workers into a squad.