ЛР. Поиск пути в разреженной матрице

Post date: Nov 13, 2010 5:28:59 PM

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

Постановка задачи

Необходимо разработать и реализовать алгоритмы поиска пути на карте, которая содержит препятствия:

1. Карта задаётся в виде матрицы в CRS формате.
2. Карта содержит ячейки следующих типов: ячейка свободна, ячейка занята препятствием, в ячейке находится ресурс.
3. Задача игрока заключается в том, чтобы как можно быстрее собрать все ресурсы на карте.
4. Реализация стратегии игрока представлется в виде dll-библиотеки.

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

Каждому необходимо реализовать поддержку CRS формата матрицы и реализовать два алгоритма поиска пути.

Ищите свою фамилию в списке (82-02), порядковый номер - соответствует алгоритмам, которые необходимо реализовать:

1. Надежная трассировка с обходом препятствий по правую руку. Поиск в глубину.
2. Надежная трассировка с обходом препятствий по левую руку. Поиск в ширину.
3. Надежная трассировка с обходом препятствий по правую руку. Двунаправленный поиск в ширину.
4. Надежная трассировка с обходом препятствий по правую руку. Поиск в глубину.
5. Надежная трассировка с обходом препятствий по правую руку. Поиск в ширину.
6. Надежная трассировка с обходом препятствий по левую руку. Поиск в глубину.
7. Надежная трассировка с обходом препятствий по правую руку. Поиск в ширину.
8. Надежная трассировка с обходом препятствий по левую руку. Двунаправленный поиск в ширину.
9. Надежная трассировка с обходом препятствий по левую руку. Поиск в ширину.
10. Надежная трассировка с обходом препятствий по правую руку. Поиск в глубину.
11. Надежная трассировка с обходом препятствий по левую руку. Двунаправленный поиск в ширину.
12. Надежная трассировка с обходом препятствий по правую руку. Поиск в глубину.

Проект, содержащий шаблон dll-библиотеки и реализующий визуализацию можно скачать тут.

Ниже представлена демонстрация того, как работать с проектом и как можно реализовать простейшуй стратегию - ход в случайном направлении (рекомендую смотреть в качестве не ниже 480p).

Ниже представлено руководство по настройке проекта для отладки динамической библиотеки, содержащей реализацию простейшей стратегии хода игрока (рекомендую смотреть в качестве не ниже 480p).

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

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

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

Dead Line: 23:59 29.11.2010

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

Dead Line: 23:59 06.12.2010