Depends on how you connect python and multithreading. Python supports threads, but the regular version suffers from the GIL, which doesn’t allow multiple python threads to run concurrently. EVE has an audio-thread, and when you pin the client to a single CPU you get stuttering and problems exactly because it sucks at multithreading.
The easy solution to this problem is multiprocessing, aka spawning a new process with its own python interpreter… in windows that’s kind of a mess, though, because windows doesn’t support forking.
I made a route tool here http://www.evetools.info/route-planner which already goes through each system in the route to find out if it’s safe or not. Might be able to add the functionality for optimization. This code isn’t in any particular language or working, I just made it up randomly right now to bounce the idea around, but i’m guessing that the optimization function works something like the code below. What do you guys think about it?
for waypoint in waypoints:
____routes.add(new route(waypoint,next_waypoint))
for route in routes:
____for waypoint in waypoints:
________potential_route = new route(route.waypoint,waypoint)
________if len(potential_route.systems_in_route) < len(route.systems_in_route):
____________route = potential_route
for route in routes:
____print str(route)
I don’t think you’re off topic. Your comment is directly related to the OP’s question. I think that even with the GIL and multi-threading, it should be possible to have the route optimization done in the background and the GUI related result done in the main thread. I’ve done something like that before, where the background thread gets data from an API, does some things with it and displays the result to the GUI (in real time), in the main thread using global variables shared between the two threads. I don’t know the differences between what I was doing and how EvE works cause i’m a noob, but maybe OP should just submit a bug report?
Chess engines have solved this with Tablebases. Basically, it’s a once performed, exhaustive solution to every possible position of every piece on the board, leading to a checkmate, in predefined scenarios.
Star systems don’t tend to move around much, do they? Unless this game is a lot more fluid that what I currently understand, an exhaustive database has to only be computed, once, and then made available?
I guess I’m confused as to why we have to recompute, all the time. Has anything moved, in relation to anything else?
Well, that’s over my head. Some of those tablebases, particularly the 4/5 man endings, took years to generate.
But the work is done, and you can download the end result. No need to redo the work. Is this not even remotely similar? It seemed to me, to be. I’m not an expert, though, by any means. Just trying to understand this all.
It’s not calculating a single route. That’s simple. I can generate routes from one star to all the rest of the stars in eve, in a fraction of a second.
The problem that’s being talked about, is taking a number of waypoints, and calculating the most efficient route that passes through each. (This is the travelling Salesman Problem)
The actual calculation of routes between each of the points, that’s dead easy. we’re talking fractions of a second. And all we need to care about, once they’re generated, is that A->B is 5 jumps, B-> C is 6 jumps, and A > C is 4 jumps.
It’s how you combine them which gets complicated.
with just 3, there aren’t that many combinations. Just 6.
a->b->c
a->c->b
b->a->c
b->c->a
c->a->b
c->b->a
When you add a 4th waypoint, that jumps to 24 possibilities. a 5th, and it jumps to 120 possibilities. Then 720.
It rapidly gets out of hand, to do in a reasonable time frame.
With 14 waypoints, there’s 87,178,291,200 different routes to check. sure, each one can be checked quickly, but if it took, say, a microsecond to check each, that’s then going to take over a day to check. (86400 seconds in a day)
So the problem is that there are not 64 squares? The user can make an arbitrary route, on a basis of way more than the ‘grid’ available in chess, with defined legal moves.
I get it. Thanks. No solution to offer, though, obviously.
There are optimizations which can be done to make these more efficient. The numbers we’re talking about are the brute force options.
if you have clusters of the waypoints, you can treat each cluster individually. It may not be the most efficient route, but it’d calculate significantly faster.
(the most efficient route still needs to you do everything. because if A, B and C are one cluster, and D, E and F are another, to get the most efficient routes between the clusters, you have to check all of them. if the most efficient route in A,B,C leaves you at C, and D, E and F starts at F, with C and F being the largest distance apart, you may have a sub-optimal route.)
That’s why this doesn’t solve the P=NP issue. It’s accepting a little inefficiency, for a significant reduction in time taken.
That’s fine with me me. I agree with the economics precept of 80/20.
You can get 80% of a result with 20% of time/effort/expense. What is going to cost you, is that last 20%. That last 20% of a perceived ‘perfection,’ is 80% of the cost.
This is a game, and while it has, at times, caused me to rage quit, I came back, with a new toon, and a new plan, but it’s always the players that cause me grief, not the mechanics. It’s ok, if I have to jump a few more jumps.
My worst days are when some group decided to abandon a group of hundreds of T1 drones to decloak me on a gate, and then I have to laugh when they are not there to capitalize on it. It’s pixels. A few of anything here or there, bah.
No problem. ‘Apartment level threading’ is not the same as making a fork() call. I get it.
And I’m a PERL schmuck.
You guys, today, with your objective code, instead of monolithic sequential ■■■■. Never done python, or ruby, or a lot crap. Trying to learn Objective-C, since it’s what my system, MacOS, uses…
But… I’m a FreeBSD monolithic straight-C coder. It’s an adjustment, something to wrap your mind around. Something I don’t think I can. But I am trying.
I think @Anderson_Geten was onto something with the ‘genetic algorithm’ suggestion. This removes the guarantee of an optimal solution, but will result in a local optima every time (which is often ‘good enough’).
The following would only be run for waypoint lists at least as long as where EVE struggles now (judging from OP, somewhere around 10).
Simple version:
Let the ‘DNA’ of each individual be an ordered list of waypoints
Define a max mutation rate (probably number of random waypoint swaps within the list)
Randomly initialize a population of individuals
Test each individual in population to get total travel distance/jumps (performance score)
Randomly select an individual to be mutated, such that the chance of selection here is proportional to performance score normalized, then randomly mutate said individual to create an offspring. Repeat until desired number of offspring are generated.
Select the top perfoming individuals from previous population and offspring until you have the original population size (see diversity suggestions below).
If stopping criteria met, exit and return most elite individual in population, else Repeat 1 with new population (the one generated in previous step)
Stopping criteria can be a set number of iterations or lack of performance gains from previous epoch. Also strong benefits to enforcing diversity (which can be accomplished directly by making sure no individual is selected for survival that is already in the survivor list or by using more advanced algorithms like ‘novelty search’ or ‘MAP Elites’). A good first try though would be the simple version, perhaps with multiple runs on each list to be optimized, to regularize results (using different random seeds each time).
Edit:
‘Novelty Search’ and ‘MAP-Elites’ are couple of my favorite algorithms…
“To achieve your highest goals, you must be willing to abandon them.”
-Kenneth O. Stanley
Well there we are in the domain of optimization algorithms …
Genetic algorithms belong to the "approximate"meta algorithms that don’t find the best solution, but rather iteratively enhance a “good enough” - assuming finding a pool of correct solutions is doable.
Constraint programing explore the solution space to find the best solution (if asked to) but is rather costly (unless using specific heuristics - same as genetic). Many optimization are well documented, eg branch-and-bound, but in the end a heuristic made by human is needed to have reasonable time (and also, reducing the precision may help - but then we find an exact solution within a margin)
Linear programing defines the problem as a linear function of the variables that it then analyticaly optimize, but since threshold effects need to be linearized too (that is, used as continous variables rather than discrete), then the solution found may be not correct and need some enumeration over the boolean variables (see constraint programming)
Of course, some combination can be used, eg branch over the boolean, then linearize, and when solutions are found add them to a pool of initial solutions for a genetic algorithm. But it’s not always feasible, and does not always perform better …
(that’s my phd domain BTW)
Maybe. This is just too much. Look at all the big words you just used.
You confused the crap out of me, and I was smart, or considered such, under Jordan Hubbard, back in the day, before he sold out to apple. Which is not being fair. Any of us would have taken it.
I guess I need to just be honest. We’re an ad-hoc group of coders, world-wide, that coded for FreeBSD. The same as for Linux, except in the case of Linux, it was one geek, making one kernel, Linus Torvalds, who then thought that the work of Jordan Hubbard, of FreeBSD, or Theo deRaddt, of OpenBSD, or the contributors to both, like me, were crap on his shoes.
The problem, as they have defined it, is so computationally expensive that you need a quantum computer to solve it.
