MediaWiki:Autorouter.js: Unterschied zwischen den Versionen

Aktuelle Version vom 19. September 2017, 20:57 Uhr

 // Code für den Autorouter der [[Gesamtkarte]]
 // Original von [[Benutzer:Count Ypsilon]] (http://www.remote-island.org/101912/autoroute.html)
 // Einbindung in [[MediaWiki:Common.js#Gesamtkarte]]
//<pre><nowiki>
var map = new Object();

// Initialisieren
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);
  gebiete = str.replace(/,/g, '|').split('Gebietslink|');
  for (i in gebiete) {
    var gebiet = gebiete[i].substr(0, gebiete[i].indexOf('}'));
    var coords = gebiete[i].match(/-*\d+\|-*\d+/g);
    for (j in coords) map[coords[j]] = gebiet;
  }

  // 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 = '4';				map_dest_y.size = '4';
  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 anordnung = Array(7, 4, 1, 6, 3, 9, 2, 5, 8 );
  var tools = document.getElementById('map_tools').getElementsByTagName('td');
  for (var i = 0; i < anordnung.length; i++) {
    map_check.name = 'opt' + anordnung[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 = 'Dunkler Magier';
  map_race.appendChild(map_option.cloneNode(true));
  with (map_optgroup = document.createElement('optgroup')) {
    label = 'Mensch';
    map_option.value = '98|102';
    map_option.firstChild.nodeValue = 'Arbeiter';
    appendChild(map_option.cloneNode(true));
    map_option.value = '100|100';
    map_option.firstChild.nodeValue = 'Kämpfer';
    appendChild(map_option.cloneNode(true));
    map_option.value = '101|102';
    map_option.firstChild.nodeValue = 'Zauberer';
    appendChild(map_option.cloneNode(true));
  }
  map_race.appendChild(map_optgroup);
  map_option.value = '508|57';
  map_option.firstChild.nodeValue = 'Natla/Händler';
  map_race.appendChild(map_option.cloneNode(true));
  map_option.value = '89|101';
  map_option.firstChild.nodeValue = 'Onlo';
  map_option.dataset.edges = JSON.stringify({
    "103|89" : new Array("108|89|Dich auf eine platzende Gasblase werfen|0"),
    "105|91" : new Array("103|89|Dich im Moor treiben lassen|0"),
    "108|89" : new Array("105|91|Dem Pfad folgen|0"),
    "122|95" : new Array("122|99|Dich von den Fäden hochziehen lassen|0"),
    "59|84" : new Array("59|90|Dich der Führung des jungen Onlos anvertrauen|0"),
    "59|90" : new Array("59|84|Dem alten Onlo folgen|0|"),
    "60|88" : new Array("61|90|Einen Weg durch die Pflanzen zwischen den Bäumen im Osten suchen|0"),
    "50|91" : new Array("50|98|In die Dunkelheit des Waldes verschwinden|0"),
    "51|108" : new Array("50|105|Durch die Luke hindurch gehen|0"),
    "50|105" : new Array("51|108|Den Durchgang betreten|0")
  });
  map_race.appendChild(map_option.cloneNode(true));
  map_option.value = '95|108';
  map_option.firstChild.nodeValue = 'Serum-Geist';
  map_race.appendChild(map_option.cloneNode(true));
  map_option.value = '101|119';
  map_option.firstChild.nodeValue = 'Taruner';
  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();
}

// Hauptteil
// Modifizierter Dijkstra-Algorithmus
//
// 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|beschreibung|tools", ...)
//
// Zauberkugeln werden grundsaetzlich nur im 1. Schritt eingesetzt
//
// edges["teleport"] = Array("nach-x|nach-y|beschreibung|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 nach Kerdis|2",
           "64|80|Portal nach Rovonia|2",
           "54|76|Portal nach Laree|2",
           "122|100|Portal nach Kuridan/Wandelfluss|2",
           "72|116|Portal nach Terasi|2",
           "144|126|Portal zur Felseninsel|2",
           "121|91|Portal nach Torihn|2",
           "122|116|Portal nach Lardikia|2",
           "62|83|Portal nach Kolun|2",
           "59|106|Portal nach Krato|2",
           "129|90|Portal nach Brondor|2",
           "115|100|Portal nach Kuridan/Prärie|2",
           "111|83|Portal nach Wilisien|2",
           "135|115|Portal nach Linya|2",
           "58|98|Portal nach Dranar|2",
           "106|93|Portal nach Ferdolien|2",
           "110|107|Portal nach Nawor|2",
           "118|124|Portal nach Dorea|2",
           "96|78|Portal nach Ragnur|2"
           ),

  // sonstige Teleport-Mechanismen
  "teleport" : new Array(
           "Heimzauber-Dummy - muss Index 0 besitzen!",
           "87|90|Stab des Handels zum Marktplatz|32",
           "88|89|Stab des Handels zum Zentrallager|32",
           "97|108|ZK/Nebel/Flügel nach Reikan|8",
           "99|115|ZK/Nebel/Flügel nach Mentoran|8",
           "98|120|Ring des Sandwindes nach Mentoran|4",
           "58|107|Ring des Sandwindes nach Krato|4",
           "121|112|Ring des Sandwindes nach Lardikia|4",
           "-599|-489|gelbe ZK zum Lichtwald|16",
           "96|101|Stab des Handels zur Markthalle|32",
           "117|113|Stab des Handels zur Markthalle von Lardikia|32",
           "81|94|ZK/Nebel/Flügel zum vergessenen Tal|8",
           "72|85|Ring des Sandwindes nach Urdanien|4",
           "87|87|Stab des Handels zur Auktionshalle|32",
           "501|51|ZK/Nebel/Flügel nach Narubia|8",
           "98|81|Ring des Sandwindes nach Latenia|4",
           "-803|-808|gelbe ZK zur Ruine|16",
           "103|110|ZK/Nebel/Flügel nach Nawor|8",
           "101|100|ZK/Nebel/Flügel nach Konlir|8",
           "65|96|Ring des Sandwindes nach Delos|4",
           "100|135|Ring des Sandwindes nach Salthos|4",
           "45|98|Ring des Sandwindes nach Tirachli|4",
           "80|75|Ring des Sandwindes zum Steinrutsch|4",
           "58|74|Ring des Sandwindes nach Venost|4",
           "147|121|Ring des Sandwindes zur Kreideinsel|4",
           "80|87|ZK/Nebel/Flügel nach Buran|8",
           "108|114|ZK/Nebel/Flügel nach Orewu|8",
           "-798|-798|gelbe ZK zum Grab|16",
           "-785|-786|gelbe ZK zur Kanalisation|16",
           "75|99|ZK/Nebel/Flügel nach Kanobien|8",
           "92|105|ZK/Nebel/Flügel zur Bank|8",
           "123|92|Ring des Sandwindes nach Torihn|4",
           "100|94|ZK/Nebel/Flügel nach Ferdolien|8",
           "-347|-693|gelbe ZK zur Eishöhle|16",
           "93|96|ZK/Nebel/Flügel zum Tal der Ruinen|8",
           "71|92|ZK/Nebel/Flügel nach Sutranien|8",
           "66|111|ZK/Nebel/Flügel nach Terasi|8",
           "85|102|ZK/Nebel/Flügel nach Anatubien|8",
           "92|90|ZK/Nebel/Flügel nach Hewien|8",
           "114|76|ZK/Nebel/Flügel nach Lodradon|8",
           "1005|1005|Auf die gefrorene Insel|128",
           "90|115|Portal nach Kerdis|256",
           "64|80|Portal nach Rovonia|256",
           "122|100|Portal nach Kuridan/Wandelfluss|256",
           "72|116|Portal nach Terasi|256",
           "144|126|Portal zur Felseninsel|256",
           "121|91|Portal nach Torihn|256",
           "122|116|Portal nach Lardikia|256",
           "62|83|Portal nach Kolun|256",
           "59|106|Portal nach Krato|256",
           "129|90|Portal nach Brondor|256",
           "115|100|Portal nach Kuridan/Prärie|256",
           "111|83|Portal nach Wilisien|256",
           "135|115|Portal nach Linya|256",
           "58|98|Portal nach Dranar|256",
           "106|93|Portal nach Ferdolien|256",
           "110|107|Portal nach Nawor|256",
           "118|124|Portal nach Dorea|256",
           "96|78|Portal nach Ragnur|256",
           "-605|-206|Portal nach Bernsteinhöhle|256",
           "-100|-95|Portal nach Keller der Post|256",
           "-286|-479|Portal nach vergessene Kathedrale (Ebene 1)|256",
           "-827|-919|Portal nach Grotte des Todes|256"
           ),

  // normale Kanten
  "108|96": new Array("105|100|Vom Geist der Wiese teleportieren lassen|1"),
  "112|97": new Array("105|100|Vom Geist der Wiese teleportieren lassen|1"),
  "113|99": new Array("105|100|Vom Geist der Wiese teleportieren lassen|1"),

  "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"),
  "90|88"      : new Array("-1298|-1399|Kampfgebiet betreten|0"),
  "92|92"      : new Array("-1294|-1393|Kampfgebiet betreten|0"),
  "-1298|-1399": new Array("90|88|Kampfgebiet verlassen|0"),
  "-1294|-1393": new Array("92|92|Kampfgebiet verlassen|0"),
  "80|75"      : new Array("87|76|Seilbahn benutzen|0"),
	"87|76"      : new Array("80|75|Seilbahn benutzen|0")
};

// Im Array normal_unbetretbar werden Felder wie die Vulkanspitze gespeichert,
// die zwar betretbar sind, aber nur durch explizite Kanten
var normal_unbetretbar = {
  "87|103"    : 1
};

// Namen der Hilfsmittel 
var teleport_mittel = {
    0 : "",
    1 : "Portale",
    2 : "Ring des Sandwindes",
    3 : "Zauberkugel/Nebel/Flügel",
    4 : "gelbe Zauberkugel",
    5 : "Stab des Handels",
    6 : "Heimzauber",
    7 : "eisiger Teleporter",
    8 : "Portalmaschine",
    9 : "Fliegen"
}

// Hauptfunktion

function finde_weg()
{
    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.

    probiert = 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;
    if (document.map_form.opt7.checked) tools |= 128;
    if (document.map_form.opt8.checked) tools |= 256;

    loesung = finde_weg_internal(src, dst, tools);

    // die Loesungs-Strings haben die Form
    // hilfsmittel;laenge;wegbeschreibung
    // - hieraus nun String bauen
    if (!loesung) string = "Kein optimaler Weg gefunden.";
    else {
        elements = loesung.split(";");
        if (elements[0] != 0) {
            string = "Erfordert: ";
            komma = 0;
            for(j = 0; j < 16; j++) {
                if (elements[0] & (1 << j)) {
                    if (komma) string += ", ";
                    string += teleport_mittel[j];
                    komma = 1;
                }
            }
        } else {
            string = "Reiner Fußweg";
        }
        string += " - Länge: " + 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, weg)
{
    makemap_point(src, "http://www.fwwiki.de/images/3/31/Red.png");
    lastplot = src;
    pts = weg.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-entfernung ist schleifen-master, x ist slave
        if (x0>x1) 
        {
            // tauschen
            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';
point.style.pointerEvents = 'none';
            document.getElementById('map_path').appendChild(point);
        }
    } else {
        // x-entfernung ist schleifen-master, y ist slave
        if (y0>y1) 
        {
            // tauschen
            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';
point.style.pointerEvents = 'none';
            document.getElementById('map_path').appendChild(point);
        }
    }
}


function makemap_point(koord, img)
{
    k = koord.split("|");
    if (k[0] < 0 || k[1] < 0) return;
    prefix = prefixes['prefix' + map[koord].replace(/\s/g, '_')] ? prefixes['prefix' + map[koord].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';
point.style.pointerEvents = 'none';
    document.getElementById('map_path').appendChild(point);
}

// interne Suchfunktion.
function finde_weg_internal(src, dst, erlaubte_bits)
{
    // menge der bearbeiteten knoten
    // struktur des "done"-arrays:
    // done["x|y"] = (pfadtext, entfernung, tool-bitmask)
    var done = new Array();

    // mit startfeld initialisieren
    done[src] = new Array("Start", 0, 0);

    // Heimzauber wird je nach Rasse aktualisiert (hat
    // immer Index 0 im teleport-Array).
    edges['teleport'][0] = document.map_form.map_race.value + '|Heimzauber|64';

    // rassenspezifische Passagen einfügen
    var race_edges = document.map_form.map_race.options[document.map_form.map_race.selectedIndex].dataset.edges;
    race_edges = race_edges && JSON.parse(race_edges)
    if (race_edges) {
        for (var race_edge in race_edges) {
            edges[race_edge] = race_edges[race_edge];
        }
    }

    // Suchradius auf 2 erweitern für Fliegen
    var search_radius = document.map_form.opt9.checked ? 2 : 1;

    // alle teleport-felder hinzufügen, sofern erlaubt.
    for(var i = 0; i < edges["teleport"].length; i++)
    {
        k = edges["teleport"][i].split("|");
        if ((k[0] + "|" + k[1]) != src && (k[3] & erlaubte_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 = finde_nachbarn(i, erlaubte_bits, search_radius);
            for (j = 0; j<nb.length; j++)
            {
                k = nb[j].split("|");
                ko = k[0]+"|"+k[1];

                // jeder nachbar, 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;
    }

    // rassenspezifische Passagen wieder entfernen nach Suche
    if (race_edges) {
        for (var race_edge in race_edges) {
            delete edges[race_edge];
        }
    }

    // ziel erreicht?
    if (i == dst) return current[2] + ";" + current[1] + ";" + current[0];
    return false;
}

// sucht die nachbarn eines feldes. gibt u.u. auch nichtbegehbare
// felder (bergfelder usw.) zurueck.
function finde_nachbarn(f, bits, radius)
{
    var k = f.split("|"), nachbarn = Array();
    var x = parseInt(k[0]), y = parseInt(k[1]);

    // die umliegenden felder stupide aufnehmen
    for (var i = -radius; i <= radius; i++) {
      for (var j = -radius; j <= radius; j++) {
        if ((i != 0 || j != 0) && (!normal_unbetretbar[(x + i) + '|' + (y + j)] || radius == 2)) nachbarn.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]) 
            {
                nachbarn.push(edges[f][i]);
            }
        }
    }

    return nachbarn;
}

// </nowiki></pre>