Gregorovitch55
Posts: 191
Joined: 2/11/2014 Status: offline
|
I think the vast bulk of ship movements in the game are simply of the "Fly there, shoot that" or "fly there, deliver, that" in response to events or circumstances where the flight end points are known. The exploration thing is different and because it does noticeably worse than we can everyone talks about it. If you scan this java program for solving the Traveling salesperson problem the scale of the problem becomes clearer: http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-neighbour-algorithm/ They key is that there are two nested while loops in the main function, TSP. In the example you have 9 cities and the corresponding 9X9 matrix of distances to work with. So it loops 81 or 72 or 100 times, dunno, haven't looked that hard, but it could probably do that quicker than you could notice if you ran it. However in DW we have up to 1400 starts each with maybe 10 planets and moons. So our distances matrix is 14,000*14,000 = 196 million loops. It might finish that by the time you finished the weekly shop, or maybe by tomorrow morning. And that's for one scout. Let's limit each of the 50 or so factions to five scouts each and we keep the total down to 49 billion loops. Sure, they'll be a lot of optimizations one could do to this, but basically we're not even remotely in the ball park of an acceptable game algorithm here, this approach is a bust - we need something to decide where each explorer goes next more or less instantly, we need something like the autopilot algorithm from X3 above, two or three simple computations, hopefully one, but almost always less than five, loop per tick. A completely different approach to the problem. Whatever we come up with it won't work anything like as well as the TSP solution and people will laugh at it on the forums, but if the explorers go explore and they visit practically all of the planets and moons they are supposed in whatever order, we'll call that a major result under the circumstances. But to answer your question directly, when you find a really, really simple algorithm something like that autopilot one to do this, whether you run it on 10 ships or 100 is immaterial really 'cos it'll do it so fast the player won't notice, so you might as well have 100.
|