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

f:id:sakage24:20170715154720j:plain

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

何故作ったし

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

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

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

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

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

  • 作者: David M. Bourg,Glenn Seemann,株式会社クイープ
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2005/01/12
  • メディア: 大型本
  • 購入: 24人 クリック: 395回
  • この商品を含むブログ (77件) を見る

ソースコード


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.append1)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.append2)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.append3)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)
>>> 実行結果
4)9, 9), (8, 8), (7, 7), (6, 7), (5, 6), (4, 5), (3, 4), (2, 4), (1, 3), (0, 2
[['■', '■', '☆', '■', '■', '■', '■', '■', '■', '■'],
['■', '■', '■', '☆', '■', '■', '■', '■', '■', '■'],
['■', '■', '■', '■', '☆', '■', '■', '■', '■', '■'],
['■', '■', '■', '■', '☆', '■', '■', '■', '■', '■'],
['■', '■', '■', '■', '■', '☆', '■', '■', '■', '■'],
['■', '■', '■', '■', '■', '■', '☆', '■', '■', '■'],
['■', '■', '■', '■', '■', '■', '■', '☆', '■', '■'],
['■', '■', '■', '■', '■', '■', '■', '☆', '■', '■'],
['■', '■', '■', '■', '■', '■', '■', '■', '☆', '■'],
['■', '■', '■', '■', '■', '■', '■', '■', '■', '☆']]

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

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

脚注   [ + ]

1, 2, 3. path_y, path_x
4. 9, 9), (8, 8), (7, 7), (6, 7), (5, 6), (4, 5), (3, 4), (2, 4), (1, 3), (0, 2

コメントを残す

メールアドレスが公開されることはありません。