ЛР. Поиск пути на карте

Post date: Nov 29, 2011 5:54:50 PM

ЛР включает в себя реализацию двух алгоритмов поиска пути на карте.

Эвристический алгоритм

Первый алгоритм должен находить путь до цели, используя для очередного хода информацию только о соседних клетках (4 соседа) и истории своих перемещений на карте.

Карта хранится в виде разреженной матрицы (CRS формат). На карте присутствую "стены" (непроходимые участки) и "ресурсы" (то что должен собирать игрок).

Результат работы необходимо выложить на SVN: исходные коды проекта + реализацию алгоритма в виде dll-библиотеке в отдельную папку со своим ФИО (например, ЛР3\bin1\IvanovII\Bot.dll, название dll-библиотеки должно быть обязательно "Bot.dll").

Пустой проект, реализующий "игрока", пример реализации и видео по разработке можно посмотреть тут.

Реализацию необходимо выложить на SVN до 5.12.11 для 82-02 и до 6.12.11 для 82-12.

Алгоритм Дейкстры

Второй алгоритм должен содержать реализацию алгоритма Дейкстры для поиска кратчайшего пути до цели и реализацию алгоритма, который решает задачу коммивояжёра.

Карта хранится в плотной матрицы (двухмерный массив целых чисел). На карте целыми положительными числами задаётся цена перехода в соответствующую ячейку. На карте присутствую "стены" (непроходимые участки) и "ресурсы" (то что должен собирать игрок). "Ресурс" закодирован предопределённым значением 2000000. Цена перехода в ячейку, содержащую "ресурс" определяется следующим образом: <значение ячейки> - 2000000. Например, если в элементе матрицы записано число 2000005, то это означает, что в этой ячейке находится "ресурс", а цена перехода в ячейку равна 5.

Программу, выполняющую эксперименты можно скачать тут (программа разработана Евгением Изутовым и немного доработана мной).

Примеры реализации игроков можно скачать тут.

Проект с реализацией "пустой" стратегии игрока можно скачать тут.

Пример использования программы для проведения экспериментов можно посмотреть ниже (рекомендую смотреть в качестве не ниже 720p).

Результат работы необходимо выложить на SVN: исходные коды проекта + реализацию алгоритма в виде dll-библиотеке в отдельную папку со своим ФИО (например, ЛР3\bin2\IvanovII\Bot.dll, название dll-библиотеки должно быть обязательно "Bot.dll").

Реализацию необходимо выложить на SVN до 12.12.11 для 82-02 и до 13.12.11 для 82-12.

По лабораторной работе необходимо предоставить отчёт (шаблон отчёта).

Сдача отчёта должна быть осуществлена не позднее, чем через неделю после сдачи реализаций двух алгоритмов поиска.