神代綺凛

[Lodash] 明日方舟公开招募计算器的简单实现
水文章(x
扫描右侧二维码阅读全文
22
2019/05

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

水文章(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 以及结果生成

  • 可以使用 ocr.space 的免费 API,每日 500 次够用了,但是效果不太好
  • 可以使用 百度OCR,高精度识别每日也免费 500 次,效果更好

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

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

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

搬瓦工VPS优惠套餐,建站稳如狗,支持支付宝,循环出账94折优惠码BWH3HYATVBJW
年付$47CN2线路,1核/1G内存/20G硬盘/1T@1Gbps【点击购买
季付$47CN2 GIA线路,1核/1G内存/20G硬盘/1T@2.5Gbps【点击购买
Last modification:December 5th, 2019 at 12:46 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment Cancel reply

19 comments

  1. Kun  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 86.0.4240.198(Google Chrome 86.0.4240.198)
    好耶!虽然但是,avgCharTag 有点意义不明(不
    1. 神代綺凛  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 96.0.4664.45(Google Chrome 96.0.4664.45)
      @Kun 灰格猫当初用的排序逻辑,总之是照搬了
  2. Zero  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 75.0.3770.80(Google Chrome 75.0.3770.80)
    草(双语),原来你学Canvas是为了做这玩意
    1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 75.0.3770.80(Google Chrome 75.0.3770.80)
  3. zephyru  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
    明日方舟好玩么...听说是萌妹子版植物大战僵尸?
    什么时候再出个vps推荐呀...我今天cloudcone直连官网都打不开了...
    之前从阿里云迁到百度云(便宜)..结果备案了两个月还没好..
    挂cloudcone上没两天整个cloudcone都打不开了...
    感觉人生好艰难呀
    1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
      @zephyru 跟植物大战僵尸差别还是挺大的,都是塔防类游戏而已,形容成萌妹子版保卫萝卜还贴切点

      打不开是因为这几天是敏感时期,每年都有那么几次大姨妈,只是今年的比较严重,等一段时间就好了

  4. kiri  Windows 7(Windows 7) / Firefox 60.0(Firefox 60.0)
    请问博主你首页文章显示的样式是怎么做到的
    1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
      @kiri 看右上角留言板 FAQ
  5. Noob  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
    node真好玩∠( ᐛ 」∠)_
    1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
      @Noob 好玩的
  6. Nanami  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
    艹,个个都是博士
    你域名在哪买的,像moe这类
    1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
      @Nanami 可以看看 porkbun
  7. WeiYuan  Windows 10 x64 Edition(Windows 10 x64 Edition) / Firefox 67.0(Firefox 67.0)
    最近在看《JavaSctipt 入门经典》,看见上面的操作一脸懵逼
    1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
      @WeiYuan JavaSctipt 从入门到懵逼
      1. WeiYuan  Windows 10 x64 Edition(Windows 10 x64 Edition) / Firefox 67.0(Firefox 67.0)
        @神代綺凜 完全不知道怎么入门前端方面的东西,觉得没一点头绪,WebPack,Nodejs,JS,NPM,Vue,BootStrap.......
        一堆,都不知道从何下手。学校选修课教完HTML+CSS基础就不管事了,老师还是那种推荐DW的23333,自己用WebStrom
        1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
          @WeiYuan 可以由浅到深慢慢实践的,我一开始先学 Nodejs 写了这个
          看 BootStrap,尝试做几个静态页面了解UI框架的用法,然后结合 WebPack 做点简单的应用
          后来开始接触 Vue,做了个单页应用

          我的信仰只有一条:vscode 大法好

          1. WeiYuan  Windows 10 x64 Edition(Windows 10 x64 Edition) / Firefox 67.0(Firefox 67.0)
            @神代綺凜 看到你发GitHub链接,我才发现,我一直忘了关注你的GitHub了
            这些项目太强了
            1. 神代綺凜  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
              @WeiYuan 还行吧,主要是每过一段时间回来看自己以前写的代码是会想死的,根本不好维护
          2. Noob  Windows 10 x64 Edition(Windows 10 x64 Edition) / Google Chrome 74.0.3729.169(Google Chrome 74.0.3729.169)
            @神代綺凜 我vscode装了个插件开始写spring项目了,主要是idea的字体太丑了