Зачем нужно икать путь?

Мне нравятся игры, в которых герой передвигается по карте. В таких играх нужно указать место, куда нужно придти, а программа сама находит самый короткий путь. Я бы хотел научиться создавать такие игры в Scratch. Но когда я начал проектировать одну из таких программ, то понял, что это очень сложно. Мне пришлось разобраться, как строиться игровой мир, понять, что такое матрица, и как найти самый короткий путь. Это правда очень сложно, поэтому я создаю проект, который поможет разобратся с этим тем, у кого есть желание создавать игры с перемещением юнитов.

Матрица

В моей программе есть небольшое игровое поле. Оно имеет размеры 5 на 5 клеток. Данные об этих клетках записаны в список Матрица.

0 - клетка свободна

-1 - на клетке препятствие

1 - клетка, в которой находится герой, из этой клетки надо будет искать путь.

С помощью Печати поле показывается на сцене. Для этого пролистывается список Матрица и печатается нужный костюм.

Волновой алгоритм

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

Чем дальше от старта клетка, тем больше её вес. Когда доходим до точки финиша проверяем матрицу и находим короткий путь. Короткий путь записывается в специальный список.

Когда список заполнен, с его помощью строим путь до нужной клетки.

Режимы показа

Я постарался сделать так, чтобы в моей программе всё было очень наглядно. Поэтому можно выбрать один из режимов показа. Когда программа выполняется клетки меняют цвета, а цифры показывают "вес" каждой клетки.

Скришноты

Скачать игру
Скачать видео

Видео прохождения игры