open All Channels
seplocked EVE General Discussion
blankseplocked So last night... I KILLED EVE.
 
This thread is older than 90 days and has been locked due to inactivity.


 
Pages: [1] 2

Author Topic

Jint Hikaru
OffWorld Exploration Inc
Posted - 2011.08.04 07:39:00 - [1]
 


Tried to 'Optimise' a 30 Waypoint journey....

After 8 hours of black screen thinking, I pulled the plug!

Lady Spank
Amarr
In Praise Of Shadows
Posted - 2011.08.04 07:56:00 - [2]
 

Good lord man, do you have any idea of the complexity of a 30 waypoint pathfinding algorithm? Your grandchildren would die of old age before it was solved.

Culmen
Caldari
Culmenation
Posted - 2011.08.04 07:56:00 - [3]
 

Edited by: Culmen on 04/08/2011 08:11:36
Edited by: Culmen on 04/08/2011 08:05:02
That's what 30 factorial will do to a computer.
Sounds small?
Its actually 265,252,859,812,191,058,636,308,480,000,000 possible combinations
If you computer tested 100,000,000,000 solutions a second, you'd be done in 8,411,113,007,743 years

Originally by: Lady Spank
Good lord man, do you have any idea of the complexity of a 30 waypoint pathfinding algorithm? Your grandchildren would die of old age before it was solved.

The sun would have died of old age before it's done.
Heck, Andromeda colliding with the Milky Way would be old news at that point

If you figure out a mathematically fast/simple way to compute the result please contact your local institute of higher learning.
There are several mathematics prizes waiting for you.

dexington
Caldari
Baconoration
Posted - 2011.08.04 08:00:00 - [4]
 

Originally by: Jint Hikaru

Tried to 'Optimise' a 30 Waypoint journey....

After 8 hours of black screen thinking, I pulled the plug!



Travelling salesman problem this explains why your computer had a hard time solving the problem.

Louis deGuerre
Gallente
Malevolence.
Posted - 2011.08.04 08:05:00 - [5]
 

For near-optimal in a few minutes, just use genetic algorithms.

dexington
Caldari
Baconoration
Posted - 2011.08.04 08:07:00 - [6]
 

Originally by: Louis deGuerre
For near-optimal in a few minutes, just use genetic algorithms.


I think that is what eve does when you set destination, or maybe it's some pre calculated lookup.

Louis deGuerre
Gallente
Malevolence.
Posted - 2011.08.04 08:10:00 - [7]
 

Originally by: dexington
I think that is what eve does when you set destination, or maybe it's some pre calculated lookup.


Pre-calculated ? That would suprise me.
There are many ways to approximate the correct solution, I'd be interested to find out what EVE uses, but I doubt they'll tell us.

Jint Hikaru
OffWorld Exploration Inc
Posted - 2011.08.04 08:17:00 - [8]
 

Originally by: Lady Spank
Good lord man, do you have any idea of the complexity of a 30 waypoint pathfinding algorithm? Your grandchildren would die of old age before it was solved.


Serve them right the little bastards, what have they ever done from me.... noisy buggers only talk to me so I give them Werthers Originals.

malaire
Posted - 2011.08.04 08:21:00 - [9]
 

Originally by: dexington
Originally by: Louis deGuerre
For near-optimal in a few minutes, just use genetic algorithms.


I think that is what eve does when you set destination, or maybe it's some pre calculated lookup.

Single route with "set destination" is trivial to calculate fast, and is completely different from travelling salesman problem.

Chribba
Otherworld Enterprises
Otherworld Empire
Posted - 2011.08.04 08:34:00 - [10]
 

or you found the EXIT out of this addiction!!

/c

dexington
Caldari
Baconoration
Posted - 2011.08.04 08:36:00 - [11]
 

Originally by: malaire
Originally by: dexington
Originally by: Louis deGuerre
For near-optimal in a few minutes, just use genetic algorithms.


I think that is what eve does when you set destination, or maybe it's some pre calculated lookup.

Single route with "set destination" is trivial to calculate fast, and is completely different from travelling salesman problem.


I didn't say it had anything to with travelling salesman, i just agreed with Louis that it was possible to find a near-optimal route using algorithms relatively fast, and that is was likely that was used when using set destination.

Jint Hikaru
OffWorld Exploration Inc
Posted - 2011.08.04 08:39:00 - [12]
 

Originally by: Chribba
or you found the EXIT out of this addiction!!

/c


Heh, funny you should post Chribba, you were one of the waypoints.
(I want to take a tourist trip around eve to see the sights, and the Veldnought is one of those sights)

malaire
Posted - 2011.08.04 08:42:00 - [13]
 

Edited by: malaire on 04/08/2011 08:47:35
Originally by: dexington
Originally by: malaire
Originally by: dexington
Originally by: Louis deGuerre
For near-optimal in a few minutes, just use genetic algorithms.


I think that is what eve does when you set destination, or maybe it's some pre calculated lookup.

Single route with "set destination" is trivial to calculate fast, and is completely different from travelling salesman problem.


I didn't say it had anything to with travelling salesman, i just agreed with Louis that it was possible to find a near-optimal route using algorithms relatively fast, and that is was likely that was used when using set destination.

You are still wrong. Its trivial to find *optimal* route with "set destination", so it doesnt need any near-optimal solution.

Those near-optimal solutions are needed for travelling salesman problem if that is wanted to be solved fast.

edit: In non-weighted graph (like eve solarsystem map), you can use simple Breadth-first search to find shortest path between two points.

Aqriue
Center for Advanced Studies
Posted - 2011.08.04 09:02:00 - [14]
 

I discovered EVE doesn't like to optimize too many waypoints few months back, it ended with me having to pull the plug as well. Seems it works best with just half a dozen and maybe up to a dozen, 40 doesn't work so well because it seems it cannot calculate crossing the same systems to many times even if its a 5 jump radious around dodixie Rolling Eyes

malaire
Posted - 2011.08.04 09:10:00 - [15]
 

Originally by: Aqriue
I discovered EVE doesn't like to optimize too many waypoints few months back, it ended with me having to pull the plug as well. Seems it works best with just half a dozen and maybe up to a dozen, 40 doesn't work so well because it seems it cannot calculate crossing the same systems to many times even if its a 5 jump radious around dodixie Rolling Eyes

Crossing same system multiple times isn't the problem, just the amount of prosessing power needed.

For 10 systems: 3,600,000 steps
For 12 systems: 480,000,000 steps
For 15 systems: 13,000,000,000,000 steps
For 40 systems: 810,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 steps

dexington
Caldari
Baconoration
Posted - 2011.08.04 09:12:00 - [16]
 

Edited by: dexington on 04/08/2011 09:13:13
Originally by: malaire
edit: In non-weighted graph (like eve solarsystem map), you can use simple Breadth-first search to find shortest path between two points.


Which does not seem to be the case for the optimized route, which heavily depend on the au/km distance between gates in each system. You are saying the same as Louis already pointed out, the problem is not finding the non-optimal route.

malaire
Posted - 2011.08.04 09:22:00 - [17]
 

Originally by: dexington
Edited by: dexington on 04/08/2011 09:13:13
Originally by: malaire
edit: In non-weighted graph (like eve solarsystem map), you can use simple Breadth-first search to find shortest path between two points.


Which does not seem to be the case for the optimized route, which heavily depend on the au/km distance between gates in each system. You are saying the same as Louis already pointed out, the problem is not finding the non-optimal route.

Even in weighted graph finding optimal route between two points quickly is trivial. However i dont think EVE considers gate distances when finding best route.

Also you seem to be mixing two completely different things. Finding optimal route between two points (trivial), and finding optimal optimized route through multiple points (hard, "travelling salesman problem")

Phelan Votronski
Posted - 2011.08.04 09:43:00 - [18]
 

Originally by: malaire

Also you seem to be mixing two completely different things. Finding optimal route between two points (trivial), and finding optimal optimized route through multiple points (hard, "travelling salesman problem")


You're completely right. However educating people who are ignorant of maths is pointless. See here for more examples of comically obtuse people.

It wouldn't bother me so much if people who don't have a clue could just stfu.

CCP Konflikt

Posted - 2011.08.04 10:15:00 - [19]
 

If you think you've found a bug, feel free to report it

And yes there is a lot of number crunching happening to optimise way points, but your client should never hang.

Jint Hikaru
OffWorld Exploration Inc
Posted - 2011.08.04 10:21:00 - [20]
 

Thanks for the post CCP Konflikt.

I didn't really think it was a bug, I did try to optimise a route of 30 waypoints after all, but if you think the hanging client is a bug, I will submit a bug report.

Shawnm339
Posted - 2011.08.04 10:21:00 - [21]
 

nerds lunch money now

Mr Kidd
Posted - 2011.08.04 12:39:00 - [22]
 

Originally by: CCP Konflikt
...your client should never hang.


Have you actually played your game?

Jack Tronic
Posted - 2011.08.04 12:45:00 - [23]
 

Edited by: Jack Tronic on 04/08/2011 12:47:34
Edited by: Jack Tronic on 04/08/2011 12:46:20
Edited by: Jack Tronic on 04/08/2011 12:46:02
Originally by: Mr Kidd
Originally by: CCP Konflikt
...your client should never hang.


Have you actually played your game?


Places where the client hangs hilariously and ALWAYS:
1. Bookmarking copying/uploading
2. Submit a petition for the first time you opened the client, it can take up to 2 minutes for the hang to stop. (Some genius must have put the web request code on the same thread as the UI from the looks of it).
3. Fitting ship at SMA with a mass amount of dragged and dropped modules at the same time
4. ...

CCP Stillman

Posted - 2011.08.04 14:05:00 - [24]
 

Just to clarify: If you attempt to optimize a route longer than 12 way-points, you'll get following message:
"You have 18 waypoints set. It can take ridiculous amount of time to calculate the optimal route when waypoints are more than 12.

Are you sure you want to continue?"

If you accept, the client tries it's hardest to calculate the route, and will respond again when it's done. So it's definitely not recommended to try to optimize very long routes I'm afraid.

daddys helper
Posted - 2011.08.04 14:14:00 - [25]
 

sigh...

um those 2 dev statements appear to be in direct conflict with each other.

the game should never hang
and
the game will hang until its done calculating

Rolling Eyes

Simetraz
Posted - 2011.08.04 14:24:00 - [26]
 

Originally by: daddys helper
sigh...

um those 2 dev statements appear to be in direct conflict with each other.

the game should never hang
and
the game will hang until its done calculating

Rolling Eyes


No when a game or program hangs it gets stuck in a coding loop, it will never respond as there is no end to it's calculations and your only option is to cntl-alt-del the game.
However when a program has to do some complex number crunching without any visual notifier it is still working , it will appear to be hung but it really isn't, you just have to wait it out.

There is a difference.

Cpt Syrinx
Posted - 2011.08.04 14:29:00 - [27]
 

Originally by: CCP Stillman
Just to clarify: If you attempt to optimize a route longer than 12 way-points, you'll get following message:
"You have 18 waypoints set. It can take ridiculous amount of time to calculate the optimal route when waypoints are more than 12.

Are you sure you want to continue?"

If you accept, the client tries it's hardest to calculate the route, and will respond again when it's done. So it's definitely not recommended to try to optimize very long routes I'm afraid.


might be an idea to include an 'omg i had no idea it would take this long please stop trying' button for after the yes-clicking Smile

daddys helper
Posted - 2011.08.04 14:38:00 - [28]
 

Originally by: Simetraz
Originally by: daddys helper
sigh...

um those 2 dev statements appear to be in direct conflict with each other.

the game should never hang
and
the game will hang until its done calculating

Rolling Eyes


No when a game or program hangs it gets stuck in a coding loop, it will never respond as there is no end to it's calculations and your only option is to cntl-alt-del the game.
However when a program has to do some complex number crunching without any visual notifier it is still working , it will appear to be hung but it really isn't, you just have to wait it out.

There is a difference.


not without some sort of benchmark there isn't
8 hrs of calculations are for all intents (in the eyes of the player) a hang.

"you may wait a long time" is not a valid scope for determining if a hang has happened, and most people won't know how to view processes or know what a runaway looks like.

anyhow, all I'm saying is the statements appear to be in conflict depending on the technical knowhow of the end user.

I mean for me I'm going to assume anything over 5 minutes constitutes a hang even if the machine is still happily grinding numbers. Why? because there's no escape, the program no longer responds and I cant use the client for its intended purpose.

That in layman's terms is a hang, regardless of it the code execution is actually in a hung state or not.

De'Veldrin
Minmatar
Norse'Storm Battle Group
Intrepid Crossing
Posted - 2011.08.04 14:41:00 - [29]
 

WTB: quantum computer for running Eve.

Thenoran
Caldari
Tranquility Industries
Posted - 2011.08.04 14:44:00 - [30]
 

Originally by: daddys helper
sigh...

um those 2 dev statements appear to be in direct conflict with each other.

the game should never hang
and
the game will hang until its done calculating

Rolling Eyes


Why do you think one of the devs is named CCP Konflikt? Razz


Pages: [1] 2

This thread is older than 90 days and has been locked due to inactivity.


 


The new forums are live

Please adjust your bookmarks to https://forums.eveonline.com

These forums are archived and read-only