Forum:Journer Planner/Mapquest idea

From the RuneScape Wiki, the wiki for all things RuneScape
Jump to: navigation, search
Forums: Yew Grove > Journer Planner/Mapquest idea
Archive
This page or section is an archive.
Please do not edit the contents of this page.
This thread was archived on 25 August 2010 by Cook Me Plox.


Discussion

There's this idea that's been floating around in my head. I thought I'd put it on the YG and see what people think. A lot of people (especially new players and members in the middle of nowhere) want to know how to get from where they are to somewhere else the fastest with their requirements. Although this isn't common knowledge to everyone. My suggestion/idea: some kind of tool that allows players to work out how to get somewhere the quickest. Say they were in "Varrock" and need to get to "Tai Bwo Wannai". They can do many methods:Karamja Gloves, Fairy Rings, walk (if they got a lot of time on their hands), etc. They'd type in their location, destination and it'd come up with all possible routes, using different methods of transportation.

Now, I know this'd be extremely hard to make or implement. But this wiki is full of gifted people who are great at this sort of stuff. I was on the cc earlier, and a user said it'd be hard, but possible. This would also be the first of its kind for RuneScape, so would be a massive drawing card to the Wiki.

Here is an example of a similar thing in real life: Metlink Melbourne Journer Planner (obviously, a when option is unnecessary) A few people also said it sounded like MapQuest, although I don't know what that is.

Comments, queries, questions? Cheers, Chicken7 >talk 13:59, October 31, 2009 (UTC)

Comment - Every area has a list of ways it can be gotten to on its article. Now that's a throwing weapon!Doucher4000******r4000I'll eat you! 14:44, October 31, 2009 (UTC)

Not every area. And it doesn't only come up with the ways to get to the place in general, it is the ways to get from 1 location to another. Like if you were in the Troll Country and needed to get to Tyras Camp, the only listing on the article is charter ships... What is the nearest charter ship to the Troll Country? Is there a teleportation spell/item to a nearby town (Lletya), etc. Chicken7 >talk 14:50, October 31, 2009 (UTC)

Comment - Is this really necessary? I do not see how it would help. Most of the area infoboxes say how to get there, and the world map is easier to use (because it's in-game). Ancient talisman.png Oil4 Talk 14:46, October 31, 2009 (UTC)

Support - Oh well. It could help. If you're able to pull this of, please do. Ancient talisman.png Oil4 Talk 21:21, October 31, 2009 (UTC)

Support - At least so far as a general attitude of support for such a concept. This wouldn't be an easy nut to crack, and it sort of fits into a very difficult class of computation, known generally as the Travelling salesman problem. For those who are computer scientists (or at least studied the art of computers and computational machinery), this is a problem with the class O(n!). In other words, the complexity of solving this problem grows at the rate of a factorial... one of the worst possible kind of computational problems that exists in computer science that is at least still "solvable" in a theoretical sense.

That some "shortcuts" do exist in terms of solving problems like this is true, and we could abstract this problem significantly in terms of restricting the overall domain to just major points of information (such as cities, entrances to dungeons, transportation links, or anything else that is a place with an article on this wiki). That some obvious transport links are far more efficient than others is true, but an exhaustive search for the "best" and "fastest" path may end up taking more time than has existed since the universe (our universe) was created with the Big Bang. I'm not kidding here either. It is amazing that some companies even try to get this to work, and while the absolute fastest may not be easily found, a pretty good path that is fairly efficient can usually be found quite quickly. There are many approaches to trying to solve this problem too, and this is very cutting-edge computer science theory that has gone into the study of this problem. If you can solve this problem, it is an easy way to get a PhD in computer science or even get the computing equivalent of the Nobel Prize. --Robert Horning 16:37, October 31, 2009 (UTC)

Comment - This is not the same as TSP. In TSP, you are trying to visit all vertices and have the ending vertex be the same as the starting vertex. That would be like trying to visit all cities/NPCs/etc. in RuneScape in the shortest time possible. In our case, we are just finding the shortest path between two different vertices, and algorithms which do this (like Dijkstra's algorithm) have times that run much better than factorial time. Dijkstra's, for example, varies from O(V2) in the worst case to O(E+V log V) in very efficient implementations. We do have other potential complications, though, such as having a gold cost versus walking distance cost (e.g. for using spells or ferries) as well as the ability to use certain methods such as fairy rings to reduce the distance. --Quarenon  Talk 21:15, October 31, 2009 (UTC)
Comment - If finding the fastest method would take ages (literally), what about listing all methods to get there and leave it up to a player's discretion on which is the fastest method that fit's their requirements. Chicken7 >talk 01:21, November 1, 2009 (UTC)
I'll admit what I wrote was a worst-case situation, although all graph spanning algorithms are complex by their nature. For routes that go directly from one point to the next (aka a teleport into Varrock next to Obbi's Staff Shop) it is obvious, but not all transportation routes work in this manner. It is the two-step and three-step transports that may be trickier, such as travel by fairy ring to the GE and then taking the mine cart to Keldagrim. Where the real issue comes up is if you need to get between dungeons and places a bit more off the beaten path. Travel between major cities tends to be a simple teleport or enchanted jewelry. I've seen Great Orb Project teletabs to altars also used for short-cuts, so it seems to me that the major sticking point would be to extract your current level and quest information to determine what is the fastest path for a specific player. Even things like the fairy rings, balloon transportation, and mine carts are transport options that have quest requirements and certain minimum levels to perform. --Robert Horning 08:34, November 1, 2009 (UTC)
Haven't read all of this yet but I'll agree with Quarenon that this looks like a simple shortest path problem (vertices would be "rendezvous points" such as cities, fairy nodes, etc and edges would be travel time) nothing harder. You could of course make it more complicated if you wanted to. Endasil (Talk) @  05:49, April 11, 2010 (UTC)


Comment - BTW if you can manage to get a polynomial-time algorithm for TSP, you would have your choice of the Nobel Prize (that's a locked-up guarantee) or about 7 billion dollars. Either from selling it to a government or using it yourself. Solving TSP entails finding polynomial-time algos for every other NP-hard problem, and that (I believe) includes number factorization. Almost all current network security depends on the computational complexity of number factorization, so if you found an efficient mechanism for that, you'd basically be able to hack RSA and subvert basically public-key based security scheme. :-) Nobel prizes are for suckers. Endasil (Talk) @  05:55, April 11, 2010 (UTC)

Support, if it's do-able. The idea sounds really great, but it'd be very difficult to implement. ~ Fire Surge icon.png Sentry Telos Talk  20:31, October 31, 2009 (UTC)


Support - If do-able. Like Robert said, finding a good path between them would generally be easier than finding the best path, so is a better option. I'd like to see if anything can be brought to the metaphorical table. Quest.png Gaz Lloyd 7:^]Events!99s 20:46, October 31, 2009 (UTC)

Support - While that is out of my league of computing knowledge, if someone knows how to create it and is willing to, then I am all for it! Unicorn horn dust.png Evil Yanks talk 01:25, November 1, 2009 (UTC)

Support - I will try to make a beta one in my Sandbox, if anyone that knows how to implement JScript in the wikia, please tell me, I'll be back when I have a solution. Quest point cape.pngTalk Newbie856 edit count Nomad guideMusic icon.png 20:02, November 1, 2009 (UTC)

Comment I have a few:

  • I suggest returning the fastest route, together with a list of requirements. Each requirement could have a "don't have" link next to it, which the use could click to recalculate the fastest route not using that requirement (of course the list of "don't have" requirements would be cumulative). This would include things like "ancient spellbook", so the user could click this off if they didn't want to switch spellbooks.
  • It would also be useful to give the fastest route between a given point and any bank (in either direction).
  • In terms of computational difficulty, this problem isn't as bad as it seems because most "fastest routes" in runescape are of the form "Teleport to X. Run a short distance from X to B."
  • My suggestion for implementing this would be to first decide on a bunch of "nodes" to act as possible start/end points and points along the way. These would include points of interest (banks, dungeons etc) as well as choke points (eg bridges) since any minimal path is basically going to be a sequence of choke points. Then one could use A* to find minimal walking routes I guess? (I've heard this is quite efficient, but I'm not a computer scientist...) I'll have a go at writing something like this, but I just wanted to put my thoughts here first.Stewbasic 12:32, November 5, 2009 (UTC)
Comment - I like your ideas, thought and tests (below), guys. Just remember I'm no coding wiz, it was just an idea I had I wanted to share. Once you get a lot of the difficult coding out of the way if someone attempts this, I am happy to help setting up locations on the map etc. (Also I like the bank idea, could be like a checkable box whether you need to go via bank. Cheers, Chicken7 >talk 05:35, November 6, 2009 (UTC)
Comment - I've had this idea where someone clicks on where he is on a world map thing, then clicks where he wants to go an it gives him some sort of trail, with teleports and all sorts of stuff. I think this could easily (well, you know what I mean) be done in a program without wiki code and implemented on the wiki, maybe VBasic? Also, as of how it should work, I think just billions of dots on the world map and links between to places (Wildy and Ardougne lever) would be needed, as well as teleportation dots and one way stuff, a hard challenge to accomplish!
If the template was to be made with wiki code (like I did below), I think we should seperate it in the 15 continents there are, to avoid lag. Also, the only things in choices would be the things written on the map, so Clan Wars would be there as for Astral Altar wouldn't. Quest point cape.pngTalk Newbie856 edit count Nomad guideMusic icon.png 11:51, November 6, 2009 (UTC)

Idea on how to get it done - Well i suppose you could create a program that includes every obstacle in RuneScape and have the program try and get from point A to point B on a huge grid of RS, this shrinks the O(n!) problem just a little bit and as noob suggested above, it should be divided. For an example have you guys ever played Roller Coaster Tycoon 3? In that game there is an autocomplete track feature where i constatntly draws and redraws track till it finds something that works.
--

Runecrafting MythbustermaTalk   HSCabbage.png<= BRASSICA PRIME

19:09, November 8, 2009 (UTC)

Support - I like the idea, though I'd imagine that it would be hard to do. My question is, how would we access this tool/program? Would there be a link to it in every location article?  Tien  20:23, November 8, 2009 (UTC)

I dont see why not? -- 20:38, November 8, 2009 (UTC)
I guess just a link in the location infoboxes would do. Cheers, Chicken7 >talk 04:50, November 9, 2009 (UTC)

Support it it's possible. But not if we end up using the template, we should use a program. White partyhat old.png C Teng talk 20:35, January 1, 2010 (UTC)

Support - I like the idea. We should find a userpage for the fastest route from area A to area B. Hehe, kidding. Fishing.png NnK Oliver (600613) talk 01:11, January 2, 2010 (UTC)

Comment - I think it's a good idea, but I'm afraid it'll turn out to be as complicated as programming a GPS system. :p Farming cape (t).png Lil cloud 9 Talk 11:05, January 4, 2010 (UTC)


Unfortunately this ended up on my todo list for a while (AKA the place for those things I never get around to doing), but I finally have a working version here. There are two main issues:

  • As far as I can tell, a wiki page can't have a script specific to that page (thanks to Quarenon for answering my questions about this). So I'm not sure how such a thing could be put on the wiki (especially the graphical version)
  • The graphical version is only supported by some browsers because of the <CANVAS> tag. The world map is too big to display all at once (it also takes a while to download). Putting it on this map would be ideal, but setting that up would require saving the map at several zoom levels, split into many tiles, plus a lot of javascript which I'm guessing the folks at rsbandb don't want to share.

As you can see here, I've only put in enough data to test it out. The node array only covers the f2p area, and ideally it would be a little finer. There are also lots of teleports and links to add (would anyone be willing to help with this? I'm looking at your comment above Chicken7 :P). Regarding running/walking, one only needs to minimize the distance travelled since a player of a given agility level will get tired after a fixed distance, no matter which way they go. Admittedly musicians complicate matters... I've ignored that. I've also assumed all teleports and links are instantaneous; it would be a bit complicated but I think that could be changed. Two miscellanious points: I don't think it's worthwhile working out the cost of charter boats, since it depends on so many things, so I've just listed the requirement as bringing 5k (this is currently moot with only one charter boat in the f2p area :P). I've also put the lumbridge swamp shed on the fairy ring network, which is not quite correct. Anyway please let me know what you think, especially if you find any bugs. Stewbasic 01:05, January 8, 2010 (UTC)

Wow, I'm impressed! For the map issue, you may want to check out this RuneScape map, which uses Google Maps API with my own tiling script. The API should deal with the IE and loading issues as well as give you the other neat features of Google Maps. The map based on the JPG image from the the official world map. I haven't managed to find a larger non-JPG map that would look better at low zoom levels, but the current one does its job. I can definitely assist you if you want to merge the Maps API with your pathfinding script as well as send you the 1,365 tile images which make this map.
As far as bugs, it seemed to work fine in Firefox 3.6 beta 5, but it doesn't appear at all in the latest public version of Google Chrome (3.0.195.38). After investigating, I found that it was because of the array assignment feature of JavaScript 1.7 which is not supported in Chrome yet. That pertains to line 14 of map.js:
[mapx,mapy]=findPos(mymap);
Another issue occurred in Opera 10.10, and I believe the cause is that your <canvas> tag is being mistakenly closed by a </div> tag rather than </canvas>. Other than that, great work! --Quarenon  Talk 05:53, January 8, 2010 (UTC)
That is fantastic!!! Some people have put so much long work into this. I like the idea of putting the dots down. Another idea is typing the location. So in a way, incorporating Newbie's idea below with this idea. And one other thing that'd be great is if it had a line on the map. from the start to finish. Anyway, sorry for throwing so many complicated ideas at you. I am able to help with the actual easy, semi-easy stuff, as I said Smile Cheers, Chicken7 >talk 08:50, January 8, 2010 (UTC)
About the walk/run times, I agree that such a thing will be very complicated to pin down a number, considering all the variables (Agility level and boosts, carried weight, musicians, Explorer charges, etc). The best idea I can come up with is to either use a confidence interval whose accuracy varies with the distance and/or use a "best-case" scenario that forms the lower bound for how fast you could make it. Then you can be (nearly) 100% certain that your time meets or is slower than the given time. This would probably be the most useful time to use if you wanted to truly compare distances of different paths in terms of times. However, this would likely be tough to implement. --Quarenon  Talk 20:42, January 8, 2010 (UTC)
I will get right on compiling a bigger map (think like 100 000 pixels wide kind of big). Since that will require an insane amount of time to transfer to your tiling script (not to mention an even more insane amount of time just to create), I will tile it locally, provided that I can figure out how. Could you either a) explain to me how tiling works so I can write my own code to do it, or b) provide a downloadable tiler? Thanks, I'm a regular user and I approve this message.  TLUL Talk - Contribs 23:59, January 19, 2010 (UTC) 
The in-game world map is 4 pixels per square at the highest zoom level, which would make an 8000 pixel wide world map; do you intend to make it larger than that? And if so, where would the images come from if not the in-game map? To set up a google map, the image needs to be scaled to half size repeatedly (ie the original image, one 50% the size, one 25%, one 12.5% etc), and each zoom level needs to be cut into 256x256 squares. For my map, I created the files in this directory using this imagemagick script. Presumably Quarenon's map has similar images, though possibly labelled differently. I'd like to be more helpful but I'm not sure quite what you're planning to do... Well please ask if you have any more questions. Stewbasic 14:02, January 23, 2010 (UTC)

Thanks for catching those errors. Per your suggestion, I put it on a google map (I was planning to do so after I saw the rsbandb map, but I got scared away by this). On second thought, having several people working on the node array might complicate putting all the data into one file, so perhaps it's easiest if I just do that myself. Stewbasic 00:16, January 15, 2010 (UTC)

Template Made

I have made a template at User:Newbie856/sandbox/journalmap. It currently contains 3 end and 3 start locations (Varrock, Fally, Lummy).

You guys were right, it's complicated to make, I will try to do something to make it easier to add locations.

Here are examples of my template:

Code:

{{User:Newbie856/sandbox/journalmap
|start=Varrock
|end=Lumbridge
}}

Result:

Starting Location: Varrock End Location: Lumbridge
  1. Teleport To Lumbridge (31 Magic)
  2. Walk
  3. Cast Home Teleport


Standard Utilisation.

Code:

{{User:Newbie856/sandbox/journalmap
|start=Varrock
|end=Lumbridg
}}

Result:

Starting Location: Varrock End Location: Lumbridg

End Location Does Not Exist


Made a mistake in end location, results in telling you it doesn't exist.

Code:

{{User:Newbie856/sandbox/journalmap
|start=Varroc
|end=Lumbridge
}}

Result:

Starting Location: Varroc End Location: Lumbridge

Start Location Does not exist.


Made a mistake in start location, results in telling you it doesn't exist.

Ooh, it's broken, I'll get right on to it.

So that's my template!

Quest point cape.pngTalk Newbie856 edit count Nomad guideMusic icon.png 20:57, November 1, 2009 (UTC)

I've managed to add forms on my template, see it at User:Newbie856/sandbox/journalmap/doc.

Quest point cape.pngTalk Newbie856 edit count Nomad guideMusic icon.png 21:08, November 1, 2009 (UTC)

Noob if you need some help ill start drawing realitive maps and helping you with those templates, just say the word. Oh and by the way, theres an epic glitch, if you try to start and end in the same place, itll say the the location doesnt exist
-- 19:09, November 8, 2009 (UTC)
That's pretty epic. Well done! =D Swiz Talk Review Me 12:25, January 3, 2010 (UTC)
Yea you should add times walking and running Ranged 14 Supawilko 12:34, January 3, 2010 (UTC)
You can't people have different run times because of their agility levels, right? Swiz Talk Review Me 12:42, January 3, 2010 (UTC)
Walking and running are constant (1 square per tick and 2 squares per tick, respectively). Agility would only come into it when you have to stop and recharge energy (that is, not use a potion/familiar/etc). How often you'd need to stop would depend on the carried weight... can be done but would be overly complicated. Just use a walk time and a run time (no rest/1 agility rest, 0 kg weight), if at all. Quest.png Gaz Lloyd 7:^]Events!99s 15:32, January 4, 2010 (UTC)
Ooooh right. Also, you could include musicians you could stop at on the way, or Explorers Ring recharges. Swiz Talk Review Me 16:46, January 4, 2010 (UTC)
Something to remember- Don't be afraid to start off with the basics-- let's just start with mapping out the ways to get from Point A - B. The rest of the stuff, like ETA, "pit stops" (banks, musicians, etc.), and the lot can wait until the groundwork is laid down. Let's figure out how to walk before we think about trying to fly. --Beware the underrated. Pikaandpi Berserker Fury!Hit hard or go home. 20:01, January 19, 2010 (UTC)
I agree. These all sound like interesting features, but point A-B is what we want right now. It seems you guys are trying to be more advanced than most modern GPS devices which usually don't predict when you need petrol and where the nearest one is. Also, the purpose of this was not necessarily to time how long it takes someone, but simply to supply a list of methods from getting to point A - B. Cheers, Chicken7 >talk 23:08, January 19, 2010 (UTC)

Comment - Nothing new has come out of this for awhile. I might try and use all the ideas from above and attempt to do something. If it takes longer than expected, maybe it should be moved off of the Yew Grove, as there is community consensus to go ahead with the idea of this tool. Cheers, Chicken7 >talk 03:06, April 11, 2010 (UTC)

WikiGuild

Scratch the above. Me and JavaScript just don't mix. I would like to propose a WikiGuild to continue this idea elsewhere. Consensus is to implement the idea, but the problem is, we don't have much. Although there are many ideas, and users who are great with coding and have presented ideas above can continue discussion there. That way we're not clogging up the YG. The WikiGuild can be simply closed once its job is done, although that may be awhile. Cheers, Chicken7 >talk 03:48, April 11, 2010 (UTC)

Support - Seems fine to me. scoot4.pngscooties 03:56, April 11, 2010 (UTC)

Request closure - Nothing has occured for the past 80 days. Discussion has died. Continue on RS:WG if it is implemented 222 talk 06:55, June 27, 2010 (UTC)

This request for closure is complete A user has requested closure for Journer Planner/Mapquest idea. Request complete. The reason given was: complete

ʞooɔ 09:20, July 5, 2010 (UTC)

Re-request closure - Per above. 222 talk 01:17, July 19, 2010 (UTC)

Comment - Is the WikiGuild going ahead? I haven't seen it in WikiGuilds. 222 talk 10:45, August 19, 2010 (UTC)

Closed - No actual discussion for seven months. If this heats up again, feel free to make another thread/WikiGuild. ʞooɔ 07:49, August 25, 2010 (UTC)