ローグライクゲームの敵の行動について...

Question

いま、Unityでローグライクゲームを製作しております。
その際に、敵の行動として障害物を避けつつ最短距離でプレイヤーに近づくような処理を用いりたいのですが
自分の知識ではどう行えばいいのか全く分からず、右記サイトを参考にしても全く分かりませんでした。　　こちら

今は簡易的に、障害物がない状態でXとYどちらが遠いか判断し、
Xが遠いかったらX+1、Yが遠かったらY+1、という風に近づけています。

アルゴリズムでも何でもいいので知識をくれたらいいなと思っています。
こんな変な質問で申し訳ありません。
ご回答お待ちしております。

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

public class AStar : MonoBehaviour
{

    bool roadPass;
    public int[,] charaPos;

    void Start()
    {
        charaPos = new int[GameController.Instance.maxHeight, GameController.Instance.maxWidth];    //マップ探索用の二次元配列

        for (int i = 0; i< GameController.Instance.mapTilesBox.GetLength(0); i++)
        {
            for (int j = 0; j< GameController.Instance.mapTilesBox.GetLength(1); j++)
            {
                if (GameController.Instance.LayerName(i, j) == "Obstacle")  //移動不可能な場所は‐1
                {
                    charaPos[i, j] = -1;
                }
                else　                                                      //0で初期化
                {
                    charaPos[i, j] = 0;
                }
            }
        }

        charaPos[GameController.Instance.enemyPosition.x, GameController.Instance.enemyPosition.y] = 1; //敵のスタート地点を1とする

    }
}

Answer 1

kabanさん回答のダイクストラ法ですが・・・
結局のところA*もダイクストラ法の考え方の応用で、ダイクストラ法で用いる「経路」が各格子の間にはりめぐらされていると想定したアルゴリズムだと思います。

A*では最適化前提でアルゴリズムが述べられてますが、最適化をせずに「どういう戦略なのか」を考えてみるとわりと単純であることがわかります。

(1) マップを格子に見立てて探索用の二次元配列を考える。
(2) 全部0で初期化(ただし、移動不可能な場所は-1など特別な値を入れておく)
(3) スタート地点を1にする
(4) 0の格子の中で隣に1以上の値を持つ格子を見つける(これをnextということにします)
(5) nextの周りの格子を調べ最も小さい数Nを求めnextの値をN+1に書き換える

(4)<->(5)を繰り返しつつ、(4)がゴールの格子だったときが最短経路を見つけたことになります。具体的な最短経路はゴールの数値がMだとするとその格子の周りをみてM-1の格子を見つけ、さらのその格子の周りをみてM-2の格子を見つけ・・・を1の格子(つまりスタート)が見つかるまで繰り返せばよいです。

要するに「格子の数値はスタート地点からその格子へたどり着くための最短経路の距離」だと思えばよいです。また初期化する際の「0」という値にはそれほどの意味はなく「最短経路の距離」と区別できる値なら何でもよいでしょう。

---

最適化について：
上記はA*の戦略の基本部分を述べたものです。比較的小さな領域なら上記のままでもよいと思います。ただ領域が大きくなってくると以下のような最適化の必要性が高まると思います。

• A*と上の論理の違い

A*と上の論理の違いは、(4)で「最もゴールに近そうな格子から先に調べる」という工夫をしているだけです。ただ計算量的には大変重要な工夫です！

• (4)のnextの見つけ方

毎回二次元の格子を端から順番に調べるという素朴な方法もありますが、領域が大きめになってくると計算量が問題になってきます。例えばスタート地点やnextに値を書き込むとき、その周りの0の格子を調べてそれをキューに入れると効果的と思います。そうしておくと、キューに入る格子の数はたかだか数個ですので、全部の格子を調べるよりはるかに高速にnextを見つけられます。
(実際問題として10x10程度の領域であれば大した問題ではありません。しかし100x100ぐらいになると1stepあたり10000回、最短経路を見つけるまでに最悪100万回オーダーのスキャンが必要になるためこうした工夫も考えたくなります)

Comments

[Zuishin]

最もゴールに近そうな格子から先に調べる工夫をしているのは A* 法の方で、上の論理の方が効率が悪いんですよね？
最初それを逆に読んでしばらく考え込んでしまいました。

A* 法より効率が悪いけど単純で実装し易い方法の提案ということですね？

[KSwordOfHaste]

ご指摘ありがとうございます。
質問者さんが「A*がわからなかった」とのことで、最初は確かに「基本アイデアは割と単純です」というつもりだったのですが・・・
最後の方で「最適化は必要」といってしまっているせいで、何を主張しているのか支離滅裂になっていますね・・・
---
後半の説明の表現を若干工夫してみました。

[Zuishin]

ありがとうございました。A* 法を使ったことがなかったので簡単な迷路探索を作って遊んでみましたが、未踏破の部分が残っているのに最短距離が出るのが面白いですね。

[KSwordOfHaste]

抽象的な探索アルゴリズムそのものは幾分退屈ですが、本件のように実際に適用できる場面に遭遇すると俄然興味がわきますよね。これが領域の塗りつぶしアルゴリズムに通じる（あるいは変形？）のように見えるのも自分には面白く感じる点だったりします(塗りつぶしなんて普通自分では書きませんが・・・w;）

[mymsmpb_love]

ご回答ありがとうございます。
今、(3)まではできたのですが(4)からがちょっとよくわからないのですが、
もう少し簡易的に教えていただけませんか？？
ごめんなさい。。。

[KSwordOfHaste]

プログラムを完成するには

(A)戦略構想（アルゴリズムの外郭）を考え
(B)そのための戦術（プログラム言語での実装）を考え
(C)デバッグしておかしなところを直し
(D)性能的に不満ながあったら改良できないか工夫する・・・

などなど完成するまで多くの段階をクリアせねばなりません。本回答は(A)にあたり「最短経路をみつける戦略の概略」を示そうとしたものです。質問者さんは(A)から(B)へ進むところに課題があるようですが、その粒度で回答やコメントを付けるとＱ＆Ａが長くなりすぎると思います。

ご自分の課題をもっと絞り込み、詰まっている点をピンポイントで具体的に質問してみてはいかがでしょう？そのためには別途質問を挙げることをお奨めします。その際には(4)を「どう捉えたか」「どの点が不明か」を詳しく書いてみてください。そうすれば適切なアドバイスがつくと思います。

「ちょっとよくわからない」とのことですが、閲覧側にも具体的にどこがわからないのか見えません。

０の格子を見つける
その格子の周りの格子を調べる
周りの格子に１以上のものが一つでもあるかを調べる
周りの格子の１以上の値のうち最小のもの（＝Ｎ）を調べる

このぐらいの粒度で「どこまでがわかってどこがわからないのか」を明示するようにしてください。そうしないと「動くコードを示す」より他に回答のしようがなくなります。

[mymsmpb_love]

わかりました、A-Starについてもう少し調べてから質問することにします。
ありがとうございました。

[KSwordOfHaste]

kabanさんのサンプルは非常に素直かつ平易に書かれていると思います。A-Startの考え方を理解しつつ、こうしたサンプルコードをじっくり解き明かしていくときっと参考になると思います。最初は少し難しく感じるかも知れませんが、他の人が書いたコードを理解するというのは実力をつけるのにもってこいですよ。

Answer 2

A*より簡単なダイクストラ法がおすすめです。

---

サンプルを書いてみました。
ご参考ください。

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

public class DijkstraSample : MonoBehaviour {
	class Node {
		public int x;
		public int y;
		public bool wall;
		public int cost;
		public bool done;
		public Node prev;

		public Node(int x, int y, bool wall) {
			this.x = x;
			this.y = y;
			this.wall = wall;
			cost = -1;
			done = false;
			prev = null;
		}
	}

	void Start() {
		int w = 5;
		int h = 5;
		int[,] map = new int[,] {
			{ 0, 1, 0, 0, 0 },
			{ 0, 0, 0, 1, 0 },
			{ 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0 },
			{ 0, 0, 0, 1, 0 }
		};

		Node[,] nodes = new Node[h, w];
		for (int y = 0; y < h; y++)
			for (int x = 0; x < w; x++)
				nodes [y, x] = new Node (x, y, map [y, x] == 1);

		int sx = 0; // 現在地x。
		int sy = 0; // 現在地y。
		nodes [sy, sx].cost = 0;
		while (true) {
			Node currNode = null;
			for (int y = 0; y < h; y++) {
				for (int x = 0; x < w; x++) {
					Node node = nodes [y, x];
					if (node.done || node.cost == -1)
						continue;
					if (currNode == null || node.cost < currNode.cost)
						currNode = node;
				}
			}
			if (currNode == null)
				break;
			currNode.done = true;
			for (int dy = -1; dy <= 1; dy++) {
				for (int dx = -1; dx <= 1; dx++) {
					if (dx == 0 && dy == 0)
						continue;
					int x = currNode.x + dx;
					int y = currNode.y + dy;
					if (x < 0 || y < 0 || x >= w || y >= h)
						continue;
					Node node = nodes [y, x];
					if (node.wall)
						continue;
					int newCost = currNode.cost + 1;
					if (node.cost == -1 || newCost < node.cost) {
						node.cost = newCost;
						node.prev = currNode;
					}
				}
			}
		}

		int gx = 4; // 目的地x。
		int gy = 4; // 目的地y。
		Node tempNode = nodes [gy, gx];
		while (tempNode != null) {
			Debug.Log (string.Format ("x:{0} y:{1}", tempNode.x, tempNode.y));
			tempNode = tempNode.prev;
		}
	}
}

Comments

[mymsmpb_love]

サーっと読んでみたのですがさっぱりよくわからないですごめんなさい...涙

[Zuishin]

書くのにかかったと思われる時間くらいはかけましたか？

[umyu]

＞mymsmpb_loveさんへ
もしもJavaScriptが分かるなら、以下の記事の解説はソースコードを読むときの参考になりませんか？
■[アルゴリズム] ダイクストラ法をやってみる
https://qiita.com/edo_m18/items/0588d290a19f2afc0a84

[mymsmpb_love]

Javaはまだ勉強してないですが、参考にさせていただきます。ありがとうございます。