Autorouter.css

From FreewarWiki
Revision as of 01:21, 26 January 2017 by Istrugar (talk | contribs)

Jump to: navigation, search
// 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
//
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);
  areas = str.replace(/,/g, '|').split('Arealink|');
  for (i in areas) {
    var areas = 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(
           "Heimzauber-Dummy - muss Index 0 besitzen!",
           "87|90|Stab des Handels zum Marktplatz|32",
           "88|89|Stab des Handels zum Zentrallager|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 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",
           "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"
           ),

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

//