EURoute
Aus EU2Wiki
EURoute ist ein Programm zur Berechnung von Routen anhand einer Datenbank mit bekannten Wurmlöchern. Als Ergebnis wird immer die schnellste Route in Abhängigkeit der Anzahl der zu nutzenden Wurmlöcher ausgegeben.
Inhaltsverzeichnis |
Features
- Bis zu 10 Sprünge (Hops)
- Berechnung der besten Route nach der reellen Flugzeit mit konfigurierbaren Antriebswerten
- Anzeige von Entfernung, Flugzeit und Wasserstoffverbrauch für die berechneten Routen
- Ergebnis wird nicht durch Optimierungen wie Suchradiuseinschränkung verschlechtert
- optionale Berücksichtigung des Sichtradius der Kommunikationszentrale
- Bookmarks (z.B. home für den HP)
- Verschiedene Flotten konfigurierbar
- SMP-Unterstützung (Multicore/-cpu Systeme)
Beispiel
EURoute Version 1.2.2 (c) escapeFTW 2007 Startkoordinaten: test Zielkoordinaten: 1234-56-78-90 Flotte [0=war,1=tr]: 1 Start: 5526-70-68-62 Ziel: 1234-56-78-90 884 / 884 Routen berechnet. -- 0 Hop(s) Flugzeit: 188.57 min Distanz: 43.74 pc 32.86 ae Verbrauch: 123386.17 H2 -- 1 Hop(s) Flugzeit: 37.28 min Distanz: 7.63 pc 109.74 ae Verbrauch: 24449.02 H2 WL-Route: <5227-29-40-5=1632-81-99-80> -- 2 Hop(s) Flugzeit: 34.13 min Distanz: 6.06 pc 190.63 ae Verbrauch: 22318.20 H2 WL-Route: <5424-14-89-84=5566-50-35-70> <5466-9-99-96=1432-93-50-86> Time: 183 ms
Changelog
Version 1.2.2
- Bugfix: Fortschrittsanzeige wurde u.U. nicht aktualisiert
Version 1.2.1
- Bugfix: Thread Error
Version 1.2.0
- Unterstützung von mehrere Flotten mit eigener Geschwindigkeitskonfiguration
- Fortschrittsanzeige während der Berechnung
- Routenberechnung beschleunigt
Version 1.1.0
- Routenberechnung um 80% beschleunigt
- Anzeige von Entfernung und Wasserstoffverbrauch
Version 1.0.1
- Bugfix: Letztes Wurmloch in der Datenbank wurde ignoriert
Installation
Einfach mit 7-Zip in einen beliebigen Ordner entpacken.
Konfiguration
Sämtliche Konfigurationsoptionen werden in der config.cfg festgelegt. Groß-/Kleinschreibung wird ignoriert.
Für die Koordinaten sind folgende Formate zulässig:
- 1234-56-78-90
- 1234:56:78:90
- 34:13:56:78:90
- 1234 (Galanummer)
- 34:13 (X-Y-Koordinaten im Universum)
- Bookmarks
InitThreadCount
Legt die Anzahl der für die 1. Berechnungsphase verwendeten Threads fest.
Empfohlene Werte: 2 (Singlecore) und darüber entsprechend der Anzahl der logischen CPU-Kerne.
WorkerThreadCount
Legt die Anzahl der für die 2. Berechnungsphase verwendeten Threads fest.
Empfohlene Werte: 1 (Singlecore) und darüber entsprechend der Anzahl der logischen CPU-Kerne.
MaxHops
Legt die Anzahl der Maximal verwendeten Wurmloch-Sprünge fest. Dieser Wert beeinflusst die Berechnungszeit vergleichsweise stark und ist künstlich auf 10 begrenzt.
UseKomzeLimit
0: Kommunikationszentrale wird nicht berücksichtigt
1: Kommunikationszentrale wird berücksichtigt
KomzeKoords
Gibt die Koordinaten der am weitesten ausgebauten Kommunikationszentrale an. Hier ist lediglich die Galanummer notwendig.
KomzeRadius
Hier wird der Radius der unter KomzeKoords angegebenen Kommunikationszentrale festgelegt. Der Radius entspricht der Ausbaustufe*10
AddMinutesPerHop
Legt die pro Sprung zu addierenden Minuten fest um Reaktionszeit und nicht exakt auf dem Tick liegende Flugzeiten zu kompensieren
Bookmark
Hier können Bookmarks im Format bookmark=NAME=KOORDINATEN angegeben werden. In EURoute muss dann nur noch NAME für die betreffenden Koordinaten eingegeben werden.
Fleet
Hier werden die Werte für die einzelnen Flotten im Format fleet=NAME=VARIABLE=WERT eingetragen.
Mögliche Variablen:
WarpSpeed
Gibt die Warpgeschwindigkeit der Schiffe an
Beispiel: fleet=Frachtflotte=WarpSpeed=8000
ImpulseSpeed
Gibt die Impulsgeschwindigkeit der Schiffe an
Beispiel: fleet=Frachtflotte=ImpulseSpeed=200
FuelConsumption
Gibt den Wasserstoffverbrauch der Flotte an (Einzelverbrauch der Antriebe addieren)
Beispiel: fleet=Frachtflotte=FuelConsumption=1.5
FlightTimeModifier
Korrigiert die Flugzeit bei Bedarf bei Abweichungen durch Spielertitel oder Kommandanten
Beispiel: fleet=Frachtflotte=FlightTimeModifier=1.0
Erstellen der Wurmlochdatenbank
Um Wurmlöcher für das von EURoute nutzbare Format zu speichern müssen diese zunächst in die wl.txt eingefügt werden. Dazu wird in jede Zeile ein Koordinatenpaar (Start und Ziel des Wurmlochs) durch , (Komma) getrennt kopiert. Die Anwendung wldatgen.exe erzeugt damit die binäre wl.dat, die von EURoute verwendet wird. Es ist zu beachten, dass von Samstag auf Sonntag 50% der Wurmlöcher neu gesetzt werden.
Herunterladen
http://www.player.to/projects/euroute/
Sourcecode
import std.perf;
import std.math;
import std.file;
import std.stream;
import std.cstream : din, dout;
import std.c.stdlib : system;
import std.string;
import std.conv;
import std.stdio;
import std.thread;
import std.c.time : msleep;
const char[] NAME = "EURoute Version 1.2.2 (c) escapeFTW 2007";
const ushort HOPLIMIT = 10;
struct koords {
ubyte x;
ubyte y;
ubyte gx;
ubyte gy;
ubyte gz;
}
struct wurmloch {
ushort id;
koords a;
koords b;
}
struct wlext {
double a_to;
double b_to;
}
struct route {
koords[HOPLIMIT*2] path;
uint pathLength;
double time;
}
struct fleetInfo {
char[] name = "default";
uint WarpSpeed = 8000;
uint ImpulseSpeed = 200;
double FuelConsumption = 1.8;
double FlightTimeModifier = 1;
}
/*
Datenbank
*/
wurmloch[] wlarr;
wlext[] wlearr;
/*
Configvariablen
*/
uint initThreadCount = 2;
uint workerThreadCount = 1;
uint MaxHops = 3;
bool UseKomzeLimit = false;
koords KomzeKoords;
uint KomzeRadius;
double AddMinutesPerHop = 0.5;
fleetInfo[] fleet;
uint fleetID = 0;
char[][char[]] bookmark;
/*
Eingabe
*/
koords from, to;
/*
Berechnung
*/
double[] minTime;
koords[][] minPath;
RouteBalancer rb;
bool calculationRunning;
int main(char[][] args) {
readConfig();
if (MaxHops > HOPLIMIT) MaxHops = HOPLIMIT;
writefln(NAME);
writef("Startkoordinaten: ");
from = parseKoords(din.readLine());
writef(" Zielkoordinaten: ");
to = parseKoords(din.readLine());
writef("Flotte [");
for (uint i=0; i<fleet.length; i++) {
if (i != 0) writef(",");
writef(i,"=",fleet[i].name);
}
writef("]: ");
char[] fleetsel = strip(din.readLine());
if (fleetsel.length == 0) {
fleetID = 0;
} else if (countchars(fleetsel, "0-9") == fleetsel.length) {
fleetID = toUint(fleetsel);
} else {
for (uint i=0; i<fleet.length; i++) {
if (fleet[i].name == fleetsel) {
fleetID = i;
}
}
}
readDatabase();
HighPerformanceCounter hpc = new HighPerformanceCounter();
hpc.start();
if (UseKomzeLimit && ceil(pcDistance(to, KomzeKoords)) > KomzeRadius) {
writefln("Achtung! Zielkoordinaten nicht in Reichweite der Kommunikationszentrale.");
}
writefln("");
writefln("Start: %d-%d-%d-%d", (from.y-1)*100+from.x, from.gx, from.gy, from.gz);
writefln(" Ziel: %d-%d-%d-%d", (to.y-1)*100+to.x, to.gx, to.gy, to.gz);
writefln("");
minTime.length = minPath.length = MaxHops+1;
minTime[0] = timeDistance(from, to);
minPath[0] = null;
for (uint j=1; j<=MaxHops; j++) {
minTime[j] = minTime[0];
minPath[j] = null;
}
runThreads();
writefln("");
writefln("");
double lastTime = minTime[0] + 1;
for (uint hops=0; hops<=MaxHops; hops++) {
if (minTime[hops] < lastTime) {
lastTime = minTime[hops];
writefln("-- %d Hop(s)", hops);
writefln(" Flugzeit: %.2f min", minTime[hops]);
if (minPath[hops] != null) {
double pcD = 0, aeD = 0;
koords at = from;
for (uint j=0; j<minPath[hops].length; j+=2) {
pcD+= pcDistance(at, minPath[hops][j]);
aeD+= aeDistance(at, minPath[hops][j]);
at = minPath[hops][j+1];
}
pcD+= pcDistance(at, to);
aeD+= aeDistance(at, to);
writefln(" Distanz: %.2f pc %.2f ae", pcD, aeD);
writefln("Verbrauch: %.2f H2", (pcD + aeD/100) * 100 * fleet[fleetID].FuelConsumption);
dumpMinPath(hops);
} else {
double pcD = pcDistance(from, to);
double aeD = aeDistance(from, to);
writefln(" Distanz: %.2f pc %.2f ae", pcD, aeD);
writefln("Verbrauch: %.2f H2", (pcD + aeD/100) * 100 * fleet[fleetID].FuelConsumption);
}
writefln("");
}
}
hpc.stop();
writefln("Time: ", hpc.milliseconds(), " ms");
system("pause");
return 0;
}
void readConfig() {
char[] buffer;
char[][] tmp;
File f = new File("config.cfg");
while (!f.eof()) {
buffer = f.readLine();
tmp = split(buffer, "=");
if (tmp.length >= 2) {
tmp[1] = strip(tmp[1]);
switch (capwords(tmp[0])) {
case "Initthreadcount":
initThreadCount = toUint(tmp[1]);
break;
case "Workerthreadcount":
workerThreadCount = toUint(tmp[1]);
break;
case "Maxhops":
MaxHops = toUint(tmp[1]);
break;
case "Usekomzelimit":
if (tmp[1] == "1") {
UseKomzeLimit = true;
} else {
UseKomzeLimit = false;
}
break;
case "Komzekoords":
KomzeKoords = parseKoords(tmp[1]);
break;
case "Komzeradius":
KomzeRadius = toUint(tmp[1]);
break;
case "Addminutesperhop":
AddMinutesPerHop = toDouble(tmp[1]);
break;
case "Fleet":
if (tmp.length == 4) {
char[] name = strip(tmp[1]);
int fid = -1;
for (uint i=0; i<fleet.length; i++) {
if (fleet[i].name == name) {
fid = i;
break;
}
}
if (fid == -1) {
fid = fleet.length;
fleet.length = fleet.length + 1;
fleet[fid].name = name;
}
switch (capwords(tmp[2])) {
case "Warpspeed":
fleet[fid].WarpSpeed = toUint(tmp[3]);
break;
case "Impulsespeed":
fleet[fid].ImpulseSpeed = toUint(tmp[3]);
break;
case "Fuelconsumption":
fleet[fid].FuelConsumption = toDouble(tmp[3]);
break;
case "Flighttimemodifier":
fleet[fid].FlightTimeModifier = toDouble(tmp[3]);
break;
default:
writefln("Ungueltige configoption: ", tmp[2]);
}
}
break;
case "Bookmark":
tmp[2] = strip(tmp[2]);
bookmark[tmp[1]] = tmp[2];
break;
default:
writef("Ungueltige configoption: ", tmp[0]);
}
}
}
f.close();
if (fleet.length == 0) fleet.length = 1;
}
void readDatabase() {
uint i=0;
File f = new File("wl.dat");
wlarr.length = cast(uint) getSize("wl.dat")/wurmloch.sizeof;
while (!f.eof()) {
wlarr[i] = *cast(wurmloch *) f.readString(wurmloch.sizeof);
i++;
}
wlarr.length = i;
f.close();
wlearr.length = i;
for (uint j=0; j<i; j++) {
wlearr[j].a_to = timeDistance(wlarr[j].a, to);
wlearr[j].b_to = timeDistance(wlarr[j].b, to);
}
}
void runThreads() {
rb = new RouteBalancer();
calculationRunning = true;
// Split WL across InitDataThreads
uint step = cast(uint) ceil(cast(double) wlarr.length / initThreadCount);
StatusThread sthread = new StatusThread();
sthread.setPriority(Thread.PRIORITY.INCREASE);
InitDataThread[] ithreads;
// Run InitDataThreads
for (uint j=0; j<initThreadCount; j++) {
uint end = (j+1)*step;
if (end > wlarr.length) end = wlarr.length;
ithreads ~= new InitDataThread(j*step, end);
if (j*step+1 >= wlarr.length) break;
}
// Join InitDataThreads
foreach (InitDataThread t; ithreads) {
t.wait();
}
/*
2nd stage separated for improved load distribution (smp)
*/
WorkerThread[] wthreads;
// Run WorkerThreads
for (uint j=0; j<workerThreadCount; j++) {
wthreads ~= new WorkerThread();
}
// Join WorkerThreads
foreach (WorkerThread t; wthreads) {
t.wait();
}
calculationRunning = false;
rb.displayProgress();
}
void dumpMinPath(in uint hops) {
writef(" WL-Route: ");
for (uint i=0; i<minPath[hops].length; i+=2) {
koords a = minPath[hops][i];
koords b = minPath[hops][i+1];
writef("<%d-%d-%d-%d=%d-%d-%d-%d> ", (a.y-1)*100+a.x, a.gx, a.gy, a.gz, (b.y-1)*100+b.x, b.gx, b.gy, b.gz);
}
writefln("");
}
koords parseKoords(in char[] str) {
koords ret;
str = strip(str);
// 4145-100-87-98
if (count(str, "-") > 0) {
char tmp[][] = split(str, "-");
if (tmp.length == 4) {
int itmp = toInt(tmp[0]);
ret.x = cast(ubyte) (itmp%100);
ret.y = cast(ubyte) ((itmp / 100) + 1);
if (ret.x == 0) {
ret.x = 100;
ret.y-= 1;
}
ret.gx = toUbyte(tmp[1]);
ret.gy = toUbyte(tmp[2]);
ret.gz = toUbyte(tmp[3]);
}
// 45:42 oder 45:42:100:87:98 oder 4145:100:87:98
} else if (count(str, ":") > 0) {
char tmp[][] = split(str, ":");
if (tmp.length == 2) {
ret.x = toUbyte(tmp[0]);
ret.y = toUbyte(tmp[1]);
} else if (tmp.length == 4) {
int itmp = toInt(tmp[0]);
ret.x = cast(ubyte) (itmp%100);
ret.y = cast(ubyte) ((itmp / 100) + 1);
ret.gx = toUbyte(tmp[1]);
ret.gy = toUbyte(tmp[2]);
ret.gz = toUbyte(tmp[3]);
} else if (tmp.length == 5) {
ret.x = toUbyte(tmp[0]);
ret.y = toUbyte(tmp[1]);
ret.gx = toUbyte(tmp[2]);
ret.gy = toUbyte(tmp[3]);
ret.gz = toUbyte(tmp[4]);
}
// 4145
} else if (countchars(str, "0-9") == str.length) {
int itmp = toInt(str);
ret.x = cast(ubyte) (itmp%100);
ret.y = cast(ubyte) ((itmp / 100) + 1);
if (ret.x == 0) {
ret.x = 100;
ret.y-= 1;
}
// bookmark
} else {
foreach (char[] index, char[] value; bookmark) {
if (index == str) {
ret = parseKoords(value);
break;
}
}
}
return ret;
}
double aeDistance(in koords a, in koords b) {
return sqrt(cast(double) ((a.gx-b.gx)*(a.gx-b.gx) + (a.gy-b.gy)*(a.gy-b.gy) + (a.gz-b.gz)*(a.gz-b.gz)));
}
double pcDistance(in koords a, in koords b) {
return sqrt(cast(double) ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
}
double timeDistance(in koords a, in koords b) {
return (pcDistance(a, b)*1000/fleet[fleetID].WarpSpeed + aeDistance(a, b)/fleet[fleetID].ImpulseSpeed) * 60 * fleet[fleetID].FlightTimeModifier;
}
class RouteBalancer {
public:
bool fetch(out route r) {
if (routes.length > nextRouteIndex) {
r = routes[nextRouteIndex++];
return true;
} else {
return false;
}
}
void add(in route r) {
synchronized routes ~= r;
}
bool waitForMore() {
if (suppliersRunning > 0) {
return true;
} else {
return false;
}
}
synchronized void addSupplier() {
suppliersRunning++;
}
synchronized void removeSupplier() {
suppliersRunning--;
}
void displayProgress() {
writef("\r%d / %d Routen berechnet.", nextRouteIndex, routes.length);
dout.flush();
}
private:
route[] routes;
uint nextRouteIndex = 0;
uint suppliersRunning = 0;
}
class StatusThread : Thread {
public:
this() {
this.start();
}
int run() {
while (calculationRunning) {
rb.displayProgress();
msleep(100);
}
return 0;
}
}
class InitDataThread : Thread {
public:
this(in uint iterStart, in uint iterEnd) {
this.iterStart = iterStart;
this.iterEnd = iterEnd;
this.start();
}
int run() {
rb.addSupplier();
for (uint i=iterStart; i<iterEnd; i++) {
double time_a = timeDistance(from, wlarr[i].a) + AddMinutesPerHop;
double time_b = timeDistance(from, wlarr[i].b) + AddMinutesPerHop;
if (time_a < time_b) {
// a->b
// KomzeRadius ignorieren, Zielkoordinaten bekannt oder Zielkoordinaten mit Galaansicht nachschlagbar
if (!UseKomzeLimit || wlarr[i].a.gx != 0 || ceil(pcDistance(wlarr[i].a, KomzeKoords)) <= KomzeRadius || ceil(pcDistance(wlarr[i].b, KomzeKoords)) <= KomzeRadius) {
if ((time_a + wlearr[i].b_to) < minTime[1]) {
synchronized {
minTime[1] = time_a + wlearr[i].b_to;
minPath[1] = [ wlarr[i].a, wlarr[i].b ];
for (uint j=2; j<=MaxHops; j++) {
if (minTime[1] < minTime[j]) {
minTime[j] = minTime[1];
minPath[j] = null;
}
}
}
}
if ((time_a + AddMinutesPerHop) < minTime[1]) {
route r;
r.path[0] = wlarr[i].a;
r.path[1] = wlarr[i].b;
r.pathLength = 2;
r.time = time_a + AddMinutesPerHop;
rb.add(r);
}
}
} else {
// b->a
if (!UseKomzeLimit || wlarr[i].b.gx != 0 || ceil(pcDistance(wlarr[i].b, KomzeKoords)) <= KomzeRadius || ceil(pcDistance(wlarr[i].a, KomzeKoords)) <= KomzeRadius) {
if ((time_b + wlearr[i].a_to) < minTime[1]) {
synchronized {
minTime[1] = time_b + wlearr[i].a_to;
minPath[1] = [ wlarr[i].b, wlarr[i].a ];
for (uint j=2; j<=MaxHops; j++) {
if (minTime[1] < minTime[j]) {
minTime[j] = minTime[1];
minPath[j] = null;
}
}
}
}
if ((time_b + AddMinutesPerHop) < minTime[1]) {
route r;
r.path[0] = wlarr[i].b;
r.path[1] = wlarr[i].a;
r.pathLength = 2;
r.time = time_b + AddMinutesPerHop;
rb.add(r);
}
}
}
}
rb.removeSupplier();
return 0;
}
private:
uint iterStart;
uint iterEnd;
}
class WorkerThread : Thread {
public:
this() {
this.start();
}
int run() {
route r;
while (true) {
rb.addSupplier();
while (rb.fetch(r)) {
uint hops = (r.pathLength>>1) + 1;
for (uint i=0; i<wlarr.length; i++) {
double time_a = r.time + timeDistance(r.path[r.pathLength-1], wlarr[i].a);
double time_b = r.time + timeDistance(r.path[r.pathLength-1], wlarr[i].b);
if (time_a < time_b) {
// a->b
if (!UseKomzeLimit || wlarr[i].a.gx != 0 || ceil(pcDistance(wlarr[i].a, KomzeKoords)) <= KomzeRadius || ceil(pcDistance(wlarr[i].b, KomzeKoords)) <= KomzeRadius) {
if ((time_a + wlearr[i].b_to) < minTime[hops]) {
synchronized {
minTime[hops] = time_a + wlearr[i].b_to;
minPath[hops] = r.path[0 .. r.pathLength] ~ wlarr[i].a ~ wlarr[i].b;
for (uint j=hops+1; j<=MaxHops; j++) {
if (minTime[hops] < minTime[j]) {
minTime[j] = minTime[hops];
minPath[j] = null;
}
}
}
}
if ((hops < MaxHops) && ((time_a + AddMinutesPerHop) < minTime[hops])) {
route r2;
for (uint x=0; x<r.pathLength; x++) r2.path[x] = r.path[x];
r2.pathLength = r.pathLength;
r2.path[r2.pathLength++] = wlarr[i].a;
r2.path[r2.pathLength++] = wlarr[i].b;
r2.time = time_a + AddMinutesPerHop;
rb.add(r2);
}
}
} else {
// b->a
if (!UseKomzeLimit || wlarr[i].b.gx != 0 || ceil(pcDistance(wlarr[i].b, KomzeKoords)) <= KomzeRadius || ceil(pcDistance(wlarr[i].a, KomzeKoords)) <= KomzeRadius) {
if ((time_b + wlearr[i].a_to) < minTime[hops]) {
synchronized {
minTime[hops] = time_b + wlearr[i].a_to;
minPath[hops] = r.path[0 .. r.pathLength] ~ wlarr[i].b ~ wlarr[i].a;
for (uint j=hops+1; j<=MaxHops; j++) {
if (minTime[hops] < minTime[j]) {
minTime[j] = minTime[hops];
minPath[j] = null;
}
}
}
}
if ((hops < MaxHops) && ((time_b + AddMinutesPerHop) < minTime[hops])) {
route r2;
for (uint x=0; x<r.pathLength; x++) r2.path[x] = r.path[x];
r2.pathLength = r.pathLength;
r2.path[r2.pathLength++] = wlarr[i].b;
r2.path[r2.pathLength++] = wlarr[i].a;
r2.time = time_b + AddMinutesPerHop;
rb.add(r2);
}
}
}
}
}
rb.removeSupplier();
if (rb.waitForMore()) {
this.yield();
} else {
break;
}
}
return 0;
}
}
