読者です 読者をやめる 読者になる 読者になる

Unityでサーキットを自動生成する

簡単なサーキットを自動生成するスクリプトを作ったのでまとめてみました。完成系はこんな感じです。
f:id:usiatan2:20170415225448p:plain
f:id:usiatan2:20170415225559p:plain

処理の流れ

ランダムに点を配置し、スプライン曲線で補完し点を増やします。そして増やした点をこのサイトのような方法でメッシュを生成させるとサーキットっぽくなるのではないかと考えました。

ランダムに点を配置

処理の内容から考えてこの点がサーキットのコーナー部分になるはずです。つまりコースの形がこの点によって決まります。今回は適当に円周上に配置しましたが、手動で配置してもいいかもしれません。

List<Vector3> points1 = new List<Vector3>();
for (int i = 0; i < _pointCount; i++) {
    float radian = Mathf.PI * 2f * ((float)i / (float)_pointCount) + Random.Range(-0.1f, 0.1f);
    float radius = Random.Range(_minRadius, _maxRadius);
    points1.Add(new Vector3(Mathf.Cos(radian) * radius, 0f, Mathf.Sin(radian) * radius));
}

点を補完

先ほど配置した点を補完して点の数を増やします。補完にはcatmull-rom曲線を使いました。この曲線はコントロールポイントを必要としないのでとても便利です。


a=p_{1}(t^{2}(2-t)-t)\\
b=p_{2}(t^{2}(3t-5)+2)\\
c=p_{3}(t^{2}(4-3t)+t)\\
b=p_{4}(t^{2}(t-1))\\
\displaystyle p_{t}=\frac{a+b+c+d}{2}

Vector3 Spline(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4, float t) {
    Vector3 a = p1 * (t * t * (2 - t) - t);
    Vector3 b = p2 * (t * t * (3 * t - 5) + 2);
    Vector3 c = p3 * (t * t * (4 - 3 * t) + t);
    Vector3 d = p4 * (t * t * (t - 1));
    return (a + b + c + d) / 2f;
}
List<Vector3> points2 = new List<Vector3>();
for (int i = 0; i < points1.Count; i++) {
    Vector3 p1 = points1[(i + points1.Count - 1) % points1.Count];
    Vector3 p2 = points1[i];
    Vector3 p3 = points1[(i + 1) % points1.Count];
    Vector3 p4 = points1[(i + 2) % points1.Count];
    for (float t = 0f; t < 1f; t += 0.05f) {
        points2.Add(Spline(p1, p2, p3, p4, t));
    }
}

セクションを作る

このサイトを参考にしました。まず方向を計算します。ある点p_{i}の方向は、p_{i-1}p_{i+1}の差を正規化したものとします。一つ前と一つ先の点を使うことでちょうどよい中間の方向を得ることができます。そして方向に対して直角の2点を計算します。この2点が道の両脇になります。

public class Section {
    public Vector3 _direction;
    public Vector3 _left;
    public Vector3 _right;
}
List<Section> sections = new List<Section>();
for (int i = 0; i < points2.Count; i++) {
    Vector3 prev = points2[(i + points2.Count - 1) % points2.Count];
    Vector3 curr = points2[i];
    Vector3 next = points2[(i + 1) % points2.Count];
    Section section = new Section();
    section._direction = (next - prev).normalized;
    Vector3 orthogonal = Quaternion.AngleAxis(90f, -Vector3.up) * section._direction;
    section._left = curr - orthogonal * (_roadWidth / 2f);
    section._right = curr + orthogonal * (_roadWidth / 2f);
    sections.Add(section);
}

セクションからにメッシュを作る

同じくこのサイトを参考にしました。それぞれのセクションが保持する方向に対して直角な2点を頂点としてメッシュを構築します。作ったメッシュはMeshColliderにも渡して当たり判定をとれるようにしておきます。

List<Vector3> vertices = new List<Vector3>();
for (int i = 0; i < sections.Count; i++) {
    vertices.Add(sections[i]._left);
    vertices.Add(sections[i]._right);
}
List<int> triangles = new List<int>();
int n = vertices.Count;
for (int i = 0; i < vertices.Count; i += 2) {
    triangles.Add((i + 1) % vertices.Count);
    triangles.Add((i + 3) % vertices.Count);
    triangles.Add((i + 0) % vertices.Count);
    triangles.Add((i + 0) % vertices.Count);
    triangles.Add((i + 3) % vertices.Count);
    triangles.Add((i + 2) % vertices.Count);
}
Mesh mesh = GetComponent<MeshFilter>().mesh;
mesh.Clear();
mesh.vertices = vertices.ToArray();
mesh.triangles = triangles.ToArray();
mesh.RecalculateNormals();
MeshCollider meshCollider = GetComponent<MeshCollider>();
meshCollider.sharedMesh = mesh;

全体のソースコード

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

[RequireComponent(typeof(MeshFilter), typeof(MeshRenderer), typeof(MeshCollider))]
public class Circuit : MonoBehaviour {
    public int _pointCount = 20;
    public float _minRadius = 100f;
    public float _maxRadius = 200f;
    public float _roadWidth = 20f;

    [System.Serializable]
    public class Section {
        public Vector3 _direction;
        public Vector3 _left;
        public Vector3 _right;
    }

    void Start () {
        Generate();
    }

    void Update() {
        if (Input.GetMouseButtonDown(0)) {
            Generate();
        }
    }

    void Generate() {
        List<Vector3> points1 = new List<Vector3>();
        for (int i = 0; i < _pointCount; i++) {
            float radian = Mathf.PI * 2f * ((float)i / (float)_pointCount) + Random.Range(-0.1f, 0.1f);
            float radius = Random.Range(_minRadius, _maxRadius);
            points1.Add(new Vector3(Mathf.Cos(radian) * radius, 0f, Mathf.Sin(radian) * radius));
        }
        List<Vector3> points2 = new List<Vector3>();
        for (int i = 0; i < points1.Count; i++) {
            Vector3 p1 = points1[(i + points1.Count - 1) % points1.Count];
            Vector3 p2 = points1[i];
            Vector3 p3 = points1[(i + 1) % points1.Count];
            Vector3 p4 = points1[(i + 2) % points1.Count];
            for (float t = 0f; t < 1f; t += 0.05f) {
                points2.Add(Spline(p1, p2, p3, p4, t));
            }
        }
        List<Section> sections = new List<Section>();
        for (int i = 0; i < points2.Count; i++) {
            Vector3 prev = points2[(i + points2.Count - 1) % points2.Count];
            Vector3 curr = points2[i];
            Vector3 next = points2[(i + 1) % points2.Count];
            Section section = new Section();
            section._direction = (next - prev).normalized;
            Vector3 orthogonal = Quaternion.AngleAxis(90f, -Vector3.up) * section._direction;
            section._left = curr - orthogonal * (_roadWidth / 2f);
            section._right = curr + orthogonal * (_roadWidth / 2f);
            sections.Add(section);
        }
        List<Vector3> vertices = new List<Vector3>();
        for (int i = 0; i < sections.Count; i++) {
            vertices.Add(sections[i]._left);
            vertices.Add(sections[i]._right);
        }
        List<int> triangles = new List<int>();
        int n = vertices.Count;
        for (int i = 0; i < vertices.Count; i += 2) {
            triangles.Add((i + 1) % vertices.Count);
            triangles.Add((i + 3) % vertices.Count);
            triangles.Add((i + 0) % vertices.Count);
            triangles.Add((i + 0) % vertices.Count);
            triangles.Add((i + 3) % vertices.Count);
            triangles.Add((i + 2) % vertices.Count);
        }
        Mesh mesh = GetComponent<MeshFilter>().mesh;
        mesh.Clear();
        mesh.vertices = vertices.ToArray();
        mesh.triangles = triangles.ToArray();
        mesh.RecalculateNormals();
        MeshCollider meshCollider = GetComponent<MeshCollider>();
        meshCollider.sharedMesh = mesh;
    }

    Vector3 Spline(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4, float t) {
        Vector3 a = p1 * (t * t * (2 - t) - t);
        Vector3 b = p2 * (t * t * (3 * t - 5) + 2);
        Vector3 c = p3 * (t * t * (4 - 3 * t) + t);
        Vector3 d = p4 * (t * t * (t - 1));
        return (a + b + c + d) / 2f;
    }
}

まとめ

アイディアの元となったサイトに感謝です。

独自に三角関数を実装する

大抵のプログラミング言語は標準ライブラリに三角関数が実装されています。今回はそのようなライブラリを使わずに独自に三角関数を実装してみました。pythonで実装しましたが、どの言語でも考え方は同じです。また勉強目的の実装なので実用性は考えていないのであしからず。

sinを近似する

\displaystyle\sin{x}=\sum_{i=0}^{\infty}{(-1)^i\frac{x^{2i+1}}{(2i+1)!}}
sinをマクローリン展開すると上記のような式が求まります。これをコードに落とし込んでみましょう。

def my_sin(x, n):
    result = 0
    for i in range(n):
        sign = math.pow(-1, i)
        frac = math.pow(x, 2 * i + 1) / math.factorial(2 * i + 1)
        result += sign * frac
    return result

三角比の相互関係

\displaystyle\sin^2{\theta}+\cos^2{\theta}=1
\displaystyle\tan{\theta}=\frac{\sin{\theta}}{\cos{\theta}}
上記の公式を見るとわかりますが、sinからcosを求めることができ、sinとcosからtanが求められることがわかります。sinはすでに実装したので、式を変形させて残りのcosとtanを実装しましょう。

def my_cos(x, n):
    cos = math.sqrt(1 - math.pow(my_sin(x, n), 2))
    return (-cos, cos)

def my_tan(x, n):
    sin = my_sin(x, n)
    cos = my_cos(x, n)
    return (sin / cos[0], sin / cos[1])

実験

標準ライブラリに実装されている三角関数と今回作った三角関数に、0.125\piを渡して比較してみました。

print("sin")
print(my_sin(radian, n))
print(math.sin(radian))
print("cos")
print(my_cos(radian, n))
print(math.cos(radian))
print("tan")
print(my_tan(radian, n))
print(math.tan(radian))

n=4

sin
0.3826834317539124
0.3826834323650898
cos
(-0.9238795327644447, 0.9238795327644447)
0.9238795325112867
tan
(-0.4142135615980602, 0.4142135615980602)
0.41421356237309503

n=16

sin
0.3826834323650897
0.3826834323650898
cos
(-0.9238795325112867, 0.9238795325112867)
0.9238795325112867
tan
(-0.41421356237309503, 0.41421356237309503)
0.41421356237309503

まとめ

うまく計算できました。nを大きくすることで精度を高めることができます。

セルオートマトンで洞窟を作る

セルオートマトンを使うと、手軽に洞窟のようなマップを生成することができます。

ランダムに埋める

ある座標が壁かどうかをboolで表現した二次元配列をマップとします。まずマップをランダムに埋め尽くします。今回の例では壁のセルと壁でないセルの比率が同じぐらいになるように設定しました。もちろん壁のセルを多め、もしくは少なめにしてもかまいません。

滑らかに

先ほど作ったランダムなマップをセルオートマトンを使って滑らかにしていきます。有名なセルオートマトンであるライフゲームでは周囲のセルの状況と、自身のセルの状況から次のセルが決定されます。今回は単純に周囲8セルに存在する壁のセルを数え、4セルより多い場合は壁のセル、4セルより少ない場合は壁でないセル、それ以外はそのままとしました。隅っこのセルを調べる際、領域外にアクセスしますが、領域外は壁として扱いました。実際に滑らかになっていく様子を見てみましょう。
n=0
f:id:usiatan2:20170405164427p:plain
n=1
f:id:usiatan2:20170405164439p:plain
n=2
f:id:usiatan2:20170405164447p:plain
n=3
f:id:usiatan2:20170405164454p:plain
n=4
f:id:usiatan2:20170405164529p:plain

繰り返しセルオートマトンを実行することで孤立した小さな壁が消え、ギザギザした壁を滑らかになっています。

ソースコード

import random

class Cave:
    def __init__(self, w, h, n_smooth):
        self.w = w
        self.h = h
        self.data = []
        for y in range(self.h):
            row = []
            for x in range(self.w):
                if x == 0 or y == 0 or x == w - 1 or y == h - 1:
                    row.append(True)
                else:
                    row.append(random.random() < 0.5)
            self.data.append(row)
        
        for i in range(n_smooth):
            self.smooth()
        
    def smooth(self):
        new_data = self.data[:]
        for y in range(self.h):
            for x in range(self.w):
                count = self.wall_count(x, y)
                if count > 4:
                    new_data[y][x] = True
                elif count < 4:
                    new_data[y][x] = False
                else:
                    new_data[y][x] = self.data[y][x]
        self.data = new_data
    
    def wall_count(self, cx, cy):
        count = 0
        for y in range(cy - 1, cy + 2, 1):
            for x in range(cx - 1, cx + 2, 1):
                if x == cx and y == cy:
                    continue
                if self.in_range(x, y):
                    if self.data[y][x]:
                        count += 1
                else:
                    count += 1
        return count
    
    def in_range(self, x, y):
        return 0 <= x < self.w and 0 <= y < self.h

まとめ

手軽にそれっぽい洞窟をつくることができました。ただしゲーム等に使うには、閉塞空間をどうにかする必要があります。それについてはまたの機会に記事を書きたいと思います。

動的計画法入門

動的計画法、いわゆるDPについて少し勉強したのでまとめました。ここではフィボナッチ数列を例に説明していきます。

愚直なフィボナッチ数列の実装

フィボナッチ数列は次のように定義されます。
F_0=0\\F_1=1\\F_{n+2}=F_{n}+F_{n+1}
これをそのままプログラムにするとこうなります。

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n - 1) + f(n - 2)

print(f(6)) # 8

問題なく動きます。このコードでもnが小さい場合特に問題になりません。しかしnが大きくなるにつれて急激に処理に時間がかかるようになります。どのように計算されているのか出力してみましょう。次のようなコードで実験してみました。

def f(n, depth):
    print("{}{}".format(" " * depth, n))
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return f(n - 1, depth + 1) + f(n - 2, depth + 1)

f(6, 0)

出力結果。

6
 5
  4
   3
    2
     1
     0
    1
   2
    1
    0
  3
   2
    1
    0
   1
 4
  3
   2
    1
    0
   1
  2
   1
   0

f(6)からf(5)とf(4)が呼ばれ、f(5)からf(4)とf(3)が呼ばれ…と繰り返し、最終的にf(1)もしくはf(0)になるまで呼び出されていることがわかります。ここで注目して欲しいことは重複が複数あるところです。例えばf(2)は5回も呼ばれれています。このような部分的な計算結果を保存して計算量を減らすことをメモ化と呼び、メモ化は動的計画法の一種です。

計算結果を保存する

cacheという辞書を作って渡されたnがcacheに登録されているか調べ、登録されている場合は辞書の値を返し、登録されていない場合は計算するようにしました。

cache = {0:0, 1:1}
def f_cache(n):    
    global cache
    if n not in cache:
        cache[n] = f_cache(n - 1) + f_cache(n - 2)
    return cache[n]

print(f_cache(6)) # 8

fと同じ計算結果になりました。fと同じように計算の過程を出力して見ましょう。

cache = {0:0, 1:1}
def f_cache(n, depth):
    print("{}{}".format(" " * depth, n))
    global cache
    if n not in cache:
        cache[n] = f_cache(n - 1, depth + 1) + f_cache(n - 2, depth + 1)
    return cache[n]

f_cache(6, 0)

出力結果。

6
 5
  4
   3
    2
     1
     0
    1
   2
  3
 4

すっきりしました。一度計算したnはcacheを使用していることがわかります。

パフォーマンス

fとf_cacheにnを渡した際の、次のようなコードで処理時間を計測しました。

s=time.time()
print(f(n))
print(time.time() - s)
s=time.time()
print(f_cache(n))
print(time.time() - s)

n=25

75025
0.09860038757324219
75025
0.0

n=30

832040
1.1280641555786133
832040
0.0

n=35

9227465
12.561718463897705
9227465
0.0

メモ化をしていないfは爆発的に処理時間が増える一方、メモ化をしたf_cacheは一瞬で処理できていることがわかります。

まとめ

たいした処理でなくても愚直な実装の場合あっという間に計算不可能になってしまいます。気をつけたいですね。

javascriptで識別子に日本語を使う

今まで知らなかったのですが、javascriptでは識別子にunicode文字を使うことができます。つまり日本語が使えるということです。面白そうなので試してみました。

実験

とりあえず本当に動くのか簡単なコードで試してみましょう。

ソースコード

var うにゅー = "いちご大福";
console.log(うにゅー);

出力結果

いちご大福

変数の中身が正しく表示されています。奇妙な感じですが問題なく動きました。次は素数を判定する処理を日本語の識別子で記述してみようと思います。

ソースコード

function 素数ですか(自然数) {
    if (自然数 < 2) {
        return false;
    } else if (自然数 == 2) {
        return true;
    } else if (自然数 % 2 == 0) {
        return false;
    }
    for (var あ = 3; あ <= 自然数 / あ; あ += 2) {
        if (自然数 % あ == 0) {
            return false;
        }
    }
    return true;
}
console.log(素数ですか(2017));

出力結果

true

関数名や引数名に日本語を使っても問題ありません。まるで会話のようですね。わかりやすいのかわかりにくいのか微妙なところです。もっと複雑な例を試したいので、クイックソートを日本語の識別子で記述してみました。ソースコードwikipediaの実装例そのままです。

ソースコード

function 高速整列(配列, 左, 右) {
    if (左 < 右) {
        var あ = 左;
        var い = 右;
        var 中央 = 配列[Math.floor((あ + い) / 2)];
        while (true) {
            while (配列[] < 中央) あ++;
            while (配列[] > 中央) い--;
            if (あ >= い) break;
            var 一時変数 = 配列[];
            配列[] = 配列[];
            配列[] = 一時変数;
            あ++;
            い--;
        }
        高速整列(配列, 左, あ - 1);
        高速整列(配列, い + 1, 右);
    }
}

var 配列 = [9, 2, 4, 8, 1, 3, 7, 5, 6];
高速整列(配列, 0, 配列.length - 1);
console.log(配列);

出力結果

[1, 2, 3, 4, 5, 6, 7, 8, 9]

変数名が日本語の配列に添え字を使ってアクセスしたりプロパティ使ったりしていますが、問題なく動きます。

まとめ

実用性はともかくネタとしては面白いかもしれません。

pythonとPillowで画像処理

pythonで画像処理をするためのライブラリ”Pillow”について少し調べたのでまとめました。

パッケージのインストール

pip install pillowでインストールできます。anacondaをお使いの方はデフォルトでインストールされています。

画像を読み込む

既存の画像から読み込む場合はImage.open(path)、プログラム上で新たに画像を作る場合はImage.new((width, height))と記述します。

ピクセルを操作する

image.getpixel(xy)(r, g, b, a)のようにタプルで座標xyのピクセルの情報が返され、image.putpixel(xy, color)で座標xyのピクセルを置き換えることができます。とりあえずグレイスケールに変換して表示するスクリプトを書いてみましょう。グレイスケール化はとても簡単で、あるピクセルのグレイスケール化した際の値は、0.299R+0.187G+0.114Bと定義されます。またimage.show()で画像を表示することができます。

from PIL import Image

image = Image.open("lena.png").convert("RGBA")

for y in range(image.size[1]):
    for x in range(image.size[0]):
        xy = (x, y)
        p = image.getpixel(xy)
        Y = int(p[0] * 0.299 + p[1] * 0.587 + p[2] * 0.114)
        g = (Y, Y, Y, p[3])
        image.putpixel(xy, g)

image.show()

f:id:usiatan2:20170327124050p:plain
モノクロになりました。

保存する

image.save(path)で保存できます。いろいろとオプションがありますが、今回は割愛します。

図形を描き込む

ImageDraw.Draw(image)が返すImageDrawクラスを操作することで線や多角形をimageに描き込むことができます。以下のコードは縦横100ピクセルの画像に三角形を描きこんでいます

image = Image.new("RGBA", (100, 100))
draw = ImageDraw.Draw(image)
draw.polygon([(50, 0), (0, 100), (100, 100)], fill=(255, 255, 255, 255))

遊んでみる

レナさんをランダムウォークのような軌跡で切り取ってみました。

import math
import random
from PIL import Image, ImageDraw

i1 = Image.open("lena.png").convert("RGBA")
w = i1.size[0]
h = i1.size[1]

i2 = Image.new("RGBA", (w, h))

draw = ImageDraw.Draw(i2)
x = w / 2
y = h / 2
for i in range(50000):
    px = x
    py = y
    while True:
        angle = random.random() * math.pi * 2
        nx = x + math.cos(angle) * 5
        ny = y + math.sin(angle) * 5
        if 0 <= nx < w and 0 <= ny < h:
            x = nx
            y = ny
            break
    draw.line([(int(px), int(py)), (int(x), int(y))],  fill=(0, 0, 0, 255))

i3 = Image.new("RGBA", (w, h))

for y in range(h):
    for x in range(w):
        xy = (x, y)
        p1 = i1.getpixel(xy)
        p2 = i2.getpixel(xy)
        color = (p1[0], p1[1], p1[2], p2[3])
        i3.putpixel(xy, color)

i3.save("lena_.png")

f:id:usiatan2:20170326234553p:plain

まとめ

他にもブレンドやフィルター、ピクセルの統計情報などさまざまな機能が実装されています。公式サイトがかなり充実しているので参考にしましょう。

Markdownを書くならStackEditがおすすめ

Markdownエディターは数多くありますが、その中でもお勧めしたいのがStackEditです。StackEditはブラウザ上で動作するので、os問わず使うことができます。 f:id:usiatan2:20170321153527p:plain

使い方

https://stackedit.io/editorにアクセスします。初めてアクセスした場合、Hello!という取扱説明書のようなMarkdownが開かれていると思います。右上のフォルダをクリックして、New Documentを選択すると新しいMarkdownファイルを書き始めることができます。

読み込みと保存、そして同期

StackEditではローカル環境はもちろんGoogleDrive等に保存することもできます。左上の#をクリックして開くメニューから読み込みや保存を行うことができます。

ローカル環境から読み込み、保存を行う

Import from diskで読み込み、Export to diskで保存できます。保存する際は好きなフォーマットを選ぶことができます。HTMLとして出力したい場合はAs HTMLではなく、Using templateを選ぶと良いかもしれません。Using templateで出力した場合cssやscriptが定義されてるので、プレビューと近い状態で表示できます。

Google driveと同期させる

メニューからSynchronizeを選び、Open from Google driveもしくはSave on Google driveを選択します。初回はGoogleのアカウントがStackEditのアクセスを許可するか聞いてきます。

まとめ

使い勝手が良く尚且つ動作も軽快で最高です。