Find the optimal path between several selected passive nodes

Abierto
  • ¿Algo no está bien?
#2,578 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
45/100
Tipo de issue
Nueva funcionalidad
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
lua
Área
game-dev

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Lua
Estrellas
1.9k
Forks
469
Sin PR fusionados en 30 d

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de PathOfBuildingCommunity/PathOfBuilding-PoE2

Todos los issues de PathOfBuildingCommunity/PathOfBuilding-PoE2

Issues similares

Más issues de Lua

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.