View Issue Details
| ID | Project | Category | Date Submitted | Last Update | |
|---|---|---|---|---|---|
| 0007037 | AI War 1 / Classic | Suggestion - Game Mechanics | Apr 11, 2012 1:55 am | Apr 14, 2012 6:45 pm | |
| Reporter | benetnash | Assigned To | |||
| Status | considering | Resolution | open | ||
| Summary | 0007037: Consider logisitic centers and zenith space-time manipulators in shortest path search | ||||
| Description | It seams that now sending units from one planet to another uses shortest path algorithm using distance between wormholes. I think this should be changed to time spent in system (the bigger speedup, the less time units are in system). Manual routing golems through systems with logistic centers can reduce transit time twice or even more compared to default path finding algorithm. | ||||
| Tags | No tags attached. | ||||
| Internal Weight | Feature Suggestion | ||||
|
|
Great idea, but would this account for also the total absolute distance traveled (which is basically the sum total of all the distances between wormholes plus the distance to the starting wormhole plus the distance from the final wormhole to the point on the planet) That could start getting a little tricky with the math. Especially if the speed of the unit across each planet starts getting involved. And there are also units that are immune to speed boosts, so that will have to be considered. Yes, I know there are effecient graph algmorithms for finding shortest path with weights (basically, the weight of the segment A-B-C is the distance from the wormhole to A on B to the wormhole to C on B), but computing that weight may be prohibitively expensive. But if it did try to find absolute shortest path given speed and distance on each planet (accounting for all speed boosts, things that are immune to speed boosts, group move, and maybe even engine damage), that would be a far more useful navigation algorithm. |
|
|
Well, if we stored a speed modifier variable in addition to the distance between each wormhole on map generation, that would improve the algorithm. I would have thought that units already utilise something like that. |
|
|
@zharmad Hmm, the good ol' precompute the info stratagy. Good idea, as the number of times this information is needed FAR outnumbers the number of times this information changes. And for the distance between every wormhole, that would never change. This makes the weight calculation step FAR cheaper in the vast majority of cases, for only a trivial amount of extra memory. (At the very worst, datatype_size * O(n^2 + n), which would be for a complete graph, which nothing even gets close to) Still doesn't handle the complexity of handling speed boost immune units and units with engine damage. |
|
|
With respect to different ship-speeds and engine damage, I personally think that: - There isn't really much point in calculating shortest paths for ships with speed 1. :P All paths take longer time than the effective half-life of such ships. I *might* allow those with half-engines to plot a course for the nearest repairer, but it's always easier to build another one or send some healthy engineers over. - When I'm directing a fleet, I usually want them to travel along the same route if not at the same time. It doesn't always makes sense to direct my Spire Attritioners one way, and my fleet ball another, as the former requires escorting especially along borders. - This is somewhat of an academic discussion for me, since I tend to see firs the course that my ships will take along allied planets, and then build logistics along that path. - They also automatically avoid AI planets in the path-finding calculation, if they're not on one already. |
|
|
OK, I am an idiot. The worst case memory usage is not O(n^2 + n), but rather O(n!/(2*((n-1)-2)!) + n) Derivation: There are n planets, and thus n sets of wormhole distances. In the worst case, a complete map, every planet would have a wormhole connection to the other n-1 planets. Every pair of distances between pairs of wormholes needs to be accounted for. This is the number of pairs (2 elements) from a set of n-1 planets without repetition (aka, the distance of wormhole to A from A is meaningless, as there can be no two wormholes to the same planet on the same planet) This is the binomial coeffecient. So each planet would need up to (n-1)!/(2!*((n-1)-2)!) distances. Since there are n planets, this would happen for each planet, thus making this n*(n-1)!/(2!*((n-1)-2)!), which simplifies to n!/(2*(n-1)-2)!) In addition to that, the current speed modifier of each planet needs to be stored, which is an additional number for each planet, aka, O(n) extra space Thus, adding this all up, we get O(n!/(2*(n-1)-2)! + n) That's a pretty nasty growth rate. Again, this is the absolute worst case, a complete map. In reality no map even gets close to this level of connectedness. The closest would be crosshatch. I will make a simplifying assumption of 8 wormholes per planet. This will overestimate the side and corner planets, but as we are trying to establish an upper bound, overestimating is OK. So, in a cross hatch map, there are n planets, each planet having 8 wormholes, and on each we need to store a value for each pair. This gives n * (8!/(2*(8-2)!) = n * (8!/(2*(6)!) = n * (2*3*4*5*6*7*8)/(2*2*3*4*5*6) = n * (7*8)/(2) = n * 56/2 = 28n With an additional number for each planet (the current speed modifier), this brings it to 28n + n = 29n. Thus, the total amount of extra memory in the worst case encounterable in game is O(29n), which is not that bad. |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| Apr 11, 2012 1:55 am | benetnash | New Issue | |
| Apr 11, 2012 9:05 am | tigersfan | Internal Weight | => Feature Suggestion |
| Apr 11, 2012 9:05 am | tigersfan | Status | new => considering |
| Apr 11, 2012 1:49 pm | TechSY730 | Note Added: 0021936 | |
| Apr 11, 2012 10:06 pm | zharmad | Note Added: 0021947 | |
| Apr 11, 2012 10:20 pm | TechSY730 | Note Added: 0021948 | |
| Apr 11, 2012 10:20 pm | TechSY730 | Note Edited: 0021948 | |
| Apr 12, 2012 5:00 am | zharmad | Note Added: 0021954 | |
| Apr 14, 2012 6:45 pm | TechSY730 | Note Added: 0022026 |
