Operation KiWi

一生使える言語はPythonだと信じてる

Python3でRPGを作る時に使えそうな技術の断片 -ブレゼンハムのアルゴリズム-

f:id:sakage24:20170715154720j:plain

二次元座標間を出来る限り、正確な直線距離で結ぶならブレゼンハムのアルゴリズムがピッタリです。

何故作ったし

ゲーム開発者のためのAI入門に載っていましたが、C言語での解説だったのでPythonバージョンを俺が作ってやるぜ!!的な感じで作りました。

正直、何故これで直線が引けるのかさっぱり分からないけども、何とか動いたので…w 詳しく知りたい方は以下のリンクから購入しましょう!!

もっと頭の良い最短経路アルゴリズム、A*法の書き方も載っていますよ!

ゲーム開発者のためのAI入門

ゲーム開発者のためのAI入門

ソースコード

def bresenham(player_pos=(0, 2), target_pos=(9, 9)):
    path_y = target_pos[0]
    path_x = target_pos[1]
    path = []
    delta_y = player_pos[0] - target_pos[0]
    delta_x = player_pos[1] - target_pos[1]
    while (path_y, path_x) != player_pos:
        if delta_y < 0:
            step_y = -1
        else:
            step_y = 1
        if delta_x < 0:
            step_x = -1
        else:
            step_x = 1

        delta_y = abs(delta_y * 2)
        delta_x = abs(delta_x * 2)

        path.append((path_y, path_x))

        if delta_x > delta_y:
            fraction = delta_y - delta_x / 2
            while path_x != player_pos[1]:
                if fraction >= 0:
                    path_y += step_y
                    fraction -= delta_x
                path_x += step_x
                fraction += delta_y
                path.append((path_y, path_x))
        else:
            fraction = delta_x - delta_y / 2
            while path_y != player_pos[0]:
                if fraction >= 0:
                    path_x += step_x
                    fraction -= delta_y
                path_y += step_y
                fraction += delta_x
                path.append((path_y, path_x))
        return tuple(path)


if __name__ == '__main__':
    import pprint
    pp = pprint.PrettyPrinter()
    maps = [["■" for x in range(10)] for y in range(10)]
    b = bresenham()
    pp.pprint(b)
    for i in b:
        maps[i[0]][i[1]] = "☆"
    pp.pprint(maps)

>>> 実行結果
((9, 9), (8, 8), (7, 7), (6, 7), (5, 6), (4, 5), (3, 4), (2, 4), (1, 3), (0, 2))
[['■', '■', '☆', '■', '■', '■', '■', '■', '■', '■'],
 ['■', '■', '■', '☆', '■', '■', '■', '■', '■', '■'],
 ['■', '■', '■', '■', '☆', '■', '■', '■', '■', '■'],
 ['■', '■', '■', '■', '☆', '■', '■', '■', '■', '■'],
 ['■', '■', '■', '■', '■', '☆', '■', '■', '■', '■'],
 ['■', '■', '■', '■', '■', '■', '☆', '■', '■', '■'],
 ['■', '■', '■', '■', '■', '■', '■', '☆', '■', '■'],
 ['■', '■', '■', '■', '■', '■', '■', '☆', '■', '■'],
 ['■', '■', '■', '■', '■', '■', '■', '■', '☆', '■'],
 ['■', '■', '■', '■', '■', '■', '■', '■', '■', '☆']]

bresenham()関数は求めたい座標と現在の座標を与えてあげると、最短の直線距離を出してくれます。

何故動いているのかよく分かっていないので、分かる方マジで教えてくださいww