Python3でRPGを作る時に使えそうな技術の断片 -経路探索の切り替えを出来るようにしよう-

f:id:sakage24:20170719010301j:plain

これまでの記事で、いくつかの最短経路アルゴリズムを作成しました。今回は状況に合わせてアルゴリズムを切り替えて、少しでも計算量を軽減しましょう。

今まで作ったアルゴリズム

A*法

A*法は目標座標までの最短距離地形の評価から(ヒューリスティック値とも言います)最短距離を求めるアルゴリズムです。ダイクストラ法とよく似ていますが、ダイクストラ法は探索地点から水を零したように広がり、全ての座標までのルートを返します。

対してA*法は目標となる座標に対して、一直線に探索を行います。壁にぶつかった場合は迂回しつつ目標に向かってくれます。

https://www.kiwi-bird.xyz/2017/07/17/20170717183403/

ブレゼンハムのアルゴリズム

ブレゼンハムのアルゴリズムは、目標となる座標までの正確な最短距離を返します。多少複雑ですが、A*法より軽量です。

https://www.kiwi-bird.xyz/2017/07/15/20170715160456/

LOS追跡

目標となる座標に対して、自身の座標を加減算して目標に近づきます。非常に単純ですが、その分軽量です。

https://www.kiwi-bird.xyz/2017/07/04/20170704184604/

まあ、基本的にA*法を使っていれば問題ないのですが、高機能故に処理が複雑なのが問題です。ソースコードの量からして重そうですよね。そして、これらのアルゴリズムはプレイヤーが移動するごとに再計算を行う必要があります。ですから、状況に応じて軽量なLOS追跡、障害物を避けられるA*法を切り替えて使えるようにしましょう。

経路探索の切り替え

NPCの座標とプレイヤーとの間に、障害物が存在するならA*法を、障害物が存在しないならLOS追跡を使いましょう。

これを判断するには、正確な直線距離を求める必要がありますが、ブレゼンハムのアルゴリズムがこの問題を解決してくれます。

擬似言語っぽく解説


def bresenham()  # ブレゼンハムのアルゴリズム
....
def los()  # LOS追跡
....
def a_star()  # A*法
....
def switch_move():
if プレイヤーを発見済みか?
routes = bresenham()
for route in routes:
# プレイヤーの座標と、NPCとの座標間の最短距離に障害物があるならA*法を使う
if ワールドマップ[route[0]][route[1]] = 障害物
results = a_star()  # 障害物があるならA*法を使おう
自身の座標位置 = results
return 
# 障害物がないなら、軽量なLOS追跡を使おう
los()
switch_move()

ソースコードをだらだら書いても多分訳分からないと思うので、擬似言語で表現しました。引数とかは各自入れて下さいw

これで状況に応じて適切な経路探索を行うことが出来るようになりました…壁を避けられない敵っていうのもなんか物悲しいですよね。

オススメの教科書類

今回紹介しているアルゴリズムはゲーム開発者のためのAI入門で詳しく解説されています。特にA*法に関しては豊富に図を使って解説してくれています。

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

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

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

C言語での解説が主ですが、しっかりとした説明があるので、だいたい分かりました。Pythonでも使える知識がほとんどです。

オススメの教科書
入門 Python 3

入門 Python 3

これ無しでPython開発は無理です。私的にはあまり演習問題の類は解かずに知りたいことがあったら読む、辞書的な感じで使っています。

  • スライスって何?
  • リスト内包表記って何なんだよあれ?
  • リストとタプルはどう違うの?
  • そもそも集合って何に使うの?

少しでも上記に当てはまるなら購入しましょう。せっかくPythonを使っているんですから、有効に使えるようにしてみませんか?

副読本
Effective Python ―Pythonプログラムを改良する59項目

Effective Python ―Pythonプログラムを改良する59項目

  • 他言語を得意としているプログラマがPythonを書いた時にやりがちなこと…
  • ゲームの保存に使えるpickle
  • この機能はこう使うべきである
  • while, for文のelseを使うべきではない理由
  • Pythonでセッター, ゲッターを使うべきではない理由

みたいに、様々な事例とともにPythonのベストノウハウ、やってはいけないアンチパターンが紹介されています。pycon2016でも確か推されてましたw

初心者から上級者まで、手元に置いておくべき本です。

副読本2
退屈なことはPythonにやらせよう ―ノンプログラマーにもできる自動化処理プログラミング

退屈なことはPythonにやらせよう ―ノンプログラマーにもできる自動化処理プログラミング

ノンプログラマー向けとありますが、経験者の方も結構アイディアを貰える本でした。
序盤は文法の解説ですので、読み飛ばせます。後半は様々な局面で使えそうな自動化処理の書き方が載っていました。

ゲームの所持アイテムを辞書で表現しよう…みたいにゲームプログラマーに役立つ演習もありましたw

終わり

次は何をしようか…皆さん、Pythonで作るエロいオープンワールド型のRPGって興味ありませんか?w

コメントを残す

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