神代綺凛の随波逐流

[Lodash] 明日方舟公开招募计算器的简单实现

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »

水文章(x

Head Pic:【明日方舟】「series」/「Alcxome」的插画 [pixiv]

明日方舟公开招募计算器的简单实现

差不多一周前还是经不住劝诱被基友拉入了坑,对刚入坑还不熟悉角色池的人来说,公开招募计算器是非常有用且必要的工具

之前我一直用的是 graueneko.github.io,做的非常好,而后面我懒癌发作,因此想能不能将这个功能也整合进我自己写的QQ机器人里,利用现成的 OCR 做到:直接识别截图获取词条->计算可能的词条组合及其包含的干员->输出

但一开始的词条排列组合问题就让我感到头疼,如果要自己用动态规划来降低计算量和复杂度又感觉很麻烦,因为当时脑子瓦特了想不到什么简便的储存词条组合中间结果的方法(后来才想起可以排序后用 hash 或者直接拼接作为 key 啊真蠢)

在神的指引下我想起了还有 Lodash,并且发现其很适合写这类需要对数组进行大量操作的算法,于是决定写一个来练习一下

1. 数据预处理

还是要感谢 graueneko 等人的工作,已经将干员数据整理成了 json 格式,可以方便的直接拿来使用

那么首先需要明确,要做的是一个公开招募计算器,得到最终结果的算法大致如下

  1. 计算指定词条的所有排列组合方案
  2. 对每种方案,找到满足这些词条的干员,并对方案进行评分
  3. 按评分对所有有效方案进行排序

实现的重点是第2步,而干员数据的结构是干员->词条,每当我们想寻找满足某些词条的干员,我们都必须把列表遍历一遍,这是非常麻烦的

因此我们可以换一种储存方式,使结构变为词条->干员,这样比如我们想寻找同时拥有词条A词条B的干员,只需要求A和B的交集就行了

以下是示例:

import { get } from 'axios';
import _ from 'lodash';

const akhr = 'https://graueneko.github.io/akhr.json';

async function pullData() {
    let json = await get(akhr).then(r => r.data);

    //将干员按照稀有度从高到低排序,后续输出的时候就不用再排序了
    json.sort((a, b) => b.level - a.level);

    let characters = []; //角色列表
    let data = {}; //词条数据
    let charTagSum = 0;

    for (let character of json) {
        if (character.hidden) continue;
        let { level, name, sex, tags, type } = character;
        //将性别和干员种类也加入词条中
        tags.push(`${sex}性干员`);
        tags.push(`${type}干员`);
        //将干员放入 characters 数组,后续直接用其在数组中的 index 指代
        let p =
            characters.push({
                n: name, //名字
                r: level //稀有度
            }) - 1;
        //储存:词条->干员
        for (let tag of tags) {
            if (!data[tag]) data[tag] = [];
            data[tag].push(p);
        }
        charTagSum += tags.length;
    }

    let tagCount = _.size(data);
    return {
        characters,
        data,
        //这是后续计算评分用的数据(来自 graueneko)
        avgCharTag: charTagSum / tagCount
    };
}

然后就能得到这样子的数据结构

{
    "characters":[{"n":"推进之王","r":6},{"n":"闪灵","r":6},{"n":"夜莺","r":6},{"n":"伊芙利特","r":6},{"n":"能天使","r":6},{"n":"银灰","r":6},{"n":"星熊","r":6},{"n":"塞雷娅","r":6},{"n":"德克萨斯","r":5},{"n":"凛冬","r":5},{"n":"白面鸮","r":5},{"n":"赫默","r":5},{"n":"华法琳","r":5},{"n":"红","r":5},{"n":"狮蝎","r":5},{"n":"崖心","r":5},{"n":"食铁兽","r":5},{"n":"普罗旺斯","r":5},{"n":"蓝毒","r":5},{"n":"守林人","r":5},{"n":"陨星","r":5},{"n":"白金","r":5},{"n":"初雪","r":5},{"n":"真理","r":5},{"n":"梅尔","r":5},{"n":"幽灵鲨","r":5},{"n":"因陀罗","r":5},{"n":"临光","r":5},{"n":"雷蛇","r":5},{"n":"火神","r":5},{"n":"可颂","r":5},{"n":"清道夫","r":4},{"n":"红豆","r":4},{"n":"末药","r":4},{"n":"调香师","r":4},{"n":"夜烟","r":4},{"n":"远山","r":4},{"n":"砾","r":4},{"n":"暗索","r":4},{"n":"阿消","r":4},{"n":"白雪","r":4},{"n":"流星","r":4},{"n":"杰西卡","r":4},{"n":"地灵","r":4},{"n":"杜宾","r":4},{"n":"艾丝黛尔","r":4},{"n":"慕斯","r":4},{"n":"霜叶","r":4},{"n":"缠丸","r":4},{"n":"蛇屠箱","r":4},{"n":"古米","r":4},{"n":"角峰","r":4},{"n":"芬","r":3},{"n":"香草","r":3},{"n":"翎羽","r":3},{"n":"芙蓉","r":3},{"n":"安赛尔","r":3},{"n":"炎熔","r":3},{"n":"史都华德","r":3},{"n":"克洛丝","r":3},{"n":"安德切尔","r":3},{"n":"梓兰","r":3},{"n":"玫兰莎","r":3},{"n":"米格鲁","r":3},{"n":"夜刀","r":2},{"n":"杜林","r":2},{"n":"12F","r":2},{"n":"巡林者","r":2},{"n":"黑角","r":2},{"n":"Lancet-2","r":1},{"n":"Castle-3","r":1}],
    "data": {
        "近战位": [0, 5, 6, 7, 8, 9, 13, 14, 15, 16, 25, 26, 27, 28, 29, 30, 31, 32, 37, 38, 39, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 62, 63, 64, 68, 70],
        "费用回复": [0, 8, 9, 31, 32, 52, 53, 54],
        "输出": [0, 4, 5, 6, 14, 15, 17, 18, 19, 21, 23, 26, 28, 29, 31, 32, 35, 41, 42, 44, 46, 47, 48, 54, 58, 59, 60, 62],
        "高级资深干员": [0, 1, 2, 3, 4, 5, 6, 7],
        "女性干员": [0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 52, 53, 54, 55, 57, 59, 61, 62, 63, 64, 65, 69],
        "先锋干员": [0, 8, 9, 31, 32, 52, 53, 54, 64],
        "远程位": [1, 2, 3, 4, 10, 11, 12, 17, 18, 19, 20, 21, 22, 23, 24, 33, 34, 35, 36, 40, 41, 42, 43, 55, 56, 57, 58, 59, 60, 61, 65, 66, 67, 69],
        "支援": [1, 2, 5, 7, 9, 10, 12, 44, 70],
        "治疗": [1, 2, 7, 10, 11, 12, 27, 33, 34, 50, 55, 56, 69],
        "医疗干员": [1, 2, 10, 11, 12, 33, 34, 55, 56, 69],
        "群攻": [3, 20, 25, 36, 40, 45, 57],
        "削弱": [3, 20, 22, 35, 41],
        "术师干员": [3, 35, 36, 57, 58, 65, 66],
        "狙击干员": [4, 17, 18, 19, 20, 21, 40, 41, 42, 59, 60, 67],
        "男性干员": [5, 51, 56, 58, 60, 66, 67, 68, 70],
        "近卫干员": [5, 25, 26, 44, 45, 46, 47, 48, 62, 70],
        "防护": [6, 7, 27, 28, 29, 30, 37, 49, 50, 51, 63],
        "重装干员": [6, 7, 27, 28, 29, 30, 49, 50, 51, 63, 68],
        "控场": [8, 13, 24],
        "资深干员": [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
        "快速复活": [13, 37],
        "特种干员": [13, 14, 15, 16, 37, 38, 39],
        "生存": [14, 25, 26, 29, 42, 45, 48, 62],
        "位移": [15, 16, 30, 38, 39],
        "减速": [16, 23, 40, 43, 47, 61],
        "爆发": [19],
        "辅助干员": [22, 23, 24, 43, 61],
        "召唤": [24],
        "新手": [64, 65, 66, 67, 68]
    },
    "avgCharTag":12.275862068965518
}

一下子就变得很直观了呢

2. 计算

需要用到 lodash.combinations

import 'lodash.combinations';
import _ from 'lodash';

let AKDATA; //假设这是上面得到的处理过后的数据

function getChar(i) {
    return AKDATA.characters[i];
}

//tags 是词条数组,例如 ['治疗','新手','削弱']
function getCombinations(tags) {
    //_.combinations 得到所有排列组合方案
    let combs = _.flatMap([1, 2, 3], v => _.combinations(tags, v));

    let result = [];
    for (let comb of combs) {
        //获取需要取交集的词条
        let need = [];
        for (let tag of comb) need.push(AKDATA.data[tag]);

        //_.intersection 取交集
        let chars = _.intersection(...need);

        //如果词条中没有“高级资深干员”则无法招募6星干员,用 _.remove 按指定条件移除
        if (!comb.includes('高级资深干员')) _.remove(chars, i => AKDATA.characters[i].r == 6);
        if (chars.length == 0) continue;

        //计算方案评分,在 graueneko 的基础上有所改进
        //因为多数情况下我们只招募3星及以上干员,因此在评分时可以忽略1星2星
        //_.sumBy 按指定方法求和,_.filter 按指定条件过滤
        let scoreChars = _.filter(chars, i => getChar(i).r >= 3);
        if (scoreChars.length == 0) scoreChars = chars;
        let score = _.sumBy(scoreChars, i => getChar(i).r) / scoreChars.length - comb.length / 10 - scoreChars.length / AKDATA.avgCharTag;

        //得到保底稀有度用于排序
        let minI = _.minBy(scoreChars, i => getChar(i).r);

        result.push({
            comb,
            chars,
            min: AKDATA.characters[minI].r,
            score
        });
    }

    //按保底稀有度和评分进行排序
    result.sort((a, b) => (a.min == b.min ? b.score - a.score : b.min - a.min));
    return result;
}

3. OCR 以及结果生成

至于展示结果的方法,我最开始用的是直接纯文字输出,但是发现这样很不直观甚至还会眼花(

后来我决定仿照 graueneko 的排版生成图片,考虑到 javascript 特色……我去花了半小时现学了下 canvas 就直接用上了,效果大概这样

最终成果可以参考 akhr.jsakhr.draw.js