Category
|
You're no bot and a page you've created got automatically deleted? Add your name to FreewarWiki:NoSpamUser |
|
Difference between revisions of "MediaWiki:Autorouter.js"
From FreewarWiki
| Line 5: | Line 5: | ||
var map = new Object(); | var map = new Object(); | ||
| − | // | + | // Initialization |
| + | |||
function init_router() | function init_router() | ||
{ | { | ||
| Line 14: | Line 15: | ||
str = str + n.nodeValue; | str = str + n.nodeValue; | ||
} while (n = n.nextSibling); | } while (n = n.nextSibling); | ||
| − | + | areas = str.replace(/,/g, '|').split('Arealink|'); | |
| − | for (i in | + | for (i in areas) { |
| − | var | + | var area = areas[i].substr(0, areas[i].indexOf('}')); |
| − | var coords = | + | var coords = areas[i].match(/-*\d+\|-*\d+/g); |
| − | for (j in coords) map[coords[j]] = | + | for (j in coords) map[coords[j]] = area; |
} | } | ||
| Line 40: | Line 41: | ||
// Die internen Tool-IDs den Positionen in der alphabetisch geordneten Tabelle zuordnen | // Die internen Tool-IDs den Positionen in der alphabetisch geordneten Tabelle zuordnen | ||
| − | var | + | var array = Array('4', '6', '3', '1', '2', '5'); |
var tools = document.getElementById('map_tools').getElementsByTagName('td'); | var tools = document.getElementById('map_tools').getElementsByTagName('td'); | ||
for (var i = 0; i < 6; i++) { | for (var i = 0; i < 6; i++) { | ||
| − | map_check.name = 'opt' + | + | map_check.name = 'opt' + array[i]; |
tools[i].insertBefore(map_check.cloneNode(false), tools[i].firstChild); | tools[i].insertBefore(map_check.cloneNode(false), tools[i].firstChild); | ||
} | } | ||
| Line 79: | Line 80: | ||
map_race.appendChild(map_option.cloneNode(true)); | map_race.appendChild(map_option.cloneNode(true)); | ||
map_option.value = '101|119'; | map_option.value = '101|119'; | ||
| − | map_option.firstChild.nodeValue = ' | + | map_option.firstChild.nodeValue = 'Tarunan'; |
map_race.appendChild(map_option.cloneNode(true)); | map_race.appendChild(map_option.cloneNode(true)); | ||
| Line 109: | Line 110: | ||
} | } | ||
| − | // | + | // Main part |
| − | // | + | // Modified Dijkstra algorithm |
// | // | ||
// Um Platz zu sparen, verzichten wir auf eine explizite Graphen-Darstellung | // Um Platz zu sparen, verzichten wir auf eine explizite Graphen-Darstellung | ||
| Line 120: | Line 121: | ||
// Zusaetzliche Kanten stehen im assoziativen Array "edges": | // Zusaetzliche Kanten stehen im assoziativen Array "edges": | ||
// | // | ||
| − | // edges["von-x|von-y"] = Array("nach-x|nach-y| | + | // edges["von-x|von-y"] = Array("nach-x|nach-y|description|tools", ...) |
// | // | ||
// Zauberkugeln werden grundsaetzlich nur im 1. Schritt eingesetzt | // Zauberkugeln werden grundsaetzlich nur im 1. Schritt eingesetzt | ||
// | // | ||
| − | // edges["teleport"] = Array("nach-x|nach-y| | + | // edges["teleport"] = Array("nach-x|nach-y|description|tools", ...) |
// | // | ||
// wobei "tools" ein Bitfeld ist, das die Hilfsmittel/Bedingungen | // wobei "tools" ein Bitfeld ist, das die Hilfsmittel/Bedingungen | ||
| Line 137: | Line 138: | ||
// Portal in Reikan | // Portal in Reikan | ||
"94|111" : new Array( | "94|111" : new Array( | ||
| − | "90|115|Portal | + | "90|115|Portal to Kerdis|2", |
| − | "64|80|Portal | + | "64|80|Portal to Rovonia|2", |
| − | "122|100|Portal | + | "122|100|Portal to Kuridan/Everchanging river|2", |
| − | "72|116|Portal | + | "72|116|Portal to Terasi|2", |
| − | "144|126|Portal | + | "144|126|Portal to Rock Island|2", |
| − | "121|91|Portal | + | "121|91|Portal to Torin|2", |
| − | "122|116|Portal | + | "122|116|Portal to Lardikia|2", |
| − | "62|83|Portal | + | "62|83|Portal to Kolun|2", |
| − | "59|106|Portal | + | "59|106|Portal to Krato|2", |
| − | "129|90|Portal | + | "129|90|Portal to Brondor|2", |
| − | "115|100|Portal | + | "115|100|Portal to Kuridan/Plains|2", |
| − | "111|83|Portal | + | "111|83|Portal to Wilisia|2", |
| − | "135|115|Portal | + | "135|115|Portal to Linya|2", |
| − | "58|98|Portal | + | "58|98|Portal to Dranar|2", |
| − | "106|93|Portal | + | "106|93|Portal to Ferdolia|2", |
| − | "110|107|Portal | + | "110|107|Portal to Nawor|2" |
), | ), | ||
// sonstige Teleport-Mechanismen | // sonstige Teleport-Mechanismen | ||
"teleport" : new Array( | "teleport" : new Array( | ||
| − | " | + | "Homespell-Dummy - muss Index 0 besitzen!", |
| − | "87|90| | + | "87|90|Staff of Trade to the Market place|32", |
| − | "88|89| | + | "88|89|Staff of Trade to the Central Traders Depot|32", |
"96|109|ZK/Nebel/Flügel nach Reikan|8", | "96|109|ZK/Nebel/Flügel nach Reikan|8", | ||
"99|115|ZK/Nebel/Flügel nach Mentoran|8", | "99|115|ZK/Nebel/Flügel nach Mentoran|8", | ||
| − | "98|120|Ring | + | "98|120|Ring of the Sand Winds to Mentoran|4", |
| − | "58|107|Ring | + | "58|107|Ring of the Sand Winds to Krato|4", |
| − | "121|112|Ring | + | "121|112|Ring of the Sand Winds to Lardikia|4", |
| − | "-599|-489| | + | "-599|-489|Yellow MS to the Forest of light|16", |
| − | "96|101| | + | "96|101|Staff of Trade to the Market hall|32", |
| − | "117|113| | + | "117|113|Staff of Trade to the Market hall of Lardikia|32", |
| − | "81|94| | + | "81|94|MS/Mist/Wings to the lost valley|8", |
| − | "72|85|Ring | + | "72|85|Ring of the Sand Winds to Urdania|4", |
| − | "87|87| | + | "87|87|Staff of Trade to the Auction Hall|32", |
| − | "501|51| | + | "501|51|MS/Mist/Wings to Narubia|8", |
| − | "98|81|Ring | + | "98|81|Ring of the Sand Winds to Latenia|4", |
| − | "-803|-808| | + | "-803|-808|Yellow MS to the Ruin|16", |
| − | "103|110| | + | "103|110|MS/Mist/Wings to Nawor|8", |
| − | "101|100| | + | "101|100|MS/Mist/Wings to Konlir|8", |
| − | "65|96|Ring | + | "65|96|Ring of the Sand Winds to Delos|4", |
| − | "80|87| | + | "80|87|MS/Mist/Wings to Buran|8", |
| − | "108|114| | + | "108|114|MS/Mist/Wings to Orewu|8", |
| − | "-798|-798| | + | "-798|-798|Yellow MS to the Grave|16", |
| − | "-785|-786| | + | "-785|-786|Yellow MS to the Sewer|16", |
| − | "75|99| | + | "75|99|MS/Mist/Wings to Kanobia|8", |
| − | "92|105| | + | "92|105|MS/Mist/Wings to the Universal Bank|8", |
| − | "123|92|Ring | + | "123|92|Ring of the Sand Winds to Torin|4", |
| − | "100|94| | + | "100|94|MS/Mist/Wings to Ferdolia|8", |
| − | "-347|-693| | + | "-347|-693|Yellow MS to the Ice Cave|16", |
| − | "93|96| | + | "93|96|MS/Mist/Wings to Valley of Ruins|8", |
| − | "71|92| | + | "71|92|MS/Mist/Wings to Sutrania|8", |
| − | "66|111| | + | "66|111|MS/Mist/Wings to Terasi|8", |
| − | "85|102| | + | "85|102|MS/Mist/Wings to Anatubia|8", |
| − | "92|90| | + | "92|90|MS/Mist/Wings to Hewn|8" |
), | ), | ||
| Line 339: | Line 340: | ||
// Im Array normal_unbetretbar werden Felder wie die Vulkanspitze gespeichert, | // Im Array normal_unbetretbar werden Felder wie die Vulkanspitze gespeichert, | ||
// die zwar betretbar sind, aber nur durch explizite Kanten | // die zwar betretbar sind, aber nur durch explizite Kanten | ||
| − | var | + | var normal_inaccessible = { |
"87|103" : 1 | "87|103" : 1 | ||
}; | }; | ||
// Namen der Hilfsmittel | // Namen der Hilfsmittel | ||
| − | var | + | var teleport_tool = { |
0 : "", | 0 : "", | ||
| − | 1 : " | + | 1 : "Portals", |
| − | 2 : "Ring | + | 2 : "Ring of the Sand Winds", |
| − | 3 : " | + | 3 : "Magic sphere/Mist/Wings", |
| − | 4 : " | + | 4 : "Yellow magic sphere", |
| − | 5 : " | + | 5 : "Staff of Trade", |
| − | 6 : " | + | 6 : "Home Spell" |
} | } | ||
| − | // | + | // Main function |
| − | function | + | function find_way() |
{ | { | ||
while (document.getElementById('map_path').firstChild) | while (document.getElementById('map_path').firstChild) | ||
| Line 370: | Line 371: | ||
// hier kommt ein Array von Loesungs-Strings zurueck. | // hier kommt ein Array von Loesungs-Strings zurueck. | ||
| − | + | try = new Array(); | |
tools = 1; | tools = 1; | ||
if (document.map_form.opt1.checked) tools |= 2; | if (document.map_form.opt1.checked) tools |= 2; | ||
| Line 378: | Line 379: | ||
if (document.map_form.opt5.checked) tools |= 32; | if (document.map_form.opt5.checked) tools |= 32; | ||
if (document.map_form.opt6.checked) tools |= 64; | if (document.map_form.opt6.checked) tools |= 64; | ||
| − | + | solution = find_way_internal(src, dst, tools); | |
// die Loesungs-Strings haben die Form | // die Loesungs-Strings haben die Form | ||
| − | // | + | // tool;length;direction |
// - hieraus nun String bauen | // - hieraus nun String bauen | ||
| − | if (! | + | |
| + | if (!solution) string = "No optimal way found."; | ||
else { | else { | ||
| − | elements = | + | elements = solution.split(";"); |
if (elements[0] != 0) { | if (elements[0] != 0) { | ||
| − | string = " | + | string = "Requires: "; |
| − | + | comma = 0; | |
for(j = 0; j < 16; j++) { | for(j = 0; j < 16; j++) { | ||
if (elements[0] & (1 << j)) { | if (elements[0] & (1 << j)) { | ||
| − | if ( | + | if (comma) string += ", "; |
| − | string += | + | string += teleport_tool[j]; |
| − | + | comma = 1; | |
} | } | ||
} | } | ||
} else { | } else { | ||
| − | string = " | + | string = "Absolute foot route"; |
} | } | ||
| − | string += " - | + | string += " - Length: " + Math.floor(elements[1]); |
makemap(src, dst, elements[2]); | makemap(src, dst, elements[2]); | ||
} | } | ||
| Line 406: | Line 408: | ||
} | } | ||
| − | function makemap(src, dst, | + | function makemap(src, dst, way) |
{ | { | ||
makemap_point(src, "http://www.fwwiki.de/images/3/31/Red.png"); | makemap_point(src, "http://www.fwwiki.de/images/3/31/Red.png"); | ||
lastplot = src; | lastplot = src; | ||
| − | pts = | + | pts = way.split("->"); |
for(var i=0; i<pts.length; i++) | for(var i=0; i<pts.length; i++) | ||
{ | { | ||
| Line 437: | Line 439: | ||
if (xd>yd) | if (xd>yd) | ||
{ | { | ||
| − | // y- | + | // y-distance ist schleifen-master, x ist slave |
if (x0>x1) | if (x0>x1) | ||
{ | { | ||
| − | // | + | // swap |
xt=x0; x0=x1; x1=xt; | xt=x0; x0=x1; x1=xt; | ||
yt=y0; y0=y1; y1=yt; | yt=y0; y0=y1; y1=yt; | ||
| Line 460: | Line 462: | ||
if (y0>y1) | if (y0>y1) | ||
{ | { | ||
| − | // | + | // swap |
xt=x0; x0=x1; x1=xt; | xt=x0; x0=x1; x1=xt; | ||
yt=y0; y0=y1; y1=yt; | yt=y0; y0=y1; y1=yt; | ||
| Line 480: | Line 482: | ||
| − | function makemap_point( | + | function makemap_point(coord, img) |
{ | { | ||
| − | k = | + | k = coord.split("|"); |
if (k[0] < 0 || k[1] < 0) return; | if (k[0] < 0 || k[1] < 0) return; | ||
| − | prefix = prefixes['prefix' + map[ | + | prefix = prefixes['prefix' + map[coord].replace(/\s/g, '_')] ? prefixes['prefix' + map[coord].replace(/\s/g, '_')] : ''; |
x = (k[0] - (Number(TopLeftXs[prefix + 'TopLeftX']) - 1) + Number(OffsetXs[prefix + 'OffsetX'])) * 15 + 5; | x = (k[0] - (Number(TopLeftXs[prefix + 'TopLeftX']) - 1) + Number(OffsetXs[prefix + 'OffsetX'])) * 15 + 5; | ||
y = (k[1] - (Number(TopLeftYs[prefix + 'TopLeftY']) - 1) + Number(OffsetYs[prefix + 'OffsetY'])) * 15 + 5; | y = (k[1] - (Number(TopLeftYs[prefix + 'TopLeftY']) - 1) + Number(OffsetYs[prefix + 'OffsetY'])) * 15 + 5; | ||
| Line 497: | Line 499: | ||
} | } | ||
| − | // | + | // internal search function. |
| − | function | + | function find_way_internal(src, dst, allowed_bits) |
{ | { | ||
// menge der bearbeiteten knoten | // menge der bearbeiteten knoten | ||
| − | // | + | // structure of the "done"-arrays: |
| − | // done["x|y"] = ( | + | // done["x|y"] = (pathtext, distance, tool-bitmask) |
var done = new Array(); | var done = new Array(); | ||
| Line 511: | Line 513: | ||
// Heimzauber wird je nach Rasse aktualisiert (hat | // Heimzauber wird je nach Rasse aktualisiert (hat | ||
// immer Index 0 im teleport-Array). | // immer Index 0 im teleport-Array). | ||
| − | edges['teleport'][0] = document.map_form.map_race.value + '| | + | edges['teleport'][0] = document.map_form.map_race.value + '|Home Spell|64'; |
for(var i = 0; i < edges["teleport"].length; i++) | for(var i = 0; i < edges["teleport"].length; i++) | ||
{ | { | ||
k = edges["teleport"][i].split("|"); | k = edges["teleport"][i].split("|"); | ||
| − | if ((k[0] + "|" + k[1]) != src && (k[3] & | + | if ((k[0] + "|" + k[1]) != src && (k[3] & allowed_bits) == k[3]) |
{ | { | ||
done[k[0] + "|" + k[1]] = new Array(k[2] + "->" + k[0] + "|" + k[1], 1.001, k[3]); | done[k[0] + "|" + k[1]] = new Array(k[2] + "->" + k[0] + "|" + k[1], 1.001, k[3]); | ||
| Line 548: | Line 550: | ||
// nachbarn des knotens finden | // nachbarn des knotens finden | ||
| − | nb = | + | nb = find_neighbours(i, allowed_bits); |
for (j = 0; j<nb.length; j++) | for (j = 0; j<nb.length; j++) | ||
{ | { | ||
| Line 554: | Line 556: | ||
ko = k[0]+"|"+k[1]; | ko = k[0]+"|"+k[1]; | ||
| − | // | + | // each neighbour, der tatsaechlich existiert, aber noch |
// nicht in der "done"-liste ist, wird mit entfernungswert, | // nicht in der "done"-liste ist, wird mit entfernungswert, | ||
// pfadbeschreibung und evtl. erweiterter tool-menge versehen | // pfadbeschreibung und evtl. erweiterter tool-menge versehen | ||
| Line 581: | Line 583: | ||
} | } | ||
| − | // sucht die nachbarn eines feldes. gibt u.u. auch | + | // sucht die nachbarn eines feldes. gibt u.u. auch nicht begehbare |
// felder (bergfelder usw.) zurueck. | // felder (bergfelder usw.) zurueck. | ||
| − | function | + | function find_neighbours(f, bits) |
{ | { | ||
| − | var k = f.split("|"), x = Array(), y = Array(), | + | var k = f.split("|"), x = Array(), y = Array(), neighbours = Array(); |
x[1] = parseInt(k[0]); | x[1] = parseInt(k[0]); | ||
x[0] = x[1] - 1; | x[0] = x[1] - 1; | ||
| Line 592: | Line 594: | ||
y[0] = y[1] - 1; | y[0] = y[1] - 1; | ||
y[2] = y[1] + 1; | y[2] = y[1] + 1; | ||
| + | |||
// die 8 umliegenden felder stupide aufnehmen | // die 8 umliegenden felder stupide aufnehmen | ||
for (var i = 0; i < 3; i++) { | for (var i = 0; i < 3; i++) { | ||
for (var j = 0; j < 3; j++) { | for (var j = 0; j < 3; j++) { | ||
| − | if ((i != 1 || j != 1) && ! | + | if ((i != 1 || j != 1) && !normal_inaccessible[x[i] + '|' + y[j]]) neighbours.push(x[i] + '|' + y[j]); |
} | } | ||
} | } | ||
| Line 608: | Line 611: | ||
if ((k[3] & bits) == k[3]) | if ((k[3] & bits) == k[3]) | ||
{ | { | ||
| − | + | neighbours.push(edges[f][i]); | |
} | } | ||
} | } | ||
} | } | ||
| − | return | + | return neighbours; |
} | } | ||
// </nowiki></pre> | // </nowiki></pre> | ||
Revision as of 14:08, 7 February 2017
// Code für den Autorouter der [[CompleteMap]]
// Original von [[Benutzer:Count Ypsilon]] (http://www.remote-island.org/101912/autoroute.html)
// Einbindung in [[MediaWiki:Common.js#CompleteMap]]
//<pre><nowiki>
var map = new Object();
// Initialization
function init_router()
{
// Füllen des assoziativen map-Arrays mit Werten aus "coordlist" per RegExp
// Zumindest FF teilt Textknoten nach 2^12 Zeichen, also alle Kindknoten aneinanderreihen
var str = '', n = document.getElementById('coordlist').firstChild;
do {
str = str + n.nodeValue;
} while (n = n.nextSibling);
areas = str.replace(/,/g, '|').split('Arealink|');
for (i in areas) {
var area = areas[i].substr(0, areas[i].indexOf('}'));
var coords = areas[i].match(/-*\d+\|-*\d+/g);
for (j in coords) map[coords[j]] = area;
}
// Anbringen der zusätzlichen Steuerelemente
var map_dest_x, map_dest_y, map_check, map_race, map_optgroup, map_option, map_radio;
map_dest_x = document.createElement('input'); map_dest_y = document.createElement('input');
map_dest_x.type = 'text'; map_dest_y.type = 'text';
map_dest_x.id = 'map_dest_x'; map_dest_y.id = 'map_dest_y';
map_dest_x.size = '3'; map_dest_y.size = '3';
map_dest_x.style.textAlign = 'right'; map_dest_y.style.textAlign = 'right';
with (document.getElementById('map_dest')) {
appendChild(document.createTextNode('X: '));
appendChild(map_dest_x);
appendChild(document.createTextNode(' Y: '));
appendChild(map_dest_y);
}
map_check = document.createElement('input');
map_check.type = 'checkbox';
// Die internen Tool-IDs den Positionen in der alphabetisch geordneten Tabelle zuordnen
var array = Array('4', '6', '3', '1', '2', '5');
var tools = document.getElementById('map_tools').getElementsByTagName('td');
for (var i = 0; i < 6; i++) {
map_check.name = 'opt' + array[i];
tools[i].insertBefore(map_check.cloneNode(false), tools[i].firstChild);
}
map_race = document.createElement('select');
map_race.name = 'map_race';
map_race.style.fontSize = 'smaller';
map_option = document.createElement('option');
map_option.appendChild(document.createTextNode(' '));
map_option.value = '82|92';
map_option.firstChild.nodeValue = 'Dark Mage';
map_race.appendChild(map_option.cloneNode(true));
with (map_optgroup = document.createElement('optgroup')) {
label = 'Human';
map_option.value = '98|102';
map_option.firstChild.nodeValue = 'Worker';
appendChild(map_option.cloneNode(true));
map_option.value = '100|100';
map_option.firstChild.nodeValue = 'Warrior';
appendChild(map_option.cloneNode(true));
map_option.value = '101|102';
map_option.firstChild.nodeValue = 'Sorcerer';
appendChild(map_option.cloneNode(true));
}
map_race.appendChild(map_optgroup);
map_option.value = '508|57';
map_option.firstChild.nodeValue = 'Natla';
map_race.appendChild(map_option.cloneNode(true));
map_option.value = '89|101';
map_option.firstChild.nodeValue = 'Onlo';
map_race.appendChild(map_option.cloneNode(true));
map_option.value = '95|108';
map_option.firstChild.nodeValue = 'Serum-Wraith';
map_race.appendChild(map_option.cloneNode(true));
map_option.value = '101|119';
map_option.firstChild.nodeValue = 'Tarunan';
map_race.appendChild(map_option.cloneNode(true));
document.getElementById('map_race').appendChild(map_race);
map_radio = document.createElement('input');
map_radio.type = 'radio';
map_radio.name = 'map_radio';
map_radio.value = 'map_';
map_radio.checked = true;
document.getElementById('map_label_start').insertBefore(map_radio.cloneNode(false), document.getElementById('map_label_start').firstChild);
map_radio.value = 'map_router_';
map_radio.checked = false;
document.getElementById('map_label_dest').insertBefore(map_radio.cloneNode(false), document.getElementById('map_label_dest').firstChild);
document.getElementById('map_label_mouse').getElementsByTagName('a')[0].href = 'javascript:switch_router_coords();';
routerloaded = true;
}
function switch_router_coords() {
var tmp = document.map_form.map_x.value;
document.map_form.map_x.value = document.map_form.map_dest_x.value;
document.map_form.map_dest_x.value = tmp;
tmp = document.map_form.map_y.value;
document.map_form.map_y.value = document.map_form.map_dest_y.value;
document.map_form.map_dest_y.value = tmp;
press_map_button();
}
// Main part
// Modified Dijkstra algorithm
//
// Um Platz zu sparen, verzichten wir auf eine explizite Graphen-Darstellung
// der Karte. Stattdessen wird eine implizite Kante zwischen allen benach-
// barten Feldern des assoziativen Arrays "map" angenommen:
//
// map["x|y"]=1
//
// Zusaetzliche Kanten stehen im assoziativen Array "edges":
//
// edges["von-x|von-y"] = Array("nach-x|nach-y|description|tools", ...)
//
// Zauberkugeln werden grundsaetzlich nur im 1. Schritt eingesetzt
//
// edges["teleport"] = Array("nach-x|nach-y|description|tools", ...)
//
// wobei "tools" ein Bitfeld ist, das die Hilfsmittel/Bedingungen
// beschreibt, um diese Kante nutzen zu koennen.
//
// Der Algorithmus wird automatisch zuerst die beste Loesung suchen und
// danach sukzessive auf eingesetzte Hilfsmittel verzichten, bis er bei
// einer reinen Fussweg-Loesung ankommt (sofern es die gibt).
var edges = {
// Portal in Reikan
"94|111" : new Array(
"90|115|Portal to Kerdis|2",
"64|80|Portal to Rovonia|2",
"122|100|Portal to Kuridan/Everchanging river|2",
"72|116|Portal to Terasi|2",
"144|126|Portal to Rock Island|2",
"121|91|Portal to Torin|2",
"122|116|Portal to Lardikia|2",
"62|83|Portal to Kolun|2",
"59|106|Portal to Krato|2",
"129|90|Portal to Brondor|2",
"115|100|Portal to Kuridan/Plains|2",
"111|83|Portal to Wilisia|2",
"135|115|Portal to Linya|2",
"58|98|Portal to Dranar|2",
"106|93|Portal to Ferdolia|2",
"110|107|Portal to Nawor|2"
),
// sonstige Teleport-Mechanismen
"teleport" : new Array(
"Homespell-Dummy - muss Index 0 besitzen!",
"87|90|Staff of Trade to the Market place|32",
"88|89|Staff of Trade to the Central Traders Depot|32",
"96|109|ZK/Nebel/Flügel nach Reikan|8",
"99|115|ZK/Nebel/Flügel nach Mentoran|8",
"98|120|Ring of the Sand Winds to Mentoran|4",
"58|107|Ring of the Sand Winds to Krato|4",
"121|112|Ring of the Sand Winds to Lardikia|4",
"-599|-489|Yellow MS to the Forest of light|16",
"96|101|Staff of Trade to the Market hall|32",
"117|113|Staff of Trade to the Market hall of Lardikia|32",
"81|94|MS/Mist/Wings to the lost valley|8",
"72|85|Ring of the Sand Winds to Urdania|4",
"87|87|Staff of Trade to the Auction Hall|32",
"501|51|MS/Mist/Wings to Narubia|8",
"98|81|Ring of the Sand Winds to Latenia|4",
"-803|-808|Yellow MS to the Ruin|16",
"103|110|MS/Mist/Wings to Nawor|8",
"101|100|MS/Mist/Wings to Konlir|8",
"65|96|Ring of the Sand Winds to Delos|4",
"80|87|MS/Mist/Wings to Buran|8",
"108|114|MS/Mist/Wings to Orewu|8",
"-798|-798|Yellow MS to the Grave|16",
"-785|-786|Yellow MS to the Sewer|16",
"75|99|MS/Mist/Wings to Kanobia|8",
"92|105|MS/Mist/Wings to the Universal Bank|8",
"123|92|Ring of the Sand Winds to Torin|4",
"100|94|MS/Mist/Wings to Ferdolia|8",
"-347|-693|Yellow MS to the Ice Cave|16",
"93|96|MS/Mist/Wings to Valley of Ruins|8",
"71|92|MS/Mist/Wings to Sutrania|8",
"66|111|MS/Mist/Wings to Terasi|8",
"85|102|MS/Mist/Wings to Anatubia|8",
"92|90|MS/Mist/Wings to Hewn|8"
),
// normale Kanten
"87|104" : new Array("-812|-810|Die Grotte betreten|0"),
"83|81" : new Array("97|116|In das Loch steigen und das Portal betreten|0",
"-312|-195|Den Ring des Vulkans in das Portal werfen|0"),
"62|95" : new Array("-288|-475|Die vergessene Kathedrale betreten|0"),
"-934|-552" : new Array("92|104|Die Diebeshöhle verlassen|0"),
"-559|-497" : new Array("88|90|Die Höhle verlassen|0"),
"-558|-497" : new Array("89|90|Die Höhle verlassen|0"),
"-568|-495" : new Array("91|90|Die Höhle verlassen|0"),
"-780|-793" : new Array("-780|-790|Nach unten gehen|0"),
"-345|-693" : new Array("98|84|Die Eishöhle verlassen|0"),
"85|97" : new Array("-10004|-10005|Die Höhle betreten|0"),
"86|97" : new Array("-10001|-10005|Die Höhle betreten|0"),
"-818|-825" : new Array("82|92|Das Verliess verlassen|0"),
"-585|-490" : new Array("90|92|Die Höhle verlassen|0"),
"-197|-396" : new Array("72|107|Dein Grab verlassen|0"),
"90|89" : new Array("-548|-497|Die Höhle betreten|0"),
"88|90" : new Array("-559|-497|Die Höhle betreten|0"),
"89|90" : new Array("-558|-497|Die Höhle betreten|0"),
"91|90" : new Array("-568|-495|Die Höhle betreten|0"),
"87|92" : new Array("-579|-497|Die Höhle betreten|0"),
"90|92" : new Array("-585|-490|Die Höhle betreten|0"),
"88|93" : new Array("-599|-498|Die Höhle betreten|0"),
"-548|-497" : new Array("90|89|Die Höhle verlassen|0"),
"-787|-790" : new Array("-758|-752|Durch den Gang nach unten gehen|0"),
"-780|-790" : new Array("-780|-793|Mit Hilfe der Holzleiter nach oben gehen|0"),
"-758|-752" : new Array("-787|-790|Durch den Gang nach oben gehen|0"),
"-500|-500" : new Array("99|103|Kathedrale verlassen|0"),
"-196|-100" : new Array("82|86|Den Keller verlassen|0"),
"-191|-98" : new Array("85|88|Den Keller verlassen|0"),
"-185|-97" : new Array("82|84|Den Keller verlassen|0"),
"-200|-93" : new Array("80|89|Den Keller verlassen|0"),
"-99|-100" : new Array("99|103|Die Treppe nach oben laufen|0"),
"-100|-95" : new Array("91|104|Die Treppe nach oben laufen|0"),
"-10001|-10011" : new Array("93|101|Den Keller verlassen|0"),
"98|102" : new Array("-790|-786|Die Kanalisation betreten|0"),
"99|103" : new Array("-99|-100|Durch die Türe nach unten in den Keller gehen|0",
"-500|-500|Kathedrale betreten|0"),
"98|104" : new Array("-100|-104|Die Gefängniszelle betreten|0"),
"-231|-369" : new Array("122|113|Auftauchen|0"),
"-230|-369" : new Array("122|113|Auftauchen|0"),
"-229|-369" : new Array("122|113|Auftauchen|0"),
"-228|-369" : new Array("122|113|Auftauchen|0"),
"-227|-369" : new Array("122|113|Auftauchen|0"),
"-226|-369" : new Array("122|113|Auftauchen|0"),
"-232|-368" : new Array("122|113|Auftauchen|0"),
"-231|-368" : new Array("122|113|Auftauchen|0"),
"-230|-368" : new Array("122|113|Auftauchen|0"),
"-229|-368" : new Array("122|113|Auftauchen|0"),
"-228|-368" : new Array("122|113|Auftauchen|0"),
"-227|-368" : new Array("122|113|Auftauchen|0"),
"-226|-368" : new Array("122|113|Auftauchen|0"),
"-225|-368" : new Array("122|113|Auftauchen|0"),
"-231|-367" : new Array("122|113|Auftauchen|0"),
"-230|-367" : new Array("122|113|Auftauchen|0"),
"-229|-367" : new Array("122|113|Auftauchen|0"),
"-228|-367" : new Array("122|113|Auftauchen|0"),
"-227|-367" : new Array("122|113|Auftauchen|0"),
"-226|-367" : new Array("122|113|Auftauchen|0"),
"-231|-366" : new Array("122|113|Auftauchen|0"),
"-230|-366" : new Array("122|113|Auftauchen|0"),
"-229|-366" : new Array("122|113|Auftauchen|0"),
"-228|-366" : new Array("122|113|Auftauchen|0"),
"-227|-366" : new Array("122|113|Auftauchen|0"),
"-226|-366" : new Array("122|113|Auftauchen|0"),
"-225|-366" : new Array("122|113|Auftauchen|0"),
"-227|-365" : new Array("122|113|Auftauchen|0"),
"-226|-365" : new Array("122|113|Auftauchen|0"),
"122|113" : new Array("-232|-368|Tauchen|0"),
"96|82" : new Array("-349|-698|Die Eishöhle betreten|0"),
"-812|-810" : new Array("87|104|Die Grotte verlassen|0"),
"111|107" : new Array("-449|-449|Durch den Felsspalt nach unten gehen|0"),
"-802|-807" : new Array("94|96|Die Ruine verlassen|0"),
"-10004|-10005" : new Array("85|97|Die Höhle verlassen|0"),
"-10001|-10005" : new Array("86|97|Die Höhle verlassen|0"),
"94|96" : new Array("-802|-807|Die Ruine betreten|0"),
"-177|-277" : new Array("122|113|Auftauchen|0"),
"-172|-277" : new Array("122|113|Auftauchen|0"),
"-177|-276" : new Array("122|113|Auftauchen|0"),
"-175|-276" : new Array("122|113|Auftauchen|0"),
"-173|-276" : new Array("122|113|Auftauchen|0"),
"-172|-276" : new Array("122|113|Auftauchen|0"),
"-171|-276" : new Array("122|113|Auftauchen|0"),
"-177|-275" : new Array("122|113|Auftauchen|0"),
"-176|-275" : new Array("122|113|Auftauchen|0"),
"-175|-275" : new Array("122|113|Auftauchen|0"),
"-173|-275" : new Array("122|113|Auftauchen|0"),
"-172|-275" : new Array("122|113|Auftauchen|0"),
"-178|-274" : new Array("122|113|Auftauchen|0"),
"-177|-274" : new Array("122|113|Auftauchen|0"),
"-175|-274" : new Array("122|113|Auftauchen|0"),
"-174|-274" : new Array("122|113|Auftauchen|0"),
"-173|-274" : new Array("122|113|Auftauchen|0"),
"-172|-274" : new Array("122|113|Auftauchen|0"),
"-171|-274" : new Array("122|113|Auftauchen|0"),
"-177|-273" : new Array("122|113|Auftauchen|0"),
"-173|-273" : new Array("122|113|Auftauchen|0"),
"-172|-273" : new Array("122|113|Auftauchen|0"),
"-178|-272" : new Array("122|113|Auftauchen|0"),
"-177|-272" : new Array("122|113|Auftauchen|0"),
"-175|-272" : new Array("122|113|Auftauchen|0"),
"-173|-272" : new Array("122|113|Auftauchen|0"),
"-172|-272" : new Array("122|113|Auftauchen|0"),
"-171|-272" : new Array("122|113|Auftauchen|0"),
"-178|-271" : new Array("122|113|Auftauchen|0"),
"-177|-271" : new Array("122|113|Auftauchen|0"),
"-176|-271" : new Array("122|113|Auftauchen|0"),
"-175|-271" : new Array("122|113|Auftauchen|0"),
"-174|-271" : new Array("122|113|Auftauchen|0"),
"-173|-271" : new Array("122|113|Auftauchen|0"),
"-178|-270" : new Array("122|113|Auftauchen|0"),
"-176|-270" : new Array("122|113|Auftauchen|0"),
"-176|-269" : new Array("122|113|Auftauchen|0"),
"-176|-268" : new Array("122|113|Auftauchen|0"),
"-594|-448" : new Array("73|99|Den unterirdischen Lichtwald verlassen|0"),
"-284|-476" : new Array("-289|-471|Die Treppe nach oben gehen|0"),
"-289|-471" : new Array("-284|-476|Die Treppe nach unten gehen|0"),
"-285|-471" : new Array("-289|-467|Die Treppe nach oben gehen|0"),
"-289|-467" : new Array("-285|-471|Die Treppe nach unten gehen|0"),
"82|92" : new Array("-818|-825|Durch die Türe nach unten in das Verliess gehen|0"),
"93|101" : new Array("-10001|-10011|In den Keller gehen|0"),
"91|104" : new Array("-100|-95|Die Treppe nach unten laufen|0"),
"92|104" : new Array("-934|-552|Die Diebeshöhle betreten|0"),
"-449|-449" : new Array("111|107|Die Höhle verlassen|0"),
"-100|-104" : new Array("98|104|Das Gefängnis verlassen|0"),
"501|57" : new Array("101|100|Katapult|0"),
"78|98" : new Array("-811|-826|Die Äste beiseite schieben|0"),
"-811|-826" : new Array("78|98|Den hohlen Baum verlassen|0"),
"79|99" : new Array("80|114|Mit der Liane durch die Lüfte schwingen|0"),
"80|114" : new Array("79|99|Mit der Liane durch die Lüfte schwingen|0"),
"-90|-90" : new Array("98|98|Die Ruhmeshalle verlassen|0"),
"98|98" : new Array("-90|-90|Die Ruhmeshalle betreten|0"),
"101|117" : new Array("-105|-95|Das Nomadenzelt betreten|0"),
"-105|-95" : new Array("-105|-95|Das Nomadenzelt verlassen|0"),
"94|90" : new Array("102|99|Vom Fluss fortgespült|0"),
"97|90" : new Array("102|99|Vom Fluss fortgespült|0"),
"90|111" : new Array("92|108|Dem Pfad in die Berge folgen|0"),
"118|106" : new Array("132|117|Dem Fährmann Geld für die Überfahrt geben|0"),
"132|117" : new Array("118|106|Dem Fährmann Geld für die Überfahrt geben|0"),
"-798|-800" : new Array("98|109|Die Grabkammer verlassen|0"),
"98|109" : new Array("-798|-800|Die Grabkammer betreten|0"),
"-288|-475" : new Array("62|95|Die vergessene Kathedrale verlassen|0")
};
// Im Array normal_unbetretbar werden Felder wie die Vulkanspitze gespeichert,
// die zwar betretbar sind, aber nur durch explizite Kanten
var normal_inaccessible = {
"87|103" : 1
};
// Namen der Hilfsmittel
var teleport_tool = {
0 : "",
1 : "Portals",
2 : "Ring of the Sand Winds",
3 : "Magic sphere/Mist/Wings",
4 : "Yellow magic sphere",
5 : "Staff of Trade",
6 : "Home Spell"
}
// Main function
function find_way()
{
while (document.getElementById('map_path').firstChild)
document.getElementById('map_path').removeChild(document.getElementById('map_path').firstChild);
var src = String(document.map_form.map_x.value) + '|' + String(document.map_form.map_y.value);
var dst = String(document.map_form.map_dest_x.value) + '|' + String(document.map_form.map_dest_y.value);
if (!map[src] || !map[dst]) {
document.getElementById('map_out_route').style.visibility = 'hidden';
return false;
}
// hier kommt ein Array von Loesungs-Strings zurueck.
try = new Array();
tools = 1;
if (document.map_form.opt1.checked) tools |= 2;
if (document.map_form.opt2.checked) tools |= 4;
if (document.map_form.opt3.checked) tools |= 8;
if (document.map_form.opt4.checked) tools |= 16;
if (document.map_form.opt5.checked) tools |= 32;
if (document.map_form.opt6.checked) tools |= 64;
solution = find_way_internal(src, dst, tools);
// die Loesungs-Strings haben die Form
// tool;length;direction
// - hieraus nun String bauen
if (!solution) string = "No optimal way found.";
else {
elements = solution.split(";");
if (elements[0] != 0) {
string = "Requires: ";
comma = 0;
for(j = 0; j < 16; j++) {
if (elements[0] & (1 << j)) {
if (comma) string += ", ";
string += teleport_tool[j];
comma = 1;
}
}
} else {
string = "Absolute foot route";
}
string += " - Length: " + Math.floor(elements[1]);
makemap(src, dst, elements[2]);
}
document.getElementById('map_out_route').firstChild.nodeValue = string;
document.getElementById('map_out_route').style.visibility = 'visible';
}
function makemap(src, dst, way)
{
makemap_point(src, "http://www.fwwiki.de/images/3/31/Red.png");
lastplot = src;
pts = way.split("->");
for(var i=0; i<pts.length; i++)
{
if (pts[i].indexOf('|') == -1) continue;
makemap_line(lastplot, pts[i], "http://www.fwwiki.de/images/9/92/Yellow.png");
makemap_point(pts[i], "http://www.fwwiki.de/images/9/92/Yellow.png");
lastplot = pts[i];
}
makemap_point(dst, "http://www.fwwiki.de/images/7/72/Green.png");
}
function makemap_line(from, to, img)
{
k = from.split("|");
if (k[0] < 0 || k[1] < 0) return;
prefix = prefixes['prefix' + map[from].replace(/\s/g, '_')] ? prefixes['prefix' + map[from].replace(/\s/g, '_')] : '';
x0 = (k[0] - (Number(TopLeftXs[prefix + 'TopLeftX']) - 1) + Number(OffsetXs[prefix + 'OffsetX'])) * 15 + 9;
y0 = (k[1] - (Number(TopLeftYs[prefix + 'TopLeftY']) - 1) + Number(OffsetYs[prefix + 'OffsetY'])) * 15 + 9;
k = to.split("|");
if (k[0] < 0 || k[1] < 0) return;
prefix = prefixes['prefix' + map[to].replace(/\s/g, '_')] ? prefixes['prefix' + map[to].replace(/\s/g, '_')] : '';
x1 = (k[0] - (Number(TopLeftXs[prefix + 'TopLeftX']) - 1) + Number(OffsetXs[prefix + 'OffsetX'])) * 15 + 9;
y1 = (k[1] - (Number(TopLeftYs[prefix + 'TopLeftY']) - 1) + Number(OffsetYs[prefix + 'OffsetY'])) * 15 + 9;
xd = Math.abs(x1-x0);
yd = Math.abs(y1-y0);
if (xd>yd)
{
// y-distance ist schleifen-master, x ist slave
if (x0>x1)
{
// swap
xt=x0; x0=x1; x1=xt;
yt=y0; y0=y1; y1=yt;
}
for(x=x0; x<x1; x++)
{
y=(y0+(y1-y0)*(x-x0)/(x1-x0));
point = document.createElement('img');
point.src = img;
point.style.position = 'absolute';
point.style.left = String(x) + 'px';
point.style.top = String(y) + 'px';
point.style.width = '1px';
point.style.height = '1px';
document.getElementById('map_path').appendChild(point);
}
} else {
// x-entfernung ist schleifen-master, y ist slave
if (y0>y1)
{
// swap
xt=x0; x0=x1; x1=xt;
yt=y0; y0=y1; y1=yt;
}
for(y=y0; y<y1; y++)
{
x=(x0+(x1-x0)*(y-y0)/(y1-y0));
point = document.createElement('img');
point.src = img;
point.style.position = 'absolute';
point.style.left = String(x) + 'px';
point.style.top = String(y) + 'px';
point.style.width = '1px';
point.style.height = '1px';
document.getElementById('map_path').appendChild(point);
}
}
}
function makemap_point(coord, img)
{
k = coord.split("|");
if (k[0] < 0 || k[1] < 0) return;
prefix = prefixes['prefix' + map[coord].replace(/\s/g, '_')] ? prefixes['prefix' + map[coord].replace(/\s/g, '_')] : '';
x = (k[0] - (Number(TopLeftXs[prefix + 'TopLeftX']) - 1) + Number(OffsetXs[prefix + 'OffsetX'])) * 15 + 5;
y = (k[1] - (Number(TopLeftYs[prefix + 'TopLeftY']) - 1) + Number(OffsetYs[prefix + 'OffsetY'])) * 15 + 5;
point = document.createElement('img');
point.src = img;
point.style.position = 'absolute';
point.style.left = String(x) + 'px';
point.style.top = String(y) + 'px';
point.style.width = '9px';
point.style.height = '9px';
document.getElementById('map_path').appendChild(point);
}
// internal search function.
function find_way_internal(src, dst, allowed_bits)
{
// menge der bearbeiteten knoten
// structure of the "done"-arrays:
// done["x|y"] = (pathtext, distance, tool-bitmask)
var done = new Array();
// mit startfeld initialisieren
done[src] = new Array("Start", 0, 0);
// alle teleport-felder hinzufuegen, sofern erlaubt.
// Heimzauber wird je nach Rasse aktualisiert (hat
// immer Index 0 im teleport-Array).
edges['teleport'][0] = document.map_form.map_race.value + '|Home Spell|64';
for(var i = 0; i < edges["teleport"].length; i++)
{
k = edges["teleport"][i].split("|");
if ((k[0] + "|" + k[1]) != src && (k[3] & allowed_bits) == k[3])
{
done[k[0] + "|" + k[1]] = new Array(k[2] + "->" + k[0] + "|" + k[1], 1.001, k[3]);
}
}
// alle bearbeiteten knoten zum scannen vormerken
// (scannen = verfolgen aller kanten vom knoten aus)
var numscan = 0;
var scan = new Array();
for (var i in done)
{
scan[i] = 1;
numscan++;
}
var current;
// der eigentliche dijkstra-loop
while(numscan)
{
// array fuer neue zu scannende knoten vorbereiten
newscan = new Array();
numscan = 0;
// alle zum scannen vorgemerkten knoten bearbeiten
for (var i in scan)
{
current = done[i];
currentk = i.split("|");
// wenn am ziel: fertig
if (i == dst) break;
// nachbarn des knotens finden
nb = find_neighbours(i, allowed_bits);
for (j = 0; j<nb.length; j++)
{
k = nb[j].split("|");
ko = k[0]+"|"+k[1];
// each neighbour, der tatsaechlich existiert, aber noch
// nicht in der "done"-liste ist, wird mit entfernungswert,
// pfadbeschreibung und evtl. erweiterter tool-menge versehen
// und zum scannen vorgemerkt
l = current[1] + (currentk[0] != k[0] && currentk[1] != k[1] ? 1.001 : 1);
if (map[ko] && (!done[ko] || done[ko][1] > l))
{
path = current[0]+"->";
if (k[2]) path += k[2]+"->";
path += ko;
done[ko] = new Array(path, l, current[2]|k[3]);
newscan[ko] = 1;
numscan++;
}
}
}
if (i == dst) break;
// scan-liste abgearbeitet; durch neue ersetzen
// (falls neue liste leer, endet die while-schleife ohne ergebnis)
scan = newscan;
}
// ziel erreicht?
if (i == dst) return current[2] + ";" + current[1] + ";"+current[0];
return false;
}
// sucht die nachbarn eines feldes. gibt u.u. auch nicht begehbare
// felder (bergfelder usw.) zurueck.
function find_neighbours(f, bits)
{
var k = f.split("|"), x = Array(), y = Array(), neighbours = Array();
x[1] = parseInt(k[0]);
x[0] = x[1] - 1;
x[2] = x[1] + 1;
y[1] = parseInt(k[1]);
y[0] = y[1] - 1;
y[2] = y[1] + 1;
// die 8 umliegenden felder stupide aufnehmen
for (var i = 0; i < 3; i++) {
for (var j = 0; j < 3; j++) {
if ((i != 1 || j != 1) && !normal_inaccessible[x[i] + '|' + y[j]]) neighbours.push(x[i] + '|' + y[j]);
}
}
// falls zusatzkanten definiert und lt. bitmaske erlaubt,
// diese mit aufnehmen.
if (edges[f])
{
for (var i = 0; i < edges[f].length; i++)
{
k = edges[f][i].split("|");
if ((k[3] & bits) == k[3])
{
neighbours.push(edges[f][i]);
}
}
}
return neighbours;
}
// </nowiki></pre>
