NMellon
@NMellon
Unity3D (C#) Developer / web-developer

Создать алгоритм заполнения игрового поля?

Приветствую!

Не могу справиться с задачей — может хабросообщество подскажет в каком направлении смотреть.

Есть игровое поле n на m клеток.

На нем выставляем x пар фигур (допустим, в случайном порядке).

Задача алгоритма — соединить пары фигур линиями, которые проходят по свободным клеткам (по диагонали клетки соединять нельзя) таким образом, чтобы на поле не осталось пустых клеток. Или сказать, что для данной расстановки фигур решения нет.

Соединительные линии не могут пересекаться.

Может кто встречал подобную задачу на олимпиадах или еще где.

Буду благодарен за любые подсказки =)
  • Вопрос задан
  • 5086 просмотров
Пригласить эксперта
Ответы на вопрос 3
Я бы смотрел в сторону поиска путей. Алгоритмов множество — A* (A star), волновой и т.д. Лично у меня имеется опыт волнового алгоритма — в реализации довольно простой. А* в свое время осилить не смог.
Рассчитываете «расстояние» между точками, и начинаете от самых близких друг к другу. Как только построили путь — эти точки(клетки), которые в него входят, более не доступны при расчете для следующего пути. Полную заполняемость поля можно добиться «играясь» с кол-вом точек.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
01 дек. 2020, в 04:48
229182 руб./за проект
30 нояб. 2020, в 03:19
25000 руб./за проект
01 дек. 2020, в 02:50
3000 руб./за проект