Простой алгоритм игры, проверяющий правильность перемещения

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

Посмотрите на это изображение:

Правило: если я взял синий шар на белом фоне (в середине), я могу переместить его во все зеленые пространства, и я не могу перенести его на фиолетовые, потому что они вроде как оголенные другими шарами. Я, естественно, не могу переместить его в места, занятые другими шарами. Мяч может двигаться только вверх, вниз, влево и вправо.

Теперь я знаю, что есть два уже существующих алгоритма: алгоритм A * и Dijkstra, который может быть полезен, но они кажутся слишком сложными для того, что мне нужно (как с использованием векторов, так и вещей, которые мне еще не научили, m совершенно новый для программирования, и это мой проект в семестр). Мне не нужно найти кратчайший путь, мне просто нужно знать, оговаривается ли выбранное место назначения другими шарами или нет.

Моя доска в игре представляет собой массив 9x9, просто заполненный '/', если это пустое место или одно из 7 букв, если оно выполнено.

Есть ли способ кодировать алгоритм простым способом?

[Я пошел на заливку флуда, и все работает отлично, спасибо за вашу помощь, и если у кого-то есть аналогичная проблема - я рекомендую использовать заливку заливом, это очень просто и быстро]

Ответ 1

Я предлагаю использовать алгоритм Flood fill:

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

В терминах времени сложности этот алгоритм будет равен рекурсивному: O(N×M), где N и M - размеры входной матрицы. Основная идея заключается в том, что в обоих алгоритмах каждый node обрабатывается не более одного раза.

В этой ссылке вы можете найти руководство по реализации алгоритма.

Более конкретно, как предложил Мартин Боннер, есть несколько ключевых концепций для реализации:

Отметьте все пустые ячейки как неизвестные (все полные ячейки недоступны)
Добавить исходную ячейку в набор маршрутизируемых ячеек
Пока набор не пуст:
- поместить элемент из набора;
- отметьте все соседние неизвестные ячейки как "достижимые" и добавьте их в набор
Все оставшиеся неизвестные ячейки недоступны.

PS: Возможно, вы захотите прочитать Flood fill vs DFS.

Ответ 2

Вы можете сделать это очень просто, используя алгоритм BFS (Breadth First Search).

Для этого вам необходимо изучить структуру данных Graph. Его довольно просто реализовать, как только вы это понимаете.

Основная идея

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

После того, как вы внедрили свой график, используя представление смежности или представление матрицы смежности, вы можете пойти и использовать алгоритм BFS для выполнения того, что вы пытаетесь сделать.