Вы определяете их. Сумма, которую вы добавляете в G, когда вы «шагаете», - это то, как вы говорите алгоритму, какие пути вам действительно нравятся (H - только допустимая аппроксимация суммирования кучки G-приращений, которая помогает ему быстрее находить то, что вам нужно). Использование 10 и 14 является приближением 1 и sqrt (2), вроде того, что произойдет, если у вас было евклидовое расстояние, но на каждом шагу вы были привязаны к окружности Мура, иногда это называется «диагональным расстоянием» или «осьмического расстояния» »(хотя более правильно этот термин зарезервирован для использования точного sqrt (2)). Поэтому этот выбор не полностью выходит из ниоткуда.
Но это до вас, выбирая разные затраты, предпочитает (или «не предпочитает») определенные пути, например, если вы сделаете диагональную стоимость такой же, как и «прямая» стоимость, она будет действительно как и диагональные движения, он не обязательно будет избегать зигзагообразных движений вперед и назад (что было бы бесплатным до тех пор, пока зигзарь идет правильным путем, например, путь /\ будет такой же длины, как и --). Используя высокую диагональную стоимость (> 2), он найдет пути, которые в основном выглядят так, как будто вы использовали район фон Неймана, за исключением того, что в «чрезвычайных ситуациях» он все равно сможет двигаться по диагонали. Между 1 и 2 разница гораздо менее выражена, но иногда она встречается вокруг препятствий.
Таким образом, использование диагональных затрат ниже, чем sqrt (2) имеет тенденцию создавать «странные» пути, которые бесполезно зигзагообразно, используя диагональные затраты выше, чем sqrt (2), как правило, делают «немые» пути, которые не могут принимать диагональные ярлыки. Но вы можете этого захотеть, особенно если это соответствует «фактической стоимости» (если она у вас есть), например, время ходьбы, затраченное единицами или что-то в этом роде. Опять же, в одной из моих собственных игр я намеренно сделал диагональную стоимость выше, чем это было бы основано на времени ходьбы, чтобы сделать дорожки более естественными (это было слишком зигзагообразно).
Желтый "исследовал". Нижний путь занимает обход с диагональной стоимостью 10 из-за деталей реализации (он добавляет узлы по часовой стрелке, начиная с NW, и использует стабильную вставку в open вместо того, что-то умное, как куча, поэтому узлы с равными F являются обрывами, первый).
Благодарим вас за разъяснение. В игре, которую я создал, не было, однако, диагонального движения, т. Е. Диагонального движения вообще не было. Обычно ли предполагается, что диагональное перемещение возможно при реализации этого алгоритма? Или это считается необязательным? Мне просто кажется странным, как использование стоимости 10 заставило игрока пройти более длинный путь, тогда как когда я увеличил G, он в конце концов дошел до точки, где он всегда занимал кратчайший путь, опять же это было без диагонального движения. – samcp20
@ samcp20 вы можете взять любой набор соседей, который вы хотите, он даже работает на произвольных графах! Так что да, диагональное движение полностью необязательно. Конечно, диагональные затраты не являются проблемой, если у вас нет диагонального движения.В любом случае, из-за того, как вы это сформулировали, это звучит так, как будто вы скорректировали G, но не H, и в этом случае принятие G small приведет к сбою (что делает эвристику недопустимой и, следовательно, может не найти оптимальных решений) – harold
А я вижу, я Я еще немного экспериментирую, когда получаю шанс. Еще раз спасибо за невероятно подробное объяснение, это очень ценится. – samcp20