111 lines
7.4 KiB
Markdown
111 lines
7.4 KiB
Markdown
# 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](https://edsm.net/) 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:
|
|
- conda ([Miniconda](https://docs.conda.io/en/latest/miniconda.html)/[Anaconda](https://www.anaconda.com/distribution/))
|
|
- [nox](https://nox.thea.codes/en/stable/index.html)
|
|
- Inno Setup Compiler
|
|
- Download from [here](http://www.jrsoftware.org/isdl.php)
|
|
- or install via [scoop](https://scoop.sh/) `scoop install inno-setup`)
|
|
- Visual Studio 2019
|
|
- nightly rust compiler (`x86_64-pc-windows-msvc`)
|
|
|
|
## Building an installer
|
|
|
|
(Assuming `conda` is in your `PATH`)
|
|
|
|
1. Run `nox -k build`
|
|
2. Grab the installer from `installer/Output/`
|
|
|
|
## Manual installation
|
|
|
|
(Assuming `conda` is in your `PATH`)
|
|
|
|
1. Start a Visual Studio 2019 x64 command prompt
|
|
2. 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](https://elite-dangerous.fandom.com/wiki/Frame_Shift_Drive#Hyperspace_Fuel_Equation)): $$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 tanks
|
|
- $m_{opt}$ is the optimized mass of your FSD (in tons)
|
|
- $f_{max}$ is the maximum amount of fuel your FSD can use per jump
|
|
- $boost$ 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 amount
|
|
- $dist_{max}$ is the maximum distance you can jump (when $m_{fuel}=f_{max}$)
|
|
- $B_{g}$ is the amount of Ly added by your Guardian FSD Booster
|
|
- $e_{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)}$$
|