Игры на основе 2D-сетки: представляют проходимость

Рассмотрим игру, основанную на тайлах, где каждый агент может двигаться прямо/диагонально (в 8-ми направлениях). По сути, подобная карта может быть представлена ​​​​как обычная 2D-сетка, где 0 будет представлять проходимое место, а 1 — непроходимое место (я использую Lua):

-- Example : 3x3 sized map
local map = {
 {0,0,0},
 {0,1,1},
 {0,0,0},
}

На данный момент, как мы можем представить проходимость плитки в зависимости от направления, откуда приходит агент? т.е. ячейка [2][2] выше, которая статически непроходима, теперь будет проходима, если исходит из [1][2] (вверху) или [2][1] (слева), но не, например, из [3 ][2] (вниз).

Я подумал об этом, но не смог придумать что-то достаточно чистое для себя.

Заранее спасибо.


path grid path-finding map
person Roland Y.    schedule 15.10.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я бы наложил еще одну 2D-сетку с отдельными байтами. Каждый бит байта соответствует возможному направлению входа, где 1 означает, что по нему можно пройти с этого направления, а 0 означает, что нет. Затем вы можете проверить возможность ввода с помощью бинарной маскировки.

Если в большинство ваших ячеек можно войти с любого направления, вы можете рассмотреть возможность использования карты с абсолютный идентификатор тайла (например, X*MaxY+Y) в качестве ключа и описанная выше байтовая схема, указывающая на возможность ввода. Это медленнее для доступа, но занимает меньше места.

Например, пусть направления изложены так:

Bit #      X offset  Y offset
123        -1 0 1    -1 -1 -1
4 5        -1 0 1     0  0  0
678        -1 0 1     1  1  1

Если я иду в северо-восточном направлении, это соответствует биту № 3. Я могу выполнить маскирование, переведя приведенные выше значения в битовые маски:

1   2   4
8      16
32 64 128

Я могу войти с направления, если следующее возвращает true

Enterability(CurrentX+Xoffset(Dir), CurrentY+Yoffset(Dir)) & BitMask(Dir)

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

Изменить

Итак, скажем, мои направления такие же, как указано выше, и мне нужна площадь, на которую можно войти только с севера. Для этого я устанавливаю бит №2:

Enterability(X)=2

Если мне нужна площадь, в которую можно войти как с севера, так и с юго-запада, я бы использовал:

Enterability(X)=2 | 64

где | — операция побитового ИЛИ.

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

Enterability(X)=(~8)

где ~ — операция «не».

Если мне нужно закрыть дверь, скажем, на восток, я могу отключить этот бит:

Enterability(X)=Enterability(X) & (~16)

Чтобы снова открыть дверь, я использую:

Enterability(X)=Enterability(X) | 16

или, проще говоря,

Enterability(X)|=16

~16 создает битовое поле, состоящее из единиц, кроме бита, относящегося к 16. Использование этого с оператором AND (&) оставляет все биты включенными, кроме одного, относящегося к 16.

Также обратите внимание, что шестнадцатеричная адресация может быть более удобной:

 Decimal          Hexadecimal
1   2   4       0x1  0x2  0x4
8      16   =   0x8       0x10
32 64 128       0x20 0x40 0x80
person Richard    schedule 15.10.2012
comment
Спасибо за быстрый ответ, Ричард. Я не так хорошо знаком с побитовыми операциями/представлениями, но я понимаю общую идею. Хотя я кое-что упустил... На самом деле я искал не проверку проходимости, а то, как ее представить. Учитывая пример, который я привел в OP, как я могу указать, что node[i][j] доступен для входа с этой/той стороны, но не доступен для входа с этой/той стороны и т. д. Тогда проверка проходимости позже должна быть прямая операция, я думаю. Еще раз спасибо, Ричард. - person Roland Y.; 15.10.2012
comment
Я думаю, что я все равно дал бы тот же ответ. Двухмерная байтовая сетка тех же размеров, что и сетка ячеек, является хорошим представлением, где каждый бит каждого байта указывает, доступна ли ячейка. Я отредактировал свой ответ, чтобы показать несколько примеров. - person Richard; 15.10.2012
comment
Ой, извини. Я не понял всей идеи с первого взгляда. Таким образом, общая идея заключается в наложении второй 2D-сетки, где каждая ячейка содержит байт, представляющий, с какого направления в эту ячейку можно войти. Что ж, благодаря гибкости таблиц Lua мне не понадобится дополнительная сетка, я просто упакую этот байт в двумерную сетку узлов, содержащих некоторую информацию о соответствующей ячейке. Но это определенно решает проблему, спасибо, Ричард! - person Roland Y.; 15.10.2012