alwzn4vr Wrote:Haha, glad to see you're paying attention. It's always fun to set impossible goals.

Anyway, the WoW example is a human effort not a programmatic one. I wanted to throw this out to see if either you or Paul thought it even feasible. That's why I attempted to stipulate strict time definitions and the assumption that items can be pre-purchased as hunting them would add another layer of complexity.

Maybe a different way to look at it is to split the quests into types first.
e.g. do all kill x of type y as the 'cost' of the quest is easy to calculate.
Then generate an ordered list of calculated cost for each quest group by type and starting NPC location. Since there is a significant cost associated with ship travel, any quest that crosses to another 'realm' and back is going to be at the bottom of the list anyway.

Serenity Wrote:You should explain how the program in wow works before asking them so they get a better idea. Also didn't mean to derail your thread but I'm sure you're aware of that program which records the damage you delt, and that both these things should be considered made.

How the quest thing in Wow works is; It figures out which one is the quickest (statistically and realistically) quest to complete, points you in the direction, once you accept the quest shows you where to get the items, then when a new 'easy' quest pops up it will throw it in the timeline of which ones should be completed first.

You also have to remember World of warcraft is a serious game. There's a guild that accepts people who fit a very very specific criteria and must attend boss runs and such on time as if it were a job. These players are actually endorsed and paid apparently.

Fiel Wrote:This is like the traveling salesman problem, but not quite. The traveling salesman problem only calculates the optimum amount of distance required to go between two places. It does not calculate the optimum set of actions to take to complete something quicker (time vs. distance). If you wish to calculate the time, you'd either have to have a computable hits/kill for each class in the game or have some sort of heuristic to calculate these things. However, even then the algorithm can fail. For example, the algorithm would likely say for you to complete Subani's Legacy at some point while you're in NLC - but if you're a blaze wizard you'll have a hard time killing fire tusks and therefore it's not a good idea to do it. Furthermore, there are different numbers of quests for every job tree in the game - Aran has it different than Cygnus which has it different than Adventurers. These all increase complexity. Plus, you are not calculating the time it takes to travel to the area where to kill the monsters. Traveling to Dark Rashes is a lot faster than traveling to Skelegons.

In short, optimizing distance is very possible, but optimizing the time is much harder.

I believe the quickest method of completing quests in a small amount of time is this: Level up to at least 100 so all of the quests will be available to you. Complete quests area by area. If area A wants you to go to area B, wait until you decide to complete all of the quests in area B before completing that quest in area A.

alwzn4vr Wrote:I apologize for any lack of knowledge with regards to WoW. I was referring to the old 'how to get to lvl 60 in 4 days' pre-BC guides that were floating around the Internet. I assumed that they were human efforts. If they're not, my apologies.

I am aware of how 'serious' WoW can be for some people, a friend at work is a dedicated player who spends many a Friday night raiding with his guild.

As I said to Kaj, I just threw this out as a potentially fun project and nothing more than that. My WoW example could have been guild wars, EQ2, etc.

Fiel Wrote:I believe the quickest method of completing quests in a
small amount of time is this: Level up to at least 100 so all of the quests will be available to you. Complete quests area by area. If area A wants you to go to area B, wait until you decide to complete all of the quests in area B before completing that quest in area A.

KajitiSouls Wrote:Fiel, perry gave us easy guidelines to count how much time a map is worth and all that stuff. We could translate the pathway lengths in terms of time. I personally don't see it as much different than the Traveling Salesman problem (I originally quoted it because it's a famous puzzle problem that represents NP-complete complexity), but nevertheless the point is that this problem is quite complex.



I didn't think about the problem that way o.O But a new question appears in my head: is that just the path of least frustration, or is that really the best path? Certainly the 1000 Drums quest is much easier with Rush than running around bopping everything for 500 damage per hit, but is it a worthwhile benefit for all the quests you're doing?

Another thing to consider is whether you have a lvl 200 friend helping you do the quests or something (they don't have much to do anyways lol), since we know how hard it is to kill MM at lvl 40 (actor quest) or how ridiculous Taurospears are at lvl 50 (spirit rocks quest). Monster kill leeching faces no lvl restrictions last time I've checked; you just don't get exp if the lvl differences are too great and you do no damage =P

Russt Wrote:Well, we accept that with all the assumptions made, the path found is not necessarily going to be THE best one, right?

I remember reading there were quadratic algorithms to find a path within 5-10% of the best solution to traveling salesman problem. You might want to look into that.

Or you could just implement greedy algorithm. Find the quest with the least cost, complete it, see where it lands you, repeat. That wouldn't be too difficult.