Блог

Главная - Вопросы по программированию - К каким локациям может получить доступ данный игрок?

К каким локациям может получить доступ данный игрок?

#c# #algorithm #unity3d

#c# #алгоритм #unity3d

Вопрос:

Если у вас есть, скажем, график 4 на 4, расположите фигуры следующим образом.

Таблица примеров

Чего я хочу добиться, так это того, что когда я нажимаю на одну из фигур, я хочу видеть все ходы, доступные для данной фигуры, которые не требуют перемещения через другую. Например,

Возможные ходы

Каков наилучший способ выполнить это программно? Я делаю это в Unity, но больше всего мне любопытно увидеть алгоритм для этого.

Комментарии:

1. Звучит как проблема маршрутизации в лабиринте, проверьте алгоритм Ли в качестве примера en.m.wikipedia.org/wiki/Lee_algorithm . У вас просто нет целевого местоположения — повторяйте цикл до тех пор, пока у вас не будет места для перемещения (точки не будут отмечены).

2. Похоже, вам нужен DFS.

Ответ №1:

DFS — это простой алгоритм, который может достичь того, чего вы хотите.

Это работает так:

 DFS(x, y):
    mark[x, y] = true
    for i = -1 ... 1:
        for j = -1 ... 1:
            if (x   i) < 0 || (x   i) >= columns  //outside of matrix
                continue
            if (y   j) < 0 || (y   j) >= rows     //outside of matrix
                continue 
            if mark[x   i, y   j]                 //already seen
                continue
            if matrix[y   j, x   i] is empty
                print("You can go to position ("   (y   j)   ", "   (x   i) ")");
                DFS(x   i, y   j)

Он просмотрит все доступные слоты и предоставит их вам.

Вы можете запустить его, позвонив DFS(column, row) со своей начальной позиции.