Как приготовить случайную еду в игре со змеями на c?

Question

Я пытаюсь создать игру со змеями, используя C.

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

Вот мой текущий алгоритм для generateFood.() функция:

1. генерирует случайную пищевую координату
2. , пока координата находится на змеиной голове ||body:
3. генерировать новую случайную продовольственную координату

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

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

но я считаю, что этот метод неоправданно сложен и может занимать много памяти и времени.

Есть ли другие способы, которыми я могу сделать это намного более эффективно на C?ТНХ

Answer 1

Я думаю, вам нужно 2 массива.

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

Всякий раз, когда вы занимает новый пиксель , вы удаляете его из массива свободных пикселей. Если это был последний элемент, вы просто уменьшаете счетчик для свободных пикселей. Если это не последний пиксель массива свободных пикселей, вы «поменяете» его последним пикселем свободного массива первым.

Поскольку массив свободных пикселей и карта свободных пикселей связаны друг с другом, занятие нового пикселя занимает только O (1) обновлений структур; То же самое относится и к моменту освобождения пикселя.

Теперь выбрать произвольный свободный пиксель для еды действительно просто, это операция O (1) - просто выберите число от 0 до n_free_pixels - 1 и выберите ith пиксель из массива свободных пикселей.

Для этого подхода вам потребуется около 4-8 байт дополнительной памяти на пиксель; если, скажем, 320x200 достаточно, то 4 байта на пиксель для 256k (у обоих массивов будут шорты без знака). НО, если вы положите еду в сетку и посчитаете, что положение сетки непригодно, если змея занимает какую-либо ее часть, тогда вы можете получить намного меньше.

---

Рассмотрим карту 2х2 для простоты. В начале все пиксели свободны, поэтому содержимое карты будет

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 1 | 2 | 3 
|  0  |  1  |
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  3  |
|     |     |
+-----+-----+

Затем вы хотите выбрать один пиксель, который должен занимать, и выбрать число от 0 до n_free - 1. В этом случае 1. Теперь вы берете позицию пикселя из списка свободных пикселей по индексу 1 (который также равен 1). ..

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 1 | 2 | 3 
|  0  |  1  |               ^
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  3  |
|     |     |
+-----+-----+

Мы помечаем этот пиксель как зарезервированный на карте свободных пикселей

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 1 | 2 | 3 
|  0  |  #  |               
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  3  |
|     |     |
+-----+-----+

Поскольку позиция в свободном списке была не последней, мы поменяемся местами последний элемент (пиксель 3) в эту позицию, и обновите свободную карту, чтобы указывать на этот индекс, и, наконец, уменьшить n_free на единицу:

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 3 | 2 
|  0  |  #  |               ^
|     |     |
+-----+-----+         n_free = 3
|2    |3    |
|  2  |  1  |
|     |  ^  |
+-----+-----+

---

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

Free pixel map        Free pixel list
+-----+-----+
|0    |1    |         | 0 | 3 | 2 | 1
|  0  |  3  |                       ^
|     |     |
+-----+-----+         n_free = 4
|2    |3    |
|  2  |  1  |
|     |     |
+-----+-----+

Answer 2

Один из способов решения проблемы заключается в следующем:

gridSize = getTotalNumberOfCells()
snakeSize = getSnakeSize()
cellsLeft = gridSize-snakeSize
randomCell = random(cellsLeft)

cell = 0
do
    while occupiedBySnake(cell)
        cell++
while randomCell-- > 0

Этот метод проходит по ячейке один за другим, пока не пройдет randomCell количество ячеек, НЕ считая ячейки, занятыезмея.

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

Если у вас сетка 300x300 (ОЧЕНЬ большая игра змей), у вас будет почти 100000 ячеек.Проверка, занята ли ячейка, должна быть в состоянии сделать в течение максимум 200 нс.Я предполагаю, что отсутствует кеш, что будет редко.200 нс * 100000 = 0,02 с.Этого достаточно для 50 кадров в секунду.

Обратите внимание, что я был очень пессимистичен.200 нс довольно долго.От 50 до 100 более типично при доступе к памяти.Но на практике сетка из 100000 ячеек всегда будет находиться в кеше L2, который имеет типичное время доступа 20 нс.Если вы уменьшите размер до 200x200, то, скорее всего, вся сетка помещается в кэш L1, время доступа которого составляет около 1 нс.Таким образом, для сетки 200x200 этот метод может дать 25000 кадров в секунду.Вам нужно больше или этого достаточно?;)

Но я чувствую преждевременную оптимизацию в вашем вопросе.Он работает достаточно быстро?Если да, зачем?

Я считаю, что этот метод неоправданно сложен и может занимать много памяти и времени.

Что ж, если вам это не нужно, то наверняка это слишком.сложно.Но ваша забота об использовании памяти неуместна.Можете ли вы представить себе запуск игры на компьютере, где использование памяти было бы проблемой, когда вы кодировали это на C?Тем более, что размер этого дополнительного списка будет расти линейно с размером сетки.Если вы не планируете запускать эту игру на компьютере с начала 70-х годов, я могу заверить вас, что это не будет проблемой.

Answer 3

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

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