Поиск ближайшего элемента с Манхэттенским расстоянием не эффективен

Question

У меня есть лабиринт с препятствиями, на котором есть различные «бонусы», расположенные на карте.Это просто цели, которые в конечном итоге должны быть достигнуты.Тем не менее, порядок, в котором они достигаются, имеет значение, так как мы хотим экономить время.

Давайте смоделируем следующую ситуацию:

   0  1  2  3
0 [ ][X][ ][ ]
1 [ ][▣][▣][ ]
2 [ ][P][ ][ ]
3 [ ][▣][Y][▣]
4 [ ][▣][ ][ ]

[▣] is an obstacle.
[X] with position (0,1) is a power-up
[Y] with position (3,2) is a power-up
[P] with position (2,1) is the player. In other words, the starting position

[P] необходимо достичьвверх.

Чтобы решить, какой из них, в настоящее время, я использую Манхэттенское расстояние, чтобы найти ближайший пункт:

abs(a1[0] - a2[0]) + abs(a1[1] - a2[1])

Манхэттенское расстояние вычислит, что расстояние между [P] и [X] равно 2, а расстояние между [P] и [Y] также равно 2. Поэтому он случайным образом выберет один из них, чтобы посетить следующий.

Однако расстояние до Манхэттена не будет учитывать, что существует препятствие между [P] и [X] и, следовательно, фактическое расстояние будет больше.

Таким образом, потребуется четыре шага, чтобы достичь [X]:

(2,1) first step-> (2,0) second step-> (1,0) third-> (0,0) fourth-> (0,1) 

При достижении [Y], будетпросто сделайте 2 шага:

(2,1) first step-> (2,2) second step-> (3,2)

Так как расстояние до Манхэттена в некоторых случаях сделает эту работу за меня, это не будет самый эффективный по времени метод.Кроме того, время является ключевым моментом для меня, так как я хочу в кратчайшие сроки получить все бонусы, чтобы выиграть игру.

Может кто-нибудь подсказать мне, как мне оптимизировать этот или каким-то другим способомиспользовать для вычисления ближайшего предмета с учетом имеющихся у меня препятствий?

Answer 1

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

То, что вы делаете сейчас, довольно хорошо, но есть способ, которым мы можем улучшить это. Вы можете использовать этот метод, чтобы определить расстояние до Манхэттена и количество препятствий на нем:

def manhattan_d_obstacles(grid, x1, y1, x2, y2):
    obs_count = 0
    if x1 > x2:
        x_range = range(x2, x1)
    else:
        x_range = range(x1, x2)
    if y1 > y2:
        y_range = range(y1, y2)
    else:
        y_range = range(y2, y1)
    for i in x_range:
        for j in y_range:
            if grid[i, j] == 'obstacle':
                obs_counter += 1
    return {
        "dist": abs(x1 - x2) + abs(y1 - y2),
        "obs": obs_counter
    }

Теперь вы можете просто использовать этот метод для сравнения манхэттенских расстояний и количества препятствий на этом пути. Итак:

best = {
    "dist": float("inf"), # int("inf") does not exist
    "obs": float("inf") # int("inf") does not exist
}
for pwu in power_ups:
    path = manhattan_d_obstacles(P['x'], P['y'], pwu['x'], pwu['y'])
    if path['dist'] < best['dist']:
        best = path
    elif path['dist'] == best['dist'] and path['obs'] < best['obs']:
        best = path

Эта функция обычно выполняется быстрее, чем вычисление фактического расстояния в случае, если фактический маршрут отличается от маршрута на Манхэттен (т. Е. Что такое P -> Y в вашем примере). В противном случае он работает с той же скоростью.