Как хранить карту? :: Создание игр :: Форум

Задался вот таким вопросом. Как хранить карту(игровую область) в памяти? Но! К сожалению, я не догоняю как, например, это реализовано в XCOM. Я знаю что там карта из модулей, но и модули из чего-то состоят.

До чего я додумался.
Карта - массив нужно размерности в длину/ширину(X и Y). В XCOM этажность ограничена довольно сильно и я решил, что разумнее будет иметь в каждой позиции массива указатель на список "клеток" с сохраненными в них "высотами" нежели расширять массив в высоту(Z).
Я привык (иначе и не умею) делать карты банально заполняя массив "проходимостями"(вес) клеток. Соответственно получается какая-то клетка твердая(тяжелая), какая-то проходимая(легкая) и на этом основывается поиск пути. Т.е. стены размером в клетку, а хочется сделать границу между клетками непроходимой(это вот не соображу). Придумал на этот счет только хранить указатели на соседние клетке стены в самой клетке. Это думаю поможет еще и посчитать укрытия(все еще про XCOM), ну и поиск пути не сильно меняется (старина A*).
Вот накидал картинку, маловероятно что на ней что-то понятное изображено(еще там ошибки).
Честно говоря, я не заморачивался долгим поиском материала по этому поводу, поэтому спрашиваю вашего мнения. Какие есть соображения на доработку/переработку моих решений или же есть инфа по используемым структурам?
Благодарю за прочтение этой кучки текста. Я успел потерять мысль несколько раз пока писал, надеюсь это читабельно.

Bullet Heaven:

Не участвую.

Древний организм

Опубликовано 11.02.2016 15:39 (9 лет назад) #

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

Bullet Heaven:

Не участвую.

Инженер‑космогоник

Опубликовано 11.02.2016 18:30 (9 лет назад) #

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

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

Bullet Heaven:

Не участвую.

Опубликовано 11.02.2016 19:04 (9 лет назад) #

Если говорить про первый X-COM, то есть открытая реализация http://openxcom.org/, исходный код которой здесь https://github.com/SupSuper/OpenXcom/. Я посмотрел структуру карты.
Есть класс SavedBattleGame (SavedBattleGame.h, SavedBattleGame.cpp) где хранится вся карта, которая загружается из YAML-файла. Карта состоит из объектов Tile, точнее там Tile** указывает на одномерный массив указателей на Tile, инициализация:
_tiles = new Tile*[_mapsize_z * _mapsize_y * _mapsize_x];
/* create tile objects */
for (int i = 0; i < _mapsize_z * _mapsize_y * _mapsize_x; ++i)
{
Position pos;
getTileCoords(i, &pos.x, &pos.y, &pos.z);
_tiles[i] = new Tile(pos);
}
Фактически карта трёхмерная.
Tile (Tile.h, Tile.cpp) - основной элемент боевой карты, состоит из 4 объектов MapData (MapData.h, MapData.cpp) - самой маленькой части боевого ландшафта (объект, стена, пол). У данного массива, из 4 объектов в Tile, индексами является enum MapDataType { O_FLOOR, O_WESTWALL, O_NORTHWALL, O_OBJECT };, т. е. западная/северная стены, пол или объект.
Класс Pathfinding (Pathfinding.h, Pathfinding.cpp) отвечает за поиск кратчайшего пути, используется A*. Для стоимости прохода там используется метод getTUCost(), который много где есть, в том числе у Tile:
int Tile::getTUCost(int part, MovementType movementType),
где part - enum MapDataType, а MovementType - задан в MapData - enum MovementType{ MT_WALK, MT_FLY, MT_SLIDE, MT_FLOAT, MT_SINK};, я так понял это каким образом происходит движение. Tile::getTUCost использует
int MapData::getTUCost(MovementType movementType).

Надеюсь это тебе немного поможет. Mefistofel похожий способ написал.

Bullet Heaven:

Не участвую.

Опубликовано 12.02.2016 05:08 (9 лет назад) #

Самое простое - это ввести промежуточные ячейки.
Вот я даже нарисовал схему: [img]https://yadi.sk/i/eVUltjU6ohUQH[/img]
Массив - клетки А1, А2, В1, В2 и т.д.
А на карте рисуются только те, что отмечены зелёными кружочками. В2 и др.
Остальные служат информацией о переходах. Там можно ставить метку "стена" или отмечать односторонние переходы (например, спрыгнули с обрыва без возможности забраться обратно).
Но грамотнее, как уже сказали, использовать преимущества ООП и внести данные с промежуточных клеток в виде вложенного объекта в "полезную" клетку. Этот объект будет хранить все переходы для неё. Соответственно, все лишние клетки уберутся из массива в объект нужной клетки.