View Issue Details
| ID | Project | Category | Date Submitted | Last Update | |
|---|---|---|---|---|---|
| 0007841 | AI War 1 / Classic | Suggestion - Unit Abilities And Behaviors | May 15, 2012 1:26 am | Jun 7, 2012 5:55 am | |
| Reporter | GrimerX | Assigned To | |||
| Status | considering | Resolution | open | ||
| Product Version | 5.034 | ||||
| Summary | 0007841: Improve "what should I target next" algorithm to take into account density of enemy at location | ||||
| Description | I've had a number of invasions through multiple wormholes where my forces will bounce back and forth. It usually goes something like: 1) Stuff comes through wormhole A -- attack it 2) A few ships come through wormhole B -- stop attacking the big mob, head over and kill the few ships 3) Head back to the main invasion ... leading to a lot of useful combat time spent transitioning between enemy groups. I have FRD, Focus Fire (snipers+regular units) and kiting enabled, so it may have something to do with that. I'll experiment a bit. I just hate to micro-manage battles like these. Generally the ship AI does a good enough job but this is one of those cases that require it. | ||||
| Tags | No tags attached. | ||||
| Internal Weight | Feature Suggestion | ||||
| related to | 0008444 | considering | When attacked unit teleports away another target should be chosen |
|
|
just a thought that would also help with melee ships, can we do graduated target searches?. start with targets within 500 then 5000 then 20000 then all targets? if it finds the first would no longer run the others... |
|
|
@motai That seems like a nice, computationally cheap way to approximate favoring nearby ships over far away ones. I'd like that. |
|
|
well i dont know how cheap it is by comparison since it adds a range calculation with basically doubles to quadruples the length of the current target matrix calculation cycle(or more). however making a range sort to prioritise nearby/far targets in general i would think should always be a priority except in reverse where snipers are concerned. by adding a ranging to the target listing it however solves both those situations at the same time. it also is likely this can be factored into the autoevade behavior to improve that as well btw. the hardest part about this is how to balance it with immunity/ammo effectiveness which has been the current priority for target sorting. my idea would actually be to amplify the triangle effects so that unwanted targets are immune and removed from the sort list. it would generate some odd things but would allow range rather than shot effectiveness to be the priority in target calculations. but that part of the idea may be a much later evolution or be considered for a backup targeting list in case no other targets are present. i.e. anything it shouldnt shoot at has effectiveness under 1(or maybe anything 1 and under ;given that most multipliers are alot more than 3,might be on a ship by ship basis)) and is put on a secondary target list. then it pursues the primary target list which is the "Good target" list. and these lists can be sorted by range and updated on the fly. basic problem as i understand it is basically units generate these lists periodically but dont update them near that often and perhaps not in a sorted fasion. a side effect of this thought is maybe reevaluating the shot bonus vs ship types to better match speed and range combinations and changing alot more ships to even up shots which may do more damage(especially some of the very slow ships like space tanks). |
|
|
I don't like the idea of range becoming an absolute factor, as sometimes I want my ships to move a little bit if the ship they want to move to they have a great bonus against. Instead, I think every factor in the targeting algorithm is a weighted factor. So like if you have a great bonus against some ship X, but all the other factors it considers are moderately in favor of Y, there is a good chance that the targeting algorithm will choose Y instead. Same thing with distance. If ship X is only a bit further than ship Y, but I have a moderately better DPS against X, my ship should go for X. But as X gets further and further away, the other factors would have to become even better to overcome that. And no, the "tiered" range check is not making distance an absolute factor. Say it found multiple ships in the first 500 distance check. Then the other factors would have a say about which one of those ships to attack, rather then going for the closest ship in the 500 range. As for how much cheaper it is, range calculation is actually quite expensive when spread out over potentially hundreds of ships evaluating whether they should go for one of another hundred ships, for each individual ship on each side. This is in part because this part of the calculations cannot be shared among ships, as each ship has its own position. Unlike the bonus type considerations, where it can share that part of the calculation with other ships of its type (in fact, the engine currently does do that optimization IIRC) If adding a true range calculation or even a rough range calculation (possibly considering its position to be that of a nearby ship and thus using that range calculation, as a rough approximation) turns out to multiply times by more than 3x or so, then the "tiered" scans would be cheaper. Otherwise, actually computing distances would be cheaper. |
|
|
what im trying to point out here is a disconnect between range, targeting, and movement. the ship will try to move at a target(that is likely out of range) shoot a different target(that is in range) and shouldnt be moving to ships out of range that are faster than it is(even though it would have the best multiplier against them). so i understand the logic is convoluted. it does make me wonder if currently the targeting/moving logic is integrated into the firing algorithm or if it needs to be moved there since that is when the range logic triggers so those can be tied together for code efficiency. |
|
|
I agree, this is incredibly annoying against certain types of enemies. Snipe-type craft that auto-retreat can have 99% of your forces chasing after 1 unit while 100 others are terrorizing your system. Keep in mind that if 10 enemy units are across the system pounding on your almost dead force field around the command station you would probably rather not have all your ships occupied with the other 100 enemy units at your wormhole. So I certainly wouldn't all out restrict craft from following far away enemies. Ideally there could be some kind of relative firepower calculation. Peg it at a 2:1 ratio for the purpose of discussion, where as soon as you have 2 fighters chasing after 1 enemy fighter beyond X distance the enemy is temporarily removed from the available targets for other craft. This would lead to a small number of your forces spliting up to follow far away enemies while the main bulk of your forces fight the main bulk of the enemy forces. Prioritize splitting off units that are very fast or designed to counter the specific enemy. This could also even reduce the CPU-strain on choosing targets since we're pruning the target selection list. |
|
|
Just keep in mind, the auto-targetting algorithm needs to be kept computationally cheap and keep the number of lookups to the current "state" small (as opposed to constant ship and weapon definitions, which are cheap to lookup), as this piece of logic, in the worst but still very possible case, dozens of times every couple of frames for each in ship involved in the battle, with each run of it considering all enemy ships in the system. This could easily add up to thousands of times per frame. And yes, that adds up, FAST! So while it could do all kinds of fun stuff like measuring firepower ratios of current matchups based on current orders while factoring in range and finding "clusters" of units, that is quite expensive, and a battle of even moderate size would slow to a crawl. While there are some nifty optimizations in place (like if another ship of the same type near me has computed what to target next, no point in trying to duplicate basically the same computation, and so I can just target what it was targeting), this doesn't change the overall computational complexity of the calculation. I suppose that this could be fixed by better separating the different reasons why you are looking for another target, your goal for it, and what parts of the current state you want, and modularizing the logic based on that, and thus insuring that the really expensive stuff is only called when you actually need it. However, this sounds like a nightmare to code, to only give a noticeable improvement in intelligence in edge cases, albeit relatively common edge cases. (Although it would make it smarter overall, the current algorithm is pretty darn smart for most cases, and thus there wouldn't be much improvement in those cases) |
|
|
How exactly does targetting work? If it's some kind of weighted decision tree of all targets then simply reducing the weight of a target proportional to the relative firepower of units already after it vs its own firepower would work very well. You wouldn't even need to update this every frame, do it once a second or whatever works best. It would also seem that you could simply approximate range checks if doing them against all units. The vast majority of battles will have 95% of units very close together, if you do a range check against all units then don't repeat the same range check again for any unit within 50 or so units away. It's pretty much irrelevant whether an enemy is 950 or 1050 distance away for most conceivable targeting purposes. |
|
|
Thankfully, the every frame thing is the absolute worst case. Usually, it does pace itself to like every few seconds, with many other clever pacing, approximation, and optimization tricks. As for the exact algorithm used, I'm not sure. |
|
|
There is also the armor/attack boost location, which seems to work ok enough with large number of (boosted) ships. Not sure how well it would work with large numbers of "source" ships, but as you note it doesn't have to do this very frequently -- it could be partitioned to do a max # of ships per interval, to put a constraint on it. That could work both for choosing which ships to attack, and choosing which ships to have re-evaluate their targets. |
|
|
truthfully the interval is firing rate o the ship i can see where even this could be too much if every ship did it. but as noted ships travel in gaggles and copy orders from each other. my main concern is that any time it doesnt find a target to shoot at it needs to consider its path to target so the ship prefers shooting something over chasing distant targets. couple with a "anti" distance code or snipers that says to target the farthest thing so less things try to chase remote targets. |
|
|
lemon as far as im aware the current process is : warp into system or notice enemy targets in system locate the best targets(based on ammo vs armor multipliers) pick x (not sure if range figures here) compile a list and store 50 targets. persue those targets in (currently) a nonsorted order this is totally separate from the can i fire on anything ok i can shoot loops that process fire control at all times. my main point starting this argument is that many things involving ranges to recalculate targets happens in the fire control loop and the pursuit list should probably be sorted each fire cycle. (that is when the guns actually fire not when they could fire so as to save cpu time;ideal would be to always do it but that is to expensive in time) main problems is the number of variable reference calls that need to be done to calculate distances that bloat the process of range finding and sorting or targets. my main thought is that when you are doing can i shoot checks you could append the ranges temporarily to the target list so that it can be sorted to closest of the good targets. i do realize this causes some corner cases when you are surrounded or when the fleet balls interpenetrate. which means you might ignore this step in your loop if more than 5 targets are inside your weapon range( yes this does mean melee wont ever side step but that is one of the things seeking a fix here is that melee really need to correct targeting more quickly than they do) |
|
|
I don't want to start new issue, so I'll complain in this one: Other problem with auto-targeting are teleporting units: you have ships ball protecting your military command center. When command center shoots first enemy and teleports it on the other side of system all ships start chasing it so military command center isn't only dispersing enemies - it's also dispersing your units. IMO when unit teleports away it attackets should find new target. |
|
|
that is likely linked in with the call it dead mechanic should remove the ship from target lists but doesnt :) i agree this is likely a proper place for the complaint but its a related and separate issue. its worth starting a new thread |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| May 15, 2012 1:26 am | GrimerX | New Issue | |
| May 15, 2012 3:20 am | motai | Note Added: 0024245 | |
| May 15, 2012 8:47 am | tigersfan | Internal Weight | => Feature Suggestion |
| May 15, 2012 8:47 am | tigersfan | Status | new => considering |
| May 15, 2012 12:15 pm | TechSY730 | Note Added: 0024268 | |
| May 15, 2012 3:29 pm | motai | Note Added: 0024271 | |
| May 15, 2012 3:37 pm | motai | Note Edited: 0024271 | |
| May 15, 2012 3:40 pm | motai | Note Edited: 0024271 | |
| May 15, 2012 3:59 pm | TechSY730 | Note Added: 0024272 | |
| May 19, 2012 9:37 am | motai | Note Added: 0024485 | |
| May 23, 2012 4:34 pm | Lemon | Note Added: 0024736 | |
| May 23, 2012 4:57 pm | TechSY730 | Note Added: 0024743 | |
| May 23, 2012 5:05 pm | TechSY730 | Note Edited: 0024743 | |
| May 23, 2012 5:13 pm | Lemon | Note Edited: 0024736 | |
| May 23, 2012 5:27 pm | Lemon | Note Added: 0024746 | |
| May 23, 2012 5:28 pm | Lemon | Note Edited: 0024746 | |
| May 23, 2012 5:30 pm | Lemon | Note Edited: 0024746 | |
| May 23, 2012 5:31 pm | Lemon | Note Edited: 0024746 | |
| May 23, 2012 5:31 pm | Lemon | Note Edited: 0024746 | |
| May 23, 2012 5:35 pm | TechSY730 | Note Added: 0024747 | |
| May 23, 2012 6:07 pm | GrimerX | Note Added: 0024751 | |
| May 24, 2012 12:12 am | motai | Note Added: 0024769 | |
| Jun 5, 2012 6:10 am | motai | Note Added: 0025533 | |
| Jun 5, 2012 6:15 am | benetnash | Note Added: 0025534 | |
| Jun 5, 2012 12:06 pm | motai | Note Added: 0025548 | |
| Jun 7, 2012 5:55 am | motai | Relationship added | related to 0008444 |
