как найти точку, которая является ближайшей к большинству точек, когда между нами есть блоки(в массиве 2D - Snake Game)

Question

Я работаю над игрой со змеями (Nibbles в Linux), в которую играют на поле 60 * 60, где четыре змеи соревнуются за случайное расположение яблока.

Я реализовал движениемоей змеи с помощью алгоритма A * (Звезда).

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

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

Вот изображение игры.Красные точки - головы змей.

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Редактировать: Пожалуйста, смотрите комментарии ниже для более выгодного решения.

Answer 3

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

Вы можете разделить вашу карту на четыре масштаба (по часовой стрелке): верхний левый, верхний правый, нижний правый и нижний левый (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 ячеек), эти ячейки могут быть вашими центрами, каждый раз, когда вы должны перемещаться из одного центра в другой (кроме случаев, когда вы находитесь ближе всего к яблоку или ваша змея ест яблоко и хочет отобрать ближайшийцентры).

Answer 4

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

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