パルワールド: 親Aと親BからターゲットCを生成する交配パスを見つけるプログラムを作ってみた

はじめに

パルワールドおもしろいね。
交配システムもなかなかユニークで、親Aのパワー + 親Bのパワー / 2に近いパワーを持つパルが生まれるというのが基本的なシステムです。　（ただし例外もいるようです。）

ゲームをやっていると今持っているオスのパルとメスのパルや、引き継がせたいスキルを持っているパルから目的のパルに辿り着きたいという欲が生まれました。

そこで、以下のようなプログラムを作ってみました。試してみたい方や利用したい方は以下のREADMEを確認ください。
https://github.com/Soyukke/palpath
※近いパワーを持つパルが複数いるときの仕様は考慮してないのでこのプログラムはたびたび間違いを生成すると思います
※仕様を完璧に把握していないので、間違いを実装しているかもしれません

dot形式で出力しているので以下のように描画できます。（この例があっているか未確認です）

見つけかた

以下のようなアルゴリズムで見つけることを考えました。

1. 親セットAと親セットBから子のセットs0を生成する
2. s_next以降は確率でオスかメスを必ず生成できるとして、s: (親セットA + 親セットB)とs0からs1を生成します。子の中でターゲットのパルが生まれたらターゲットのリストに追加します。
3. s+s0をsとして、s1をs0として繰り返します

そして、パルの構造を以下のように木構造で定義してあげればターゲットのパルまでのグラフを記述できます。

pub struct PalNode {
    pub name: String,
    pub parents: Option<(Box<PalNode>, Box<PalNode>)>,
}

例外

• 例外1. パルパワーの距離が同一のパルが複数いる場合は、idが小さい方が生まれる
• 例外2. 組み合わせが特殊なパルは、その組み合わせでしか生まれないので、パルパワーの距離を比較するときにこのパルは無視する。

これで以下のようになる。

cargo run -- combine -p ヘルガルダ -q ライバード

結果
ヘルガルダ      x       ライバード      =       ライバード

ヘルガルダとライバードの間にはエレパンダとルナクインが存在するがそれらは例外1に該当するので省く。
ヘルガルダとライバードのパワーの和/2に近いのはヘルガルダとライバードだが、ライバードの方がidが若いのでそちらが生まれる。

使用例

ヘルガルダに神速，走るのが得意を引き継がせたいのでそれらのスキルを持っているパルを引数に与える。
オスにヘルガルダ，グラクレス
メスにライバード，パピテフ，ブルフェルノがあって，この中から配合してヘルガルダを作りたい。

palpath tree -m ヘルガルダ,グラクレス -f ライバード,パピテフ,ブルフェルノ -t ヘルガルダ

出力結果

digraph PalNode {
  node [shape=box];
  ヘルガルダ [label="ヘルガルダ"];
  ヘルガルダ [label="ヘルガルダ"];
  ルナクイン [label="ルナクイン"];
  デスティング [label="デスティング"];
  ヘルガルダ [label="ヘルガルダ"];
  グラクレス [label="グラクレス"];
  ヘルガルダ [label="ヘルガルダ"];
  パピテフ [label="パピテフ"];
  ヘルガルダ -> グラクレス;
  パピテフ -> グラクレス;
  ヘルガルダ -> デスティング;
  グラクレス -> デスティング;
  リリクイン [label="リリクイン"];
  ササゾー [label="ササゾー"];
  ヘルガルダ [label="ヘルガルダ"];
  ライコーン [label="ライコーン"];
  ブルフェルノ [label="ブルフェルノ"];
  シーペント [label="シーペント"];
  グラクレス [label="グラクレス"];
  ブルフェルノ [label="ブルフェルノ"];
  グラクレス -> シーペント;
  ブルフェルノ -> シーペント;
  ブルフェルノ -> ライコーン;
  シーペント -> ライコーン;
  ヘルガルダ -> ササゾー;
  ライコーン -> ササゾー;
  フラリーナ [label="フラリーナ"];
  ブルフェルノ [label="ブルフェルノ"];
  フブキツネ [label="フブキツネ"];
  ブルフェルノ [label="ブルフェルノ"];
  イヌズマ [label="イヌズマ"];
  ブルフェルノ [label="ブルフェルノ"];
  ライコーン [label="ライコーン"];
  ブルフェルノ [label="ブルフェルノ"];
  シーペント [label="シーペント"];
  グラクレス [label="グラクレス"];
  ブルフェルノ [label="ブルフェルノ"];
  グラクレス -> シーペント;
  ブルフェルノ -> シーペント;
  ブルフェルノ -> ライコーン;
  シーペント -> ライコーン;
  ブルフェルノ -> イヌズマ;
  ライコーン -> イヌズマ;
  ブルフェルノ -> フブキツネ;
  イヌズマ -> フブキツネ;
  ブルフェルノ -> フラリーナ;
  フブキツネ -> フラリーナ;
  ササゾー -> リリクイン;
  フラリーナ -> リリクイン;
  デスティング -> ルナクイン;
  リリクイン -> ルナクイン;
  ヘルガルダ -> ヘルガルダ;
  ルナクイン -> ヘルガルダ;
}

こんな感じで今持っているパルから目的のパルを作る方法がわかる。

おわり