|
MAPS
Dec 16, 2011 11:34:37 GMT -5
Post by Usagi Reisen on Dec 16, 2011 11:34:37 GMT -5
I'm currently working on a php site that allows you to find the most direct path between one location to another (choose location from two list box and press go thingy). I don't think it will be usefull since : - it's still not finished, but algorithm is working, I just have to travel to all location to get the html source and fix some weird location (like travel by horse). - nobody will use it if the link is only provided in this forum. - I want to add all items as well (where to find them function) but that would take some huge time. - I want it to be automatically refresh via my facebook account by simulating request... well that's maybe a little too far...
But if you think you would be interested in it, let me know, I would post the link when it's ready.
|
|
|
MAPS
Dec 16, 2011 13:55:15 GMT -5
Post by Mirumoto Shigekazu on Dec 16, 2011 13:55:15 GMT -5
It is interesting tool. But I do not understand why nobody will use it if the link would be provided only in this forum?
If you need some help with items, I can provide my little assistance. I am working on this problem for several months so some obstacles are already known to me and I can share my knowledge on that issue.
|
|
|
MAPS
Dec 17, 2011 13:20:29 GMT -5
Post by Usagi Reisen on Dec 17, 2011 13:20:29 GMT -5
I love regex, I use them everywhere. I iniatialy intend to use your thread for item, getting the html, parsing it and that's all. That's what I did with location. If I had some problem to parse your thread, I'll mp you.
As for the link, I very seldom go to the forum, and searching for the link I want is too much burden. That's why I said that people might not use my tool. Well, I will provide the link then, and add a stats function to see if it is used.
Thanks for the help.
|
|
|
MAPS
Dec 17, 2011 14:32:30 GMT -5
Post by Mirumoto Shigekazu on Dec 17, 2011 14:32:30 GMT -5
I am really interested how you managed to find best routes. I thought about tree which divide its branch every time it expands to new location with multiple possible exits and quits branch when entry is equal to any entry from lower parts of the tree (including different branches). Algoritm ends when final destination is reached (checked at the end of iteration). It would allow not only easily include horse and sea travel but also home locations.
|
|
|
MAPS
Dec 19, 2011 5:41:45 GMT -5
Post by Usagi Reisen on Dec 19, 2011 5:41:45 GMT -5
Dijkstra's algorithm For The Win. And I count the distance by mouse click, so the algorithm is quite simple since all travel time is set to 1. In a nutshell algorithm : save all edge (directed edge, since there is a one-way travel), set them as unvisited, start from start input, visit all non visited neighbor, make them visited, start over from each just visited neighbor, stop when arrived.
As for I treat horse and sea travel as any other location, which it is (travel by sea has even its own action).
|
|
|
MAPS
Dec 19, 2011 11:09:39 GMT -5
Post by Mirumoto Shigekazu on Dec 19, 2011 11:09:39 GMT -5
Does it include requirements for moving to location? It may be difficult for some characters to get into Siska or Reihado Shinsei. Speaking of Reihado Shinsei, two routes are one-way only. I am curious how you implemented that?
I hope I do not sound aggresive in any way. I am very curious since I thought about this problem for some time.
|
|
|
MAPS
Dec 19, 2011 12:32:39 GMT -5
Post by Usagi Reisen on Dec 19, 2011 12:32:39 GMT -5
I wasn't aware of a second one-way route apart from Reihado Shinsei to Seven Fold Palace. I use directed-edge, that mean one-way route, apart from that, can't tell you more than post the code . You don't seem aggressive, don't worry. $step = 0; $from = $_POST['from']; $to = $_POST['to']; $itinary[$step][] = $from; $visited[$from] = true; // Visit all nodes till arrival while (! isset($visited[$to])) { $step ++; // Start from all previous added node foreach($itinary[$step-1] as $way) { foreach($travel[$way] as $location => $info) { // Add new node if not yet visited if(! isset($visited[$location])) { $visited[$location] = $way; $itinary[$step][] = $location; // If arrival, save the last edge if($location == $to) { $track_back_from = $way; $track_back_to = $to; } } } } } // Find the route we took for($i = $step-1; $i >= 0; $i--) { $path[$i]['from'] = $track_back_from; $path[$i]['to'] = $track_back_to; // We saved the route in the visited array $track_back_to = $track_back_from; $track_back_from = $visited[$track_back_from]; } // Display route and save skills needed for($i = 0; $i < $step; $i++) { if($i == 0) { echo $path[$i]['from'].' <img src="'.$img[$path[$i]['from']].'"/>'.' => '.$path[$i]['to'].' <img src="'.$img[$path[$i]['to']].'"/>'; } else { echo ' => '.$path[$i]['to'].' <img src="'.$img[$path[$i]['to']].'"/>'; } $skill[$travel[$path[$i]['from']][$path[$i]['to']]['skill']] = max($skill[$travel[$path[$i]['from']][$path[$i]['to']]['skill']], $travel[$path[$i]['from']][$path[$i]['to']]['level']); } // Display skills needed echo '<br> -=-=-=- need -=-=-=- <br>'; foreach($skill as $need => $level) { echo $need.' '.$level.'<br>'; } The $travel array contains the directed edge like that [from][to][skill+level]. link for the very sober alpha here
|
|
Shagi the Mad
Crane Clan
Fallen Crane * Scout * Mad * Shadowlands * Experienced 4 Hiruma Shagi
Posts: 180
|
MAPS
Dec 19, 2011 15:16:17 GMT -5
Post by Shagi the Mad on Dec 19, 2011 15:16:17 GMT -5
Bookmarked!
One thing that occurs to me is that I'm going to have to assess any path twice: once from my current location and once from my home location (which is always one click away). Maybe another field for home location, calculating both routes, and choosing the shorter might be a future addition?
|
|
|
MAPS
Dec 19, 2011 15:42:22 GMT -5
Post by Mirumoto Shigekazu on Dec 19, 2011 15:42:22 GMT -5
That would require some database on Home Locations... which do not exist yet.
|
|
Shagi the Mad
Crane Clan
Fallen Crane * Scout * Mad * Shadowlands * Experienced 4 Hiruma Shagi
Posts: 180
|
MAPS
Dec 19, 2011 17:14:16 GMT -5
Post by Shagi the Mad on Dec 19, 2011 17:14:16 GMT -5
But in the meantime, the user could select one manually from a third drop-down menu if desired.
|
|
|
MAPS
Dec 19, 2011 19:13:55 GMT -5
Post by Usagi Reisen on Dec 19, 2011 19:13:55 GMT -5
hum... yeah, third optional drop down list for home seem the most elegant way to do it. Thanks for the idea. Will propably suspend updates for this year, I'm on leave and I only work on this at work It's technology intelligence
|
|
|
MAPS
Dec 21, 2011 6:33:24 GMT -5
Post by Soshi Kiso on Dec 21, 2011 6:33:24 GMT -5
Nice!
|
|