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

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

python プログラミング

前回のあらすじ。。。

…最短経路を求められたは良いが、どうやってその場所までの道順(座標)を求めれば良いのか分からなくて積みました!

答えは簡単だった。その場所までの最短経路は求められているのだから、ゴールから数が少ない順にたどれば、スタートにたどり着く。スタートから辿ろうとするからプログラミングの闇に落ちるのだ。

こんな当たり前のことに気がつくまでまた1日使ってしまった。悲しい現実である。

なんとか解決したので、動かしてみる。街から街へせっせと往復するNPC…うむ。頑張って作ったかいがあった。

水を垂らしたようにアルゴリズムが広がっていくさまがなんとも壮観である。

ただ、めっちゃ重い。10*10のマップなら実用レベルだけど、それ以上にすると凄まじく計算時間が必要になってしまう。ここは改善すべき点だな。マップは15 * 50くらいは欲しい。。。

どうやったら改善できるのか…また苦難の日々が続きそうだ。

最後にソースコード

main.py

from field import Field
from caravan import Caravan
from player import Player


if __name__ == '__main__':
        field = Field()
        player = Player(field)
        anzio_caravan = Caravan(field, (4, 5), (7, 8))
        roma_caravan = Caravan(field, (2, 2), (4, 5))
        while 1:
            # gameループ
            player.is_movable()
            anzio_caravan.is_movable()
            roma_caravan.is_movable()

player.py

class Player(object):
    def __init__(self, field):
        """ 初期化時にマップ関連を処理しとく """
        self.__field = field
        self.__grid_stack = []  # 座標のデータを格納する
        self.__y = self.__field.height // 2  # 現在位置の縦軸
        self.__x = self.__field.width // 2  # 現在位置の横軸
        self.__grid_stack.append(self.__field.field[self.__y][self.__x])   # 現在の座標の位置データをバックアップ
        self.__field.field[self.__y][self.__x] = 2  # 現在位置を設定
        self.__vision_ratio = 3  # 視界の範囲

    def is_movable(self):
        """ 移動を管理する関数 """
        # self.__field.field_print()
        self.__field.visibility_print(self.__y, self.__x, self.__vision_ratio)
        self.__field.field[self.__y][self.__x] = self.__grid_stack.pop()  # 現在位置を元のデータに戻す
        command = input("移動先を入力して下さい。1:上 2:右 3:下 4:左")

        if command == "1":
            if self.__field.field[self.__y - 1][self.__x] != -1:
                self.__y -= 1
        elif command == "2":
            if self.__field.field[self.__y][self.__x + 1] != -1:
                self.__x += 1
        elif command == "3":
            if self.__field.field[self.__y + 1][self.__x] != -1:
                self.__y += 1
        elif command == "4":
            if self.__field.field[self.__y][self.__x - 1] != -1:
                self.__x -= 1
        else:
            print("貴方は待機しました...")

        self.__grid_stack.append(self.__field.field[self.__y][self.__x])  # 移動後のマップの数値を格納しておく
        self.__field.field[self.__y][self.__x] = 2  # 移動後にマップに自分自身を入れる

caravan.py

class Caravan(object):
    def __init__(self, field, grid, target):
        self.__field = field
        self.__grid_stack = []  # 座標のデータを格納する
        self.__y = grid[0]
        self.__x = grid[1]
        self.__target_y = target[0]
        self.__target_x = target[1]
        self.__source = [self.__y, self.__x]
        self.__dist = [self.__target_y, self.__target_x]
        self.__height = 10
        self.__width = 10
        self.__grid_stack = []  # 座標のデータを格納する
        self.__grid_stack.append(self.__field.field[self.__y][self.__x])  # 現在の座標の位置データをバックアップ
        self.__field.field[self.__y][self.__x] = 3

    def is_movable(self):
        """ 移動を管理する関数。 """
        self.__field.field[self.__y][self.__x] = self.__grid_stack.pop()  # 現在位置を元のデータに戻す
        route = self.dijkstra((self.__y, self.__x), (self.__target_y, self.__target_x))
        route.remove([self.__y, self.__x])  # 現在地を削除。
        next_grid = route[0]
        self.__grid_stack.append(self.__field.field[next_grid[0]][next_grid[1]])  # 移動後のマップの数値を格納しておく
        self.__field.field[next_grid[0]][next_grid[1]] = 3  # 移動後にマップに自分自身を入れる
        self.__y = next_grid[0]
        self.__x = next_grid[1]

        if self.__y == self.__target_y and self.__x == self.__target_x:
            self.__target_y = self.__source[0]
            self.__target_x = self.__source[1]
            self.__source = [self.__y, self.__x]
            self.__dist = [self.__target_y, self.__target_x]

    def dijkstra(self, *args):
        """ ダイクストラ法を使って最短経路を求める。 """
        impact_map = [[0 for x in range(self.__width)] for y in range(self.__height)]
        # 評価用のマップ。10 * 10のマップ。

        for x in range(self.__height):
            for y in range(self.__width):
                if x != 0 and y != 0 and x != self.__height - 1 and y != self.__width - 1:
                    impact_map[x][y] = 99999  # 最大値
                else:
                    impact_map[x][y] = -1  # 番兵(見えない壁)
        score = 0  # 現在のスコア
        grid = args[0]
        target = args[1]
        y = grid[0]
        x = grid[1]
        node = len(impact_map)  # ノードの数

        impact_map[y][x] = score
        score += 1
        if impact_map[y - 1][x] != -1:
            impact_map[y - 1][x] = score
        if impact_map[y][x + 1] != -1:
            impact_map[y][x + 1] = score
        if impact_map[y + 1][x] != -1:
            impact_map[y + 1][x] = score
        if impact_map[y][x - 1] != -1:
            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:
                        if duplicate_data[0] >= 1 and duplicate_data[1] >= 1:
                            uniq_list.append([duplicate_data[0], duplicate_data[1]])
            grid_list = uniq_list.copy()  # 固有の値のみをリストとして保持。
            temp_list = []
            uniq_list = []
            if self.get_result(impact_map):
                break
        return self.find_path(impact_map, grid, target)

    def find_path(self, impact_map, grid, target):
        """ 目的地までの座標を返す関数 """
        y = grid[0]
        x = grid[1]
        target_y = target[0]
        target_x = target[1]
        target = impact_map[target_y][target_x]
        pos = []
        pos.append([target_y, target_x])
        while 1:
            if impact_map[target_y - 1][target_x] == target - 1:
                if impact_map[target_y - 1][target_x] != -1:
                    pos.append([target_y - 1, target_x])
                    target_y = target_y - 1
                    target_x = target_x
            elif impact_map[target_y][target_x + 1] == target - 1:
                if impact_map[target_y][target_x + 1] != -1:
                    pos.append([target_y, target_x + 1])
                    target_y = target_y
                    target_x = target_x + 1
            elif impact_map[target_y + 1][target_x] == target - 1:
                if impact_map[target_y + 1][target_x] != -1:
                    pos.append([target_y + 1, target_x])
                    target_y = target_y + 1
                    target_x = target_x
            elif impact_map[target_y][target_x - 1] == target - 1:
                if impact_map[target_y][target_x - 1] != -1:
                    pos.append([target_y, target_x - 1])
                    target_y = target_y
                    target_x = target_x - 1
            else:
                return pos[::-1]
            target -= 1

    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):
        """ フィールドの評価を行う関数。-1のセルは評価しないようにする。
         上下左右に走査を行い、scoreよりマップのセルの値が高いならば更新。
         """
        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()

field.py

class Field(object):
    def __init__(self):
        self.height = 10  # 縦幅
        self.width = 10  # 横幅
        self.field = [[0 for x in range(self.width)]for y in range(self.height)]  # マップの初期化

        for x in range(self.height):
            for y in range(self.width):
                if x != 0 and y != 0 and x != self.height - 1 and y != self.width - 1:
                    self.field[x][y] = 0  # 平原
                else:
                    self.field[x][y] = -1  # 番兵(見えない壁)
        self.field[2][2] = 1  # ローマ(街)
        self.field[4][5] = 1  # アンティウム(街)
        self.field[7][8] = 1  # コンスタンティノープル(街)

    def field_print(self):
        """ 視界外のマップも全て表示するデバッグ用関数 """
        for x in range(self.height):
            for y in range(self.width):
                if self.field[x][y] == 0:
                    print("・", end='')
                elif self.field[x][y] == -1:
                    print("#", end='')
                elif self.field[x][y] == 1:
                    print(">", end='')
                elif self.field[x][y] == 2:
                    print("*", end='')
                elif self.field[x][y] == 3:
                    print("N", end='')
            print()  # 改行用

    def visibility_print(self, y_vision, x_vision, vision_ratio):
        """ 視界を制御して表示する関数 """
        for y in range(self.height):
            for x in range(self.width):
                if self.field[y][x] == -1:
                    print("#", end='')  # 見えない壁
                elif (y_vision - vision_ratio) <= y <= (y_vision + vision_ratio) and\
                        (x_vision - vision_ratio) <= x <= (x_vision + vision_ratio):
                    if self.field[y][x] == 0:
                        print("・", end='')
                    elif self.field[y][x] == 1:
                        print(">", end='')
                    elif self.field[y][x] == 2:
                        print("@", end='')
                    elif self.field[y][x] == 3:
                        print("N", end='')
                else:
                    print("?", end='')  # 視界外
            print()  # 改行用