Red Brick Games

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.

A.I. players can now pave roads!

The A.I. recognizes two cases in which to pave roads:

• when there’s a nearby concentration of resources - roads help the resources get harvested faster
• when there’s a nearby friendly base

The purpose of roads between friendly bases is, of course, to allow for quicker troop movement.

In the future, I want the A.I. to be able to send reinforcements to allied bases that are under attack, from allied bases that have extra forces. The A.I. isn’t capable of that yet, but implementing inter-base roads helps pave the way for that feature (pun intended : ) ).

Base-to-base roads can be between bases of the same player, or of different players on the same team. Here, one of the computer players built a road between his base and mine:

Also, once I get the A.I. building towers at bottlenecks, it may make sense to build roads there, too. They could help distant bottlenecks get fortified faster, and during a siege, repairers would get there quicker.

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.

Here’s some more nice progress! Three items:

• Improved selection rings
• Improved shadows
• Removal of buildings’ dirt mounds

Improved selection rings

I revised the selection rings for units. The new rings are sharper and easier to see from a distance, IMO. I’m still using a solid ring for normal selection, but am now using a broken ring to indicate a “hovered-over” unit, i.e. an unselected unit that the mouse is pointing to, and also for dragging-but-not-yet-selected units. I think it gives better visual feedback as to whether a unit is selected or not.

I’m still sticking with the color scheme of green rings for one’s own units, yellow for an ally’s, and red for an enemy’s. Starcraft followed that scheme and I think it works well.

Improved tree and building shadows

Before, trees cast simplistic circular shadows, and buildings cast no shadows at all. Now, trees and buildings cast correct shadows.

The new shadows need a little more work, but they’re a big improvement, eh?

Good-bye dirt mounds

Several of OVM’s 3-D models for buildings include dirt mounds. Dirt mounds usually make buildings appear to “sit” more naturally in a game scene. From a player’s point of view, the dirt looks as though its part of the regular terrain, but it really isn’t, at least not from a game developer’s point of view. It’s part of the building model itself. The regular terrain has a completely separate computational model.

Dirt mounds cause significant problems for Orcs vs. Martians:

• when a building is located at a steep cliff edge, the dirt mound juts out into space. Very unnatural looking.
  
• shadows only work on “regular” terrain, so if a building has a dirt mound, no shadow appears for the extent of the dirt mound.
• shadows are computed by making an projection rendering of the building. So if a building model includes a dirt mound, the building’s shadow includes the mound shadow too! This is bad, because it prevents a possible workaround where you hide the mound by “sinking” it beneath the regular terrain. I.e, even with the mound hidden, the shadow still looks wrong.

So finally, I took the dirt mounds out of the game. Things look considerably better now IMO.