взаимная видимость узлов на сетке - PullRequest
Новая
       18

взаимная видимость узлов на сетке

1 голос
/ 06 июля 2019

У меня есть простая сетка, и мне нужно проверить два узла для взаимной видимости. Все координаты стен и узлов известны. Мне нужно проверить два узла для взаимной видимости.

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

Я использовал этот код для проверки узлов на взаимную видимость: 

def finding_vector_grid(start, goal):
    distance = [start[0]-goal[0], start[1]-goal[1]]
    norm = math.sqrt(distance[0] ** 2 + distance[1] ** 2)
    if norm == 0: return [1, 1]
    direction = [(distance[0]/norm), (distance[1]/norm)]
    return direction

def finding_vector_path(start, goal):
    path = [start]
    direction = finding_vector_grid((start[0]*cell_width, start[1]*cell_height),
        (goal[0]*cell_width, goal[1]*cell_height))
    x, y = start[0]*cell_width, start[1]*cell_height
    point = start

    while True:
        if point not in path and in_map(point):
            path.append(point)
        elif not in_map(point):
            break

        x -= direction[0]
        y -= direction[1]
        point = (x//cell_width, y//cell_height)
    return path

def vector_obstacles_clean(path, obstacles):
    result = []
    for node in path:
        if node in obstacles:
            result.append(node)
            break
        result.append(node)
    return result

например: 

path =  finding_vector_path((0, 0), (0, 5))
path = vector_obstacles_clean(path, [(0, 3)])
  1. in_map - проверить, находится ли точка за границей карты;
  2. начало, цель - координаты кортежей ширины x и y;
  3. cell_width, cell_height - переменные типа int с шириной и высотой узла в пикселях (я использую pygame для графика визуализации).

У меня нет проблем с этим методом, но он работает не с графиками, он работает "сам по себе", это не совсем то, что мне нужно. Я плохо разбираюсь в английском, пожалуйста, прости меня:)

1 Ответ

1 голос
/ 06 июля 2019

Код, который вы разместили, кажется очень хорошим, и ваш вопрос не проясняет, что нуждается в улучшении.

Вместо того, чтобы делать арифметику FP для векторов, вы можете предпочесть увеличить целочисленный указатель X или Y на один пиксель ввремя.Подумайте об использовании алгоритма линии Брезенхема , который перечисляет пиксели на линии прямой видимости между start и goal.Ключевое наблюдение состоит в том, что для данного наклона он замечает, будет ли X или Y увеличиваться быстрее, и выполняет цикл по этому индексу.

...