# 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)}$$