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