В данном проекте реализован модуль для проектирования кратчайшего пути ровера.
Для проектирования пути используются данные о местности в закодированном виде: фотография, закодированная в матрицу с цифрами. Одна матрица — это прямоугольный снимок размером х на y метров. Вот пример одной такой сконвертированной фотографии, на ней снимок в 100 на 100 метров:
Пример фото 1:
0 2 3 4 1
2 3 4 4 1
3 4 5 6 2
4 5 6 7 1
6 7 8 7 1
Числа показывают высоту над уровнем моря. 0 — это высота ровно на уровне моря, а, например, 4 — это 4 единицы над уровнем моря. На примере 1 закодирован холм, пологий слева и резко обрывающийся справа.
Небольшой холмик выглядел бы вот так
Пример фото 2:
0 1 1 1 0
1 1 3 1 1
0 1 1 1 0
0 0 0 0 0
А вот так: ложбина между двумя холмами
Пример фото 3:
1 1 2 3 4
1 0 1 2 3
2 1 1 1 2
3 3 1 0 1
4 3 1 1 0
На этих данных - скала или овраг, так как виден очень резкий перепад высот в середине снимка
Пример фото 4:
1 1 6 7 7
1 1 6 7 8
1 6 7 8 9
А на этом - маленькая ямка
Пример фото 5:
3 4 4 4 4 3
3 2 1 1 1 4
4 2 1 1 3 4
4 4 2 2 3 4
А на этом - каньон.
Пример фото 6:
-1 0 1 2 3
0 -1 0 1 2
1 0 -1 0 1
2 1 0 -1 0
3 2 1 0 -1
Данные приходят в виде матрицы с положительными и отрицательными числами. Размер матрицы NxM.
Ровер всегда движется из верхней левой точки [0][0] в правую нижнюю точку [N - 1][M - 1], где N и M - это длина и ширина матрицы.
У ровера есть несколько свойств:
- Движение Из любой точки ровер может двигаться в любую соседнюю точку. Ровер может ехать как в четыре стороны света: север, юг, запад и восток, так и по-диагонали. Ровер не может вернуться в ту точку, в которой уже был.
- Заряд Ровер ездит на заряде. Для ровера очень затратно подниматься и опускаться. Он тратит единицу заряда на само движение, и дополнительные единицы на подъем и спуск. Ровер бы вообще спокойно жил, если бы ездил по асфальту в Беларуси, тогда бы он тратил себе линейно заряд и в ус не дул, но жизнь его сложилась иначе.
- Расход заряда Заряд расходуется по правилу: На 1 шаг ровер всегда тратит 1 единицу заряда. На подъем или спуск ровер тратит заряд, пропорциональный сложности подъема или спуска. Сложность подъема или спуска - это разница между высотами.
Например, в такой местности:
1 2
1 5
на путь из [0][0] в [1][1] ровер потратит 5 единиц заряд: 1 единица заряда на само движение, и еще 4 единиц заряда на подъем в [1][1]. Задача модуля рассчитать путь ровера из верхей левой [0][0] точки в правую нижнюю [N - 1][M - 1] точку с минимальной тратой заряда. Размер фотографии, которую необходимо обработать, неизвестен: N и M - произвольные неотрицательные числа.
Модуль создает план пути и планируемый расход в txt файле. Название файла - path-plan.txt
Для фотографии:
0 4 3
1 3 2
план будет такой: path-plan.txt [0][0]->[1][1]->[2][1] steps: 2 fuel: 6
Ровер едет из 0 в 3 в 2, сделает два шага, потратит 6 заряда. Если бы он поехал сначала в 4, потом в 2, он бы сделал то же количество шагов, но потратил бы 8 заряда. Оптимальный путь: 2 шага и 6 заряда. Если на карте есть несколько вариантов пути, будет выбран первый найденный.
Чтобы использовать данный модуль, нужно скачать файл rover.js и подключить его через функцию require() в node.js. Запустить модуль можно исполнив функцию calculateRoverPath, передав в качестве аргумента матрицу. Матрица должна быть сформирована согласно условию, описанному ранее.