A* was invented by researchers working on Shakey the Robot's
path planning.
Suppose the robot has to cross some rugged terrain from one location to another and have to count the most short way among the obstacles:
C - concrete, surface with good quality, crossing this way will take 1 action points (ap)
S - static field, it takes a bit longer time to cross it - 3 ap
M - magnetic field on its way, 4 ap
R - this path with very strong radiation, so robot hangs a lot and this way would take 9ap
V - vacuum, imposible to cross this space at all costs
Use mouse and click on desired start and end point, path should be the most optimal if it posible according to current map ;)
Screenshots
There are several examples of possible situations on the map.
A* алгоритм был придуман при
разработке алгоритма поиска пути для
робота Шеки.
Представьте, что робот должен преодолеть пересеченную местность из одной точки в другую, преодолевая препятсвия наиболее оптимальным путем:
C - бетон, хорошая поверхность, преодоление этого участка отнимает 1 день
S - статическое поле, здесь робот задержится на 3 дня
M - магнитное поле эта дорога займет 4 дня
R - this path with very strong радиация, здесь робот будет много раз зависать, так что путь займет 9 дней
V - вакуум, это пространство вообще невозможно преодолеть
Кликайте мышью там где хотите чтобы было начало или конец маршрута, а алгоитм покажет наиболее оптимальный путь если он существует ;)
Изображения
Несколько возможных вариантов маршрутов
1. Простой маршрут ценой в 18 дней. Хорошо видно, что любое отклонение сделает маршрут более продолжительным т.е. неоптимальным.
2. Гораздо более длинный путь черед всю карту. Видно как алгоритм обходит зону вакуума и радиации предпочитая мене дорогостоящий маршрут.
3. Невозможный маршрут поскольку один из его концов лежит внутри зоны вакуума.
