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.

For that comparison, keep the starting state and any random seed the same in both runs, and change only the tanks. Otherwise a different outcome could come from a different random event rather than removing that group

When it comes to pathfinding for 100 units you can do it free of charge if you run dijkstra at the begining of the game and compute accesibility for every tile on the map. For a 10x10 map you would have to run dijkstra 100 times and store the information in a 4d array. If you proceed this way you can have not just 100 units you can have 1000 units or 10000 units. No crazy optimization techniques needed.

Calin wrote:

No crazy optimization techniques needed.

But lots of memory, thinking of maps at practical sizes.
Adding buildings / other obstacles at runtime would also invalidate your data, without much hope to update it fast enough to remain realtime.
But yeah, a nice example of how to get a speedup from using more memory. Maybe we can have some after all those data centers have been built (or not). ; )

For now, just upgrade Dijsktra to A-star. Should be a huge speed up, maybe already good enough.

This discusion gets me thinking about steering. You can use a math formula to steer around a tank that takes 2x2 tiles on the map but how do you get past a compact group of tanks or a compact group of simple units. I imagine you would have to keep steering in the same direction for extensive periods of time, you would probably also have to skip path waypoints. In Starcraft 2 the compact group would split in 2 and let the unit pass through which seems like an odd solution )

With steering and flocking routines, many exciting behaviors emerge. The parting around vehicles is one of many.

Another fun set is when units have different speeds but steering wants them to stay together. Faster units tend to get excited, sometimes you'll encounter orbiting, zigzags, and run/wait/run/wait patterns.

Simple rules like "pass towards the left" create speed lanes.

"Split apart for oncoming units" can create lines of rows or columns. Northbound column, southbound column, northbound column, southbound column.

I would treat a group that will not move as a temporary obstacle for the route planner. Steering can keep a unit from bumping into the edge, but it still needs a route around the whole group if there is no gap through it

Calin wrote:

You can use a math formula to steer around a tank that takes 2x2 tiles on the map

I propose to stop thinking in tiles when it comes to steering behavior. Imo we are past that point.
Coincidentally i just saw this game on YT, showng lots of steerng behavior for all kind of vehicles:

Looking at the soldiers at the end, they litterally move like particles in a fluid simualtion. No movement seems quantized to a grid.

That's what i expect from a modern RTS. I'm not up to date with the genre, but this game is impressive as fuck.

Calin wrote:

but how do you get past a compact group of tanks or a compact group of simple units.

You could mark each tile occupied by tanks as blocked, and navigate using path finding. But you'll need to smoothen the trajectories to hide the grid anyway, so there is no way around of learning the 'math formulas'.

Or you could calculate a bounding rectangle, sphere, n-gon, or convex hull around the group of tanks, find the left and right most vertices of the bounding shape as seen from the simple uints, pick the vertex closest to to their current velocity, and navigate towards that vertex. You'll navigate around the group of tanks without a need for paths or grids.

Imo, the secod option isn't any harder to implement than the first. It's actually easer, if you have the basics in vector math and physics, which is both just common sense.

That's what i expect from a modern RTS

Yes, you will play until the novelty feeling goes away then you will place the cd or dvd or whatever somewhere and never get back to it. The problem with Starcraft 2 and games like the one you mentioned is that what you deal with is not a stupid robot that moves in straight lines anymore, but rather it`s something with it's own will.

Calin wrote:

The problem with Starcraft 2 and games like the one you mentioned is that what you deal with is not a stupid robot that moves in straight lines anymore, but rather it`s something with it's own will.

You mean the game becomes worse due to more realistic / natural movement, because the movement is harder to predict than a straight line?

That's the opposite of what i think. Becasue pathfinding on a grid makes arbitrary choices on when to take a turn. Do it now or one cell later - the path length remains the same, so it's random choice and unpredictable. It fails to find the shortest path of minimum euclidean distance. It's unpredictable zig zag trajectories.

Contrary, the advanced simulation gives straight lines and natural flows easy to predict.
Natural motion is easy to predict for us becasue we are used to it from the real world.

Natural motion is easy to predict

That's only a supposition. It LOOKS natural but the problem is that computers are not natural.
When I'm driving a car I want to feel the smell of gasoline and smoke, it keeps my senses on high alert. We are humans not animals our natural senses can ADAPT to working with technology, the interaction with technology can be very tight. Building supply depots (they have no practical function, it's just a sprite that you can not interact with) or the limitation of being able to select only 12 units at a time are annoying yet useful for your senses, you can feel the smell of smoke and gasoline. You can have a good grip on the machine only if there is a clear cause and effect chain. When I saw the group of units splitting to make room for some unit to pass in Starcraft 2 my confidence what shattered, I begin asking myself mabye I had pressed the wrong button. It's the enemy units the ones that display independent behavior not the units I'm supposedly controling. Humans and animals are magic their behavior is not driven by a strict cause and effect chain, I can guess only in broad terms what drives their behavior. Advanced behavior in games is nice but it's magic. Your senses are triked into believing it's the real thing.

Calin wrote:

That's only a supposition.

No. The reason you can catch a ball is you can predict the trajectory of a parabola. Becasue that's what you saw happening all the time since you're alive. You have learned about it before you learned to speak.

Now you are older, and you can no longer learn so easily and quickly. Learning artificial and quantized computer game patterns takes effort. It is exhausting. Eventually, rage quit and refund.

What i mean is: When making video games, we ideally achieve realism to match the players experience and expectations. And ideally we require skills the player has already learned in the real world before. This way the players can jump in and have fun right away. Building up specific skills to beat the game - e.g. various stratgies for RTS - is something the player learns subconsciously over time, ideally without effort. There can be frustration involved, but there should not be a need for 'practicing' to finally become good enough at playing. Playing should be fun, not work.

Calin wrote:

It LOOKS natural but the problem is that computers are not natural.

You can simulate Newtons equations quite well wih a computer, and the result on screen does look natural.

Calin wrote:

When I'm driving a car I want to feel the smell of gasoline and smoke, it keeps my senses on high alert.

Sounds you need a new car.
What keeps your senses at alert for real is your sense of acceleration.
Which sadly video games can not deliver, so realistic driving simulatios ar doomed to remain niche forever.

Calin wrote:

We are humans not animals our natural senses can ADAPT to working with technology, the interaction with technology can be very tight.

You say it yourself: It's WORK. And work is not fun.
(well, some work is ok ofc., but just for the sake of argument ; )

Calin wrote:

It's the enemy units the ones that display independent behavior not the units I'm supposedly controling.

Sounds you came into a situation where increased realism broke your expectations.
But your expectations on abstract gameplay have been learned from a younger you, from games now considered retro.
You have adopted an inferior standard, and you liked it. But this does NOT confirm this standard to be better for your potential players, which may have never played the good old retro games.

I'm with you, my friend. I became a retro gamer too. But we need to stay objective.
Imo you use the wrong arguments against realism. If you like retro and want to create retro, that's fine and needs no argument against any curret state of the art.

Calin wrote:

Advanced behavior in games is nice but it's magic. Your senses are triked into believing it's the real thing.

I would call something 'magic' only in cases i have no idea how it works. But that's not the case for video games. Speculating how it works always was an important part of having fun with games to me.

And i would not say it's 'tricking to believing' either. It's the other way around. I make it realistic for the reasons explained initially, to make it a more natural experience. If the consequence is that players feel more like 'being in the game', or the game feeling 'real', that's a welcome outcome.

I really like the coarse-for-distant, fine-for-close idea — it mirrors how players actually plan, with a broad goal first and details only when they matter. For steering, treating a tight group as one obstacle to flow around, rather than dozens of tiles, also feels much closer to how movement reads in play.

JoeJ wrote:

And ideally we require skills the player has already learned in the real world before

A video game is rewarding because it places you in roles similar to certain real life roles but real life skills and playing video game skills aren't the same. You have one situation when real life skills and vide game skills do match: the flight simulators used to train pilots where the player sits in a phisical cabin identical to a real life plane cabin.
Identifying images from the screen and matching them with images from your memory triggers a reaction in your brain, when you can somehow iteract with that image that's rewarding, it's like a dream where you choose what happens in the dream. Video game interaction makes your brain enter a certain state. The problem with dreams is that you can't have super realistic dreams, the experience can not be enhanced to the point where it resembles reality. Super realistic video games are OVER DOING it. When you have something very complex going on your brain is not captivated (intrigued) anymore.
(note: it's obvious we have different perspectives on the issue but the fact that I keep threading in the same direction doesn't mean I'm disregarding your point of view)

JoeJ wrote:

But this does NOT confirm this standard to be better for your potential players, which may have never played the good old retro games

It's about understanding your nature and building things you can work with. And I agree with you newer generations can connect better with advanced stuff.