Red Brick Games

To implement the graph data structure that represents terrain passages and intersections, I’m trying out the Boost Graph Library’s adjacency_list:


template<
   class OutEdgeList,
   class VertexList,
   class Directed,
   class VertexProperties,
   class EdgeProperties,
   class GraphProperties,
   class EdgeList
   >
class adjacency_list
{
   // ...
};


which, despite its not-very-intuitive name, is a graph class.

I always find boost libraries hard to understand, but they’re very flexible.

I mentioned earlier that I’m writing Orcs vs. Martians in a home-brewed programming language, Meta-C. Meta-C gives me a chance to experiment with the design of a programming language, to try to make programming easier.

To me, “easier programming” means

1. less code is required to implement a particular feature
2. the code is easier to maintain and refactor as the app evolves

So I made Meta-C to have the same syntax as C++, but modified it to be less verbose, and to require fewer changes when the architecture of the code evolves. (Excuse me for going a bit off-subject about a programming language probably nobody will ever use but me, but I like this stuff : )

Here’s an example that illustrates some of the improvement possible over C++. Orcs vs. Martians has a function that looks for the nearest enemy base. It’s a small function, and it does three fairly common things; it:

1. iterates over a container (all the entities in the game map)
2. tests elements of a certain type (”Bases”)
3. returns the “best” element by some criteria (the nearest base)

Comparing the C++ and the Meta-C implementations of this function is pretty revealing. First, here’s the C++:

01   Base* Base::getBaseToAttack()
02   {
03      Base* ret = NULL;
04      for (set<Entity*>::iterator ent = gMap->getEnts().begin();
05           ent != gMap->getEnts().end();
06           ent++) {
07         Base* base = dynamic_cast<Base*>(*ent);
08         if (base)
09            if (isEnemy(base) && (!ret || distTo(base) < distTo(ret)))
10               ret = base;
11      }
12      return ret;
13   }

Now, here’s the Meta-C:

01   Base* getBaseToAttack()
02   {
03      for gMap.ents,Base*
04         if isEnemy(base) && (!$ || distTo(base) < distTo($))
05            $ = base;
06   }

With Meta-C, there’s much less code! Mostly, because

1. Meta-C’s “for” keyword natively understands STL containers. When its argument is an STL container, it automatically generates that ugly STL iteration code
2. “for” also takes an optional element type (”Base*”), when you only want to iterate over elements of that type
3. The “$” symbol means the return value of the function. If used, Meta-C automatically generates its declaration and a return statement for it in the function
4. other minor things you can probably pick out

Not only is there less code, Meta-C requires less re-work as the application evolves. For example, if the following changes happened, here’s what the impact would be on the two implementations of the function.

1. if the type of the container changed, e.g. from a std::set to a std::list, the C++ implementation would need a change to its “for” loop. The Meta-C wouldn’t need any change.
2. if the function’s return type changed from Base* to something else, the C++ function would need changes in four places. Meta-C would need changes in two places.
3. if a dedicated “gMap.bases” container was created that contained only bases, and you wanted to iterate over that instead of the “gMap.ents” container that contains all game entities, the C++ function would require several changes: changing the two instances of “gMap->getEnts()” in the for loop to “gMap->getBases()”; deleting the lines doing the dynamic_cast operation and testing its result; and un-indenting the 2nd if statement. Meta-C would only require one change: from “for gMap.ents,Base*” to “for gMap.bases”.

I like this language :)

We now return you to your regularly scheduled blog.

Making good progress on the unit selection behavior. I plan for selection to behave in a “Starcraft plus” way, meaning it’ll have the same behavior as Starcraft plus a few enhancements. One enhancement will be that multiple buildings may be selected, which is not allowed in Starcraft. Another will be that ctrl-clicking (or double-clicking) a unit will give priority to multi-selecting the nearest units to the unit clicked. This’ll make squad grouping easier. In Starcraft, ctrl-clicking selects units randomly all over the screen with no regard to proximity.

I also started work on selection ring colors. Your own units will have green rings, allies will have yellow, and enemies red (screenshot on left). I think I’m going to need two different resolutions for the selection rings, one for buildings and one for units. Currently the ring looks too thick around buildings and too thin around units because it’s the same bitmap, scaled.

The Torque + STL issue may be resolved, hooray! It required inlining one function, and building Torque with TORQUE_DISABLE_MEMORY_MANAGER set. My only reservation is that this solution turns off Torque’s real-time memory manager. I’m sure there’s a reason the Torque developers wrote their a custom memory manager, so I’m wary about turning it off. The normal C run-time’s memory manager may be more prone to “hiccups” and less smooth gameplay. We’ll see, I’ll leave it set this way for a while and watch for problems.

Last week marks a milestone for me, as I left my old job (and a steady paycheck) to become a full-time “indie” developer. Today is my 2nd day at it. So far, no worries! I’m loving it. I relish the freedom and responsibilities that this new venture entails. I have 23 years of programming experience and a couple of years of Ph.D. work in geometric modeling, and I plan to put them all to good use. The risk of this venture is, of course, that I’ll have no income until I release my first product. But that just makes this career move more exciting.

I posted a bunch of new screenshots of Orcs vs. Martians on the left. The first one shows a new status bar on bases. The bar displays the number resources and workers that a base has. It’s necessary because I plan for each base to have its own, dedicated collection of resources, unlike the single, global pool of resources that other RTS games have. I think this will add an interesting territorial aspect to the game. Once an area runs out of resources, it will become difficult to defend. To counteract that, a player can build infrastructure, like roads or railroads, to ferry resources from resource-rich areas to the areas with factories and such. This should allow some interesting strategies for attacking and defending lines of supply.

The next three pairs of screenshots show improvments to the game’s pathfinding algorithm. The 1st screenshot in each pair shows the path found by my previous, tile-based pathfinding (the path is shown as a green line). Notice the kinks and “jaggies” in the original path. The 2nd screenshot shows the same path, but after a smoothing algorithm has been applied. The jaggies are almost completely gone, resulting in nearly-natural path for units to follow. The smoothing algorithm still needs some work, but overall I think this puppy is nearly ready to roll. Performance is good too! I’m using Micropather in the most inefficent way possible, yet the pathfinding still seems almost instantaneous.

The next four screenshots just show the pathfinding algorith in action: figuring out to cross a river in the shallow part; finding a roundabout way up a hill because the direct route is too steep; and finding a couple of very long paths across nearly the entire map.

Next tasks up will be to fix up the selection logic for units and buildings, which really needs improvement. It’s currently both hard to use, and buggy. Then, there’s still an STL issue with using Torque and Micropather together that needs addressing. I got release builds to compile ok (though I’m not sure I did it “right”), but I haven’t gotten debug builds to compile. Or more specifically, they won’t link. The linker sees multiple definitions for operator new and fails. I’m not yet sure exactly why this is, but I do know that not having debug builds is Bad Thing. So I’ll also be trying to get Torque and STL to peacefully coexist.

Development is still coming along splendidly. The game’s UI is now working. The player can now

• build workers
• build soldiers
• build new bases
• set rally points from bases
• select units
• send units to attack other players

Also, networked multiplayer games now work! I can’t believe how easy that was to get working. Thanks, Torque.Unfortunately though, I have run across one major “risk item” with Torque. You can’t use STL in the Torque engine! The STL header files won’t compile, the result of Torque doing some funky stuff in overloading operator new. The bottom line is that no compiler translation unit can see header files from both Torque and STL, or things blow up. You can use one or the other, but not both (and actually the problem is slightly worse than that). I’ve got a bad feeling this is going to be a very big headache for me. I’ve been planning to rely heavily on 3rd-party C++ libraries to write this game, but nearly every modern C++ library uses STL.

Speaking of 3rd-party libraries, I’ve started using a path-finding library called micropather. A pretty neat library. I now have very rudimentary path-finding working. Units now walk around bodies of water in the map, staying on land (except for shallow water, which they can wade through). It’s pretty crude at the moment, as the movement is jerky, and units only walk along 90-degree or 45-degree angle paths now. There’s a good bit more work to do to get it polished.

The exciting thing, though, is that I think I see how to do pathfinding and still support all the game features I want to implement. I want units to be able to dig trenches, which will cause existing paths to become invalid while the game is running. I also want to allow players to build buildings adjacent to each other, which has the same blocking effect. In addition, if a building gets destroyed, a previously closed path becomes open again, so my pathfinding model has to handle that too. I think I see how to support all these features with micropather and the A-star pathfinding model. This had been an open question for me up til now, so this is a good thing.

Starting Feb. 11th, I’ll be working full-time on this project (whose working title is now “Orcs vs. Martians”).