Prev: Last Call for Papers Reminder (extended): The World Congress on Engineering WCE 2010
Next: P = 1/2N2P Conjecture
From: BobDobbs on 19 Mar 2010 15:21
So in Eve Online... there is an interesting example of the travelling
salesman problem. This might not sound very clear as it is much easier
to understand if you see it... but I will try.

So when you blow up ships... they leave wreckage which you might want
to "loot" to get items from. They are scattered about in 3d space. In
order to loot... you must be within 2500 meters of the wreck. So I
suppose you could view it as a group of 5000 meter diameter spheres
that you have to "touch" in order to visit. Keep in mind... a field
where you have wrecks can be 100km x 100km. When I was playing it
became obvious that this was the travelling salesman problem at least
as far as complexity is concerned... except that you don't have to
roundtrip back to your starting location.

As I got a little farther into the game... I got a tractor beam.
Here... if you are less than 20km from a wreck.. you can pull it to
you. Often ships are in clusters so instead of visiting each wreck...
and if lots of wrecks are within 20km from a particular position.. you
can simply navigate to that position and stop your ship... then just
tractor everything within range to you. You can then move to another
cluster and do the same.

Finally... there is a salvager that can pull useful materials from the
wrecks... apart from the cargo. It only works within 5km. Salvaging
can fail on an attempt so it often takes longer to salvage than to
tractor a wreck within range... so I get most of the ships clustered
around me and concurrently try to salvage them (generally I have
everything tractored in and have to wait for salvaging to finish). The
detail here is that with the tractor... when I am getting low on
wrecks within range.. I can start moving towards a new cluster while
still tractoring items from the first cluster towards me. With a
salvager.. I can't really do this because I have maybe 10 wrecks
pulled in around me from the tractor all within range of the
salvager.. but if I start to try to move to another cluster before I
have finished salvaging... I will move out of range of the 10 wrecks
that I so carefully clustered around me with the tractor.

So anyway... might sound weird since I can't show you guys visually..
but I was wondering which of these flavors (no tractor or salvager,
only tractor, both tractor and salvager) seems the most
computationally complex.

For example... the nearest neighbor heuristic for TSP works fairly
well for the first... however it wastes a bunch of time if you apply
it to the tractor beam scenario. A human player often looks at the
field spatially and finds a path that moves them within tractor range
of as many ships as possible. I would imagine even determining what
constitutes a cluster could be tricky. I was thinking you might be
able to cut the field into cubes and perhaps determine hotspots of
ships (ie a cluster).

Anyway... any thoughts?
 | 
Pages: 1
Prev: Last Call for Papers Reminder (extended): The World Congress on Engineering WCE 2010
Next: P = 1/2N2P Conjecture