Find the optimal path between several selected passive nodes

Aperta
  • Qualcosa non va?
#2,578 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
45/100
Tipo di issue
Funzionalità
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
lua
Ambito
game-dev

Direzione di ricerca

Start with the Tree tab's bottom bar and node allocation and preview paths; the issue does not name files or tests, so locate those entry points in the Lua code first. Then trace how tree state, compare mode, undo, and build saving are handled. Done means the optimizer finds and previews the minimum point connection for selected nodes while respecting the listed allocation rules, and applying it is one undo step; run the relevant tree tests.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

enhancement
Check for duplicates
  • I've checked for duplicate open and closed issues by using the search function of the issue tracker
What platform are you running Path of Building on?

Windows

Is your feature request related to a problem?

When planning a tree, I usually know which notables, keystones and jewel sockets I want, but not the cheapest way to reach all of them. Path of Building only shows the shortest path from my current tree to the one node I'm hovering. Allocating my targets one at a time depends on the order I click them and often costs extra points, because the cheapest tree branches at nodes that none of the individual shortest paths use.

Describe the solution you'd like

An Optimal Path button at the end of the Tree tab's bottom bar, after the node power options:

  • While it's on (the button turns green), left-click allocates as usual and right-click cycles a node: the first click selects it for the optimizer (green ring), the second marks it to avoid (red ring), the third unmarks it. Alt stays free for showing node power; the rings only show while the mode is on, and a Clear Selected button deselects everything. A short tip explains this for a minute after turning the mode on.

  • A Find Path (N) button (N = selected nodes) finds the fewest passive points that connect all selected nodes to the current tree without going through avoided nodes (a minimum Steiner tree). The result is previewed on the tree with a summary such as "Optimal path: 29 points connect 4 selected nodes", and Apply / Discard buttons appear in the bottom bar next to a note naming the tree it will be applied to.

  • It follows the same rules as normal allocation: weapon set allocation modes, ascendancy boundaries, unlock constraints, multiple choice nodes, and the attribute choice for "+5 to any Attribute" nodes. Applying is one undo step.

  • It works with Compare: the preview is coloured as if it was applied (white where the compared tree has the same nodes, red where only the current tree would have them).

  • The selection belongs to the build, so switching trees keeps it. It's saved with the build only when there is one, so other builds and the save format don't change.

  • It only runs when Find Path is pressed, in the background like the Power Report, so normal tree editing stays as fast as it is now.

Describe alternatives you've considered

  • Allocating targets one at a time: the result depends on the click order and is often a few points worse.

  • Path trace mode (hold Shift): works, but finding the best route by hand is slow for more than two or three targets.

  • External planners: pathofpathing.com (linked in PathOfBuildingCommunity/PathOfBuilding#7671) does this for the PoE1 tree only (versions 3.22 to 3.29), and I haven't found anything similar for the PoE2 tree. Even with an external tool, the build has to be moved between tools.

Additional context

Related but different: #1726 asks to mark nodes you're interested in, and #1785 asks for an allocation order. On the PoE1 repo, PathOfBuildingCommunity/PathOfBuilding#6561, PathOfBuildingCommunity/PathOfBuilding#7671 and PathOfBuildingCommunity/PathOfBuilding#5094 ask for this same feature and are still open.

The approach comes from PoESkillTree's "Skill Tagged Nodes" Steiner tree solver (MIT licensed), which I've already ported to the PoE2 tree in a standalone app (https://github.com/nooree00/PoE2SkillTree). I have a working, tested implementation for PoB on my fork: https://github.com/nooree00/PathOfBuilding-PoE2/tree/optimal-path-planner

On the 0.5 tree (Witch, notables 8–30 points away) it uses 49, 76 and 122 points for 4, 8 and 16 targets, where allocating them one by one, nearest first, takes 51, 79 and 125. A search takes 0.1–0.25 s in PoB's LuaJIT. I'd open a PR against dev if you're interested.

Lingua principale
Lua
Stelle
1.9k
Fork
469
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di PathOfBuildingCommunity/PathOfBuilding-PoE2

Tutte le issue di PathOfBuildingCommunity/PathOfBuilding-PoE2

Issue simili

Altre issue su Lua

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.