Red Brick Games

Archive for the ‘Pathfinding’ Category

Models and more

Wednesday, March 19th, 2008

I did a small favor for a fellow indie, and he in turn made some new 3-D models for OVM! OVM now sports a UFO model to serve as the Martians’ base, and a laser rifle for Martian crewmen to hold.

I felt the placeholder art I originally had for those two items really detracted from the game’s look, even as placeholders. What a nice improvement. Thanks Thak!

If you’re interested in more of Thak’s work, check out 3dmatter.com or spellcraft.biz. He works fast - he turned out those two models in no time flat.

Progress

These last few weeks I:

finished the A.I. personal-view-of-the-world feature
started to separate OVM’s pathfinding code into a stand-alone library
added new features to meta-C (my homegrown programming language, which OVM is written in)
optimized meta-C for speed

I kind of spread myself too thin these last weeks, trying to do all those things simultaneously, and several of them didn’t go as planned. Still, I got some progress done.

A.I. personal view of the world

This is done! The A.I. now makes all important decisions based on a limited, imperfect view of the world. No cheating anymore!

This is a huge milestone, and it’s been a long time coming. I remember putting this feature on my to-do list well over a year ago. At the time I thought to myself, that’s pretty ambitious, I don’t know if I’ll get that feature in. So, I’m definitely happy that it’s actually in!

I still need to do the follow-up work of increasing the A.I.’s exploration ability; without that, as predicted, the A.I. is behaving dumb as dirt.

Pathfinding library

I started pulling out OVM’s pathfinding code for packaging as a sellable product.

Here’s what the main API currently looks like:

   F32 findPath(
      Point2F          bgnPoint,
      RectF            endRect,
      IMap*            map,
      Vector<Point2F>* path,
      ICoster*         coster = NULL,
      F32              range = 0,
      F32              maxCost = FLT_MAX
      );

It’s simply a global function that outputs a vector of way points. Maybe I’ll describe the parameters in a later post. I’m still figuring out how to make the API as user-friendly and flexible as possible, by using C++ templates, etc. Naturally, it’ll also need a friendly TorqueScript interface, too.

There will also be some utility functions and data structures, for things like iterating over the tiles crossed by a ray (useful for smoothing out the final path).

One good thing is, I’ve taken a look at some other free pathfinding packages, and it looks like OVM’s pathfinding does indeed provide features beyond what’s already out there. Got to provide value, to sell a product.

Next up: Squads

I’ve started working on giving OVM a notion of sqauds, i.e. groupings of units.

The more I think about squads, the more issues I see them impacting in the game. For example:

making units march in formation
reducing the number of calls to pathfinding (and hence reducing CPU demand), via squad flocking
reducing network traffic, via squad flocking
allowing the A.I. to temporarily subdivide a force to deal with attacks from multiple directions, via a hierarchy of squads (i.e., squads of squads), and then bring those forces back together to resume the squad’s original mission
helping the AI manage multiple units sent to do a single job, e.g. when multiple workers go to build a new base
allowing units to auto-explore in two’s or three’s, in addition to individually

I thought that was kind of interesting. Originally, I thought of squads as mainly relating to marching in formation. But they seem to touch quite a few other areas, at least from a programming perspective.

Posted in C++, TorqueScript, Pathfinding, A.I., Networking, Development tools | No Comments »

Back to natural dumbness

Friday, February 29th, 2008

I’m back on the task of making the A.I. reason from a personal, imperfect view of the world. Like I mentioned earlier, there’s lots of work involved there. Ugh. But, I’m well underway on the task, and it’s going reasonably well, all things considered.

This task also kind of dovetails with cleaning up the pathfinding API, which will possibly help me package up and sell the pathfinding code in the future. I’m seeing though that there’s considerable work to do there, so that won’t happen in the immediate future.

And along those lines, I’ve also been thinking more about how to recoup my investment in Orcs vs. Martians. There may be other parts of the code I could also sell, like maybe the fog-of-war implementation.

Anyhow, I’m feeling pretty good about the project as a whole right now. The A.I.-personal-view-of-the-world task is probably the biggest, hairiest task left on my list. Once that’s done, it kind of looks downhill from there.

Remaining work generally involves the A.I., squad handling, ease-of-use features, gameplay tweaks, graphics improvements, optimization, optimization, did I mention optimization?, 2-D art, 3-D art, and bug fixes. Lots of work, but not exactly what I’d call rocket science.

I hope OVM ends up being a game that people like and that sells. After two years of working on it, I still find myself playing it. For fun, not for testing. That’s a good sign.

I think probably that people who like the strategy aspect of RTS’s, will like Orcs vs. Martians. I’ve really worked hard to fight the micromanagement “issue” in the RTS genre, to free up the OVM player so he can enjoy directing high-level strategy. On the other hand, I’m not sure whether people who like the RTT (Real-Time Tactics) aspect of RTS gameplay will like OVM too much. OVM has few unit types and doesn’t really emphasize tactics.

I guess I could try to make it please both crowds. But I think that’d take significantly more work. And doing that might also dilute OVM’s focus.

I’d rather make a game that does its core gameplay well — and make its core gameplay be what I enjoy, because that’s what I know.

Posted in Pathfinding, A.I. | No Comments »

Dos Años

Sunday, February 17th, 2008

Red Brick Games turned 2 yesterday. Happy birthday, RBG.

(”Dos años” = Spanish for “two years”. Or is it…”two old ladies”? Not sure. yeah, language isn’t my strong suite)

I’ve implemented all the gameplay features I mentioned in the prior post. w00t! The gameplay is basically all defined now. There are still other possible gameplay elements I’m considering (e.g., walls - suggested by several ppl), but they’re not core essentials, so I’ll mull them over as playtesting motivates / time allows.

With that done, I’ve moved over to working on pathfinding for a bit. Which is getting to be more interesting than I anticipated…

Technicals

I’m pretty excited about the pathfinding in Orcs vs. Martians. It’s gotten powerful. OVM’s pathfinding code can now collect multiple metrics on the paths it finds, not just the traditional single floating-point number (usually representing distance). Right now I’ve got it collecting (1) distance, (2) travel time, and (3) damage incurred by enemy fire. The path metrics are then converted to a cost, by a parameterized costing function.

How’s that useful?

Since the costing function is a parameter, different costing functions can achieve different behavior for different unit types. For example, worker units use one costing function, that makes them avoid enemy fire like the plague. Makes sense; workers are delicate and don’t like to get shot. Military units use a different costing function, one that ignores all but the most intense enemy fire, since mililitary units are tougher, and are meant for combat.

The result: pathing behavior that is specialized and appropriate for each unit type, but is all handled by the same pathfinding code. w00t!

If I were to add new unit types, each would need only a new costing function, which takes only one line of code to write.

I could see this system being easily extendable to handle, e.g., air units! (they’d ignore ground obstacles, but avoid enemy AA fire)

I also use the same pathfinding code to lay out road plans; they use yet another costing function (one based solely on distance).

I said I was excited; in fact my head is kind of swimming as I think of the possibilities of this level of flexibility. I can even see pathfinding being used to answer high-level A.I. questions. Now that has me really excited!

For example, say there’s an A.I. base and it’s “thinking” about attacking an enemy fortification. But does it have sufficient troops to win an attack? It can answer that question by pathfinding to the enemy base and summing up all the damage its troops would receive, en route, plus damage they’d receive at the final battle.

If the received damage is more than the total hit points of the troops, then the A.I. base should probably wait and build additional troop strength, before sallying forth.

Or, better yet, the A.I. base could search for different enemy fortifications, ones that it could successfully beat. Even if they are farther away than the first choice, it might prefer to take on those instead.

That could probably all be done with yet another costing function, one specialized for a squad of mixed-type troops.

Seriously, wow.

Ahh. I feel grateful to be at this stage of development in OVM. This kind of work (A.I., etc.), more than any other kind of work, is what I’ve been looking forward to getting to for the last two years!

One other thought, once I’ve gotten the pathfinding code ironed out (and parameterized, and templat-ized, etc.), I’m thinking seriously about packaging it, and seeing if I can sell it as a code resource.

I think it has sufficient value-add, beyond what’s already available out there, to be sellable.

Posted in Pathfinding, A.I. | No Comments »

I’m sorry Dave, I’m afraid I can’t do that.

Tuesday, February 5th, 2008

- HAL 9000, 2001: A Space Odyssey

Good news on the A.I. front!

Workers now avoid danger!

When an enemy builds fortifications, your workers will no longer harvest in that area. They don’t want to get killed! Instead, your workers harvest elsewhere, even if “elsewhere” is farther away.

And, if you send your army to take out the enemy fortifications, your workers will resume working in the original area!

w00t! Workers that are smart! What a concept! :)

The A.I. is starting to reason based on only what it can see

I’ve started to remove the A.I. cheat mentioned in this post. Double-w00t! :) This is really exciting, because it makes the A.I. fairer, and much more human-like.

So far, I’ve got the pathfinding working without the cheat. So, if you build fortifications, the first time the A.I. ventures out, he’ll blunder right into them. But after that, he’ll pathfind around your fortifications if possible, because he now knows where they are.

This means if you build defenses on a single side of your base, the first time the A.I. comes at you, he may impale himself on your defenses. But on later attacks, the A.I. will intelligently try an alternate route, perhaps coming at your base from behind.

There’s other code (besides pathfinding) that needs to be modified to fully implement this feature, so it’ll be in-work for a while.

The exploration algorithm is working!

The exploration algorithm I mentioned a while back now fully works - it can both explore never-explored terrain, and re-explore already-explored terrain.

- - - - -
I hope to make the A.I. in Orcs vs. Martians be some of the most enjoyable A.I. to play against, of any RTS out there. Your units will try hard to avoid being stupid, and the enemy A.I. won’t cheat (*cough* Starcraft *cough*).

Leaving you, the player, to have fun focusing on the “Strategy” part of “Real Time Strategy”!

In other news, the first pre-pre-preview of Orcs vs. Martians has appeared on the web! Courtesy of Wolf_Dreamer, head on over here to read it!

Posted in Pathfinding, A.I. | No Comments »

More features, more features

Saturday, February 10th, 2007

It’s been a while since I’ve posted much progress on Orcs vs. Martians. Here’s some specific features that have gone in since November:

implemented roads!
improved the pathfinding.
added tooltips to the in-game GUI
made the GUI show helpful messages when planning a new building.
enlarged bases’ footprint (to 3×3 tiles).
applied players’ colors to their units!
made arrows fly in a parabolic arc.
made Martians shoot red laser beams!
made an in-game menu
made the game pause, while the in-game menu is open
added death animations to units
prettied-up the end-of-game GUI
added graphs to the end-of-game GUI
added support for *many* new sound effects!

So progress continues.

Writing an RTS is a lot of work, though. When I was planning this project, everybody and their dog warned me not to attempt to write an RTS. I have to admit it’s been more work than I thought. There are just so many featuers that go into an RTS, even a simple one like Orcs vs. Martians.

When this project is done, I think I’ll be tackling Rock-Paper-Scissors next.

Posted in General, Pathfinding | No Comments »

Scalability

Tuesday, October 3rd, 2006

Wow, October has started off with a bang, in terms of web site traffic. That’s definitely nice to see.

I’ve started working on the scalability of Orcs vs. Martians. That is, making OvM accomodate larger numbers of units in the game. After a couple of days of optimizing, OvM can now deliver smooth gameplay with up to about 300 moving units. It even plays fairly well with up to 500 units.

500 units is a quite a few; to get an idea here’s a screenshot of 500 Orc workers.

Here’s the 500 workers harvesting. Notice the long congo line of workers on the horizon. In addition to the workers, there are also about 350 trees in the game.

A better view of the congo line.

Another screenshot, with human workers.

Getting 300-500 workers in the game is a huge improvement over where the game was before. It used to lag / play choppy at about 30 moving units. That limitation really made it a pain to test (for the last seven months!), so this is one improvement that I am glad to see!

Interestingly, even with 500 units moving around the map, the pathfinding code only takes about 0.2% CPU time. That’s quite a bit less than I expected. The bottleneck now seems to be network bandwidth (again; even after I already made some optimizations). Also, depending on the view, my laptop’s mediocre ATI X300 graphics chip struggles to render all those units/trees.

The CPU for all tests was a Athlon 64 4000 (2.4GHZ).

Posted in Torque, Pathfinding, Networking | No Comments »

Pathfinding

Tuesday, February 14th, 2006

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.

Posted in Pathfinding, STL | No Comments »

Archive for the ‘Pathfinding’ Category

Models and more

Back to natural dumbness

Dos Años

I’m sorry Dave, I’m afraid I can’t do that.

More features, more features

Scalability

Pathfinding

Visitors

Archives

Categories