3

Здравствуйте,

Написал алгоритм поиска А* в базовой форме для нахождения пути из 1 ячейки в другую, но мне требуется поиск для группы таких ячеек (т.е составной фигуры из таких ячеек). Можете подсказать, есть ли возможность как-то расширить алгоритм, или надо представлять сразу эту фигуру в виде одной ячейки и перекраивать карту алгоритма под нее?

На данный момент, я имею что-то вроде такого: введите сюда описание изображения

Мне же нужно развить это до этого:введите сюда описание изображения

6
  • Поясните, что Вы имеете в виду под составной фигурой из ячеек? Алгоритм должен только по определённым ячейкам искать путь? Надеюсь нет, а то это не сложно.
    – AivanF.
    Commented 3 мая 2016 в 7:12
  • как вы определяете может ли ячейка/группа ячеек переместиться в соседнюю ячейку?
    – Grundy
    Commented 3 мая 2016 в 11:40
  • @Grundy У меня есть список, где содержатся "закрытые" ячейки. Поэтому, при итерации A*, когда рассматриваются соседи ячейки с наименьшей стоимостью, я просто не беру во внимание соседей, которые находятся в этом списке. Повторюсь, алгоритм у меня работает пока только для 1 ячейки, а хотелось бы для группы.
    – spartaneg
    Commented 3 мая 2016 в 11:46
  • один из вариантов - проверять что все ячейки фигуры не попадают на закрытые
    – Grundy
    Commented 3 мая 2016 в 11:51
  • @AivanF. Добавил графические объяснения, надеюсь, теперь вам стало понятно, что я имею ввиду. Мне непонятно, можно ли, например, для моего примера с фигурой из 2 ячеек работать дальше с моим разбиением карты на ячейки. Или же стоит как-то перекроить карту и за 1 ячейку уже брать целый прямоугольник, чтобы фигура полностью вошла в него.
    – spartaneg
    Commented 3 мая 2016 в 11:51

1 ответ 1

0

В целом, решение получилось довольно частным, но какое есть. Решено было создать объект ComplexFigure для фигур из группы ячеек, который бы включал в себя эту группу ячеек и имел схожие с ними параметры (Оценка пройденного пути, оценка пути до цели и ссылка на родительскую фигуру). Оценка пути до цели для него рассчитывается, как сумма таких оценок для входящих в него ячеек.

Здесь и кроется некий подвох: каждая ячейка должна знать в какую именно позицию она должна попасть в итоговой фигуре. То есть, имея фигуру из 2 ячеек, как в примере, первая ячейка стремится именно к первой позиции, а вторая ко второй.введите сюда описание изображения Если фигуре пришлось как-то перевернуться в процессе прохода к цели, то ей придется перевернуться еще раз, чтобы ячейки заняли именно свои позиции.

В остальном, все происходит как с 1 ячейкой. Когда рассматриваются соседи для фигуры с наименьшей стоимостью пути, для каждого направления движения рассматриваются соседи каждой отдельной ячейки в фигуре. И если хоть одна ячейка не может сместится в сторону этого соседа, то он сразу считается непроходным для целой фигуры.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.