the AI discussion

[mbu]

Hi,

I'm new in this forum and first i would say: From the short time I was playing this game it was great!

I've reading this post and I had an other way which might make the calculation of the hit probability faster. The problem could be solved by the graphic card very fast. It's made to make this kind of calculations. So when you are able to abuse it a little bit (I didn't read the source code, nor i know if we can access it in this way) its just adding a flashlight from the shooting player pointing to the targets boundary grid. Then summing up the values of the targets grid triangle edges illumination values should give a quit accurate hit probability (deviding by total light). To increase the precision of the calculation, one can increase the targets grid by additional points.

It's just a thought how it can be done with "invisible" light. It would be much faster for an often used method and very exact.

An other, nearly the same way is to let the screen show from the gun point of view with a view field which shows exactly the target, make the target a special color(lets's say red), make a in-memory image and show how many pixels of this color you have (in this case the amount of red images).
I hope we can abuse our engine this way. I'm not in graphic programming nor have I programmed c in the last years so i just can't do this myself.

It will be the fastest way to calculate the hit probability for a target, because the graphic cards are optimised to do exactly this calculation.
Of course this is just the rough description to give the idea.

[yobbo]

So, it's been really bugging me that the aliens clump up in places where they can't actually reach the player's soldiers.

It seems their positioning heuristic takes into account the absolute distance to the nearest soldier, so failing to find anything better to do, they minimize absolute distance, thus standing in corners "close" to the soldiers, and hovering above or below them on the wrong floor.

I have a proposed fix for this, but I haven't looked at the code yet, so I'm not sure if it makes sense.

My proposal is to calculate (once per turn, after the player has finished moving) the distance to the nearest soldier for every point on the map. I assume there must be some data structure in place already representing the movable area of the map, so this could be walked over for each soldier. Not too much of a computational burden as it's only done once per turn.

Thus in stead of taking into account absolute distance to soldiers, the aliens could take into account the actual movable distance, based on this calculated distance map.

It can be explained by saying the aliens can "smell" the soldiers .

In terms of the AI, I assume this is a fairly simple fix. Just change the distance metric to instead use the actual calculated walking-distance.

So I have two (and a half) questions, answers would help if anyone knows off the top of their head:

1a) Is there a movement grid structure I can easily walk over with a simple distance calulating routine?
1b) Where is the best place to store the resulting distance data? It needs to be recalculated each turn, and accessable by the alien AI.

2) Where do aliens decide that "closer is better"?

I can probably find the answers to these questions myself, but it will take some time to familiarize myself with the code. I figured I'd post my proposal and ask my questions while I do so.

[Mattn]

they are not taking the absolute distance to another solider - but the real path distance. BUT our max path distance is sometimes too short. E.g. an alien is not able to walk out of an ufo on the back if a soldier is standing in front of the ufo (can be seen in +africa). The movement data is already cached. But it's too short. If they behave differently like this - this is a bug. They should not use the absolute distance at all - as this is no statement about the reachability. If you see a part in the code that does this, please let us know.

[Mattn]

to elaborate a little bit more. What we need would be a memory about the last movement and why the ai did it. E.g. a target is too far away and we tried to get closer - we should try to get even closer in the next turn - and not walk back to the initial location. The behaviour based on scores (see g_ai.cpp top for the score defines)

oh, and to answer your second question (and maybe also your first question):
* We do have AI_PrepBestAction and AI_SearchBestTarget

for the caching we have the Grid_MoveStore

[DarkRain]

they are not taking the absolute distance to another solider - but the real path distance.

Sorry, but that's wrong, the AI does use the absolute distance - see the AI_[Fighter|Civilian|Panic]CalcActionScore functions: they are clearly using VectorDist/VectorDistSqr to get the distance to other actors.

[Mattn]

Oh yes - you are right - and this also makes sense . we need a line of sight and a distance. but an alien should not try to walk to the closest actor if this actor is not reachable by walking or not even visible.

@DarkRain: didn't you fix the ai-walk-to-invisible-actor-because-he's-closest bug already?

[DarkRain]

Nope, the AI is still unable of navigating a semi-complex map to save their lives. Duke was looking into it not long ago, and I remember that using the routing/pathing data for this was already discussed (and seemed the best idea), the thread should be around here in the forum.

[yobbo]

I couldn't find any previous discussion of using the routing info to solve this. If you could find a link for me that would be helpful.

So far it looks like this solution is complicated by movement depending on the actor doing the moving. It looks like the code can handle things such as smller actors moving thru smaller holes while larger ones can't.

That and the routing code is doing my head in.

Particularly

Code: [Select]

/**
 * @sa G_RecalcRouting
 */
void G_CompleteRecalcRouting (void)
{
Edict *ent = nullptr;

while ((ent = G_EdictsGetNextInUse(ent)))
if (IS_BMODEL(ent))
G_RecalcRouting(ent->model, GridBox::EMPTY);
}
Why is the routing info recaculated for every entity in use? Shouldn't there be just one routing table? Why does it relate to specific game entities at all? Am i misunderstanding?

[H-Hour]

Why is the routing info recaculated for every entity in use? Shouldn't there be just one routing table? Why does it relate to specific game entities at all? Am i misunderstanding?

My uninformed hypothesis which someone else will likely correct: I think the game may only be calculating the routing within a certain radius of each entity defined by their max TUs.

[DarkRain]

My uninformed hypothesis which someone else will likely correct: I think the game may only be calculating the routing within a certain radius of each entity defined by their max TUs.

Let's not confuse routing with pathing,

Duke is the one to ask about this but let's see if I can shine some light on this:
there is indeed only one routing table (well actually two: server and client side each have one), and as you can see G_CompleteRecalcRouting only recalculates routing for BMODELs which are part of the map (doors and breakables AFAIK) every other entity is ignored here, I don't know why is it needed but as I understand G_CompleteRecalcRouting is called once after loading the map, maybe it has to do with our random maps, as they need to be rerouted after assembly?

Also I can't seem to find the previous discussion, maybe it was on IRC instead...

[Duke]

Hi yobbo,
it seems that the helpful members of the dev team have already at least *mentioned* the answers to all of your questions. Especially DarkRain's guesses are very close to the truth. Not sure if those answers have been explained well enough so a newbie to the ufoai code can easily understand them. So feel free to ask

Let me add some points:
- both routing and pathfinding tables consume quite a lot of memory
- routing is cpu-intensive
- pathfinding is not, BUT
- the AI-pathfinding is very costly because of the additional stuff (hiding, shooting, RF)

For the situation mattn mentioned (africa) I coined the term 'The harvester problem'. There is an item in the bug tracker about this.

The major AI problems are:
- AI is calculated per alien ==> NO team strategy
- AI is calculated per turn ==> NO multi-turn strategy
- AI thinks in 'cells' (== one x,y,z place) as it's biggest unit ==> NO strategic view on the scene

Keep in mind that if we manage to make the AI much smarter, we'll have to rebalance the whole game.

[Telok]

I prefer to think of the current AI as a placeholder for when the real AI is implemented.

AI from scratch

1: check health/morale and set status
(different thresholds for different species, % of health/morale combo?)
cower, flee, insane, berserk, normal
examples:
bloodspider [flee 0-15, berserk 16-40, normal 41+]
taman [cower 0-5, insane 6-10, flee 11-25, berserk 26-55, normal 56+]
ortnok [flee 0-7, insane 8-16, berserk 17-45, normal 46+]

2: implement status per alien
examples:
normal= get weapon, move to comfort zone, do job
flee= maximum movement away from enemy and out of LoS
berserk= get weapon, move closer and/or attack nearest enemy in LoS with preferred attacks

comfort zone: a set of parameters per alien species defining things like minimum and maximum distances to allies and enemies, attack preferences (most attacks, highest damage, highest hit %), target preferences (civies, objects, players, nearest enemy, best % to hit enemy, enemy nearest death), concealment and movement preferences.

The distance to allies and enemies is to be a simple way to diversify AI tactics. Giving bloodspiders low minimums and maximums will make them clump up and rush the player, if hovernets have high numbers they will spread out and stay at distance. A high minimum and low maximum will make them stay at range from each other but move as a group, while no minimum and a max higher than the map size will let them wander at will. Combine with movement and concealment preferences to generate more dynamic action, hovernets and shevvar use 25% TUs moving, taman and ortnoks always reserve TU for RF, taman and bloodspiders always move out of LoS if they see more than 2 enemies.

The distance thing also allows for a check to the nearest ally/enemy, develop a path to it, path as far along that path as possible. This would be a troubling "perfect enemy information" thing normally but the telepathy virus/parasite allows it to work for the aliens knowing where they are in relation to each other. If need be we can use that for them finding the player or mock up a ranged brain wave scanner of some sort (improved IR goggle type thing or psi-detector that finds humans?) that allows this.

Pros: Different aliens show different tactics, solves harvester pathing issue
Cons: Needs flowcharting and programming that I'm not up to

[Sandro]

This is pretty much how current AI works.

[yobbo]

Sooo, after three failures that really should have worked, and now that i've cooled down from the resulting tantrum, i figure i'll just post what i wanted to do and hope someone can point out the best way to actually do it.

Here is some code that does not work for various reasons.

Code: [Select]

typedef struct enemy_distance_s {
/* Approximate distance in TUs to the nearest enemy (capped at 255) */
byte distance[PATHFINDING_HEIGHT][PATHFINDING_WIDTH][PATHFINDING_WIDTH];

inline byte getDist(const pos3_t pos) const {
return distance[pos[2]][pos[1]][pos[0]];
}
inline void setDist(const int x, const int y, const int z, const byte val) {
distance[z][y][x] = val;
}
inline void setDist(const pos3_t pos, const byte val) {
setDist(pos[0], pos[1], pos[2], val);
}
} enemy_distance_t;

/**
 * @brief Calculate the distance to the nearest enemy for every point on the map.
 * @param[in] routing The routing map (either server or client map).
 * @param[out] enemy_dist The map of nearest-enemy distances.
 * @param[in] team The AI team we're calculating this for.
 */
void CalcEnemyDistances(const Routing &routing, enemy_distance_t *enemy_dist, const int team)
{
/* Clear the distance grid: set all distances to max.
* (this is probably about 512KiB of data to maxify) */
for (int z = 0; z < PATHFINDING_HEIGHT; z++) {
for (int y = 0; y < PATHFINDING_WIDTH; y++) {
for (int x = 0; x < PATHFINDING_WIDTH; x++) {
enemy_dist->setDist(x, y, z, (byte)(-1));
}
}
}

/* Maintain a list of cells to be checked. */
std::list<pos3_t> cells_to_check;

/* Start with distance 0 at all enemy positions. */
edict_t *ent = nullptr;
while ((ent = G_EdictsGetNextLivingActor(ent))) {
/* Assume we are hostile to members of all other teams.
* (ReactionFire::isEnemy seems to work this way also) */
if (ent->team == team) {
continue;
}
enemy_dist->setDist(ent->pos, 0);
cells_to_check.push_back(ent->pos);
}

int updatedCells = 0;

/* Check the surroundings of each cell,
* to see if we found a shorter path.
* If so, update the distance map, and recurse. */
while (!cells_to_check.empty()) {

std::list<pos3_t>::iterator cell;
for (cell = cells_to_check.begin(); cell != cells_to_check.end(); cell++) {
int dist = enemy_dist->getDist(*cell);

for (int dir = 0; dir < PATHFINDING_DIRECTIONS; dir++) {
/* Get the cell leading to this cell in this direction. */
pos3_t from_cell;
int crouching = 0;
VectorCopy(*cell, from_cell);
PosSubDV(from_cell, crouching, dir);

/* Is it connected?
* For now don't take into account size etc,
* just if there is a grid connection. */
if (!routing.getConn(ACTOR_SIZE_NORMAL, from_cell, dir)) {
continue;
}

/* How many TUs does it take to move from there to here? */
int tustep = Grid_GetTUsForDirection(dir, 0);

/* Have we found a shorter distance? */
if (tustep + dist < enemy_dist->getDist(from_cell)) {
enemy_dist->setDist(from_cell, tustep + dist);
/* Add to the list to be checked next cycle. */
cells_to_check.push_front(from_cell);
updatedCells++;
}
}

cell = cells_to_check.erase(cell);
}
}
}

The most obvious reason this does not work, is that std::list doesn't know how to deal with a pos3_t. That's easily solved by defining a new 3-pos struct to use here and converting to and fro, but it's not the main problem.

The main problem is that it seems this combination of things i want to do is unable to be called together from anywhere in the codebase. Specifically G_EdictsGetNextLivingActor and Grid_GetTUsForDirection. In grid.cpp it can't call the G_ function, and in g_ai.cpp it can't call the Grid_ function.

Maybe i'm wrong about that, and there's some way i can easily do this, but in the end i still have no idea where this function should go.

Probably it wants to be called from G_ClientEndRound? And the enemy_distance_t must be made accessible to the AI somehow. The routing table needs to be accessible to whatever is calling this function, and enemy_distance_t needs to be declared somewhere everyone can see it.

It's possible there's a better way to organize things, but i've already tried integrating this in three different places unsuccessfuly, so i really hope someone can look at this and tell me where and how it can fit in.

[DarkRain]

You should be able to call the GetTUsForDirection function via the game_import_t function pointers (See for example how G_MoveCalcLocal, G_ClientMove and co work)

On the other hand, IIRC (most?) std containers are not to be used, so that might be a problem