Category
You're no bot and a page you've created got automatically deleted? Add your name to FreewarWiki:NoSpamUser |
Autorouter.css
From FreewarWiki
// 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; } //