L2 dream geodata rev 93.

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

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

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

Основная задача геодаты - проверить, может ли объект (персонаж или NPC) пройти от точки A к точке B или совершить действие, стоя в точке A над объектом (объектами) в точке B (в точках B1, B2, B3, ...).

Как же можно получить реализацию геодаты? Самый простой способ - это разделить карту на клетки малого размера, и каким-то образом помечать клетки ("можно ли пройти", "можно ли видеть", "можно ли взаимодействовать"). Вот пример:

(вход справа, красные стрелочки показывают, что в этом направлении идти нельзя).

Плюсы:
- Простота.
- Легко можно вычислить путь от одной точки к другой.
- Легко можно проверить любое действие (помеченные клетки).

Минуты:
- Клетки дискретны, поэтому описание объектов, стенки которых не паралельны или перпендикулярны осям координат, а также объекты, которые будут не полностью вписываться в клетку, будет содержать ошибки.
- Большой объем информации (большой объем информации при хранении и большой объем работ при создании)
- Нужны дополнительные средства для создания "многоэтажности". (создание нескольких слоев).

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

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

Плюсы:
- Наглядность - видно, "где можно пройти, а где нет".
- Возможность создавать "многоэтажность".
- Малый объем информации для описания.

Минусы:
- Сложный алгоритм создания самих областей.
- Сложная реализация и взаимосвязь.
- Сложный алогоритм поиска пути.

Ccылка: dump