Find the optimal path between several selected passive nodes

オープン
  • 何か問題がありますか？
#2,578 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
45/100
issue の種類
機能追加
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
lua
領域
game-dev

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
Lua
スター
1.9k
フォーク
469
30日以内にマージされた PR はありません

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

PathOfBuildingCommunity/PathOfBuilding-PoE2 のほかの issue

PathOfBuildingCommunity/PathOfBuilding-PoE2 の issue をすべて見る

似ている issue

Lua の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。