TouhouGD/level_design/2.py

import json
from igraph import Graph, plot

with open('data.json', 'r', encoding='utf-8') as file:
    data_raw = json.load(file)
    data = json.loads(json.dumps(data_raw))
#数据补充
for node_name in data_raw:
    node_info_raw = data_raw[node_name]
    node_info = data[node_name]
    for path_to in node_info_raw['path_to']:
        is_key_need = 'key_need' in path_to
        key_need = path_to['key_need'] if is_key_need else ''
        is_one_way_door = key_need == '单向门'
        is_one_way = not is_one_way_door and 'is_one_way' in path_to
        if is_one_way_door:
            if not 'key_get' in node_info:
                node_info['key_get'] = []
            is_key_need = True
            key_need = f'单向门-{node_name}-{path_to['name']}'
            node_info['key_get'].append(key_need)
            node_info['path_to']
        if not is_one_way:
            target_node_info = data[path_to['name']]
            append_path = {'name':node_name}
            if is_key_need:
                append_path['key_need'] = key_need
            target_node_info['path_to'].append(append_path)
#多余数据删除
for node_name in data:
    node_info = data[node_name]
    for path_to in node_info['path_to']:
        is_key_need = 'key_need' in path_to
        key_need = path_to['key_need'] if is_key_need else ''
        is_one_way_door = key_need == '单向门'
        is_one_way = not is_one_way_door and 'is_one_way' in path_to
        if is_one_way_door:
            key_need = f'单向门-{node_name}-{path_to['name']}'
            path_to['key_need'] = key_need
            path_to.pop('is_one_way', None)

#BFS
start_node_name = '破碎遗迹'
end_node_name = '战斗-魂魄妖忌'
start_node = (start_node_name,set(),set(),[start_node_name],'') #name，key_get, key_use，path，portal
stack = [start_node]
close_set = set()

useless_node_list = []
useless_key_list = []

while True:
    if len(stack)==0:
        break
    current = stack.pop(0)
    current_name = current[0]
    current_key_get = current[1]
    current_key_use = current[2]
    current_path = current[3]
    current_portal = current[4]
    
    if current_name == '白玉楼' and current_portal == '':
        current_portal = current_name
    
    if current_name == end_node_name:
        useless_node = []
        useless_key = []
        for node_name in data:
            if not node_name in current_path:
                useless_node.append(node_name)
            if 'key_get' in data[node_name]:
                for key_get in data[node_name]['key_get']:
                    if not key_get in current_key_use:
                        useless_key.append(key_get)
        useless_node_list.append(useless_node)
        useless_key_list.append(useless_key)
        continue
    
    if 'key_get' in data[current_name]:
        for key_get in data[current_name]['key_get']:
            if not key_get in current_key_get:
                current_key_get.add(key_get)
                current_path.append(f'获取({key_get})')
    
    for path_to in data[current_name]['path_to']:
        is_key_need = 'key_need' in path_to
        if is_key_need and not path_to['key_need'] in current_key_get:
            continue
        next_name = path_to['name']
        current_key_list = list(current_key_get)
        current_key_list.sort()
        next_name_with_key = next_name + ':' + ','.join(current_key_list)
        if next_name_with_key in close_set:
            continue
        close_set.add(next_name_with_key)
        next_path = current_path.copy()
        next_path.append(next_name)
        next_key_use = current_key_use.copy()
        if is_key_need and path_to['key_need'] in current_key_get:
            next_key_use.add(path_to['key_need'])
        next_node = (next_name, current_key_get.copy(), next_key_use, next_path, current_portal)
        stack.insert(-1,next_node)
    #传送
    if current_name == '白玉楼' and not current_portal == '':
        next_name = current_portal
        current_key_list = list(current_key_get)
        current_key_list.sort()
        next_name_with_key = next_name + ':' + ','.join(current_key_list)
        if next_name_with_key in close_set:
            continue
        close_set.add(next_name_with_key)
        next_path = current_path.copy()
        next_path.append(f'传送({next_name})')
        next_node = (next_name, current_key_get.copy(), current_key_use.copy(), next_path, current_portal)
        stack.insert(-1,next_node)
            
    if not current_name == '白玉楼' and not current_portal == '':
        next_name = '白玉楼'
        current_key_list = list(current_key_get)
        current_key_list.sort()
        next_name_with_key = next_name + ':' + ','.join(current_key_list)
        if next_name_with_key in close_set:
            continue
        close_set.add(next_name_with_key)
        next_path = current_path.copy()
        next_path.append(f'传送({next_name})')
        next_node = (next_name, current_key_get.copy(), current_key_use.copy(), next_path, current_name)
        stack.insert(-1,next_node)
        
success_count = len(useless_node_list)
key_set = set()
useless_node_dict = {}
useless_key_dict = {}
for node_name in data:
    useless_node_dict[node_name] = 0
    if 'key_get' in data[node_name]:
        for key_get in data[node_name]['key_get']:
            if not key_get in key_set:
                key_set.add(key_get)
                useless_key_dict[key_get] = 0
node_max = len(data)
key_max = len(key_set)

for useless_node in useless_node_list:
    for key in useless_node: 
        useless_node_dict[key] += 1
        
for useless_key in useless_key_list:
    for key in useless_key: 
        useless_key_dict[key] += 1

useless_node_count_sum = sum(map(lambda x: len(x), useless_node_list))
print('success_count:', success_count)
print('useless_node_avg:', "{:.2f}%".format(useless_node_count_sum / success_count / node_max * 100))

for useless_node in useless_node_dict:
    print("{}  {:.2f}%".format(useless_node,useless_node_dict[useless_node] / success_count * 100))

print("-"*20)
for useless_key in useless_key_dict:
    print("{}  {:.2f}%".format(useless_key,useless_key_dict[useless_key] / success_count * 100))