Делать случайные точки появления справедливыми?

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

Есть ли способ сформировать точки появления или изменить карту, чтобы:

1. Все игроки имеют ограниченное количество соседних противников.
2. Все игроки имеют равные шансы встретить соседних врагов.
3. Размер карты не нужно увеличивать пропорционально количеству игроков.
4. Эти ограничения не применяются для произвольных непроходимых мест.

Ответ не должен быть идеальным, просто явно лучше, чем альтернатива. Из коробки мышление приветствуется.

Пусть игроки сами выберут свои начальные локации.

В начале игры появляются все игроки в центре карты, но без каких-либо средств причинения вреда другим игрокам. Затем они должны будут роиться и приобретать средства, чтобы взаимодействовать друг с другом (построить базу, подобрать оружие, собрать ресурсы и т. Д.)

Для того, чтобы найти хорошее начальное местоположение на ранней стадии, нужно немного удачи или знания карт (в зависимости от того, используете ли вы процедурные или ручной карты). Но когда и где обосновываться - это в основном стратегическое решение. Раннее развертывание дает вам преимущество во времени, но ставит вас в опасное положение. Тщательный отбор базы в начале игры оставляет вас позади, но может стать решающим преимуществом в середине и конце игры.

Понимание требований

1. Все игроки имеют ограниченное количество соседних противников.

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

Смежные хорошо определены, когда мы говорим о графе. Мы можем думать о карте, которая отображает навигацию на карте - отныне «график».

Если узел can может иметь не более одной точки возрождения, то говорить о том, что они «смежны», имеет смысл. Примечание: я не буду ограничивать узлы, чтобы иметь максимум одну единственную точку появления, по причинам, которые будут очевидны позже.

Чтобы построить график, нам нужно будет рассмотреть такие вещи, как стены, мосты, лестницы, точки телепортации или даже рассмотреть пространство для полета, если может существовать игрок, способный летать. Каждый узел представляет собой проходимое местоположение; каждое соединение представляет возможное движение.

Примечание: узнайте размер и форму узлов и работайте с фактически смежными узлами. Не считайте узлы точкой. Не рассматривайте соединения как имеющие длину. Также используйте выпуклые узлы.

График мог быть предварительно скомпилирован (карта была создана дизайнером); в противном случае его можно создать на лету, если карта генерируется случайным образом.

2. Все игроки имеют равные шансы встретить соседних врагов.

Я предполагаю, что враги - другие игроки. Опять же, просто убираю это с пути.

Предполагая, что каждый игрок совершает случайную прогулку, вероятность нахождения игрока в данной точке - на ровном пространстве, свободном от препятствий - будет определяться (гауссовой) функцией расстояния до точки появления - с этого момента функция».

Поскольку мы работаем над графиком, мы вместо этого будем аннотировать значения на графике.

3. Размер карты не нужно увеличивать пропорционально количеству игроков.

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

4. Эти ограничения не применяются для произвольных непроходимых мест.

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

Решение

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

Мы можем получить меру ошибки как сумму различий между шансами и средними шансами. Мы пытаемся минимизировать это (фактически мы хотим сделать это 0).

Для этого нам нужно знать шанс встретить игрока на каждом узле графика.

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

Примечание 1: Добавление или перемещение точки появления влияет на шанс встретить игрока на всей карте.

Примечание 2: Отслеживание того, насколько каждая точка появления влияет на шанс, упростит ситуацию.

Примечание 3: Поскольку узлы имеют размер, то насколько близко вы можете добраться до error = zero, зависит от размера узлов. Вы можете быть более точным, работая с диапазонами значений (минимальный и максимальный шанс, в зависимости от конкретной позиции точек появления в узле).

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

Примечание 4: При перемещении точки возрождения вы можете использовать шанс встречи с игроком (исключая точку возрождения, которую вы будете перемещать), чтобы случайным образом выбрать новую позицию для точки возрождения, такую, чтобы иметь возможность встретить игрока ближе к среднее значение более вероятно. Напоминаю, что перемещение точки появления влияет на среднее значение.

Ожидаемое поведение заключается в том, что точки появления, находящиеся слишком близко друг к другу, раздвигаются, а точки появления, находящиеся слишком далеко друг от друга, сближаются. Пока они не достигнут равновесия.

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

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

Попробуйте смоделированный отжиг, чтобы переместить точку появления внутри узла. Хотя, если честно, вероятно, не стоит возиться с таким уровнем детализации.

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

Это зависит от того, какую игру вы хотите создать и насколько быстро она будет развиваться. Идеальное равномерно распределенное распределение возможно в такой сфере, как мир (например, планетарная аннигиляция). Но это справедливый вариант в вашей игре? Даже если все люди нерестятся на одинаковом расстоянии, некоторые из них могут иметь большее преимущество.

• Ближе / лучшее оружие в радиусе действия / больше ресурсов
• Лучшее покрытие / более скрытый / обзор
• «поток» игроков, некоторые места более привлекательны, чем другие (подумайте о полной карте леса с одним домом в одном месте, независимо от того, где находится этот дом, хороший шанс, что люди его проверят)

Является ли ваша карта фиксированной или процедурной? И когда-нибудь пытались играть в Age of Empires с 8 людьми на карте для 2 человек? Невозможно масштабировать игроков до бесконечности без изменения размера карты. Даже несправедливое начальное размещение может привнести в игру много динамики (см. Серию «Черви»). Никто не жаловался, если вы появлялись прямо в большом кластере, пока длился ваш союз в один раунд с другим игроком или у вас не было самых выживших червей после первого раунда.

(Я добавлю еще несколько примеров, если я узнаю больше о вашем типе игры)

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

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

В качестве альтернативы, вся карта может существовать вне сферы, однако это затрудняет создание координат.

Вот несколько возможных решений:

• Появляется случайным образом по окружности круга
• Появляются случайным образом по радиусам (не появляются, чтобы закрыть центр)
• Добавить случайный компонент времени появления

По сути, я считаю, что это проблема распределения графиков. Если предположить, что существует ситуация с лицом смерти (каждый игрок является врагом), вам нужно смоделировать свои карты как взаимосвязанный граф и отследить, к какому узлу на графике ближе всего подходит каждый игрок. Не каждый узел должен быть точкой появления, но вам нужен сложный график для моделирования расстояний между точками появления. Затем, во время появления, вы выполняете итерацию графика и забиваете каждый spawnable-узел в зависимости от того, есть ли у соседних узлов игроки.

Идеальный узел тогда имеет:

• Нет игроков в настоящее время в нем
• Больше чем ноль игроков в узлах поблизости (небольшое количество ссылок далеко)

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

Вы будете должны увеличить размер карты , как количество игроков растет, ноk не должно быть 1 или больше. Ваш худший случай все еще будет состоять в том, что каждый узел на графике имеет по крайней мере одного игрока - в этом случае нет хороших узлов для использования, и вам придется пострадать от этого случая и породить игрока, зная, что они будут земля прямо поверх другого. Алгоритм скоринга должен по-прежнему взвешивать узлы, чтобы вы появлялись в узле с наименьшим количеством других игроков.

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

Уточнения:

• Добавьте временный штраф, чтобы забить, если игрок недавно появился в этом узле, чтобы препятствовать формированию удушающих точек (бесконечный поток игроков, прибывающих с одного и того же направления и отрывающихся)
• Добавьте случайность в пределах диапазона (например, выберите лучшие 3 узла и затем случайным образом выберите между ними с равной вероятностью), чтобы получить больше вариаций.
• Добавьте начальный вес к центру карты (или к наиболее интересным точкам), когда никто еще не появился, чтобы вы появлялись в известных местах, даже когда каждый узел имеет нулевой счет, потому что других игроков нет.

Несколько других уже обсуждали ограничения ваших требований (карту нужно будет масштабировать в какой-то момент, чтобы предотвратить переполнение и т. Д.), И в конечном счете ускользнули от факта, что, вероятно, не существует «идеального» алгоритма размещения. Когда, вероятно, не существует «идеального» алгоритма, я всегда обращаю внимание на эвристику. У вас есть несколько критериев, которые прямо или косвенно расходятся друг с другом, а также очень сложное пространство поиска. Поиск оптимального решения может быть неосуществимым или практичным, но с небольшой настройкой статистический подход может работать очень хорошо большую часть времени.

Обращаясь к третьему и четвертому критериям: «Карта не должна расширяться».

Я хотел бы убедиться, что в начале у вас есть избыток узлов (т. Е. Такой плотный, как навигационная сетка для поиска пути). Это делает вычисление расстояния до других игроков более дорогим (не непосредственно соседних узлов), но это не процесс, который будет происходить более одного раза за раунд (я полагаю). Бонусом этого является то, что вы можете использовать предварительно свернутую навигационную библиотеку для большинства ваших операций. Кроме того, это будет справедливо учитывать обход препятствий, когда евклидово расстояние не может (игроки в лабиринте могут быть расположены ближе друг к другу, чем на открытом поле).

Рассчитать эвристику для желаемых характеристик появления:

После случайного размещения всех игроков рассчитайте производительность окружающих узлов на основе ваших критериев (расстояние от других игроков, расстояние до спавна и т. Д.). Веса ваших значений можно настраивать и манипулировать, чтобы они были нелинейными для точной настройки производительности. Вы хотите в очищенном идеальном случае (плоская прямоугольная сетка без препятствий), и производительность должна быть одинаковой, когда вы добавляете мир обратно. Оттуда вы можете решить, сколько узлов искать, какой порог для перемещения начальной точки и сколько итераций вы хотите выполнить, прежде чем завершить спавн и начать игру.

Если игровое поле является топологическим тором (т. Е. Прямоугольник, где «выход за пределы» означает вход с противоположной стороны), это, вероятно, будет хорошим ответом: игрок jпоявляется в x = (pjW/N) mod W, y = (qjH/N) mod H, где W,Hразмеры прямоугольника, Nэто количество игроков и p,qцелые числа, которые будут определены; они различны, (вероятно) относительно просты, и не слишком далеко от sqrt(N). Точки возрождения образуют наклонный рисунок «обои».

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

Как насчет:

Каждый игрок окружен нерестовым ящиком (или кружком).

Например, есть квадрат определенного размера, который появляется вокруг каждого игрока и следует за этим игроком вокруг - никакой другой игрок не может появиться в этом поле.

Эти квадраты влияют только на нерест, а не на любое другое движение во время игры.

Это работает либо с начальным, либо с непрерывным нерестом.

(Точки обозначают игроков, а зеленый цвет обозначает возможную область появления новых игроков)

Размер карты не должен увеличиваться пропорционально количеству игроков

Чтобы справиться с этим, вы можете сделать одну из двух вещей: (или оба)

• Уменьшите размер нерестящихся ящиков в зависимости от количества игроков.
• Разрешить до X вражеских игроков появляться в каждой коробке.
  • Это число может увеличиваться с ходом (начиная с 0).
  • Вариант 1: иметь меньший ящик без порождения и больший ящик с ограниченным порождением.
  • Вариант 2: весовые вероятности в зависимости от того, насколько близок новый спавн к этому игроку (если он внутри коробки) - может быть сложно реализовать эффективно.