Поиск позиции на 2D-карте, которая соответствует нескольким критериям

Question

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

Когда игрок присоединяется, я хочу создать свою начальную позицию в месте, где есть хотя бы 1 клетка каждого из 4-х ресурсов в диапазоне (круг с неподвижным, чтобы определить диаметр, я думаю о 3-4 клетках), но нет плитки океана (Tile.Type! = "ocean") и не конфликтуют с полем, принадлежащим другому игроку (Tile.Owner == null).

Размер карты может варьироваться, в настоящее время он равен 600x450, и он реализован в виде простого массива: Tile [] [], где Tile.Resource имеет значение null или имеет Tile.Resource.Type в качестве строки имени ресурса (так как он настраивается текстовыми файлами, подходящими для любого пейзажа, в который я хочу его вставить, поэтому встроенные перечисления невозможны).

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

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

Как лучше всего реализовать алгоритм для этого в C #?

Редактировать

Область игроков может и будет увеличиваться / изменяться, ресурсы могут быть использованы и могут даже появляться случайным образом (=> "Ваши поисковики нашли новую золотую жилу"), поэтому предварительно Расчетные позиции, вероятно, не будут работать.

Answer 1

Вместо того, чтобы перебирать все свои позиции, почему бы вам не перебрать все свои ресурсы? Ваши ресурсы, вероятно, будут более скудными. Затем выберите один из наборов ресурсов, которые соответствуют вашему критерию кластеризации.

Answer 2

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

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

Answer 3

Предопределенные данные все равно будут лучшим способом продвижения вперед.

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

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

Answer 4

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

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

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

Answer 5

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

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

-int NrOceanTiles
-int NrResourceA
-int ...

Теперь, когда вы хотите получить плитку, вы можете сделать это немного быстрее:

IEnumerable<Tiles> goodTiles = tiles.Where(tile => tile.NrResourceA >= 1 && tile.NrResourceB >= 2);
Tile goodTile = goodTiles.ElementAt(randomI);

Answer 6

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

Есть список свободных мест и занятых мест. Игрок занимает территорию? Переместить ресурсы в диапазоне к списку Занятые. Игрок безжалостно раздавлен? Переместить ресурсы в диапазоне в свободный список. Ресурс ликвидирован? Удалите все местоположения, которые использовали его в ваших открытых / занятых списках. Ресурс добавлен? Пересчитайте, используя радиус действия, чтобы определить зону воздействия. Когда область вашей карты расширяется, просто запустите начальные вычисления для нового раздела вашей сетки + радиус эффекта и добавьте новые местоположения.

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