+- Southperry.net (https://www.southperry.net)
+-- Forum: Maplestory (https://www.southperry.net/forumdisplay.php?fid=15)
+--- Forum: Maplestory Discussion (https://www.southperry.net/forumdisplay.php?fid=31)
+--- Thread: A programming challenge (/showthread.php?tid=16154)
Pages:
1
2
A programming challenge - alwzn4vr - 2009-09-09
I've been going through the quests to get that elusive quest medal and that made me think of the WoW quest guides that help people level in a short amount of time. This isn't really possible in maple since quests are mostly crap when it comes to EXP. I do like effiency though and since we have several people on southperry that enjoy coding as well as a challenge, here it is:
Design a program that will calculate the least amount of time to complete the 800 quests needed to obtain the quest medal.
Assumptions:
The player has completed all quests on the beginner island since we can't return there.
The player has not completed any other quests except those required for job advancement.
The player is at a high enough level to have (800 -beginner quests) available to them.
The player can input their own level so you can ascertain what quests will be available to them.
The player can input their own job type so you can ascertain what job specific quests are available.
The player has not increased their etc inventory but has cleared it of all non quest related items.
The player is not allowed to use VIP scrolls or family teleports.
The player is allowed to use all taxi services
The player is allowed to use warp capsules
The player is allowed to use the omega/nautilus warp when the warp item becomes available to them (from quest)
When warping using the random warp guy in ariant assume he always gets you in the wrong place and add 1 taxi ride.
The player has pre-purchased all items required for quests when possible and stored them in MTS to avoid etc inventory filling up.
You may use the closest available map that a monster spawns on even if other maps have better spawn/density.
repeatable quests may be done only once.
How to measure the total time:
each map to map travel counts as 20 seconds
each town scroll/taxi teleport counts as 5 seconds
When defeating x monsters for a quest each kill counts as 3 seconds.
When gathering commonly dropped quest items assume a 50% drop rate. (i.e. kill 100 for 50 drops = 100 x 3 seconds)
When gathering not so common quest items such as cornian marrow, assume that it drops after 3 minutes of hunting.
When gathering quest drops from bosses assume that it drops on the first try and that the boss can be killed in 20 minutes. (e.g. manon's cry)
All bosses and mini-bosses that drop quests items are already spawned.
each world transfer counts as the actual time with no wait time. e.g. ellinia - orbis = 10 minutes = 600 seconds
each jump quest takes 15 minutes. (e.g shumi's coin quests)
What the output should be
1. total amount of time in days/hours/minutes/seconds
2. An ordered list of quests to be completed including the quest name, NPC name, NPC location
3. A list of al required items for pre-purchase
A programming challenge - Serenity - 2009-09-09
I agree, you know what else would be good? A matrix that keeps tab of how much damage you do per minute. That would settle a lot of class vs class disputes.
A programming challenge - Dusk - 2009-09-09
Serenity Wrote:I agree, you know what else would be good? A matrix that keeps tab of how much damage you do per minute. That would settle a lot of class vs class disputes.
lolwut
We have one of those and it hasn't done anything to settle class v. class disputes.
A programming challenge - Serenity - 2009-09-09
Dusk Wrote:lolwut
We have one of those and it hasn't done anything to settle class v. class disputes.
Er I'm talking about an in game program, sorry I dont know why I said matrix. For WoW, thers a box top left corner that litterally 'adds' your damage over a period of time and gives you an ending number for your specific character.
A programming challenge - Dusk - 2009-09-09
Serenity Wrote:Er I'm talking about an in game program, sorry I dont know why I said matrix. For WoW, thers a box top left corner that litterally 'adds' your damage over a period of time and gives you an ending number for your specific character.
Oh, I see. Doesn't seem too useful though, people always seem to forget how much of a difference equips make in comparing two classes.
A programming challenge - MasPan - 2009-09-09
Dusk Wrote:Oh, I see. Doesn't seem too useful though, people always seem to forget how much of a difference equips make in comparing two classes.[color="#cc8899"]
As well as mob vs single target.
Which reminds me, still L> HIGHLY mob oriented boss. 6+ targets at a time please.[/COLOR]
A programming challenge - Takebacker - 2009-09-09
MasPan Wrote:[color="#cc8899"]
As well as mob vs single target.
Which reminds me, still L> HIGHLY mob oriented boss. 6+ targets at a time please.[/COLOR]
Multiple bosses at once would just be broken up into 1v1 like in CWKPQ because combined they'd be a huge pain in the ass.
A programming challenge - Serenity - 2009-09-09
Dusk Wrote:Oh, I see. Doesn't seem too useful though, people always seem to forget how much of a difference equips make in comparing two classes.
Yes but I want you consider this. It's something anyone can do. People argue about tables, examples, pictures and such because of situations, monsters, speed yada yada. However if you were to say have two dedicated players or even a private server to make two identical characters equip or fund wise, whatever you prefer, then those numbers will be fact and not a scenario or a hypothesis.
The simulator on Wow also includes mob damage and if asked will compare it to your single target DPS and do some equation to see which ones more efficient. I dont know the numbers.
A programming challenge - Holypie - 2009-09-09
Takebacker Wrote:Multiple bosses at once would just be broken up into 1v1 like in CWKPQ because combined they'd be a huge pain in the ass.Put em all into a tiny room.
A programming challenge - Typhoon - 2009-09-09
lol, took 1 post to completely change the subject >_<<
A programming challenge - Serenity - 2009-09-09
TheTyphoon Wrote:lol, took 1 post to completely change the subject >_<<
Hey, I said and.
I mean both programs are in the same package that you get for WoW.
A programming challenge - Russt - 2009-09-09
-ctrl+f's "and"-
Dusk Wrote:lolwutFirst one after the main post
We have one of those and it hasn't done anything to settle class v. class disputes.
Anyway, that's a hefty list of assumptions...
A programming challenge - bio9205 - 2009-09-09
Why would you want a program for this anyway? :f6:
A programming challenge - kingdj333 - 2009-09-09
MasPan Wrote:[color="#cc8899"]
L> HIGHLY mob oriented boss. 6+ targets at a time please.[/COLOR]
Say good bye to corsairs, nightlords, BMs amd MMs. Hello mages, and all warrior classes. DO want.
Also, I'm not sure if I count but I haven't done enough quest to equal even 40.... I don't do quests....
I've only done like 30ish.
A programming challenge - ArbalistMaster - 2009-09-09
kingdj333 Wrote:Say good bye to corsairs, nightlords, BMs amd MMs. Hello mages, and all warrior classes. DO want.
Also, I'm not sure if I count but I haven't done enough quest to equal even 40.... I don't do quests....
I've only done like 30ish.
My pierce would like a word with you. I think someone's torpedo would too
A programming challenge - mrcowcow - 2009-09-09
kingdj333 Wrote:Say good bye to corsairs, nightlords, BMs amd MMs. Hello mages, and all warrior classes.
Oh come on. It might not be too effective, but at least they've got ninja storm. And I'm pretty certain that BMs can at least do something with Arrow Rain, right? :\
A programming challenge - WingZero - 2009-09-09
kingdj333 Wrote:Say good bye to corsairs, nightlords, BMs amd MMs. Hello mages, and all warrior classes. DO want.Uh MMs have Pierce and Corsairs have Torpedo.... <.<
Also, I'm not sure if I count but I haven't done enough quest to equal even 40.... I don't do quests....
I've only done like 30ish.
EDIT~ Oops, this was already mentioned.
A programming challenge - alwzn4vr - 2009-09-10
This thread is about programatically finding the best path to complete the quest medal. I can not fathom how you people manage to totally pollute the thread with non related crap
If you are not interested in taking up the challenge or don't have the skills, feel free to contribute to someone elses thread
A programming challenge - KajitiSouls - 2009-09-10
I find this to be infeasible perry. Is there hard evidence that WoW players actually found the most optimal quest route programmatically? (I have no idea, which is why I'm asking) This is probably also roughly of NP-complete (Traveling Salesman problem, for example) or just NP complexity and is probably better dealt with by human effort, as there are level requirements to consider (an infamous quest is the Missing Dropship quest, which can only be done if you didn't save the NPC from the desert island first, and it comes several levels after the rescue quest), the locations of mobs and the quest NPCs, and so forth.
Maybe talk to those guys that try to program accurate weather simluators or something.
EDIT: Is it okay to assume that, for the case of an alternate character, that quest items that are obscenely hard to come by (Phantom Seeds) or convenience items (warp capsules) have already been prepared ahead of time via searching FM?
Also, I remember being able to do Shumi3 JQ in less than 5 minutes in my prime. I suppose it's really up to the player's skills though.
EDIT2: Ic wat u did der perry-san *points to sig*
A programming challenge - alwzn4vr - 2009-09-10
KajitiSouls Wrote:I find this to be infeasible perry. Is there hard evidence that WoW players actually found the most optimal quest route programmatically? (I have no idea, which is why I'm asking) This is probably also roughly of NP-complete (Traveling Salesman problem, for example) or just NP complexity and is probably better dealt with by human effort, as there are level requirements to consider (an infamous quest is the Missing Dropship quest, which can only be done if you didn't save the NPC from the desert island first, and it comes several levels after the rescue quest), the locations of mobs and the quest NPCs, and so forth.
Maybe talk to those guys that try to program accurate weather simluators or something.
EDIT: Is it okay to assume that, for the case of an alternate character, that quest items that are obscenely hard to come by (Phantom Seeds) or convenience items (warp capsules) have already been prepared ahead of time via searching FM?
Also, I remember being able to do Shumi3 JQ in less than 5 minutes in my prime. I suppose it's really up to the player's skills though.
EDIT2: Ic wat u did der perry-san *points to sig*
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.
Btw, I've never extracted any of the .wz file, can you or Paul provide an example of what an extracted quest would look like.