BDO‑NodeRouter solves Multi‑Commodity Flow Problems for node‑weighted Steiner forests, providing both optimal (MIP‑based) and approximated (PD, GSSP, PBS) routing solutions. The project targets a relatively small (< 1000 nodes) planar graph extracted from Black Desert Online, but the architecture is general enough to adapt to larger planar graphs with modest adjustments.

To explore the underlying graph, nodes, and routing behavior visually, see Shrddr’s excellent Workerman empire planner.

Scroll to the bottom of this file to see the testing results.

Usage notes:

• Requirements:

  • nightly for coroutines

  rustup install nightly

WASM

• Requirements:
  • wasm-pack for wasm
  • python to run the demo (or some other mini server)

cargo install wasm-pack

rustup target add wasm32-unknown-unknown

• Build for wasm using

wasm-pack build --release --target web --features wasm

• To run the wasm demo after building:

> cp -Rf ./pkg ./demo/pkg
> cd demo
> python -m http.server 8080

or on Windows...

> Copy-Item -Path ".\pkg" -Destination ".\demo\pkg" -Recurse -Force
> cd demo
> python -m http.server 8080; Start-Process http://localhost:8080

Then load the clean exploration.json from python/bdo_noderouter/data. Lastly input terminal,root pairs (as waypoint ids) and hit solve.

Python

• Requirements:
  • python
  • uv
  • maturin for python

Setup project dependencies (you may need to setup a .venv if uv doesn't just do it for you):

uv sync

Build for Python using:

maturin develop --profile release --features python --uv

Demo scripts...

optimizer_mip.py

Uses the HiGHS linear optimization software. It utilizes the solver configuration in the config.toml file and can be configured to use multiple threads. When multiple threads are used the solve() function coordinates solution sharing between the threads to dramatically improve runtime. Big shout out to mathgeekcoder on the HiGHS discord server for providing the inspiration for the solution sharing setup and other HiGHS callback uses.

The problem is modelled as a Multi-Commodity Flow Problem with reverse flow and a 'super root' to allow 'super terminals' to connect to any potential base town.

The optimizer_mip solution is the optimal solution.

.venv/bin/python python/bdo_noderouter/optimizer_mip.py

optimizer_nr.py

Uses the NodeRouter approximation algorithms (PD and GSSP) along with the Pulsing-Bridge Spanners (PBS) heuristic. The heuristic uses a Rust implementation of the DNDTree and IDTree data structures for constant-time connectivity testing.

.venv/bin/python python/bdo_noderouter/pd_approximation.py

fuzz.py

The fuzz.py script is a controlled fuzzer that generates random (terminal, root) pairs using a variety of pairing strategies to stress test the accuracy and performance of the NodeRouter compared to MIP solutions. (It will cache the MIP results in .cache for re-use in future runs.)

.venv/bin/python python/bdo_noderouter/fuzz.py

fuzz_suboptimal_viewer.py

Provides a UI to select suboptimal results generated by the fuzzer for visualization in a browser to compare the NodeRouter and MIP solutions in an interactive setting where edges, nodes and terminals can be enabled or disabled independently. The solutions are overlays on the game map.

.venv/bin/python python/bdo_noderouter/fuzz_suboptimal_viewer.py

This will open a browser instance for with an interactive map.

Notes

Since the NodeRouter is an approximation and the bridge heuristic improves solutions using a combinatorial method the following settings can be altered using the set_option function:

• max_removal_attempts (default: 350)
• max_frontier_rings (default: 4)
• ring_combo_cutoff (inner to outer most ring, default: [0, 3, 2, 2, 2])

Credits

Core Libraries

• Rustworkx and Petgraph
  Rustworkx is built on top of Petgraph and provides the Python‑side graph infrastructure used throughout the project.

• HiGHS linear optimization software
  Parallelizing the dual revised simplex method,
  Q. Huangfu and J. A. J. Hall, Mathematical Programming Computation, 10(1), 119–142, 2018.

Algorithmic Foundations

• DNDTree and IDTree data structures from
  Xu, Lantian, et al.
  Constant-time Connectivity Querying in Dynamic Graphs.
  Proceedings of the ACM on Management of Data 2.6 (2024): 1–23.

• Node‑Weighted Primal‑Dual Approximation from
  Demaine, Erik D., MohammadTaghi Hajiaghayi, and Philip N. Klein.
  Node-weighted Steiner tree and group Steiner tree in planar graphs.
  ICALP 2009.

• Dial’s Algorithm 360
  R. Dial, Algorithm 360: Shortest-Path Forest with Topological Ordering, 1969.

• Gluttonous: A greedy Algorithm for Steiner Forest
  As described in
  https://vihang-ag.github.io/data/Greedy_Algorithms_for_Steiner_Forest_report.pdf

Project‑Introduced Methods

• Greedy Shortest Shared Paths (GSSP)
  A greedy Steiner Forest approximation that batches terminal pairs using primal‑dual intuition and processes them in a Gluttonous‑inspired order using a bi‑directional, weight‑limited variant of Dial’s Algorithm 360, combined with constant‑time connectivity querying via DNDTree.

• Pulsing‑Bridge Spanners (PBS)
  A novel augmentation/pruning heuristic for node‑weighted Steiner forests.
  PBS temporarily inserts targeted multi‑node “spanning bridges” to induce beneficial cycles, then prunes non‑articulation points to reduce cost while preserving connectivity.

Implementation Notes

To the best of our knowledge, this project contains the first public‑domain implementations of DNDTree and IDTree.
Lantian Xu provided reference material and a C++ implementation of the DNDTree, which was adapted and simplified for this project.

• DNDTree is used in an edge‑insertion‑only setting with multiple queries between insertions.
• IDTree is used with both insertions and removals, with relatively few queries between updates.

Performance and Results

** Coming soon - its takes a long time to solve the MIP problems. **

This section summarizes the accuracy and runtime characteristics of the NodeRouter approximation stack (PD, GSSP, and PBS) compared against the optimal MIP solution. All results are generated using the controlled fuzzer (fuzz.py), which evaluates a wide range of (terminal, root) pairing strategies and caches MIP solutions for reproducibility.

Accuracy Compared to MIP Optimality

• PD baseline accuracy
• GSSP accuracy
• GSSP + PBS accuracy
• Distribution of suboptimality across pairing strategies

(Coming Soon)

Runtime Characteristics

• MIP solve times (single‑threaded vs multi‑threaded)
• PD/GSSP per‑batch runtime
• PBS post‑processing overhead
• WASM warm/cold timings

Observed Behavior

• When PD outperforms GSSP
• When GSSP finds better sharing structure
• When PBS yields significant improvements
• Failure modes and pathological cases

Suboptimal Case Viewer

The fuzz_suboptimal_viewer.py tool provides an interactive map overlay for examining cases where the approximation diverges from the MIP solution. This is useful for identifying structural patterns that lead to suboptimality and for guiding future heuristic improvements.

TODO

Generate:

• disjoint-bridges

• spidering bridges

• inner-ring spanning bridges

• Finish studying the implementation details of scip-jack and process each terminal set cluster identified by the NodeRouter as a final pass to improve the solutions that the pulsing-bridge spanner obtains.