Минимизируйте вершины полигона
Похоже, лабиринт создан как текстовый блок. * используется для обозначения стены или за ее пределами. Буква «Е» используется для обозначения выхода из лабиринта. Вероятно, это выглядело так:
********************E**
*......*......*......**
*.********.*******.****
*.....*......*........*
*.*************.*****.*
*..*............*****.*
***********************
Из строки y < 1 y> 8 размеры должны быть 8 высокими, но вы поняли идею. Когда в позиции находится буква «Е», то выход найден, и лабиринт решен. «A» и «H» используются для обозначения некоторой ширины. Я не совсем понимаю, но это та же идея.
Рекурсия работает так. Возьми мою отправную точку, скажем, х = 7, у = 6. Если это выход, то мы успешны. Если это на стене, мы потерпели неудачу. если это выходит за границы, мы потерпели неудачу, теперь проверьте все четыре местоположения вокруг меня и сделайте то же самое. Если какое-либо из этих четырех мест нашло выход, то мы успешны.
Если лабиринт разрешим, тогда мы получим «истину», если ветвь разрешима, то мы получим истину. Если лабиринт не может быть разрешен из заданной начальной позиции, возвращается false, а если ветвь не приводит к выходу, возвращается false.
2 ответа
Править: О, посмотрите, Упрощение Полигонов
Вы упомянули обнаружение коллизий. Вы могли пойти действительно простые и вычислить выпуклую оболочку ограничения вокруг этого.
Если Вы заботились о вогнутых областях, можно вычислить вогнутую оболочку путем взятия центроида полигона и выбора точки для запуска. От начальной точки вращаются вокруг центроида, находя каждую вершину, которую Вы хотите сохранить, и присвоение что как следующая вершина в оболочке ограничения. Сложность алгоритма вошла бы, как Вы определили, какие вершины сохранить, но я уверен, что Вы уже думали об этом. Можно бросить все вершины в блоки на основе их местоположения относительно центроида. Когда блок получает больше, чем произвольное число полных вершин, можно разделить его. Затем возьмите средние из вершин в том блоке как вершина для использования в оболочке ограничения. Или, забудьте блоки, и когда Вы переместите центроид, только выберете точку если ее больше, чем данное расстояние от последней точки.
На самом деле Вы могли, вероятно, просто использовать все вершины в своем полигоне как "облако точек" и вычислить вогнутую оболочку вокруг этого. Я буду искать ссылку алгоритма. Худший случай на этом был бы абсолютно выпуклым полигоном.
Другая альтернатива должна запуститься с ограничительного прямоугольника. Для каждой вершины на прямоугольнике найдите расстояние от точки до полигона. Для самой дальней вершины, разделение это в еще две вершины и перемещают их в некоторых. Повторитесь, пока некоторая пропорция или вершин или области не будет встречена. Я должен был бы думать о деталях этого немного больше.
Если бы Вы заботитесь о полигоне, на самом деле выглядящем подобными, даже в случае самопересекающегося полигона, то другой подход требовался бы, но он не кажется, что это необходимо, так как Вы спросили об обнаружении коллизий.
Это сообщение имеет некоторые детали о части выпуклой оболочки.
Существует много материала там. Просто Google для вещей как "сетчатое сокращение", "поймали в сети упрощение", "поймали в сети оптимизацию", и т.д.