Decisions

There are nearly 3 decades of old articles on this subject, I'd suggest an awful lot of reading. Start perhaps with the old 1500 Archers on a 28.8 Modem article. The Gaffer On Games website has tons of articles. There are hundreds, perhaps thousands of GDC articles in the GDC Vault covering the topics.

RTS games back in the day introduced group commands, selecting a bunch of units and clicking once on the map, there is no need for that to result in hundreds of individual orders rather than one combined order exactly as the player issued it. Steering behaviors and simple flocking / avoidance techniques mean you don't need to reroute often, and temporary blockages don't force a reroute. The most simple example is a thin bottleneck allowing only one unit through at a time, with good steering behaviors they'll all navigate through; with bad ones the moment a unit enters the bottleneck every other unit will reroute trying to find a way around the temporarily blocked passage, when they first unit gets through they'll all reroute heading back to the now unblocked passage, then all reroute again when the next unit enters. A single command, implemented well, allows units to even stay in formations, you can put armored vehicles surrounding a bunch of fleshy infantry and the combined command keeps the faster-moving units and the slower-moving units moving slowly to maintain the formation rather than darting ahead, or alternatively, a different command allows them all to travel on their own, with the faster units clearing the way.

How you decide each of thousands of little choices make all the difference in the finished game.

Calin wrote:

JoeJ if you're reading this I found your post about pathfinding for 100 units very interesting.

Glad you like it, but i have another idea about optimizing pathfinding, so i'll mention that as well. I've kept this image to memorize it:

Let's say this is a map of 100 x 100 tiles intially, making pathfinding across the whole map very expensive.

And instead of optimizing the algorithm, this time we aim to optimize the data. We want a graph of lower complexity to desribe the scene instead the brute force grid.

To get it, my idea is to to compute a signed distance field from the scene boundaries, which i have illustrated in the image using a Photoshop relief effect. (Those effects are all based on SDF)
Then we can look for local maxima in the SDF to get the points i have drawn in the image, giving us the graph vertices.
We can also connect the points by tracing along the saddles of the SDF, giving our graph edges.
(i'm misusing some topological terms here to keep it simple)

The resulting graph is about 120 nodes and just a tiny fraction of the intial 10000 tiles, so the speed up shoud be huge.

But we only get a coarse path good enough to navigate across all obstacles, and we get no path towards a precise goal which is not a graph vertex.
So we need local sensing and steering behavior to fix this. E.g., Units can trace ray along the path to find the farthest visible point on the path and moving towards that point instead moving along the path. I'm not sure if this would give the ideal shortest path, but it's surey good enough, an allways batter than the random zig zag from pathfinding on a regular grid.

I would say this is probably a typical algorithm to generate navigation meshes for 3D games. And it's worth to realize how such algorithms can optimize the data.
Likely such data has also benefits for AI and behavior.
But it's much harder to work with, compared to the simple regular grid. So maybe it's an optimization better added later than earlier.

Calin wrote:

In broad terms schematic simulations should be used for events far in the future, precise simulations should be used events just about to take place.

I usually think about it like 'coarse is good enough for distant stuff, fine is needed for close up stuff'.
But you're right, it's the same concept temporally.
Combining both, we get 4D lod \:D/
At the cost of higher complexity, though.

However, notice you have just said 'having an approximated prdiction of the future is good enough'.
If so, maybe you do not need to presimulate multiple copies of your map to make good startegic decisions for the future.
Maybe some guess considering only the trends of the present moment are good enough.
(reading on, i would try to minimize a need for simscearios as you call it, as good as possible)

Calin wrote:

because if you go detailed simulation for everything that is about to happen (from start to finish) on the timeline the number of options in the simscenarios you have to simulate increases exponentially.

Exactly. Which is why i personally assume the futere to be unpredictable in general, not only in reality but also in a video game.

The question you are facing now is probably: 'What are common tools to calculate the 'trends' affecting a pending decision of my game AI?' And that's a very broad question. Some tools i came across personally are: Gradients, temporal average, histograms, local minima / maxima, fitting a line to a set of data points, fourier transform, spherical harmonics, singular value decomposition, etc.
So it's math stuff i picked up from working an all kinds of problems, but probably not used that often in traditional game AI.
So keep in mind i'm an outsider here and others could give a better list.
Also, using such tools the next question just becomes: 'On what data should i run those tools of analysis?'
For that i gave an example of units chasing the player using pathfinding based on following the gradient of eergy coming from the player as a source, diffused over the map respecting a boundary from obstacles. I have posted a code example some years ago if you remember. And recently i saw YT video headlines about 'flow field pathfinding' for games, which i guess s the same thing.
But i never thought about high level strategic decisions for a RTS game, and can't give a related example for that.
You gave many example RTS situations in the past, and you listed potential actions to be taken or not.
So, personally i would just hardcode decision trees for all those examples. But i would use those tools of analysis to inform those decisions, so the guesses are mostly good.
That's no magic agorithm to produce intellignce, but i don't know any better.

Calin wrote:

You want to travel to another city. I order to get where you want to travel you have to take the train.

That's a good example. You know you want to get to the city, and you can ask your pathfinding algorithm to give you the global route.
But what happens on your way is unpredictable. So a system of local sensing and behavior is needed to actually move your units, and to decide about defense or attack behavior, etc.
But those global and local AI systems are independednt of each other. And - at a distance - we can replace the local simualtions with throwing a dice to decide for the outcome, if needed.
And maybe there should be more layers than just two. Depends on the scope of the game ofc.

Calin wrote:

You should use low resolution versions of the map for remote events in the future and higher res maps for things that are about to happen.

Yep, but it comes with many pitfalls. If you naively scale your map down like an image, bounderies may merge, blocking pathways. Or boundaries may vanish, opening passages which can't be passed.
The undersampling / quantization problems exist in many places, and achieving robust solutions can become very difficult.
(I expect some issues with my graph reduction idea from above, for example. It's surely not as easy as the post implies.)

Calin wrote:

When writing code for AI we use a simscenario for each "my option enemy option" pair. 2 base build options on my behalf and 2 base build options on the enemy behalf is theoretically 4 low resolution simcenarios. But if we use a pasive version of the enemy and active version of the enemy that mounts for 8 simscenarios total.

Can player 1 even know about the two potential spots to build a base of player 2?

To avoid this complexity explosion, player 1 could think about his own options, considering only the known present state of the enemy.
The resulting AI might be still strong enough to beat human players, and nobody might ever notice a difference?

That's what i'm thinking at least, but i'm not RTS player and don't know how exploiting bad AI is a problem in the genre.
But just look at the real world - obviously wars can be started without a need for any brain at all. If idots can do wars, CPUs can do too? Ok - scratch that.

Calin wrote:

When you`re advancing in a new teritory options emerge, there are decisions to be made.

I'd prefer to think: 'I have certain needs and desires. When entering a new place, i look around to see of related options emerged.' That's much easier to handle, no? You only need to know what you want, and the rest folds out from there.

Calin wrote:

In a mutiplayer RTS match it is important to ... find out what the enemy is doing.

I can at least imagne. It's probably not easy to make good AI based on the obseravtions it can gather.

Calin wrote:

That's why figuring out all the moves in advance in an exhaustive way is probably impossible for AI.

Probably you can only do 'so mutch'. But if you do that well, and it's fun and challenging, it's good enough.
Though, i don't think we can emulate the experience of multiplayer with singleplayer AI.

frob wrote:

There are nearly 3 decades of old articles on this subject

For me it's just curiosity. I have no hopes of implementing such aproaches in my game. To keep things manageable I only use about 5 or 10 combat units per player, more than that and things get out of control (the game crashes or units start displaying buggy behavior when the game runs extensive periods of time).

JoeJ wrote:

At the cost of higher complexity, though.

A good aproach is to proceed the same way you proceed with pathfinding, start from the destination. You start from the very last moment and run the simulation in reverse. Tipically the last thing you attack is the command center so you have one unit "attacking" the command center whith nothing else around it. While the unit attacks the command center the HP of the command center which initially is 0 begins to increase. When the command center hp reaches the maximum level a worker is spawned with 0 hp next to the hp, the unit attacks the worker which begings to gain hp, when the worker has maximum hp another worker is spawned etc. Basically you're reproducing the distruction on the base in reverse. You use just one attacking unit because it's a coarse plan. You don't know how many units will make it to the last stages of the attack. At some point in reproducing the distruction on the base in reverse picture that you will be attacking enemy combat units defending the base. But the thing is you don't know where the enemy units will be when you will be attacking the enemy base so you roll back the moment of the encounter with the enemy combat units closer to present time. Basically you're imagining you're fighting the enemy combat units in YOUR base. That should happen sometime at the beggining of the game (which coresponds to the end of the reverse simulation). If the enemy combat units are not present in the simscenario implementation (real game that is) in your base you push the moment of the encounter forward in time (closer to the beggining of the reverse simulation), basically the encounter will take place when the enemy units are on the way to your base but have not reached it yet.

Now lets say you got to the point where you are about to attack the enemy base for real. You send your units to the enemy base using the shortest path and on the path near the enemy base you stumble on a powerfull alighnment of enemy tanks that blocks access to the enemy base. You don't engage the enemy just yet. You update the setup of the reverse simscenario and when you run it you observe that the enemy tanks distroy all of your units and when the simscenario starts your attack force attaking the command center is made of 0 units. So basically the simscenario tells you that engaging the tanks is bad. At this point you need alternatives. Lets say there is the option of going round the tanks there is plenty of space on the edges of the tank alighnment for that. Lets say there is a total of 3 or 4 options to avoid the tanks. The question is how do you "emerge" those options for AI. (note that you need to consider these options only at this time, you don't need the options sooner). You need a spatial orientation algorithm for this (One way to do it is to split the map into rectangular sectors of walkable and unwalkable areas. The tanks in this case would be an unwalkable sector. Then you would try to build a path using the walkable sectors) or you can use an enemy avoidance algorithm based on traditional pathfinding.
When you have found some alternaties you can run a simscenario for each of them.

Calin wrote:

For me it's just curiosity. I have no hopes of implementing such aproaches in my game. To keep things manageable I only use about 5 or 10 combat units per player, more than that and things get out of control (the game crashes or units start displaying buggy behavior when the game runs extensive periods of time).

You should be more self-confident. The videos you posted show you can do it. It's just a long way of learning and growing to do more.

Sounds the first thing you wanna improve is debugging skills. Bugs need to be fixed, not ignored. You never know which other parts of your program are affected i presence of mysterious bugs.

Learn to use the debugger in case you don't.
Write debug tools such as logging text to a file and also to the screen at runtime.
Beside text, are often better. If i work on pathfinding, i do viasualize the paths on screen. Only if i can see them i feel it's probably working correctly.

In short: Spend time on improving your workflow, even if that's overwhelming, boring, and not what you want to do. Because it saves you much more time than you have spent.

(I'm saying this for years and assume you still didn't listen ; )

In the tank example above you should run a simulation with tanks on the map and a simulation without the tanks on the map. This way you can tell if the tanks were the cause of the failure. You have to do it this way because you might have intelligence about other groups on enemy combat units on the path towards the command center that might be the real cause of the failure. You don't have to worry about those other units option wise (if they are after the tanks in the queue of things you will meet on the path) but they will affect the outcome of the simulation.