Find the optimal path between several selected passive nodes

Đang mở
  • Có gì không ổn?
#2,578 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
45/100
Loại issue
Tính năng
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
lua
Lĩnh vực
game-dev

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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.

Ngôn ngữ chính
Lua
Star
1.9k
Fork
469
Không có pull request nào được merge trong 30 ngày

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của PathOfBuildingCommunity/PathOfBuilding-PoE2

Tất cả issue của PathOfBuildingCommunity/PathOfBuilding-PoE2

Issue tương tự

Thêm issue về Lua

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.