Spring RTS Engine

Updated 27/01/2006 - new links added at the bottom of this post.

I've been promising for a while to post these materials, which detail ideas on how to improve the pathfinding engine and AI of TA Spring.

I'm hoping that one day we can renovate Spring's pathfinding engine using the system described in document #1 to move units, and the one described in document #3 to create the "backbone path" doc #1 talks about. We'll need to have a some system to account for the dynamically modifiable terrain in Spring, though.

Let me emphasize that all these papers are really worth reading (even if you skip over the code/formulas-heavy sections). I selected them after a long research, and wading through masses of other documents. These are actual recent scientific papers, which describe ideas that are common to both the RTS gaming and robotics fields. Please take time to analyse them, and post your comments.

Most of these links are directly to pdf files, so you might want to right-click and save as instead of opening them in your browser.

I'll briefly comment each set of files, and add more links/comments as I get the time.

Core ideas for a new pathfinding engine

1. Finding paths for Coherent Groups using Clearance
2. Automatic Construction of High Quality Roadmaps for Path Planning

The first document is the best, it shows how you can move a whole group of units while calculating only one path, and keeping the group together. The promise of low CPU use is very interesting for Spring!
The second document covers similar topics, but it has some ideas that complement the first paper, such as how to move the path away from obstacles to have sufficient clearance.

3. The Visibility-Voronoi Complex and it's applications

A very technical paper, but that shows an interesting way of quickly calculating smooths paths with different clearances from obstacles. Of course these calculations are based on polygonal obstacles, not real-world terrain such as you can have in Spring. Therefore we'd need to have an algorithm that analyses a Spring map (before the game) and divides it in regions that have roughly the same kind of traversability all over them (ranging from "impassable" to "flat ground without obstacles").
Chapter 3 in the following paper describes some elements of this kind of terrain analysis algorithm:
4. Terrain-Based Information Fusion and Inference
The last part of the paper also has interesting considerations about Avenues of Approach - AI programmers, this could be of use if you want your computer opponent to make intelligent attack choices.

5. Formation-Based Pathfinding With Real-World Vehicles

A somewhat dated paper, but I find it interesting because it deals with the problem of moving vehicles with speed and turning angle constraints. You have to deal with this if you use steering behavior for something else that moving dots. It even talks about vehicles backing and making three-point turns, which would be a nice addition to Spring pathfinding.

AI and Terrain analysis/decomposition ideas

6. How qualitative spatial reasoning can improve strategy game AIs

This is a must-read: it covers in summary plenty of good ideas for both AI and pathfinding. From page 5: "Much effort has been put into developing search techniques such as A*. Much less effort has been put into creating better descriptions of space to search through."

MORE LINKS

A nice applet that allows you to make polygonal shapes and see the resulting voronoi diagram on-the-fly. The page is in german. Click the word "start" - you need to have Java installed. (If you can't find the link to start the program just click here.)

Voronoi.com - the voronoi diagram and its applications.

Good reading! (And better implementing...)

Therefore we'd need to have an algorithm that analyses a Spring map (before the game) and divides it in regions that have roughly the same kind of traversability all over them (ranging from "impassable" to "flat ground without obstacles").

Pretty sure this is what "Estimating Path Costs" does already.

I like your enthusiasm, but I think it's more a question of who's willing to invest a lot of time into an already working and quite optimized (afaik) pathfinder. There aren't exactly a lot of people willing to do that (so far I count zero )
Before someone brings up dj_oldfield, he's proposing a script language to bind all AI components, so units can react smart based on factors from pathfinding, nearby units (I believe it's called reactive pathfinding what I mean here) and global AI state. So that doesn't really involve any of these AI theories either...

Caydr wrote:

Therefore we'd need to have an algorithm that analyses a Spring map (before the game) and divides it in regions that have roughly the same kind of traversability all over them (ranging from "impassable" to "flat ground without obstacles").

Pretty sure this is what "Estimating Path Costs" does already.

I does analyse the map for paths. I believe it does it with different sizes of grids, to have rough paths available to start units quickly on their way, and then refine the path. But it doesn't do it in the way I'm proposing.

Zaphod wrote:I like your enthusiasm,

Thanks. And by the way congrats for taking the lead programmer position, these are big shoes to fill!

but I think it's more a question of who's willing to invest a lot of time into an already working and quite optimized (afaik) pathfinder. There aren't exactly a lot of people willing to do that (so far I count zero )

You know, if nobody has time to use any of this material, it's ok. Hopefully at least some people will learn something by reading these documents. But what I gathered from past discussions was that the pathfinder, optimized or not, was the thing that eats up most CPU resources and slows down Spring when there are many units.

Besides, there is room for improvement at different levels. Document #1 above holds the most promise for an improvement that doesn't modify much the current engine. It would use basically any path found by the current pathfinder, but create based on it a virtual corridor for the group of units to move through. It would ensure the group of units move together, and anticipates moves through narrower areas. All that, at a low CPU cost... sounds interesting to me, I hope people look into it.

Before someone brings up dj_oldfield, he's proposing a script language to bind all AI components, so units can react smart based on factors from pathfinding, nearby units (I believe it's called reactive pathfinding what I mean here) and global AI state. So that doesn't really involve any of these AI theories either...

Documents #4 and #6 should be of interest to all AI programmers, I believe.

Ahem,

Zaphod I admire your insistence on conventionalism, btu it simply wont bring us any closer to having a superior AI community to other games, or satisfying the needs fo the community in its current state.

Dont put down AI theory of any kind unless you have specifics such as "I tried that and it was too cpu intensive", it may be of use later.

Good work gabba, this'll make good reading.

well, now all the pathfinding is cached, so the main path is low cost.

the ai doesn't need to now about pathfind. the problem of those paperwork (of wich i readen some) is that works with a deep integrated system while we have a strict interface that separates the ai from the engine.

I think that the good'ol a* will does all the needed work for the paths, as gabba (if i understood right) is doing.
The better approach we could have is to analize the map at the start, using a big square system doing precomputation about reachability (or have a way to access the spring one's) just to know the general layout.
this simple grid will permits a quick map of the land/water reachability.

On the other hand, the trigger sistem I've read of in the paper about putting the intelligence on the map itself ot's very similar of the zone system that I'm doing, wich is somewat based on the system used in the sims to analyze the house layout. (read ai game programing gems for references)

The main problems about those paperwork is that those wont build an ai but will put the intelligence of the coder in the game. this is somewhat limiting, as I'm better as coder than player (ask mong =) ); also because a player can learn to fend off everything an ai can throw out. Still, if you know papers on learning system (as ro-learning, or flocking) don't dorget to post them!

I was posting about a similar bit later on in a thread. http://taspring.clan-sy.com/phpbb/viewtopic.php?t=2840

Near the end, my question was how a unit decides if it can climb a hill or not, and this is due to the MaxSlope setting. The units would need to be grouped based on their MaxSlope setting, and either obey a path set by the lowest MaxSlope, least shallow water traversal, or all work independently. Group movement seemed an obvious step in the right direction, I was talking about this with the use of Formations. If I say, "move in formation Column" then the units would arrange themselves and follow a group based path with enough clearance for the column. With a setting "MoveSlowest" the entire group would move at the same speed. Braking and Acceleration would need to be accounted for in the FormationAI

I went a little further in my post, talking about methods for detecting if something is traversable, using several different algo. Most are probably inefficient since I have not looked deeply into Spring yet. I do note that no one has proposed a method for an AI to morph the terrain, clear obstacles, etc.

The biggest problem I see with abstractions like this is most of these papers are based on a single "passable" value, whereas we have multiple dynamic settings for passable vs impassable. A blended approach updated (hopefully by callback per Alantai) and recalculated will be necessary to allow for the basic map revisions that Spring allows.

I have this mapped out in my mind, I just ahve so much in ym head to offload you'll ahve to wait for it.