【GB】ゲームボーイでライフゲームを実装しました

ゲームボーイソフトを作成の練習のために、gbdkを使ってライフゲームを実装しました。

例えば今後は以下のようなことがしたいと考えています。

• NES（ファミコン）向けに作成されたmmlファイルを、GBソフトに変換(トランスコンパイル?)して再生したい
  • いろいろな経緯で、実機で楽曲を演奏する場合、GBではLSDjやnanoloop等の専用ソフトで作曲することが多いのに対し、NESではWindowsでFamiTracker等で作曲したソフトを再生するのが主流だそうです
  • 既に「GameBoy Music Compiler」もあるのですが、凝った曲がうまく再生できませんでした
• 何らかのアルゴリズムでPC上で音楽を生成して、USB→通信ケーブル経由で再生したい
• ついでにゲームボーイ用のゲームソフトを作ってみたい（かっこいい）

sakana38.hatenablog.com

LIFEGAMEを実装した意図

サンプル実装として「ある程度実装方法が想像ついて、適度に難しい」課題を探していました。

ja.wikipedia.org

この本にMITでライフゲームを実装したハッカーの話が出てきたのでそれを参考にしています。

ハッカーズ

以前プログラマーの友達に相談したところ「新しい言語を学ぶ時、けっこういろいろなことをしなきゃいけない簡単なLisp処理系を実装している」と聞いたのですが、そもそもゲームボーイでプログラム（文字列）を打ち込むのは言語処理系そのものより入力処理が難しそうなので、最初に何を実装するのか悩んでいました。ちょうどいいアイデアが見つかってよかったです。

実装したもの

ソフトはこちらです。エミュレータ等で試してみてください。

drive.google.com

最初にランダムに配置し続けて、初期値を決めています。ランダム配置なのは「とりあえず完成して達成感を得る」ために手を抜いているためです。

スタートボタンを押し続けるとライフゲームが始まります。大抵、だんだん数と減って動きも無くなってくるので悲しい気分になります。

Bボタンを押し続けるとランダム配置モードの戻ります。

今後の展望

インタラクティブに黒丸を配置したいのですが、「時間のかかる描画中の合間にしかボタンの押下をチェックしていない」ので、「しばらく押し続けないとライフゲームモード」に遷移しない状態になっています。

実際にゲームボーイのCPUにも割り込み処理が存在し、GBDKにもその機能があるのですが、ドキュメントの意味が分からないのと、他の人の実装を見てもよくわかんないので困っています。

gbdk.sourceforge.net

あまり実装方針や用語が分からないので、ひたすら大学（母校）の図書館で「組み込み系プログラミングの割り込み処理」のことを書いた本を探して、この本を買ってしまいました。

12ステップで作る組込みOS自作入門

ついでにこれも買いました。

低レベルプログラミング

正直OSより低レイヤーの話は今までほとんど知らなくてけっこう楽しいのですが、正直100%役に立たないと思ってるので、会社の同僚（真面目な人が多い）には黙ってこっそりやっています。大目に見てください。

ソースコード

コードはだいたいこんな感じです。まだC言語の実装に慣れていないので、けっこういろいろツッコミどころあると思います。

github.com

コードが今後もどんどん変わっていく可能性高いので貼っておきます。

#include <gb/gb.h>
#include <gb/drawing.h>
#include <rand.h>

#define RADIUS 2
#define X_MIN 4
#define X_MAX 156
#define X_NODES (X_MAX - X_MIN) / 8 + 1
#define Y_MIN 4
#define Y_MAX 140
#define Y_NODES (Y_MAX - Y_MIN) / 8 + 1

UBYTE current_map[X_NODES][Y_NODES] = {0};
UBYTE next_map[X_NODES][Y_NODES] = {0};


void init(void);
void init_map(void);
void update_map(void);
UBYTE count_neighbors(UBYTE i, UBYTE j);
void draw(void);
enum State {
    INPUT,
    DRAW
};


int main(void) {
    enum State state = INPUT;
    init();
    while (1) {
        switch (state) {
            case INPUT:
                init_map();
                draw();
                state = (joypad() == J_START) ? DRAW : INPUT;
                break;
            case DRAW:
                draw();
                update_map();
                state = (joypad() == J_B) ? INPUT : DRAW;
                break;
            default:
                break;
        }
    }
}


void init(void) {
    UBYTE x1, y1;
    for (x1 = X_MIN; x1 <= X_MAX; x1 += 8) {
        line(x1, Y_MIN, x1, Y_MAX);
        delay(16);
    }

    for (y1 = Y_MIN; y1 <= Y_MAX; y1 += 8) {
        line(X_MIN, y1, X_MAX, y1);
        delay(16);
    }

    for (x1 = X_MIN; x1 <= X_MAX; x1 += 8) {
        for (y1 = Y_MIN; y1 <= Y_MAX; y1 += 8) {
            color(WHITE, WHITE, SOLID);
            circle(x1, y1, RADIUS, M_FILL);
            delay(1);
        }
    }
}


void init_map(void) {
    UBYTE i, j;
    for (i = 0; i < X_NODES; i++) {
        for (j = 0; j < Y_NODES; j++) {
            current_map[i][j] = rand() % 2;
        }
    }
}


void update_map(void) {
    UBYTE count, i, j;
    for (i = 0; i < X_NODES; i++) {
        for (j = 0; j < Y_NODES; j++) {
            count = count_neighbors(i, j);
            if (current_map[i][j]) {
                if (count <= 1 || count >= 4) {
                    next_map[i][j] = 0;
                } else {
                    next_map[i][j] = 1;
                }
            } else {
                if (count == 3) {
                    next_map[i][j] = 1;
                } else {
                    next_map[i][j] = 0;
                }
            }
        }
    }

    for (i = 0; i < X_NODES; i++) {
        for (j = 0; j < Y_NODES; j++) {
            current_map[i][j] = next_map[i][j];
        }
    }
}


UBYTE count_neighbors(UBYTE i, UBYTE j) {
    UBYTE k, l;
    UBYTE result = 0;
    for (k = 0; k < 3; k++) {
        for (l = 0; l < 3; l++) {
            if (k == 1 && l == 1) continue;
            if (i + k == 0 || i + k >= X_NODES) continue;
            if (j + l == 0 || j + l >= Y_NODES) continue;
            result += current_map[i + k - 1][j + l - 1];
        }
    }
    return result;
}


void draw(void) {
    UBYTE i, j;
    for (i = 0; i < X_NODES; i++) {
        for (j = 0; j < Y_NODES; j++) {
            color(current_map[i][j] ? BLACK : WHITE, WHITE, SOLID);
            circle(i * 8 + 4, j * 8 + 4, RADIUS, M_FILL);
        }
    }
}

【Python】クラス内のプライベート変数の名前解決方法についての調査

モジュールの外からアクセスするクラス( from sample import SampleClass )のために、以下のようなモジュール内のprivateな関数に利用するコードを書いていました。

# sample.py
class SampleClass(object):
    def public_method(self):
        __private_function()

def __private_function():
    print("ok")

if __name__ == "__main__":
    instance = SampleClass()
    instance.public_method()

そうすると次のようなエラーが出ました。どうやら"__"が冒頭につく変数の探索時に、自動的に '_SampleClass__private_function' という名前に置き換えられています。

docs.python.org

今まで self.__private_method() みたいに呼び出す場合だけ名前の置き換えが発生すると思っていたので少々びっくりしました。初めて知ったのですが、名前マングリング( name mangling )と呼ぶそうです。

$ python sample.py 
Traceback (most recent call last):
  File "sample.py", line 14, in <module>
    instance.public_method()
  File "sample.py", line 3, in public_method
    __private_function()
NameError: global name '_SampleClass__private_function' is not defined

実験

ここで気になるのが通常のローカル変数がセットされる時点でも、同様に名前がマングリングされているのかということです。そこで以下のサンプルコードで実験してみました。 locals は、そのスコープのローカル変数を辞書として取得する関数です。

class ExampleClass(object):
    def public_method(self):
        __val = 1
        print(locals())

if __name__ == "__main__":
    instance = ExampleClass()
    instance.public_method()

結果、 '_ExampleClass__val' に名前が書き換えられていることが分かります。

$ python sample.py 
{'_ExampleClass__val': 1, 'self': <__main__.ExampleClass object at 0x10dd12310>}

また、外の関数名を _SampleClass__private_function に直したちょっと無理やりな感じのコードも動作しました。

# sample.py
class SampleClass(object):
    def public_method(self):
        __private_function()

def _SampleClass__private_function():
    print("ok")

if __name__ == "__main__":
    instance = SampleClass()
    instance.public_method()

クラスではなく、関数だとどうでしょうか？

def main():
    __val = 1
    print(locals())


if __name__ == "__main__":
    main()

こちらは名前が置き換えられていません。

$ python sample.py
{'__val': 1}

まとめ

というわけで、Pythonのクラス内のプライベートな変数（"__"がつくもの）は以下のような挙動をすることが確認できました。

• クラス内の変数の宣言時にも探索時に名前が置き換えられた上で動作する
• クラス外ではこのような動作をしない

実は公式ドキュメントにも該当する項目はありました。「コードが生成される前により長い形式に変換されます」とあるので、実行前のASTの変換処理あたりで挟まれてるんじゃないかと思います。

docs.python.org

プライベートな名前のマングリング: クラス定義内に書かれた識別子で、2つ以上のアンダースコアから始まり、末尾が2つ以上のアンダースコアで終わっていないものは、そのクラスの プライベートな名前 とみなされます。プライベートな名前は、コードが生成される前により長い形式に変換されます。この変換によって、クラス名の先頭にアンダースコアがあれば除去し、先頭にアンダースコアを1つ付加し、名前の前に挿入されます。

【Rust】Rustで数値計算プロジェクトを試す その11

振動子の減衰系で、rulinalgの練習も兼ねて実装してみました。この場合のケースならいちいちクロージャ使う必要はなかったですね。

kiito.hatenablog.com

若干ハマった点としては、 rulinalg::vector::Vector<f64> * f64 は実行されるものの、 f64 * rulinalg::vector::Vector<f64> はコンパイルエラーになることです。あまり調べてないですが、組み込み型に他の型引数でtraitを実装するってできないのかな。

#[macro_use]
extern crate rulinalg;

use rulinalg::vector::Vector;

use gnuplot::{Figure, Caption, Color};


const M: f64 = 1.0;
const K: f64 = 1.0;
const A: f64 = 2.0;
const X0: f64 = 0.0;
const V0: f64 = 1.0;
const DELTA_T: f64 = 0.01;


fn main() {
  let mut vsp = Vector::new(vec![X0, V0]);
  let mut xs = vec![];
  let mut ts = vec![];

  for i in 1..1000 {
    let t = (i as f64) * DELTA_T;
    ts.push(t);
    xs.push(vsp[0]);
    vsp += rk4(&vsp, |vsp| {
      &matrix![0.0, 1.0; - K / M, - A / M] * vsp
    });
  }

  plot(ts, xs);
}

fn rk4<F>(vsp: &Vector<f64>, f: F) -> Vector<f64>
    where F : Fn(&Vector<f64>) -> Vector<f64> {
  let k1 = &(f(vsp) * DELTA_T);
  let k2 = &(f(&(vsp + k1 / 2.0)) * DELTA_T);
  let k3 = &(f(&(vsp + k2 / 2.0)) * DELTA_T);
  let k4 = &(f(&(vsp + k3)) * DELTA_T);
  (k1 + k2 * 2.0 + k3 * 2.0 + k4) / 6.0
}

fn plot(x: Vec<f64>, y: Vec<f64>) {
  let mut fg = Figure::new();
  fg.set_terminal("pngcairo", "output.png");
  fg.axes2d()
    .lines(&x, &y, &[Caption("A line"), Color("black")]);
  fg.show();
}

結果です。

【Rust】Rustの行列計算ライブラリについて調べる

この間までLotka-Volterraの方程式をRustで解いて勉強していましたが、そろそろPythonの numpy.ndarray のような行列計算を楽にする機構が欲しくなります。

もちろん、実際のソースコードで使われているライブラリ(crate)が良いです（メンテナンスされておらず、最新のコンパイラで動作しない場合もあるようなので…）。ということでまずはawesome-rustにある機械学習ライブラリの依存ライブラリをつてに探してみます。

github.com

AtheMathmo/rusty-machine

Rustの機械学習ライブラリだそうです。依存ライブラリはこんな感じ。

[dependencies]
num = { version = "0.1.41", default-features = false }
rand = "0.4.1"
rulinalg = { git = "https://github.com/AtheMathmo/rulinalg", rev = "1ed8b937" }

いきなり見つかりました。ちゃんと調べていないですが、逆行列(inverse)の計算も行えるようです。

github.com

A linear algebra library written in Rust https://crates.io/crates/rulinalg

avinashshenoy97/RusticSOM

こちらでは別のライブラリが使われています。

[dependencies]
rand = "0.4"
ndarray = "0.11"

github.com

こちらは追加のライブラリでシリアライゼーション( serde-1 )や並列化( rayon )、実験的のようですがblasの利用などできるみたいです。

autumnai/leaf

[dependencies]
collenchyma = { version = "0.0.8", default-features = false, features = ["native"] } # native feature to read/write data into tensors
collenchyma-blas = { version = "0.2.0", default-features = false, features = ["native"] } # only compiles with native feature
collenchyma-nn = { version = "0.3.2", default-features = false }

log = "0.3.2"
rand = "0.3.0"
num = "0.1"

capnp = "0.6.2"

timeit = "0.1.2"

clippy = { version = "0.0.41", optional = true }

[build-dependencies]
capnpc = "0.6.1"

こちらもまた別のライブラリに依存しています。

github.com

Provides a simple and unified API to run fast and highly parallel computations on different devices such as CPUs and GPUs, accross different computation languages such as OpenCL and CUDA and allows you to swap your backend on run-time.

OpenCLやCUDA等の計算言語をまたがって、統一的なAPIでCPUやGPU上で計算できるcrateのようです。ただ、以下の2017年の記事の時点で開発が止まっているようで、Githubのコミットログを見ても最近は開発されていないようです。

qiita.com

Leafはフレームワークのコアの部分までRustで書かれていたのですが、当時はRustでCPU/GPUで高速に行列演算できるライブラリがなく、ディープラーニングのコアの部分(計算グラフの構築, 微分計算の記述, backward/update)自体よりもバックエンドの行列演算のライブラリ利用・開発に難儀していたようです。

そのような状況でTensorFlowのRustバインディングが公開され、Autumnの開発者がLeafの開発を停止したのですが、TensorFlowのRustバインディングは学習済みのモデルをloadしてinferenceに使用できるだけというもので、実際にはPythonなど他の言語でモデルの開発・学習・保存する必要があり、Leafの開発の中止は非常に残念でした。

tensorflow/rust

有名なニューラルネットワークのライブラリ tensorflow のRustバインディング。

[dependencies]
libc = "0.2.43"
aligned_alloc = "0.1.3"
num-complex = { version = "0.2.1", default-features = false }
tensorflow-sys = { version = "0.15.0", path = "tensorflow-sys" }
byteorder = "1.2.7"
crc = "1.8.1"

どうやらlibc経由でC言語（C++?）を呼び出していて、自前で行列計算は実装していないように見えます。

maciejkula/rustlearn

[dependencies]
rand = "0.3"
crossbeam = "0.2.9"
serde = "1.0"
serde_derive = "1.0"

どうやらこのライブラリ自体でdense / sparse matricesの実装がされているようです。

参考

どうやら、いまのところPythonにおける numpy のような、デファクトスタンダードにまでなっているライブラリは無いようですね。この辺りから、自分にとって使いやすいものがどれか試してみたいと思います。

• AtheMathmo/rulinalg
• rust-ndarray/ndarray
• maciejkula/rustlearn

また、Rust自体の進化が激しく、ライブラリの情報がすぐに古くなっていて最新情報が分かりづらいのは、言語初心者としてはけっこうつらいですね…。これは新興のプログラミング言語なのである程度は仕方ないかもしれませんが。

【Rust】Rustで数値計算プロジェクトを試す その10

中間目標であったLotka-Volterraの方程式がシミュレーションで解けました。

shimaphoto03.com

use gnuplot::{Figure, Caption, Color};


const A: f64 = 0.01;
const B: f64 = 0.05;
const C: f64 = 0.0001;
const X0: f64 = 1000.0;
const Y0: f64 = 100.0;
const DELTA_T: f64 = 0.001;


fn main() {
  let (mut x, mut y) = (X0, Y0);
  let mut xs = vec![];
  let mut ys = vec![];
  let mut ts = vec![];

  for i in 1..500000 {
    let t = (i as f64) * DELTA_T;
    let (dx, dy) = runge_kutta(x, y, |x, y| {
      (
        A * x - C * x * y,
        - B * y + C * x * y
      )
    });
    x += dx;
    y += dy;
    ts.push(t);
    ys.push(y);
    xs.push(x);
  }

  plot(xs, ys);
}

fn runge_kutta<F>(x: f64, v: f64, f: F) -> (f64, f64) 
    where F : Fn(f64, f64) -> (f64, f64) {
  let df = |x, v| {
    let (rx, rv) = f(x, v);
    (rx * DELTA_T, rv * DELTA_T)
  };
  let (k1x, k1v) = df(x, v);
  let (k2x, k2v) = df(x * k1x / 2.0, v + k1v / 2.0); 
  let (k3x, k3v) = df(x + k2x / 2.0, v + k2v / 2.0);
  let (k4x, k4v) = df(x + k3x, v + k3v);
  (
    (k1x + 2.0 * k2x + 2.0 * k3x + k4x) / 6.0,
    (k1v + 2.0 * k2v + 2.0 * k3v + k4v) / 6.0
  )
}

fn plot(x: Vec<f64>, y: Vec<f64>) {
  let mut fg = Figure::new();
  fg.set_terminal("pngcairo", "output.png");
  fg.axes2d()
    .lines(&x, &y, &[Caption("A line"), Color("black")]);
  fg.show();
}

x ウサギ（被食者）の個体数、y キツネ（捕食者）の数が、相平面上でどんな軌道を描いているのか分かります。

【Rust】Rustで数値計算プロジェクトを試す その9

以前のコードを改造して、 x と v それぞれで微分方程式を指定できるようにしました。クロージャ便利ですね。

use gnuplot::{Figure, Caption, Color};


const K: f64 = 1.0;
const M: f64 = 1.0;
const A: f64 = 2.0;
const X0: f64 = 0.0;
const V0: f64 = 1.0;
const DELTA_T: f64 = 0.01;


fn main() {
  let (mut x, mut v) = (X0, V0);
  let mut xs = vec![];
  let mut ts = vec![];

  for i in 1..1000 {
    let t = (i as f64) * DELTA_T;
    let (dx, dv) = runge_kutta(x, v, |x, v| {
      (
        v,
        (- K * x - A * v) / M
      )
    });
    x += dx;
    v += dv;
    ts.push(t);
    xs.push(x);
  }

  plot(ts, xs);
}

fn runge_kutta<F>(x: f64, v: f64, f: F) -> (f64, f64) 
    where F : Fn(f64, f64) -> (f64, f64) {
  let df = |x, v| {
    let (rx, rv) = f(x, v);
    (rx * DELTA_T, rv * DELTA_T)
  };
  let (k1x, k1v) = df(x, v);
  let (k2x, k2v) = df(x * k1x / 2.0, v + k1v / 2.0); 
  let (k3x, k3v) = df(x + k2x / 2.0, v + k2v / 2.0);
  let (k4x, k4v) = df(x + k3x, v + k3v);
  (
    (k1x + 2.0 * k2x + 2.0 * k3x + k4x) / 6.0,
    (k1v + 2.0 * k2v + 2.0 * k3v + k4v) / 6.0
  )
}

fn plot(x: Vec<f64>, y: Vec<f64>) {
  let mut fg = Figure::new();
  // fg.set_terminal("pngcairo", "output.png");
  fg.axes2d()
    .lines(&x, &y, &[Caption("A line"), Color("black")]);
  fg.show();
}

【Rust】Rustで数値計算プロジェクトを試す その8

昨日のやつから、関数の中で x と y を += するように変更すれば、多少コードがスッキリするんじゃないかと思ってやってみました。

ミュータブルな参照で渡して、参照を外して…って感じなので書きづらい。多分間違った道に来たと思うので引き返します。

stackoverflow.com

use gnuplot::{Figure, Caption, Color};


const K: f64 = 1.0;
const M: f64 = 1.0;
const A: f64 = 2.0;
const X0: f64 = 0.0;
const V0: f64 = 1.0;
const DELTA_T: f64 = 0.01;


fn main() {
  let (mut x, mut v) = (X0, V0);
  let mut xs = vec![];
  let mut ts = vec![];

  for i in 1..1000 {
    let t = (i as f64) * DELTA_T;
    runge_kutta(&mut x, &mut v, |x, v| {
      - K * x - A * v
    });
    ts.push(t);
    xs.push(x);
  }

  plot(ts, xs);
}

fn runge_kutta<F>(x_ref: &mut f64, v_ref: &mut f64, f: F) where F : Fn(f64, f64) -> f64 {
  let x = *x_ref;
  let v = *v_ref;
  let k1v = f(x, v) * DELTA_T / M;
  let k1x = v * DELTA_T;
  let k2x = (v + k1v / 2.0) * DELTA_T; 
  let k2v = f(x + k1x / 2.0, v + k1v / 2.0) * DELTA_T / M;
  let k3v = f(x + k2x / 2.0, v + k2v / 2.0) * DELTA_T / M;
  let k3x = (v + k2v / 2.0) * DELTA_T;
  let k4v = f(x + k3x, v + k3v) * DELTA_T / M;
  let k4x = (v + k3v) * DELTA_T;
  *v_ref += (k1v + 2.0 * k2v + 2.0 * k3v + k4v) / 6.0;
  *x_ref += (k1x + 2.0 * k2x + 2.0 * k3x + k4x) / 6.0;
}

fn plot(x: Vec<f64>, y: Vec<f64>) {
  let mut fg = Figure::new();
  // fg.set_terminal("pngcairo", "output.png");
  fg.axes2d()
    .lines(&x, &y, &[Caption("A line"), Color("black")]);
  fg.show();
}