124 lines
4 KiB
Python
124 lines
4 KiB
Python
|
import json
|
||
|
|
import networkx
|
||
|
|
import matplotlib.pyplot as plt
|
||
|
|
import math
|
||
|
|
import requests
|
||
|
|
|
||
|
|
raw_skill_tree = requests.get('https://raw.githubusercontent.com/poe-tool-dev/passive-skill-tree-json/master/3.21.0-atlas/SkillTree.json').text
|
||
|
|
atlas_data = json.loads(raw_skill_tree)
|
||
|
|
|
||
|
|
atlas_node_data = atlas_data['nodes']
|
||
|
|
|
||
|
|
atlas_graph = networkx.Graph()
|
||
|
|
for node in atlas_node_data:
|
||
|
|
node_1 = 0 if node == 'root' else int(node)
|
||
|
|
for i in atlas_node_data[node]['in']:
|
||
|
|
node_2 = 0 if i == 'root' else int(i)
|
||
|
|
atlas_graph.add_edge(node_1, node_2)
|
||
|
|
for i in atlas_node_data[node]['out']:
|
||
|
|
node_2 = 0 if i == 'root' else int(i)
|
||
|
|
atlas_graph.add_edge(node_1, node_2)
|
||
|
|
|
||
|
|
mandated_nodes = [
|
||
|
|
39896, 65464, 62028, 64740, 10530, 32784, 25301, # blocking
|
||
|
|
6530, 8171, 57512, 39180, # core + keystone
|
||
|
|
39276, 53175, 54874, 57163, # harvest
|
||
|
|
51834, 44249, 57784, 27002, 40700, 7382, # metamorph
|
||
|
|
33361, 55438, 55885, 45869, # betrayal
|
||
|
|
]
|
||
|
|
|
||
|
|
# start()
|
||
|
|
# set_init()
|
||
|
|
# step()
|
||
|
|
# find_closest()
|
||
|
|
# find_alternate_paths()
|
||
|
|
# adjust_and_compute_shortest()
|
||
|
|
# if multiple_skip()
|
||
|
|
# allocate()
|
||
|
|
# remove_from_list()
|
||
|
|
|
||
|
|
def find_closest(curr_node):
|
||
|
|
global mandated_nodes, atlas_graph
|
||
|
|
shortest = -1
|
||
|
|
next_node = None
|
||
|
|
for node in mandated_nodes:
|
||
|
|
path_len = networkx.shortest_path_length(atlas_graph, curr_node, node)
|
||
|
|
if shortest == -1 or shortest > path_len:
|
||
|
|
shortest = path_len
|
||
|
|
next_node = node
|
||
|
|
#elif shortest == path_len:
|
||
|
|
# return -1
|
||
|
|
return next_node
|
||
|
|
|
||
|
|
def find_all_shortest(curr_node, next_node):
|
||
|
|
global mandated_nodes, atlas_graph, node_set
|
||
|
|
paths = networkx.all_shortest_paths(atlas_graph, curr_node, next_node)
|
||
|
|
shortest = -1
|
||
|
|
next_path = None
|
||
|
|
for path in paths:
|
||
|
|
path_len = len(path) - sum([node in node_set for node in path])
|
||
|
|
if shortest == - 1 or shortest > path_len:
|
||
|
|
shortest = path_len
|
||
|
|
next_path = path
|
||
|
|
#elif shortest == path_len:
|
||
|
|
# return -1
|
||
|
|
return next_path
|
||
|
|
|
||
|
|
curr_node = 0
|
||
|
|
node_set = []
|
||
|
|
node_jail = []
|
||
|
|
release = False
|
||
|
|
|
||
|
|
while len(mandated_nodes) + len(node_jail) != 0:
|
||
|
|
if release:
|
||
|
|
mandated_nodes += node_jail
|
||
|
|
node_jail = []
|
||
|
|
if not release:
|
||
|
|
release = True
|
||
|
|
next_node = find_closest(curr_node)
|
||
|
|
next_path = find_all_shortest(curr_node, next_node)
|
||
|
|
if next_path == -1:
|
||
|
|
node_jail.append(next_node)
|
||
|
|
del mandated_nodes[mandated_nodes.index(next_node)]
|
||
|
|
release = False
|
||
|
|
else:
|
||
|
|
for node in next_path:
|
||
|
|
if node not in node_set:
|
||
|
|
node_set.append(node)
|
||
|
|
curr_node = next_node
|
||
|
|
del mandated_nodes[mandated_nodes.index(curr_node)]
|
||
|
|
|
||
|
|
for node in node_set:
|
||
|
|
if node == 0:
|
||
|
|
continue
|
||
|
|
print(f'{atlas_node_data[str(node)]["skill"]}\t{atlas_node_data[str(node)].get("name")}')
|
||
|
|
|
||
|
|
|
||
|
|
def draw_atlas_graph():
|
||
|
|
global atlas_data, node_set
|
||
|
|
pos = {}
|
||
|
|
for node in atlas_node_data:
|
||
|
|
if node != 'root':
|
||
|
|
group = atlas_node_data[node]['group']
|
||
|
|
orbit = atlas_node_data[node]['orbit']
|
||
|
|
orb_idx = atlas_node_data[node]['orbitIndex']
|
||
|
|
|
||
|
|
base_pos = [atlas_data['groups'][str(group)]['x'], atlas_data['groups'][str(group)]['y']]
|
||
|
|
orbit_r = atlas_data['constants']['orbitRadii'][orbit]
|
||
|
|
orbit_n = atlas_data['constants']['skillsPerOrbit'][orbit]
|
||
|
|
|
||
|
|
angle = orb_idx / orbit_n * 2 * math.pi
|
||
|
|
full_pos = [base_pos[0] + orbit_r * math.sin(angle), -1*(base_pos[1] - orbit_r * math.cos(angle))]
|
||
|
|
pos[int(node)] = full_pos
|
||
|
|
|
||
|
|
pos[0] = [0, -100]
|
||
|
|
nodes = atlas_graph.nodes()
|
||
|
|
color = [('#0000a0' if node in node_set else '#000000') for node in nodes]
|
||
|
|
sizes = [(40 if node in node_set else 20) for node in nodes]
|
||
|
|
networkx.draw(atlas_graph, pos=pos, node_color=color, node_size = sizes)
|
||
|
|
plt.show()
|
||
|
|
|
||
|
|
draw_atlas_graph()
|
||
|
|
|
||
|
|
print(len(node_set) - 2)
|