Поиск координат, вакантных для респауна

[maksimov]

Обстоятельства:
Двумерный массив представляет из себя игровое поле, где каждый элемент массива - это клеточка этого поля. Поля бывают доступные и недоступные (вода). Кроме того, по полю перемещаются персонажи (массив объектов) каждый из которых в каждый момент времени находится в той или иной клеточке поля (имеет координаты).
Задача:
Находить клетку, подходящую для того, что бы в ней появился новый персонаж. Условия "подходящести" следующие: а. она должна быть доступна; б. никакой из уже существующих персонажей не должен находиться от неё ближе чем на икс клеток.


Долгое ломание головы выявило всего два варианта решения (оба уже реализовал и опробовал):
1. в цикле с условием "пока не найду", брать рандомную клетку на игровом поле, проверять её на доступность, после чего пробегать по всем объектам, проверяя нет ли среди них такого, который бы находился на расстоянии от этой клетки, меньшем чем допустимо.
2. создавать дополнительный массив булевых, размером с игровое поле, после чего пробегаться по массиву объектов, отмечая все находящие рядом клетки, как "недоступные" в связи с близостью к уже существующему объекту. после чего бежать по массиву поля, в поисках первой же доступной клетки (и "не вода", и "не отмечена в булевом массиве как недоступная").


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

Но ничего другого в голову не приходит. Есть какие-нибудь идеи?

[1max1]

1. в цикле с условием "пока не найду", брать рандомную клетку на игровом поле, проверять её на доступность, после чего пробегать по всем объектам, проверяя нет ли среди них такого, который бы находился на расстоянии от этой клетки, меньшем чем допустимо.

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

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

class Cell
{
    public enum Type
    {
        Water,
        Character,
        Available
    }

    public int id;
    public Type type;
    public Vector2Int pos;
}

Потом набросать методы для работы с этим классом, к примеру:
GetTypeCell
GetCellByID
GetCellByPos
Ну и дальше в таком стиле, что тебе нужно для работы с клетками.
Еще желательно обзавестись словарем с персонажами и их недоступными клетками ну и + список клеток с водой:

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

List<int> cellsWithWater = new List<int>();
Dictionary<int, List<int>> charCells = new Dictionary<int, List<int>>();

key - id персонажа.
value - список клеток (по их ид), которые недоступны.
И когда персонаж делает ход, просто заново заполнять ему список недоступных клеток.
Когда ты будешь искать доступную клетку просто пробегись по списку всех перемешанных (об этом выше) и если идшник не равен ни одной водной клетке и ни одной клетке персонажа, берешь эту клетку.

[maksimov]

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

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

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

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

Большое спасибо за искреннюю попытку помочь. Но ваши предложения способны разве что увеличить потребление ресурсов (причём, даже не в разы, а на порядки), а никак не сократить его.

[lawson]

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

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

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

[1max1]

Вместо того, что бы просто "взять из двумерного массива элемент по случайному индексу"

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

совершить перемешивание элементов списка, взять первый элемент из списка"

НЕ ПЕРВЫЙ, потому что первый в списке может быть не валидным, он будет случайным, АЛЛО! Логика проснитесь, вы обосрались!

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

Если персонаж делает ход, список валидных клеток меняется, как ты собрался чекать валидный список если он не будет меняться? ><
Невежда, я тебе дал вполне дельные советы, а ты просто не захотел в них разобраться, ну удачи...

[seaman]

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

Отличие:
- один список, вместо 2-3...
- При выборе свободной ничего не нужно сортировать/перебирать
- Правда придется при перемещении персонажей постоянно менять список.

[maksimov]

вы там что, проект на калькуляторе запускаете

Ресурсы сэкономленные "в одном месте", всегда могут быть использованы "в другом месте". =)
Вы удивитесь, но отказ от использования в игре текстур, позволил забить болт на формирование у генерируемых мешей uvmap'ы.

или у вас карта размеров вселенной?

Размер "вселенной" - 64 на 64 клетки. В смысле геймплея, это увы "очень мало" (минимальный необходимый минимум). А вот в смысле ресурсов, это 4096 клеток, каждая из которых остро нуждается в любви, заботе и уходе.

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

Эээ... Каждый персонаж имеет координаты (x, z). Что и является "ссылкой" на ту клетку, в которой он в данный момент находиться.

[maksimov]

Это сарказм сейчас был?

Безусловно. Ибо любая другая степень иронии, была бы бессильна обнажить всю масштабность предложенных вами "оптимизаций".

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

Когда планируете посмотреть? К обеду уже можно ждать звонка в дверь?

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

взять первый элемент"

НЕ ПЕРВЫЙ, потому что первый в списке может быть не валидным, <skiped> вы обосрались!

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

Невежда, я тебе дал вполне дельные советы

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

[maksimov]

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

"Ареолы занятости" персонажей, могут пересекаться (в те моменты, когда расстояние между персонажами будет меньше "диаметра" "ареолов").

[IDoNotExist]

Потенциальные поля тут должны зайти. https://habr.com/post/262181/

[lawson]

Вы удивитесь, но отказ от использования в игре текстур, позволил забить болт на формирование у генерируемых мешей uvmap'ы.

Не может быть! наверное еще и материалы с шейдерами не нужно применять!?

Размер "вселенной" - 64 на 64 клетки.

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

Эээ... Каждый персонаж имеет координаты (x, z). Что и является "ссылкой" на ту клетку, в которой он в данный момент находиться.

Вы что вычисляете каждую клетку под персонажем по расстоянию? О какой тогда оптимизации идет речь!?

[maksimov]

Не может быть! наверное еще и материалы с шейдерами не нужно применять!?

Вы наверное не знаете, что такое материалы и шейдеры, раз задаёте такой вопрос.
Но отсутствие текстур, позволяет весьма значительно упростить код шейдера.

Размер "вселенной" - 64 на 64 клетки.

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

У вас наверное весьма пространные представления о многопоточности, если вы возлагаете на неё столь странные надежды.

Вы что вычисляете каждую клетку под персонажем по расстоянию?

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

О какой тогда оптимизации идет речь!?

Я вообще не представляю, о чём у вас идёт речь. Больше похоже на флуд. =)

[1max1]

Безусловно. Ибо любая другая степень иронии, была бы бессильна обнажить всю масштабность предложенных вами "оптимизаций".

Прощу меня простить за столь убогие советы(( Мне искренне жаль что ваше Высочество их не оценило

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

Ах, да, перед тем как отвечать на сообщения, я никогда не читаю их содержимое, опять мой косяк, еще раз ПРОШУ МЕНЯ ПРОСТИТЬ О ВЕЛИКИЙ ТРУ ПРОГРАММИСТ!

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

Как скажете, о Великий.

[lawson]

Вы наверное не знаете, что такое материалы и шейдеры, раз задаёте такой вопрос.

нет, ни разу ими не пользовался.

Но отсутствие текстур, позволяет весьма значительно упростить код шейдер

ну и слава богу!

Под персонажем в каждый момент времени может находиться лишь одна клетка. Персонаж размером с клетку. Как в шахматах.

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

У вас наверное весьма пространные представления о многопоточности, если вы возлагаете на неё столь странные надежды.

нет, я серьезно.

[maksimov]

Потенциальные поля тут должны зайти. https://habr.com/post/262181/

Ну, у меня, получается, что во втором варианте как раз таки и реализовано использование "потенциальных полей". Причём, в максимальном их упрощении и оптимизации.
А вопрос состоял в поиске "ещё менее ресурсозатратного способа". =)

Но за ссылку всё равно большое спасибо! Очень классная статья, подарившая массу идей для решения ряда других задач.

* * *
К слову, вот код обоих методов:

Синтаксис:

Синтаксис: [ Показать ]

Используется csharp

public Position GetPositionOne()
        {
            //Position[] characters
           
            Position pos = null;
            while (pos == null)
            {
                pos = new Position(UnityEngine.Random.Range(0, 64), UnityEngine.Random.Range(0, 64));

                if (tiles[x, z] == TileType.Water)
                {
                    pos = null;
                }
                else
                {
                    foreach (var c in characters)
                    {
                        if (Position.Distance(c, pos) < 10)
                        {
                            pos = null;
                            break;
                        }
                    }
                }
            }

            return pos;
        }

        public Position GetPositionTwo()
        {
            //Position[] characters
           
            bool[,] fnya = new bool[64, 64];
           
            foreach (var c in characters)
            {
                int minX = Math.Max(0, c.x - 10);
                int maxX = Math.Min(64, c.x + 10);
                int minZ = Math.Max(0, c.z - 10);
                int maxZ = Math.Min(64, c.z + 10);
                for (int x = minX; x < maxX; x++)
                    for (int z = minZ; z < maxZ; z++)
                        fnya[x, z] = true;
            }
           
            for (int x = 0; x < 64; x++)
                for (int z = 0; z < 64; z++)
                {
                    if (!fnya[x, z] && tiles[x, z] != TileType.Water)
                            return new Position(x, z);
                }

            return null;
        }