MediaWiki:Autorouter.js: Unterschied zwischen den Versionen

aus Chaos FreewarWiki, der Referenz für Freewar
Zur Navigation springen Zur Suche springen
(Verbesserungsversuch)
(Klappt nicht, hab grade keine Zeit zum Debuggen, also vorerst revert)
Zeile 331: Zeile 331:
   "98|109"    : new Array("-798|-800|Die Grabkammer betreten|0"),
   "98|109"    : new Array("-798|-800|Die Grabkammer betreten|0"),
   "-288|-475" : new Array("62|95|Die vergessene Kathedrale verlassen|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_unbetretbar = {
  "87|103"    : 1
};
};


Zeile 576: Zeile 570:
function finde_nachbarn(f, bits)
function finde_nachbarn(f, bits)
{
{
     var k = f.split("|"), x = Array(), y = Array(), nachbarn = Array();
     var k = f.split("|");
     x[1] = parseInt(k[0]);
     var x1=parseInt(k[0]);
     x[0] = x[1] - 1;
     var x0=x1-1;
     x[2] = x[1] + 1;
     var x2=x1+1;
     y[1] = parseInt(k[1]);
     var y1=parseInt(k[1]);
     y[0] = y[1] - 1;
     var y0=y1-1;
     y[2] = y[1] + 1;
     var y2=y1+1;
     // die 8 umliegenden felder stupide aufnehmen
     // die 8 umliegenden felder stupide aufnehmen
     for (var i = 0; i < 2; i++) {
     nachbarn = new Array(
      for (var j = 0; j < 2; j++) {
        x0+"|"+y0, x1+"|"+y0, x2+"|"+y0,
         if (!normal_unbetretbar[x[i] + '|' + y[j]]) nachbarn.push(x[i] + '|' + y[j]);
        x0+"|"+y1, x2+"|"+y1,
      }
         x0+"|"+y2, x1+"|"+y2, x2+"|"+y2);
    }


     // falls zusatzkanten definiert und lt. bitmaske erlaubt,
     // falls zusatzkanten definiert und lt. bitmaske erlaubt,

Version vom 23. Januar 2007, 21:52 Uhr

// <pre>
// 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]]<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 = '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 anordnung = 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' + 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_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",
           "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"
           ),

  // sonstige Teleport-Mechanismen
  "teleport" : new Array(
           "Heimzauber-Dummy - muss index 0 besitzen!",
           "87|90|Stab des Handels zum Marktplatz|32",
           "96|109|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 zurMarkthalle|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 Natubia|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",
           "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"
           ),

  // 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")
};

// 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"
}

// 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;
    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: " + 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';
            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';
            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';
    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);

    // alle teleport-felder hinzufuegen, sofern erlaubt
    for(var i=0; i<edges["teleport"].length; i++)
    {
        k = edges["teleport"][i].split("|");
        if ((k[3] & erlaubte_bits) == k[3])
        {
            done[k[0]+"|"+k[1]] = new Array(k[2]+"->"+k[0]+"|"+k[1], 1, 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];
            // wenn am ziel: fertig
            if (i == dst) break;

            // nachbarn des knotens finden 
            nb = finde_nachbarn(i, erlaubte_bits);
            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
                if (map[ko] && !done[ko])
                {
                    path = current[0]+"->";
                    if (k[2]) path += k[2]+"->";
                    path += ko;
                    done[ko] = new Array(path, current[1] + 1, 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 nichtbegehbare
// felder (bergfelder usw.) zurueck.
function finde_nachbarn(f, bits)
{
    var k = f.split("|");
    var x1=parseInt(k[0]);
    var x0=x1-1;
    var x2=x1+1;
    var y1=parseInt(k[1]);
    var y0=y1-1;
    var y2=y1+1;
    // die 8 umliegenden felder stupide aufnehmen
    nachbarn = new Array(
        x0+"|"+y0, x1+"|"+y0, x2+"|"+y0,
        x0+"|"+y1, x2+"|"+y1, 
        x0+"|"+y2, x1+"|"+y2, x2+"|"+y2);

    // falls zusatzkanten definiert und lt. bitmaske erlaubt,
    // diese mit aufnehmen. Heimzauber wird je nach Rasse
    // aktualisiert (hat immer Index 0 im teleport-Array)
    edges['teleport'][0] = document.map_form.map_race.value + '|Heimzauber|64';
    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>
Abgerufen von „https://cf.fwwiki.de/index.php?title=MediaWiki:Autorouter.js&oldid=88394“