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

Python3.5.2でRPGを制作する② ~ダイクストラアルゴリズム編~

python プログラミング

祝!ダイクストラ法の導入成功

パフパフ~!(自分で祝う

苦難の末、ダイクストラ法を用いたマッピングが出来るようになりました。

なんかめっちゃ時間掛かるけど気のせいだよね

外部ライブラリ(networksとか)使ってみたり、qiitaに公開されてるアルゴリズムいじってみたり、色々してみたんだけど、なかなか合わなかったり、ブラックボックスな部分が多かったりで、結局自作することに。地獄への入り口であった

http://notame.hatenablog.com/entry/dijkstras-algorithm-sample

こちらの説明がとても簡潔で、なんと画像まで乗っけているので、とっても分かりやすかったです。

あと、絵が可愛くて癒やされました。

ソースコードもあったのですが、javascriptなのでさっぱり分からず、画像と文章から想像して作ることに。

anzio_caravan.py

class AnzioCaravan(object):
    def __init__(self, field, y=4, x=5):
        self.__field = field
        self.__grid_stack = []  # 座標のデータを格納する
        self.__y = y
        self.__x = x
        self.__height = 10
        self.__width = 10
        self.__grid_stack = []  # 座標のデータを格納する
        self.__grid_stack.append(self.__field.field[self.__y][self.__x])  # 現在の座標の位置データをバックアップ
        self.__field.field[y][x] = 3

    def is_movable(self):
        """ 移動を管理する関数。 """
        impact_map = self.dijkstra(self.__x, self.__y)
        self.dijkstra_print(impact_map)

    def dijkstra(self, *args):
        """ ダイクストラ法を使って最短経路を求める。 """
        impact_map = [[0 for x in range(self.__width)] for y in range(self.__height)]  # 評価用のマップ。15 * 50のマップ。
        for x in range(self.__height):
            for y in range(self.__width):
                if x != 0 and y != 0 and x != self.__width - 1 and y != self.__height - 1:
                    impact_map[x][y] = 99999  # 最大値
                else:
                    impact_map[x][y] = -1  # 番兵(見えない壁)
        score = 0  # 現在のスコア
        y = args[1]
        x = args[0]

        impact_map[y][x] = score
        score += 1
        impact_map[y - 1][x] = score
        impact_map[y][x + 1] = score
        impact_map[y + 1][x] = score
        impact_map[y][x - 1] = score
        grid_list = [[y - 1, x], [y, x + 1], [y + 1, x], [y, x - 1]]
        temp_list = []
        uniq_list = []

        while 1:
            # フィールドの評価ループ
            score += 1
            for z in grid_list:
                self.impact_field(z, score, impact_map)
                temp_list.append([z[0] - 1, z[1]])
                temp_list.append([z[0], z[1] + 1])
                temp_list.append([z[0] + 1, z[1]])
                temp_list.append([z[0], z[1] - 1])
                for duplicate_data in temp_list:
                    # 重複データの除去
                    if duplicate_data not in uniq_list:
                        uniq_list.append(duplicate_data)
                grid_list = uniq_list.copy()
            temp_list = []
            uniq_list = []
            if self.get_result(impact_map):
                break
        return impact_map

    def get_result(self, impact_map):
        """ ボードが全て埋まっていたらTrueを返す """
        score = 0
        for y in range(self.__height):
            for x in range(self.__width):
                if impact_map[y][x] == 99999:
                    score += 1
        if score == 0:
            return True
        else:
            return False

    def impact_field(self, grid, score, impact_map):
        """ フィールドの評価を行う関数。 """
        if grid[0] < 0:
            grid[0] = 0  # 範囲外の参照防止
        elif grid[0] > self.__height - 2:
            grid[0] = self.__height - 2

        if grid[1] < 0:
            grid[1] = 0  # 範囲外の参照防止
        elif grid[1] > self.__width - 2:
            grid[1] = self.__width - 2

        if impact_map[grid[0] + 1][grid[1]] > score:
            impact_map[grid[0] + 1][grid[1]] = score

        if impact_map[grid[0]][grid[1] + 1] > score:
            impact_map[grid[0]][grid[1] + 1] = score

        if impact_map[grid[0] - 1][grid[1]] > score:
            impact_map[grid[0] - 1][grid[1]] = score

        if impact_map[grid[0]][grid[1] - 1] > score:
            impact_map[grid[0]][grid[1] - 1] = score

    def dijkstra_print(self, impact_map):
        """ ダイクストラ法で評価したマップの評価値を表示する関数 """
        for y in range(self.__height):
            for x in range(self.__width):
                if impact_map[y][x] == 99999:
                    print("*", end='')
                elif impact_map[y][x] == -1:
                    print("#", end='')
                elif impact_map[y][x] == 0:
                    print('0', end='')
                elif impact_map[y][x] == 1:
                    print('1', end='')
                elif impact_map[y][x] == 2:
                    print('2', end='')
                elif impact_map[y][x] == 3:
                    print('3', end='')
                elif impact_map[y][x] == 4:
                    print('4', end='')
                elif impact_map[y][x] == 5:
                    print('5', end='')
                elif impact_map[y][x] == 6:
                    print('6', end='')
                elif impact_map[y][x] == 7:
                    print('7', end='')
                elif impact_map[y][x] == 8:
                    print('8', end='')
                elif impact_map[y][x] == 9:
                    print('9', end='')
                else:
                    print(impact_map[y][x], end='')
            print()

一つ問題あって、最短経路を求められたはいいんですが、どうやって移動させればいいのかが分からないwwww

おかしいな。ここクリアしたら楽勝だと思ったんだけど。とりあえず一段落ついたので、風呂入ってリフレッシュします。乙!