.chglog | ||
celery | ||
docs | ||
ed_lrr_gui | ||
icon | ||
installer | ||
rust | ||
tests | ||
.env | ||
.gitignore | ||
appveyor.yml | ||
build_gui.py | ||
CHANGELOG.md | ||
LICENSE | ||
MANIFEST.in | ||
noxfile.py | ||
pyproject.toml | ||
README.md | ||
setup.cfg | ||
setup.py |
Elite: Dangerous Long-range router
Features
- Five different routing algorithms:
- Breadth-first search:, always finds the shortest route but is quite slow
- Bidirectional BFS:: should give similar route quality to BFS but take less time (not yet implemented)
- A-Star: has an adjustable tradeoff between speed and quality
- Greedy search: always picks the next reachable star that's closest to the destination, very fast but very poor quality routes
- Economic: computes route with lowest possible fuel consumption (WIP)
- Nice GUI! (made with PyQt5)
- Two themes! (Dark and Light)
- Uses data from EDSM for star data
- Only routes through scoopable systems, no more running out of fuel! (assuming you have a fuel scoop)
- Take fuel consumption into account and add refueling stops along the route (Not yet implemented)
- Precomputing of BFS routing graphs for:
- near-instant routing from your home system to any destination!
- near-instant routing any source back to your-home system (WIP)!
- near-instant routing between any pair of systems (Not yet implemented, see TODO)
- Routing code written in Rust, so it's quite speedy!
- Export routes as HTML, JSON, CSV and SVG (WIP)
- Automagically copy next jump destination into system clipboard (works by monitoring the player journal file) (Not yet implemented)
- (optional) Web interface with job queue for route computations and multi-user support
Installation
Prerequisites
- Python:
- Inno Setup Compiler
- Visual Studio 2019
- nightly rust compiler (
x86_64-pc-windows-msvc
)
Building an installer
(Assuming conda
is in your PATH
)
- Run
nox -k build
- Grab the installer from
installer/Output/
Manual installation
(Assuming conda
is in your PATH
)
- Start a Visual Studio 2019 x64 command prompt
- Run the following commands:
conda install pycrypto ujson
pip install setuptools_rust
pip install .[all]
then you can run ed_lrr -h
from your command prompt to get help
Notes on FSD Fuel consumption and jump range
FSD Fuel consumption (E:D Wiki): $$Fuel = 0.001 \cdot l \cdot \left(\frac{dist \cdot \left(m_{fuel} +
m_{ship}\right)}{boost \cdot m_{opt}}\right)^{p}
Solving for dist
gives the jump range (in Ly) for a given amount of fuel (in tons) as: $$dist = \frac{boost \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}
Assuming f_{max}
tons of available fuel gives us the maximum jump range for a single jump as: $$dist_{max} = \frac{boost \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot f_{max}}{l}\right)^{\frac{1}{p}}}{f_{max} + m_{ship}}
Since the guardian FSD booster increases the maximum jump range by B_g
Ly we can calculate a correction factor for the fuel consumption as: $$0.001 \cdot l \cdot \left(\frac{boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{B_{g} \cdot \left(m_{fuel} + m_{ship}\right) + boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}\right)^{p}
Incorporating e_{fuel}
into the distance equation yields $$dist = \frac{boost \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot e_{fuel} \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}
Expanding e_{fuel}
yields $$dist = \frac{boost \cdot m_{opt} \cdot \left(1.0 \cdot \left(\frac{boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{B_{g} \cdot \left(m_{fuel} + m_{ship}\right) + boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}\right)^{p} \cdot \min\left(f_{max}, m_{fuel}\right)\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}
Finally, Expanding dist_{max}
yields the full equation as $$dist = \frac{boost \cdot m_{opt} \cdot \left(\frac{1000000.0 \cdot \left(\frac{boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{B_{g} \cdot \left(m_{fuel} + m_{ship}\right) + boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}\right)^{- p} \cdot \min\left(f_{max}, m_{fuel}\right)}{l^{2}}\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}
Where:
Fuel
is the fuel needed to jump (in tons)l
is the linear constant of your FSD (depends on the rating)p
is the power constant of your FSD (depends on the class)m_{ship}
is the mass of your ship (including cargo)m_{fuel}
is the amount of fuel in tons currently stored in your tanksm_{opt}
is the optimized mass of your FSD (in tons)f_{max}
is the maximum amount of fuel your FSD can use per jumpboost
is the "boost factor" of your FSD (1.0 when jumping normally, 1.5 when supercharged by a white dwarf, 4.0 for a neutron star, etc)dist
is the distance you can jump with a given fuel amountdist_{max}
is the maximum distance you can jump (whenm_{fuel}=f_{max}
)B_{g}
is the amount of Ly added by your Guardian FSD Boostere_{fuel}
is the efficiency increase added by the Guardian FSD Booster
Fuel multiplier (CMDR jonburnage)
F_f = f_{max} \cdot \left(\frac{B_{g} \cdot m_{ship}}{m_{opt}} + l \cdot \left(\frac{f_{max}}{l}\right)^{\frac{1}{p}}\right)^{- p}
Fuel multiplier (Spansh)
$$F_f = 0.001 \cdot l \cdot \left(\frac{boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{\left(B_{g} + \frac{boost^{2} \cdot m_
{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}\right) \cdot \left(m_{fuel} + m_{ship}\right)}\right)^{p}
F_f = 0.001 \cdot l \cdot \left(\frac{boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{B_{g} \cdot \left(m_{fuel} + m_{ship}\right) + boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}\right)^{p}
dist = \frac{boost \cdot m_{opt} \cdot \left(1.0 \cdot \left(\frac{boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{B_{g} \cdot \left(m_{fuel} + m_{ship}\right) + boost^{2} \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}\right)^{p} \cdot \min\left(f_{max}, m_{fuel}\right)\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}
Misc Stuff
dist = \frac{- B_{g} \cdot m_{fuel} - B_{g} \cdot m_{ship} + boost \cdot m_{opt} \cdot \left(\frac{1000.0 \cdot e_{fuel} \cdot \min\left(f_{max}, m_{fuel}\right)}{l}\right)^{\frac{1}{p}}}{m_{fuel} + m_{ship}}
e_{fuel} = \frac{l \cdot \left(\frac{10.0^{- \frac{3.0}{p}} \cdot \left(B_{g} + dist\right) \cdot \left(m_{fuel} + m_{ship}\right)}{boost \cdot m_{opt}}\right)^{p}}{\min\left(f_{max}, m_{fuel}\right)}
TODO
Routing
- Implement Neutron Mode
- Filter for neutron stars, plot route, then plot "fine" router between waypoints
- What Jump-Range to use for neutron route?
max_range*4
?
- What Jump-Range to use for neutron route?
- Filter for neutron stars, plot route, then plot "fine" router between waypoints
- Implement Bidir BFS
- Optimized All-Pairs BFS for graph precomputation
- Take fuel consumption into account (WIP)
- Guardian Booster support (Done?)
- Economic routing
- Custom weights and filtering for routing
GUI
- Implement estimate time to completion display for route computation and preprocessing (Done?)
- Export route as:
- JSON
- HTML (WIP)
- CSV
- SVG
Installer
- Update PATH from installer
Preprocessing
- Build index over
systemsWithCoordinates.json
instead of loading it into RAM (reuse modifiedLineCache
fromrouter.rs
) - Finish
galaxy.jsonl
preprocessor - Implement Python interface to preprocessor
Misc
- Luigi based Task queue for distributed routing
- Full route tree computation
- overlap elimination