Найти все стрелялки в сетке

Question

Я делаю простую сетку, как игра (сетка - матрица 128x128), и матрица заполняется 0 и 1 (1 пуля может пройти, 0 пуля не может пройти, не может продолжать путешествовать больше, также У меня пуля 32 ячейки). Я стою, например, в позиции (32,89). Может ли кто-нибудь предложить мне какой-нибудь эффективный алгоритм для расчета всех стреляющих полей? (Я знаю, чтобы рассчитать простой способ с простой проверкой каждого поданного в диапазоне, но мне интересно, есть ли лучшая идея)

Answer 1

Существует более эффективный алгоритм. Эрик Липперт написал отличную серию теневого кастинга в сетчатых играх. Если я правильно понимаю, это именно то, что вам нужно.

• Shadowcasting in C#, Part One
• Shadowcasting in C#, Part Two
• Shadowcasting in C#, Part Three
• Shadowcasting in C#, Part Four
• Shadowcasting in C#, Part Five
• Shadowcasting in C#, Part Six

Answer 2

К сожалению, нет лучшего способа.

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

Если ваша сетка не изменяется, вы можете оценить ее для каждой позиции и сохранить ее для последующего использования. Это будет использовать память 128 * 128 * (2pi * range), которая составляет около 4 МБ. Если это так, вы можете сохранить его для каждого возможного угла, что приведет к максимальному диапазону 2pi * range = 202, а затем выполнить 202 проверки вместо 1024 (32 * 32), необходимых ранее.