the AI discussion

[nonickch]

I took some time and had a discussion with my brother (who just happens to be into the math we need because of engineering) and he could identify some of the maths we need, without having any compromises.
Let's hope that works out ok, otherwise it's cpu grinding time.
Interesting thing about the RF/nock there dodon. Maybe if we can conjure the math properly we could give a helping hand to that part of the code. 100's of calls to the shoot is probably quite painful to the cpu (albeit in a time when you don't really need the cpu). So the mockshot tries to do something similar like us? Hmmm

Shaunc311: Yes, that's pretty much the stuff we'd have to replicate for shotSingle. For the AoE equivalent, I really didn't look much into it since I did expect it to be more complicated.
Even if we replicate the needed functionality in the AI, the cpu expense will stay about the same (we still need to play with vectors). The gain by copying the code/calcs is ofc not to abuse a system that wasn't meant for our case. I'll go and take a look at the RF code dodon mentioned since it does look a lot like ours (I'd like to see how it handles the out-of-turn player_t struct).

Right, I believe we should wait a few days and see if we can solve it by maths. If not, we can bite the bullet and copy code into the AI (or augmenting mock shot code to fit our needs).

Here's the issue as I described it to my brother, relayed here to make sure I won't ask the wrong things from him:
The point is to accurately (eve semi-accurately if it's faster/easier) find the expected dmg and hit % to a target with the least possible resources. As it is right now, we take 10 shots to the target, avg the dmg, which gives us  roughly a avg_dmg*hit_ratio that fits our needs. <Explaining the trace-rand-retrace mentioned in my last post>. The tracing/intersection math is what's really expensive, and we'd like to limit it down to one. Given that we know the gaussian generation values, can't we just estimate the hit% to the target by taking into account the fact that the rands apply to the equation of the vector?
Apparently this isn't something hard, BUT, we do have issue no.2:
Well yes, but we don't care just for the hit % to the exact target (a point), but to the body of the target itself. So it's many points. And to make matters worse, at any distance from our gun, there can be an object partially occluding the hit window. In this case we want to project the 'shadow' of the object to the target window and subtract the 'target' area by it's shape.
Suffice to say this isn't as simple as the first case scenario as he started foaming a bit.

So, am I missing/forgetting something from my description? It'd be a drag to make him run the math only to find out at the end that I missed an important point.
edit: ah, yeah, we ignore dmg from bullets (non-gravity weapons) since the avg damage is easy to calculate. In explosion/indirect weapons the window suddenly expands and lays on the floor, while projecting shadows now becomes something that I can't even describe with magic markers. Ergh, maybe we can just bite the cpu bullet when the weapon is gravity-based?

[arakis]

maybe aproach it from another angle, insted of calculating 10 shots to a target and getting an avarage, why not read the variables used in single calculation, and estimate from them rthe given percentige. maybe loging  all shots made during the some arbitary game and averiging the results in a fast lookup table?

btw i am not sure the game need the hit calculations to be that accurate I think +-10% is more then enough(for the percentige hit prediction)

[nonickch]

So, here's the current plan with the hit % calculations, WITHOUT support for target occlusion from random things in the line of fire (more on it later):

Given the optimal shot point (the point which G_ShootSingle considers as the target point for a target entity), we really want to calculate the hit probability for every point in space the entity occupies.
We drop the calculation the 3rd dimension (which does lead to less accuracy but much greater performance) and essentially we calculate the hit % for each point in a slice of the target (perpendicular to the shot). In simpler terms, try shooting someone with only one of your eyes open.
So, in essence we have something like this:

----**----
---***---
---***---
--*---*---

legend:
*: points of the 'slice' we care about shooting

Because calculating for each point is a very expensive procedure, we scan line by line for each axis:
Calculate the chance a bullet will land in the first line's RANGE interesting points, and so on.
Then calculate the chances a bullet will land in the first row's interesting points, and so on.

Bear in mind that we calculate for a range, which in this example is for 2 points in the top line, and 3 for the 2nd. Now, we have to translate the range hit % to point hit chances. There proper way of doing that is employing the CDF cumulative distribution functions of a normal distribution. Now, this looks very expensive. Instead we use lookup tables, that are commonly used today to solve such problems by hand (yay, for saved cpu cycles). This is another loss of precision.
So what we really plan on doing is calculate the hit % on the series of the points we're considering and then assign individual hit % according to a weight defined in the lookup table. So, for example, the series of 3 points in the 2nd row end up having a chance of 12%, we give 12/3*lookup_weight on each on.
The reason for having to do this once in the x axis and once in the y is that we have 2 gauss vars in the shooting calculations. Once for each variables. The final hit % of each point is the multiplication of the values it was assigned on each scan.

Up to here we have 0 tracing calculations and quite the lightweight math (avoiding the erf function is a big plus), but we also have 0 idea if there is an actual Line Of Fire. We basically calculate with (an expectedly) very nice precision what would happen if there were no obstacles in the course.
We're pretty confident that up to here we're on a good road, and even though the equations we used were for non-gravity (bullet-based) weapons, the parabola of the grenade/launcher shouldn't be that difficult to implement.
Interesting observation: Ever noticed that many games can only predict up to 95-7% max shot chances? I believe this is a direct result from the gaussian randoms and the  respective calculations (like the ones we use here).

The problem is now occlusion. Given our previous raster-like approach, we need to find out which 'points' are occluded by objects in the line of fire.
Tracing shots for each and every one of the points and then calculating intersections with objects is right out of the question, since that'd probably be more expensive that the sampling that swamps the AI atm.
In theory, we could try create a cone (or pyramid if that's expensive) originating from the gunpoint and having as it's base the 'slice' we're shooting at. Then, find all objects contained/intersecting this cone and project their shape on the slice. All points that are overshadowed get their hit % set to 0.
Unfortunately, not even my brother could think of an easy way to run the math, nor me think of any function I've seen in the code that could handle that kind of intersection calculations.
The simplest thing we've thought of is to trace the shot on the center of the 'slice' (the perfect shot) and depending onto whether that gets through:
a) Consider the shot impossible (even if the occlusion is light and any accuracy deviations would land us hits)
b) Project only that object to the slice and use it's shadow.

I believe (b) is what the gamer sees in the UI (hit % along with the red part of the line if the perfect shot is not possible), and what we'll probably end up with.

EDIT: the cl_battlescape.c/CL_GetHitProbability, but we couldn't grasp... Oh crap, I think that function does exactly what I've been talking about here. Will try to use that instead of reinventing the wheel.

RE-EDIT concerning CL_GetHitProbability:
Ok, so the difference (the ones I can grasp at least) in that function is that it considers the target (the actor for our considerations atm) to be box-shaped.
Is that true in game-terms, or do we actually have the actors have more complicated/non-convex hulls?
From the looks of it, the chance to hit that box is calculated just fine, it's the method of calculating occlusion from objects in the LOF (to the box-target) that drops the accuracy. If you take a look at the function you'll see that it takes 8 prefixed (in width/height percentages) points to the target and traces a line at them. After doing that, it multiplies the hit percentage with the percentage of traces that actually went through.
I don't think it even considers shooting the center of the target (need to double-check), which probably leads to the 1 or 2 occasions that bursts for 95+% chances all miss because they land on a protrusion. Apart from that, all traces are considered with equal weight (in terms of their ability to reduce hit %), which is true for uniform distribution but not for our gaussian: occlusions at the edge of the window have minimal hit % impact compared to something close to the 'perfect shot'.
Unless I copy/pasted something wrong in the AI code (which I probably did), I noticed serious deviations from the sampling code and the predictive code where there is partial occlusion in place (I think that happens a lot when there's that africa-map fence).
Obvious possible semi-solution is to reposition & weight those sampling points.

Since I did look a bit into bsp trees looking for a 'perfect' solution, I was told that it's probably possible to employ the bsp tree while trying to find occluding objects (as in possibly do it fast enough):
Our problem: if the gunpoint is a lightsource pointing at the target-box, find me the parts of the box that are shadowed from random objects in the map.
Now, the basic idea is to traverse the bsp tree and keep checking for objects intersecting the pyramid defined by the gunpoint and the target box. I'll bribe the graphics-geeks with coffee tomorrow and see what they really meant. If this works, it's all up to profiling to show us if the performance hit is worth it (at least we could use it in the UI if it's too heavy for the AI).
A notice on performance: we're already traversing the bsp tree for each sample-trace, so this might end up being faster (don't know how heavy the object intersection math is compared to the line intersections).

Question: what is the edict_t->origin point? Is it the center of the object, or some other predetermined point?

I know I need to at least release the code I'm currently working at, but it has so many leftovers from previous experiments, I'm ashamed to show XD. Will have to cleanup and post.

[shaunc311]

Finally back online and I had a thought.  

We are using g_trace to make a bunch of lines to simulate %s.  Can we instead make 1 trace but make the end point larger and larger (based on the ACC) as it traces away from the gun almost like a cone?  Then calculate the % based on the surface area of the trace circle when it hits the target.

So if the area of the circle at point X is 400 and the overlap is 200, it would be 50%.  

Then if something is in front of the target, we can figure out which percentage of the circle is blocked.

For example, two objects in front of the target.  The area of the target circle at the first object is 100, and 30% of it is covered.  The area of the target circle at the 2nd object is 200 and it's 15% covered.  The area of the target circle at the target is again 400, with 50% coverage.  Since we still don't know how much of the 30% and 15% are overlapped (but we probably could figure it out somehow) we'd probably say the shot has (((.5 * 400)-(.3 * 400)-(.15 * 400))/400 = (200 - 120 - 60 ) / 400 = 5%

And I just realized that all those 400's cancel out so it's really just: .5-.3-.15 = .05.

Not sure how this would work with grenades though.



Yeah...pretty much ignore this.  I spent a lot of time looking at the trace functions and I'm not seeing a way to do it.  It also is probably oversimplifying stuff.

[shaunc311]

The main loop in AI_PrepBestAction is also a bit buggy

Code: [Select]

/* set borders */
dist = (ent->TU + 1) / 2;
xl = max((int) ent->pos[0] - dist, 0);
yl = max((int) ent->pos[1] - dist, 0);
xh = min((int) ent->pos[0] + dist, PATHFINDING_WIDTH);
yh = min((int) ent->pos[1] + dist, PATHFINDING_WIDTH);

...
/* evaluate moving to every possible location in the search area,
* including combat considerations */
for (to[2] = 0; to[2] < PATHFINDING_HEIGHT; to[2]++)
for (to[1] = yl; to[1] < yh; to[1]++)
for (to[0] = xl; to[0] < xh; to[0]++) {
const pos_t move = gi.MoveLength(gi.pathingMap, to, crouchingState, qtrue);
                                if (move != ROUTING_NOT_REACHABLE && move <= ent->TU) {

I think I have found a couple problems that might need someone to verify.

The first problem is the border consideration.  It's perfect if the actor is in the dead center of the battlefield.  It is wrong if the actor is by an edge.  For example:

Let's say an actor is standing on the right edge of the map, but still vertically centered.  Instead of having a box with a horizontal side of (tu+1)/2 + (tu+1)/2 (or just tu), we have (tu+1)/2 + 0.  If I'm right, then that is just a simple if/else fix.

The 2nd problem is the last if statement.  I was curious as to how inefficient the loop was so I added an else to it that just counted the number of unreachable moves.  Depending on the position of the alien it was between 200 and 11,000.  I'm unable to figure out why it spikes that high.  My next step was to see how many possible moves there are to see if 11,000 is just noise or a lot and something is wrong.  I might try that tonight.


Update:
Ok, so it is pretty significant.  The aliens are averaging about 8700 impossible moves out of 9248.  One thing I noticed is that the math above assumes 1 TU per move which is optimistic.  Another thing is that it tries all 4 floors, but this map only really has 1 (africa small).

Maybe a better calc would be:

Code: [Select]

dist = ((ent->TU + 1) / 2) / TU_MOVE_STRAIGHT;

This results in 2048 total moves with about 200 being possible (again, just 1 floor out of 4 being possible, and I always assume a straight walk but the real path is probably curved).  This seems to be a significant performance gain.

Update 2:
Debugging this has made me realize that the original /2 was for TU_MOVE_STRAIGHT but never labeled that.  The square needs to be 2TU/TU_MOVE_STRAIGHT to check the farthest the alien can possibly walk in all directions.  That explains the performance boost I saw but it certainly crippled the aliens. 

I still don't like the loops.  Mainly the issue I have now is that PATHFINDING_HEIGHT is always 8, even if a map is only 4 levels tall.  The other thing is that the PATHFINDING_WIDTH is always set to 256 but I think the Africa small map is a lot smaller than that so a lot of movements aren't going to be reachable.  A better implementation would be a sphere around the actor that has a radius of TU/TU_MOVE_STRAIGHT.   

[nonickch]

shaunc311: well, keep playing with it

I was kinda afk the past 2 weeks, so I just came back to my old mess:
the CL_GetHitChance is most of the math I wanted to code, so I opted in copy/pasta'ing it while fixing the very annoying partial-occlusion bug it has (see last post).
Instead of multiplying the no-cover hitchance with the percentage of the 8 tracings that were succesfull, we're going to assign weights each 'hitbubble' that the tracing checks for. So missing the center bubble of the target is way more important than missing one on the edge.
My brother is out there fixing this atm, but we have one very important question we need answered before we can even start:

What point of the 'model' is the edict_t->origin?
Is it the center of the object, or some corner of it?

We kinda need that so we can extrapolate the center of the shooting surface and start creating the boxes.

[nonickch]

I'm close to producing something semi-usable (pending the fixes ont he hitprobabilities), and I spent my last day debugging my working copy.

Here's one thing that really puzzled me:
some aliens end up having "ent->chr.reservedTus.reaction>0" while the other members of the reservedTu struct seem uninitialized (like weapon).

AI_FighterCalcBestAction considers using "tu = ent->TU - move", which is fine as long as noone has enabled RF. This ends up in aliens trying to use more TU's than they have while shooting (G_ActionCheck returning qfalse), and even worse, when moving (so they end up a few spots before their cover destination in plain LOS/LOF).
I replaced the usages of "ent->TU" with "G_ActorUsableTUs(ent)", as an immediate patch to this behaviour, but this needs to be looked into more detail as it gimps some aliens (less tu's) without a reason.

For some reason RF keeps giving my alien who's interrupting a chance to play as if it was his turn. Somehow it only works for the alien that is reacting, and I like this one. The problem is that the G_ActionCheck always returns false because "level.activeTeam != player->pers.team". activeTeam is set for the player.
So currently, this RF doesn't work with the AI I'm building unless some changes in trunk in the past 2 weeks adressed this issue. If someone is up-to-date in trunk, try and see if G_ActionCheck's first if statement is ever entered while you're causing a RF.

Also: please consider rolling the 2.3 AI back to it's release version, at least for changes produced in this thread. Lemme play around with the AI in the trunk, and if we deem them to be proper AND STABLE, then we can copy them to 2.3. You could keep the dodon patch if you think it's ok, but I believe it's behaviour is only fitting along with the fixes in the damage estimation.
The mess I created by that 'innocent' code refactorization that got posted in 2.3 introduced a series of crash-bugs. Thank god for geever pointing that out to me the hordes of angry players.

UPDATE
Ok, since the playtime is now below 2-3mins for small maps, haven't crashed in 3 hrs and I merged with latest trunk, I guess you can have a look at my current work copy and see how it feels:
the diff vs trunk 31041. I have no idea how easy it is to apply those, I spent like 40 mins trying to get mine to work when I was moving to latest trunk.
The entire g_ai.c file if you don't like the patch You should also add "#define GUETE_DAMAGE_AVOID_FACTOR   0.4" in g_ai.h.
PLEASE DON'T COMMIT THE PATCH. There are quite a few things I need to do before we can consider that one, namely the performance.
Kildor on IRC mentioned that he gets an undefined reference for TR_TestLine on line 165, you can just delete lines 33 up to 203 and get away with it (as long as you don't try to enable math estimation as mentioned later on). Also delete the entire AI_CalculateDamageMath in this case.

Now some general notes on the code: Currently only the sampling damage estimation via G_ShootSingle is in, after applying some sensible optimizations. You can find some blocks of "#if 0/#endif" that drop the main dmg estimation function of 31041 and most importantly the code that enables selection between sampling and math-based damage estimation.
The reason why the math-based (see: CL_GetHitProbability) is out is because:
a) it has some inherent problems with occlusion (as mentioned in previous posts) which are still not fixed
b) I think I did something wrong. The result comparison between those the two estimation methods vary so much, as to imply it.
Uncomment the block before line 500 to see the difference with the math enabled (while commenting out line 500). You may wish to also comment-out 494-497 and all lines referencing testTotalDamage, these are used to compare results from both damage estimations.

You will find many //-style comments, these are things that need to be removed/ironed-out before considering to applying this patch to trunk.

I'd mention the new wonderful things I saw my critters do, but I'm biased and want to hear your own comments. The bad things I've spotted so far that I need to fix are:
* Need to preclude from the G_Vis calculation (next to the HideNeeded) any units we expect to kill. Example: a machinegunner chose to run away and hide from a lone knife yielder that had the misfortune to end his turn 2 blocks away from him. The knifer was also the only one in the building.
* Get rid of the RF TU's that are auto-magically held for some (apparently random) aliens. Waaaait a moment, I do remember that shaken actors 'refuse to let his guard down', maybe this is the perpetrator?

Also, in reference to the dodon patch, I switched the "!HideNeeded || !G_Vis..." to "!G_Vis && !HideNeeded". The reason is that you want to be BOTH non-visible AND non-shootable, and in that order, is because:
a) If you're visible, you're most likely shootable, so don't use the horrendously expensive HideNeeded (I kinda beefed it up a bit)
b) You can be non-visible and still shootable: EXACTLY Behind someone's back (so CLOSE_IN maximizes too). Which was what the critters (melee units mostly) would prefer to do in closerange. It can be 'oh WOW!' if you didn't pay attention on the enemy's turn, but unless we can find a way to only allow this via non-visible flanking moves, it's too silly.

A very precious performance trick that I just thought:
Since the G_Shoot*'s are the performance hitters, and AI_HideNeeded really hammers those mulitple times for each alien, why not create a 'Threat Map' that is common for all the aliens? The only thing mobile in our turn is us, so all the damage an enemy can apply to a certain square is almost (unless we cut a LOF with the body of an alien) fixed (sans the armor protection). Assuming that aliens really consider 200 spots to move (as per shaun's post), they will also check damage received from 8 enemies, with an avg of 3 different firetypes. So 200x8x3=4800 calls to damage estimations (ha! times 10 for the sampling)
Then we should (we actually don't) do the same in the case we shoot-and-move (FindHidingLocation), times the amount of aliens we move == the reason this is still slow.
If we share a 'threat map' common for all aliens, we should be dropping the performance cost of hiding anywhere from X-fold to 2X-fold (where X is the number of aliens we have).

[Lew Yard]

/* evaluate moving to every possible location in the search area,
    * including combat considerations */
   for (to[2] = 0; to[2] < PATHFINDING_HEIGHT; to[2]++)
      for (to[1] = yl; to[1] < yh; to[1]++)
         for (to[0] = xl; to[0] < xh; to[0]++) {
            const pos_t move = gi.MoveLength(gi.pathingMap, to, crouchingState, qtrue);
                                if (move != ROUTING_NOT_REACHABLE && move <= ent->TU) {

Glancing at that snippet, it strikes me that if you're willing to (1) store movement costs and/or paths, (2) ignore movements that aren't from one adjacent tile to another (which would presumably exclude aliens leaping from a ledge to a multi-step drop), and (3) stipulate that aliens use a single consistent heuristic during movement (either maximizing safety, or maximizing speed) -- that you might be able to save some computation by caching.

Under those assumptions, the 'best' movement from one tile to another will likely be the 'best' movement from the source tile to an adjacent tile, plus another movement.  This is false if you aren't willing to assume (3) -- e.g. it might be 'worth it' to walk standing to one location IF that leaves TUs to reach a safer location, while if that intermediate destination were actually the endpoint you'd crouch.    But if you can cache, you might save some computation by more quickly excluding impossibilities (because they're not adjacent to any possible shorter-path tile), and depending on whether the moveLength caches.  If THAT caches, then the above stuff I wrote can mostly be ignored -- I'm basing this just on the loop structure and that it's pathfinding, not on a deep examination of the code base.

[nonickch]

/* evaluate moving to every possible location in the search area,
    * including combat considerations */
   for (to[2] = 0; to[2] < PATHFINDING_HEIGHT; to[2]++)
      for (to[1] = yl; to[1] < yh; to[1]++)
         for (to[0] = xl; to[0] < xh; to[0]++) {
            const pos_t move = gi.MoveLength(gi.pathingMap, to, crouchingState, qtrue);
                                if (move != ROUTING_NOT_REACHABLE && move <= ent->TU) {

Glancing at that snippet, it strikes me that if you're willing to (1) store movement costs and/or paths, (2) ignore movements that aren't from one adjacent tile to another (which would presumably exclude aliens leaping from a ledge to a multi-step drop), and (3) stipulate that aliens use a single consistent heuristic during movement (either maximizing safety, or maximizing speed) -- that you might be able to save some computation by caching.

I'm not sure I'm following your train of thought, then again I only just woke up and my coffee is not even half empty.
Even though I never tried to play with this set of loops (shaunc did), what I get from it is that it sequentially tries to evaluate movement cost to any tile within a box surrounding the alien. It doesn't calculate each step separately. So, if you're standing at the top of the stairs, the bottom of the stairs might be 4 TU's away (2 tiles),  but reaching the tile at the bottom of the drop next to the stair is only 2 TU's (one step into the air, then drop). This is all ofc done from the pathing algorithm which does consider drops. I've seen both soldiers and aliens casually drop from ledges instead of going for the stairs (actually getting them to use the full length of the stairs is kinda tough). As for (3), we don't use any heuristics, we calculate the full set of possible moves but we never even know the series of steps we'll take to reach the destination. The pathing might be using some kind of heuristic, and it definitely seems to be producing the fastest path to a destination (as I've seen the code laced with comments/ideas about checking the visibility/RF-exposure while we walk).

Under those assumptions, the 'best' movement from one tile to another will likely be the 'best' movement from the source tile to an adjacent tile, plus another movement.  This is false if you aren't willing to assume (3) -- e.g. it might be 'worth it' to walk standing to one location IF that leaves TUs to reach a safer location, while if that intermediate destination were actually the endpoint you'd crouch.    But if you can cache, you might save some computation by more quickly excluding impossibilities (because they're not adjacent to any possible shorter-path tile), and depending on whether the moveLength caches.  If THAT caches, then the above stuff I wrote can mostly be ignored -- I'm basing this just on the loop structure and that it's pathfinding, not on a deep examination of the code base.

Crouch is so not considered in the AI, it makes me sad. The only chance for the alien to crouch is if it ends it's about to end it's turn and it has enough TU's. On the next round it will always stand up before moving . At least shooting from a crouched position is one of the 'todo' things on my list. Moving while crouched can only come into play after that, as moving somewhere crouched, only to stand up and shoot, is always (not considering safety) counter-productive.
The current structure of the aiAction_t, is pretty simplistic atm. It can only store:  [mov],[shoot],[mov]. Each one is optional, and moves only define coords, not crouch status. As you can see, there's very little that can happen with this struct, and upgrading it to a linked list of generic actions is a must for any serious additions. There's a light exception to this struct, but it's not worth mentioning since it's almost the same behaviour.
If you check a few lines above the quoted code snippet, you'll see a G_MoveCalc call. I'm not 100% sure, but I believe that it precalculates the 'pathingMap' for usage from our team. So in essence every call to gi.MoveLength should be locating the appropriate cached value rather than re-calculating pathing.

update: I looked into the move algo's because of a crashbug, and I saw: "/** @todo add heuristic for A* algorithm */", so it sounds we got no heuristic for that either. Anyone wanna go for it? Pathing doesn't seem to be the issue atm, but aliens hugging the hulls of ships needs pathing calculations for a greater area (we need to use pathDistance instead of vectorDistance). A complete search would smack us face if we expand the 'searchbox' to a needed size, so finding out the proper heuristic would be a very nice addition.

[Lew Yard]

Oh, was mostly musing whether it'd be possible to incrementally consider interesting states (e.g. compute what one can do with 2 TUs of movement, then 3 TUs based on those, then 4 TUs based on the prev. TUs) but that'll only be useful in a highly constrained environment (e.g. interiors) where much of what's in a large cube won't actually be reachable.   Precomputation of pathing presumably makes this moot, anyway.

Speaking of heuristics, a quick look at AI_FindHidingLocation suggests to me that the loops there will return immediately when it finds the first spot within a grid that meets the reachability lack-of-visibility criteria -- and that the search operates in a row-by-row (or column-by-column, one of these) ways. 

Seems that this would bias towards a particular direction (towards wherever pos[1] is smallest, I think), and perhaps towards using more TUs  than necessary (and leaving fewer for reaction fire)?   A search organized ala concentric squares of increasing radius around the actor's location would be slightly more complicated but might result in a shorter move leaving more TUs for RF, crouching, reloading et al; while trying to bias direction towards or away from the nearest enemy (depending on weapon range vs current distance, or health?)  might be more tactically interesting.

[nonickch]

You are correct on the AI_FindHidingLocation point.
Wanna play around with it? I'm tied with the shooting & bugs atm.

Bear in mind that LUA uses that function aswell, we can adjust for any changes (e.g parameters) you'd want in the C AI, but I have no idea what lies in LUA-land.

Also, this function only checks visibility and not shootability, which may lead to silly things like 'hide behind someones back' (common for mellee units). Now, I wouldn't suggest putting the AI_HideNeeded there aswell. It's heavy as it is atm.
Gah, I'm torn again on the G_Vis AND/OR HideNeeded combination. The OR is clearly slower (atm, because of mockshots), but the AND doesn't let the aliens shoot from positions that are visible yet can't take that much fire back (e.g. corners).

[Lew Yard]

Hm, 'k.  Will see about getting my build environment set up.  Haven't attempted to build the tree, just been meandering through the code w/ Emacs. 

[Lew Yard]

http://sourceforge.net/tracker/?func=detail&aid=3033378&group_id=157793&atid=805244

'k.  This includes a patch which is a pretty incremental change.

Known assumptions and limitations retained:

- Only destinations in the same plane are considered.   This was present in the replaced code.

- The shortest path to another point in the same plane is fully within the plane, and includes tiles which are closer by Manhattan distance.  This is both new and incorrect in some cases (maps making heavy use of stairways et al could provide shorter paths in terms of TU); where it is wrong, the increasing-ring approximation is more likely to be wrong.

Facets changed:

- Average path length taken should be reduced, since locations are considered in order of Manhattan distance to alien.

- Bias towards y=0 should be reduced for the same reason; bias occurs, but within the expanding diamonds, so one hiding spot would be preferred to another with a lower y if the Manhattan distance is less.



Now, with respect to 3D -- because of falls et al, it seems possible that it might be faster to descend further sometimes (unless height changes cost TU even when caused by gravity) -- have not checked this.  With this in mind it seems like a BFS or A* traversal of node to node might be much preferred to iterating over grid patterns.   e.g. something with a signature ala

triplet_list_node_t ** bfs(int maxTUs, byte x, byte y, byte z, some_map_object_type_I_dont_remember_right_now_t * foo);

where the return value is an array of length maxTUs (if we ignore 0-cost moves, which don't exist right now AFAIK), whose contents are pointers to linked list nodes (or, alternately, a structure type with an array pointer and a length field) w/ X-Y-Z triplets with a shortest-path cost of exactly the corresponding TU.  This would codify a bias towards shortest paths, which might be absurdly bad (like a civvie's "escape" route passing next to a visible alien with a Kerrblade),  but it might be useful in quite a few functions.    This would also better facilitate hypothetical silliness like a hypothetical April Fools' map in which everybody moves like knights in chess (or more seriously, maps with teleporters, varying gravity for locally different movement costs, et al).

I haven't yet looked at the map / routing code to see how readily it'd be implementable.  For something like the above, what would need to exist would probably be something like "from this spot, where can I get to in 2..max(min(number of TUs required to actually make a move))".   Doors are another consideration; if the code that computed movement cost ignored the possibility of opening doors, that'd need to be handled separately; if it did, then that TU range for the search would need to consider cost of door opening + cost of moving through that door.

[nonickch]

gonna go afk for another 2 weeks because of vacations

[Mattn]

that's a pity - as i'm back now

anything we should apply to trunk? or do you want an own branch to work on?