配列をソートする

Papyrusで配列をソートする時に調べたことをまとめます。

Papyrusにおけるソートの事情

Papyrusは以下の制約があります。

• Papyrusは多次元配列がありません。
• Papyrusは配列をソートする関数がありません。
• Papyrusは変数を入れ替える関数がありません。
• Papyrusは参照渡しができません。

用意されていないものに関しては、SKSEのライブラリを利用するか、Papyrusのコードを書いて実装する必要があります。

ソートに使うアルゴリズム

アルゴリズムは色々ありますが、 ゲームなので速いことが重要になります。アルゴリズム自体が良いことも大切ですが、Papyrus特有の仕様によるボトルネックもあるでしょうから、実際のところは試してみないとわかりません。

アルゴリズムに関してはソートを極める！ 〜 なぜソートを学ぶのか 〜を参考にさせていただきました。

バブルソート

最も単純で理解しやすくコードも書きやすいので、ソートと言ったらとりあえずはこれになると思います。CK Wikiにもソートの例としてサンプルコードが示されています。

欠点は遅いことですが、1日1回実行するかどうかという頻度であれば、たいした問題にはなりません。

クイックソート

速くしたいときは、とりあえずこれを使っておけばいいみたいです。

関数を再帰的に呼び出すという部分がPapyrusでどれほどのボトルネックになるのかが気になるところです。

変数の入れ替え

ないものはないので仕方なくPapyrusで実装します。

一時的な変数を用意して3つの変数の間で値を代入していきます。

変数の入れ替え (papyrus)

Int i = 10
Int j = 20

; iとjを入れ替えたい
Int k = i ; i = 10, j = 20, k = 10
i = j ; i = 20, j = 20, k = 10
j = k ; i = 20, j = 10, k = 10


多次元配列の扱い

ないものはないので仕方なくPapyrusで実装します。

一次元配列を複数用意して、それぞれの配列でソートをします。

例として、Actorをプレイヤーからの距離が近い順にソートするとします。アルゴリズムはバブルソートです。

多次元配列のソート (papyrus)

Actor[] Function MySort(Actor[] akActors)
    Int len = akActors.Length
    Float[] fDistances = Utility.CreateFloatArray(len)

    ; Actorとプレイヤーとの距離を取得する
    Actor kPlayerRef = Game.GetPlayer()
    Int i = len

    while i > 0
        i -= 1
        fDistances[i] = kPlayerRef.GetDistance(akActors[i])
    endwhile

    ; 距離の近い順に並び替える
    i = 0

    while i < len - 1
        Int j = 1

        while j < len - i
            if fDistances[j] < fDistances[j - 1]
                ; 距離の配列の入れ替え
                Float f = fDistances[j]
                fDistances[j] = fDistances[j - 1]
                fDistances[j - 1] = f

                ; Actorの配列の入れ替え
                Form k = akActors[j]
                akActors[j] = akActors[j - 1]
                akActors[j - 1] = k
            endif

            j += 1
        endwhile

        i += 1
    endwhile

    return akActors
EndFunction


多次元配列をクイックソートする例

クイックソート用の関数を定義します。

関数の引数に参照渡しが使えないため、関数の戻り値として1つの配列しか受け取れず、そのため配列はスクリプト内スコープにして処理します。

クイックソートの例 (papyrus)

Function QuickSort(int left, int right)
    if right - left <= 1
        return
    endif

    ; 適当にpivotを選ぶ
    int pivot_index = (left + right) / 2
    float pivot = FoodLimits[pivot_index]

    ; pivotを右端に移しておく
    int j = right - 1
    float l
    FoodLimits[pivot_index] = FoodLimits[j]
    FoodLimits[j] = pivot
    form k = FoodForms[pivot_index]
    FoodForms[pivot_index] = FoodForms[j]
    FoodForms[j] = k
    int c = FoodCounts[pivot_index]
    FoodCounts[pivot_index] = FoodCounts[j]
    FoodCounts[j] = c

    ; iもjも左端からスタート
    int i = left
    j = left
    while j < right - 1
        if FoodLimits[j] < pivot
            l = FoodLimits[i]
            FoodLimits[i] = FoodLimits[j]
            FoodLimits[j] = l
            k = FoodForms[i]
            FoodForms[i] = FoodForms[j]
            FoodForms[j] = k
            c = FoodCounts[i]
            FoodCounts[i] = FoodCounts[j]
            FoodCounts[j] = c

            i += 1
        endif
        j += 1
    endwhile

    j = right - 1
    l = FoodLimits[i]
    FoodLimits[i] = FoodLimits[j]
    FoodLimits[j] = l
    k = FoodForms[i]
    FoodForms[i] = FoodForms[j]
    FoodForms[j] = k
    c = FoodCounts[i]
    FoodCounts[i] = FoodCounts[j]
    FoodCounts[j] = c

    QuickSort(left, i)
    QuickSort(i + 1, right)
EndFunction


実行してみます。検証用に実行にかかった時間を表示しています。

クイックソートの実行例 (papyrus)

Form[] FoodForms ; 食べ物のFormが一覧で入っている
Int[] FoodCounts ; 食べ物の個数が一覧で入っている
Float[] FoodLimits ; 食べ物の賞味期限（ゲーム内時間）が一覧で入っている

Function SortFood()
    Float fStart = Utility.GetCurrentRealTime()

    ; 配列の要素数が20個の場合
    QuickSort(0, 20)

    debug.trace("SortFood: sort time = " + (Utility.GetCurrentRealTime() - fStart) as string)
EndFunction


結果は、バブルソートが0.19～0.24秒、クイックソートが0.17秒前後でした。