Компьютерная игра — компьютерная программа, служащая для организации игрового процесса (геймплея), связи с партнёрами по игре, или сама выступающая в качестве партнёра. Также это одно из основных и массовых применений микропроцессорной вычислительной техники, относящейся к досугу, воспитанию и образованию.
Компьютерные игры могут быть классифицированы по нескольким признакам:
· Жанр: игра может принадлежать как к одному, так и к нескольким жанрам, а в уникальных случаях — открывать новый или быть вне всяких жанров;
· Количество игроков и способ их взаимодействия: игра может быть однопользовательской — рассчитанной на игру одного человека, или многопользовательской — рассчитанной на одновременную игру нескольких человек; а также вестись на одном компьютере, через интернет, электронную почту, или массово;
· Визуальное представление: игра может как использовать графические средства оформления, так и напротив, быть текстовой. Игра также может быть двухмерной или трехмерной. Есть и звуковые игры — в них вместо визуального представления используются звуки.
· Платформа: игра может принадлежать как к одной платформе, так и быть мульти платформенной.
В данной программе для поиска привидениями пути к цели (игрок или точка, определённая по алгоритму в зависимости от привидения) был использован волновой алгоритм (алгоритм Ли).
Волновой алгоритм (алгоритм Ли) – алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.
Этот алгоритм в основном используется при компьютерной трассировке (разводке) печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх, собственно чем и было обосновано его выбор. Сам алгоритм описан ниже.
Алгоритм работает на дискретном рабочем поле (ДРП), представляющем собой ограниченную замкнутой линией фигуру, не обязательно прямоугольную, разбитую на прямоугольные ячейки, в частном случае — квадратные. Множество всех ячеек ДРП разбивается на подмножества: «проходимые» (свободные), т. е. при поиске пути их можно проходить, «непроходимые» (препятствия), путь через эту ячейку запрещён, стартовая ячейка (источник) и финишная (приемник). Назначение стартовой и финишной ячеек условно, достаточно — указание пары ячеек, между которыми нужно найти кратчайший путь.
Алгоритм предназначен для поиска кратчайшего пути от стартовой ячейки к конечной ячейке, если это возможно, либо, при отсутствии пути, выдать сообщение о непроходимости.
Работа алгоритма включает в себя три этапа: инициализацию, распространение волны и восстановление пути.
Во время инициализации строится образ множества ячеек обрабатываемого поля, каждой ячейке приписываются атрибуты проходимости/непроходимости, запоминаются стартовая и финишная ячейки.
Далее, от стартовой ячейки порождается шаг в соседнюю ячейку, при этом проверяется, проходима ли она, и не принадлежит ли ранее меченной в пути ячейке.
Соседние ячейки принято классифицировать двояко: в смысле окрестности Мура и окрестности фон Неймана, отличающийся тем, что в окрестности фон Неймана соседними ячейками считаются только 4 ячейки по вертикали и горизонтали, в окрестности Мура — все 8 ячеек, включая диагональные (в данной программе использовались соседние ячейки только по вертикали и горизонтали).
При выполнении условий проходимости и непринадлежности её к ранее помеченным в пути ячейкам, в атрибут ячейки записывается число, равное количеству шагов от стартовой ячейки, от стартовой ячейки на первом шаге это будет. Каждая ячейка, меченая числом шагов от стартовой ячейки становится стартовой и из неё порождаются очередные шаги в соседние ячейки. Очевидно, что при таком переборе будет найден путь от начальной ячейки к конечной, либо очередной шаг из любой порождённой в пути ячейки будет невозможен.
Восстановление кратчайшего пути происходит в обратном направлении: при выборе ячейки от финишной ячейки к стартовой на каждом шаге выбирается ячейка, имеющая атрибут расстояния от стартовой на единицу меньше текущей ячейки. Очевидно, что таким образом находится кратчайший путь между парой заданных ячеек. Трасс с минимальной числовой длиной пути, может существовать несколько. Выбор окончательного пути в приложениях диктуется другими соображениями, находящимися вне этого алгоритма. В данной программе – выбирается первый полученный минимальный путь.
