The RTS ai...

Okay, I'm making an RTS, and it'll be a simple RTS. You have a mission, you control only one type of unit, and so does your enemy. You only have one objective, and so does your enemy. Now, the maps are reletively small, and I was wondering, what is a good algorithm for my AI? What processes should it go through to acheive it's goal?

The first mission you have to defend your bunker from the AI, who is attacking you. The goal is simple, the AI wants to kill you. The ai sends waves of troops in increasing number. What is a good algorithm here?

I think your methodology should be simple point and click with vec_dist calls for 'attack, defend, retreat, reingage' coupled with simple path finding to avoid lock-ups when a team mate gets in the way.

Maybe state machines should be employed here.

I have had a few tests with rts and never completed any so am not sufficiently competent to give a definitive reply, only the above guess .

My suggestion is , make your (all of your) units 'universal'. I mean , if a certain skill (for interraction) is for example 1 , the unit will go to a certain place. This way , you could script player interraction (when I press LMB , change skill to 1) and AI interraction (when Finite State Machine decides , change skill to 1 , to make the unit move.) This way you could use the same actions for player & AI.

Hi Kojak,

I will give you some advices, like I do the RTS-AI, which is nearly finished, in "2662 - The Year of the Conflict".
In my opinion the AI consists of two important parts.
1. Multi-tiered-AI
2. Influence-Map

A Multi-Tiered-AI is similar to the ranking in the army. There are units which can fight, but they are all working by their own (just use Finite-State-Machines like WAIT,ATTACK, MOVE, RETREAT....what ever you want), there are sergeants who control a group and tell the units to attack someone or scout (you need FSMs for the groups ..... and finally their is a commander who tell the sergeants what to do.

An Influece-Map is an extra layer on your terrain. Use an array for example 20x20.
Now, you can get lots of informations:
1. Is the tile unexplored, belongs to the player or AI or is it a conflict area? (This is important for scouting)
2. You can give each tile a weight by simply checking in which tile the entity is and adding f.e. the health points of the units to the tile value. Then you can also calculate the influence to neighboring cells (long distances to units are contribute less to the influence map then short distances to the unit). This gives you the power to get lots of informations like weak spots or best path....and you can make lots of other influence maps, too.

I hope this will help, you.

Bye G.S.

I like that influence map thing. But how would you set that up? How big would each tile be? Would every unit have to check where he is? These are all problems that need to be explained, as this is my first run with an RTS. The soldiers were the easy part, the AI is a toughy.

Yeah, I already have all the units set up. See, they work based on animations. The units do what you tell them. They handle their own methods of attacking, moving, etc. Lets say that we have a soldier(you), and to make him move:

you.anim = anim_move;
you.gox = target.x;
you.goy = target.y;
you.goz = target.z;

or to make him attack:

you.attack = on;
you.attackhandle = handle(enemy_guy);
(all of the anim_ are defined as 1, 2, 3, and .anim is declared as a skill)

See? All my ai is going to do is simulate an actual player. I already have the player's controls hooked up to the mouse.

What I was needing was a good process that the AI can go through to figure out what the best strategy is, where the weak spots are, etc. I'm going to make my maps bigger later on, with more objectives such as to take over a building, secure and defend a power plant, etc. I was just wondering how to make my AI smart-ish enough for it to be fun.

One more important thing, this game will be small, so there is only one type of unit, but they have special abilities. One side can bring back enemy soldiers to fight for them, and one side can crouch, to snipe the enemies. Of course, both of these have thier drawbacks, such as crouching takes time to set up(which is handled by the soldier), and the ressurecting takes half of the unit's life and speed(which can be recovered by killing, and is also handled by the unit). So, you know, the AI needs to use these abilities.

Last, do you know of a good auto-setup pathfind system that sets the nodes for you? I really don't want to have to set up the nodes for every map. I also want to incorperate a "map-builder" once you complete the game.

Lots of questions....ok I will give my very best to explain:
1. How big is each tile ? This depends on you and your memory. I use for a large area a square by 20x20 tiles. All I have to do is to devide the areasize by 20 and then I know how big is each tile. One hint for you, if you use 20x20=400 tiles and you save 5 informations in each tile your array is of scale[2000]...be carefull with you resources.
2. For update the influence map - updating takes time and your game will slow down. But you don't have to update this that often. I'm using a master AI, which is update every few seconds and the group AI is update every second and the unit AI is update every time. During the update you have to check every unit and its contribution to the map tiles.
3. I think it is easier to use just one skill for the units status....
you.status=status_move or you.status=status_Attack
then just use define
define status_move=1;
define status_attack=2;.....
4. For getting informations like weak spots:
use the influence-map, check all tiles with tile_status=enemy(belongs to the enemy) the one with the smallest value and f.e. shortest distance is the next attackgoal.
5. To decide what a unit should do...use a formular, f.e., a big tank is coming and a single soldier is waiting just in front of him, what to do retreat or fight? Formular: decision = enemy.hp+enemy.attack_power - my.hp - my.attack_power. So if decision is < a special value retreat else attack the enemy.
6. Pathfinding is also very important in an AI, in some cases obstacle avoidance algorithm are good enough, but sometimes A*-Algortihm or similar are very important, too. But be carfull using them very often takes lots of resources (150 entities calculating a new path at one time).

So, I hope this will help you.
If you have any question please ask again.

Bye G.S.

There's only one problem, it is a command & conquer type game where the troops move freely, so that no tiles are used.

Is there any way you can combine a self-creating, chart pathfinding system(where a chart is made at the very beginning telling where to go from your location to get to where you're going) with your influence map? That way the nodes of the pathfinding system could be your influence map, and the AI would know where the troops are, and based on some if statements and some formulas, know how to attack. I could also allow the AI and player to follow footprints to find the enemies. I can also set up an AI "unknown" factor, where they have no idea where they're going, or where the players are. This can make a "search and Destroy" mission even more fun.

I just need to know how to set up this self-creating pathfinding system. I can handle the charts, and the influence map, I understand how those work. I just need to know how make the nodes space themselves apart, and fall into place on the terrain. Then once they are in place, I can code them to scan eachother, delete the ones that are too high, or on top of buildings, etc. A little help would be appreciated on the actual pathinding part, where I generate the chart.

I'n not quite sure, if I understand your question correctly. Your problem is the making of the nodes on your terrain?
So, you can use the influence map and the center of each tile could be a possible node position.

I understand that much. I'm just asking HOW do I make the nodes do that? I need a specific description. I don't need the code, but I do need to know how to code it.

After the pathfinding system set itself up, I was going to make each node a part of the influence map with a skill and some defines such as "player_control", or "neutral_control" etc. I was going to make each node a part of the influence map, and therefore make it easier to code the AI.

Now that I know how to code good AI(thanks to all of your help), what I really need to know now is how to code a pathfinding system that positions the nodes on the terrain.

Ok, you're thinking of nodes as used in the WED, aren't you?
But if it is so, forget about that. Just use in extra layer (you can combine it with the influence map) or use your influence map as the layer for the nodes.
You should have something like this (for 5x5 tiles)
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
All you have to do is to find out in which tile is your unit and in which tile is your goal, then start the pathfindingsysteme and erverything should work.
The tile is your node or in an extra layer some nodes belong to one tile.
Is this your problem? If it is not, please make an example.
Bye G.S.

Ohh.. I see where the confusion is.

See, in all of my pathfinding systems, I have never used WED's nodes. I use a low-poly model, and assign it an action which is "pathfind_node". This is a part of the whole pathfinding map. Although I have added to my system over time, I was going to scrap it and start from scratch this time, in order to fit it in with the whole RTS system. See, I'll have an action called "pathind_node", that I will set up to scan every other node, register itself into an array(the influence map), and set itself up. The code will generate the needed number of nodes over the terrain/level, make the nodes drop from above, and position them over the whole level. This done, the ones that are too far above all the others(impassible terrain such as mountains and buidings) will be deleted before they register so that no troops can go there. The rest will register in the array, and the AI will be able to use skills and flags of the nodes as it's influence map.

So if a player sends some troops to a location, the nearest node will become "occupied" by the player. The AI will react accordingly.

I understand how to make the influence map. I understand that perfectly. What I'm having trouble with all of this, is how do set up a function that creates all the nodes, and positions the nodes far enough apart? I was going to make the nodes drop themselves, but how do I tell the code what the boundaries are in which it should create the node models? How high should the nodes be created for them to drop correctly? How many should the function create?

Before I answer, just for me, if I understand you correct:
(LOL sometimes discribing a problem is not that easy )

You have low poly model who acts as a node.
You assign a action to it called "pathfind_node".
Then you want a function who creates lots of such low poly models and align them in a for example grid pattern.
You want to drop the models on your terrain, so you're intresting in a special hight, too.

So, you need a function who does all this ?

Are these your problems?

Bye G.S.

YES! Thank you! That is exactly what I want.

would such a function work in a turn based game? to enable the pathfinding on a flat 3d grid?
like this

Ok, if you want to do it that way, I will give you some hints.
I would make a grid similar to the influence map.
- So you need two variables: grid_x_max and grid_y_max (grid_x means the maximum number of grid tiles in x direction)
- important information: grid_x_max * grid_y_max = number_of_nodes
- tile_width = level_width/grid_x_max (example: 40000/20 = tile_width = 2000 .... tile_length similar with y_max
- example for 3x3 grid (grid_x_max=3, grid_y_max=3)it looks like this
7 8 9
4 5 6
1 2 3
- make while loop from i=1 up to number_of_nodes
- inside the loop: calculate the position of the node (use the cornerpoint or the middle point) - (the next calculation is for your lowest level borders in x and y direction at Zero, if it is not use an offset)
x-position (middle of the tile)= ((i-1)%grid_x_max)* tile_width + tile_width/2 and then
y-position (middle of the tile) = (int((i-1)/grid_x_max))* tile_length + tile_length/2
( for better understanding make a scatch on a sheed of paper then everything should be clear)
- the z-position, I think there are some possibilities like using trace from a position (x,y calculated before, but z much higher then the terrain), so you can calculate a good hight for every node. Or using a very high z-value and let them drop or ......
- use ent_create at the x,y,z position

This could be one way for such a function.
I haven't tested this pseudocode, so I hope everything will be correct. But it is one possible way.

I hope this will help you !!!

Bye G.S.

Thanks. I now have a blueprint for my code...

Thanks a bunch. That helps a lot.

I do have one more question, what is better, having the troops calculate the path once they are told to move, or calculating the path in advance and have the troops check an array for where to go next? Would it be worth the RAM space to store 100*100 handles, or would it be worth the computing time to find a path through 100 nodes?

These are some questions which are not that easy to answer, because depends on your type of game.
But you can answer the questions yourself:
If your game has 100s of game entities and every entity has to do a full pathscan to find the next waypoint, when the entity arives at a new node ... with this method dynamics of units can be taken into account, BUT this will kill your FPS.

If your game has only a few units this method should be no bigger problem for the FPS.
It also depends on the number of nodes - to find a path through 10000(100*100) nodes can take much longer than calculating a path through 1000(10*10) nodes.

What kind of algorithm you will use, is also an important question. For some applications a Brute-Force-Algorithm could be much faster than for example A*, for other apps A* is the one and only. Sometimes simple obstacle-avoidance could solve problems, too.

All depends on your type of game.

I hope this will help you a little bit.

Bye G.S.

Thanks. It does help.

However, what is this obstacle avoidance algorithm you keep talking about? For my level plans that could me all I need!

Hi Kojak,
sorry, I can't give you a name for an algorithm or a link, sorry. Just keep on searching for the topic Obstacle Avoidance. This could be enough for your type of game.
Bye G.S.

Raiden posted an obstacle avoidance code in this forum. It's in a Loopix post titled "Avoiding object while walking to player "