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

Question

[bootch]

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


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

Answer 1

[TheHorse]

Cell: struct {
x,y, height, width: float/double/int/bool (про bool пошутил)
neighbors: list of cell;
isLeftRed, isRightRed, itTopRed, isBottomRed: bool;
}

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

Comments

[bootch]

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

[TheHorse]

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

[xanep]

Я бы предложил хранить список только соседних полей, на которые можно перейти. Тогда отпадет необходимость хранить цвет границы. Для удобства доступа, список соседних полей можно хранить в 4-х массивах — для каждой стороны.

Answer 2

[ertaquo]

Может просто линиями? Пересечения линий довольно легко проверить, да и будет более гибко — можно будет строить любые фигуры, а не только прямоугольники.

Answer 3

[ramilexe]

Может хранить только красные границы? Те, через которые запрещено ходить.

Answer 4

[Виталий Желтяков]

Не надо придумывать велосипедов, используйте стандартную схему:

— Карту с границами в файл php. Обращение напрямую, поиска не надо. У каждой ячейки свой порядковый номер, параметры возможности перемещения и связи с другими ячейками.
— Положение объектов на карте (и игроков тоже) в memcached, можно с дублированием в БД.
— Profit

Comments

[barker]

Несколько раз прочёл вопрос и ответ и всё равно не понял — причём тут php.