как найти точку, ближайшую к большинству точек, когда у нас есть несколько блоков между ними! (в массиве 2D - Змейка)

Я протестировал несколько способов и, наконец, решил использовать этот способ:

Я думаю, что лучший способ - создать 2D-массив размером: 60 * 60 , затем для каждого узла (x) массива вычислить, сколько узлов поля, по которым можно пройти! (не блокировать), является ли этот узел ( х) ближайший к.

то ответ будет Максимальное количество, то я ставлю этому узлу цель.

но поскольку я должен найти следующий ход менее чем за 0,1 секунды, и для выполнения этой работы есть 4 цикла размером: 60, (60 ^ 4), и когда я его найду, алгоритм A * тоже будет запущен, эта работа будет никогда не выполняться менее чем за 0,1 сек.

Итак, поскольку Змея не может двигаться по диагонали и движется только вверх, вниз, вправо, влево, я решил не проверять все узлы, так как в каждом цикле (0,1 сек) я могу двигаться только на 1 единицу, я решил чтобы проверить только 4 узла (вверх, вниз, влево, вправо) и перейти к узлу, количество которого равно Max.

теперь он работает почти правильно. ;)

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

Чтобы сгенерировать это, я бы сказал, что вы можете начать с каждой ячейки и назначить ей одно очко за каждую ячейку, которую она может посетить за один ход. Например, ячейка в углу получит два очка за первый ход, потому что у нее есть доступ только к двум другим ячейкам. За второй ход он получит пять очков, потому что может получить доступ к пяти ячейкам за два хода. Повторяйте, пока не посетите все остальные квадраты, и тогда у вас будет счет за этот квадрат.

С этого момента, если появляется яблоко, а ваша змея находится не ближе всего к нему, ваша змея может направиться к ячейке с наибольшим весом, которую вы вычислили заранее.

Изменить: см. комментарии ниже для более выгодного решения.

Если вы находитесь ближе всего к яблоку, вы должны идти, чтобы получить его, но если вы находитесь далеко от яблока, ваш лучший шанс - пройти по середине карты, вы должны найти стратегию, как занять середину карты.

Вы можете разделить карту на четыре масштаба (по часовой стрелке), верхний левый, верхний правый, нижний правый и нижний левый (1,2,3,4). Мы проверяем это между двумя змеями: если яблоко в настоящее время находится в масштабе 1 (предположим, что центр находится в среднем), а вы находитесь в центре карты, ваш противник может быть в масштабе 1,2,3,4 (опять же предположим, что оно находится в центре этой карты). масштабирует, чтобы получить среднее значение более простым способом), если он находится в масштабе 1, у него больше шансов (1-0), если он в масштабе 2 или 4, ваше расстояние равно sqrt (2)/2, а расстояние до вашего противника равно 1, поэтому вы ближе всего , и, наконец, если ваш противник находится в масштабе 3, ваше расстояние равно sqrt (2)/2, а расстояние вашего противника равно sqrt (2), поэтому в 3 случаях с одним противником у вас больше шансов.

Но поскольку ваша фигура имеет несколько блоков, вы должны вычислить положение центра другим способом, фактически, для каждой точки в вашей сетке вычислите ее расстояние до всех других точек. это займет 60 ^ 2 * 60 ^ 2, что можно сделать быстро. и найдите ячейки с минимальной общей суммой (вы можете выбрать лучшие 10 ячеек), эти ячейки могут быть вашими центрами, каждый раз, когда вы должны перемещаться из одного центра в другой (за исключением случаев, когда вы находитесь ближе всего к яблоку или ваша змея ест яблоко и хочет вернуться к ближайшему центры).

Ближайшим к максимальному количеству мест является центр, как заявляли другие. Ближе к максимальному количеству локаций, чем у других змей, есть гораздо, разные и более сложные вопросы. В этом случае я бы A* голову каждой змеи, чтобы увидеть, у кого больше квадратов под контролем. Это базовая оценка. Затем, когда я рисую пустое место, я выбрал Монте-Карло случайный набор точек на карте и выбрал точку, которая дала наивысший балл, в качестве пункта назначения. Если бы у вас была вычислительная мощность, вы могли бы попробовать каждую точку сетки и выбрать лучшую, как К.Г. предложено, но это может стать довольно интенсивным.

Настоящее испытание — это когда вы находите свою точку, выясняете, как далеко в будущем вам нужно добраться до нее, и запускаете ИИ для других змей, чтобы увидеть, перехватят ли они вас. Вы начинаете входить в плисы, как в шахматы. :)