Нужна помощь в оптимизации кода игры «Змейка» для Arduino Nano

Question

Нужна помощь в оптимизации кода игры «Змейка» для Arduino Nano

arduino-nano code-optimization

Вот код:

https://pastebin.com/ypWe4NZw

Вот что получается при компиляции:

Sketch использует 13086 байт (42%) пространства для хранения программ. Максимум — 30720 байт. Глобальные переменные используют 1456 байт (71%) динамической памяти, оставляя 592 байта для локальных переменных. Максимум — 2048 байт.

Все идет гладко до getNextFood(), строка 194. Я пытаюсь создать LinkedList целых чисел от 0 до 255 (так как я использую сетку светодиодов 16x16). Однако мой список заполняется только до 39, затем остальные устанавливаются в ноль. Я подозревал, что у меня не хватает памяти, поэтому я попытался оптимизировать несколько вещей и смог получить 42. Я изменил все целые числа на байты в функции getNextFood и получил 61, но это каким-то образом сломало мою программу (цикл inf).

Есть ли какие-либо предложения, как это исправить? Если я смогу уместить этот список, программа в основном готова, мне больше нечего добавить, если она работает так, как задумано.

И, кстати, почему у меня вообще заканчивается оперативная память? Может кто-нибудь объяснить, какие части программы пожирают эти байты во время выполнения (потому что я ожидал, что список целых чисел займет около 512 байт, оставляя 80 байт, так почему же я обрезаюсь около 40 целых чисел или 80 байт?)

Спасибо.

Редактирование 1: Люди указали, что связанные списки занимают много места. Я использую эту библиотеку, потому что программа спроектирована так, что мне нужно было создать массив, который мог бы менять размер. Мне нужно было иметь возможность добавлять и удалять элементы. Может быть, есть лучший способ сделать это, я не знаю. Я думал о том, чтобы сделать один массив 16x16 для всего этого и использовать разные числа для каждого типа элементов. Я не знаю, как бы я делал движение змеи в этом случае, потому что каждый элемент «связан» с тем, который находится перед ним. Если кто-то знает похожую библиотеку, которая сэкономит место, я был бы рад попробовать. Также, возможно, есть способ избежать использования списка tempSnake.

Edit2: По предложению Пола я переписал код, используя один массив 16x16 для представления всего игрового поля, устранив необходимость в LinkedList. Однако, похоже, я все еще не дотягиваю, если только в моем коде нет других ошибок. Программа сбрасывается, когда я пытаюсь сгенерировать плитки еды. https://pastebin.com/ZU4hX477

@user6615434, 👍-1

Обсуждение

Сайты Stack Exchange предназначены для задач, которые можно кратко сформулировать на странице вопроса. Вам нужно будет сузить область действия до того, что можно представить без ссылки. **Зачем вы вообще используете связанный список?** Это будет чрезвычайно затратно для такой системы. Вам следует использовать простой массив, но если у вас нет управления яркостью, даже это не будет излишним, вероятно, вам нужен растровый массив с 1 битом на пиксель. Вы также можете рассмотреть более подходящую платформу, например, микроконтроллер ARM с большим объёмом памяти; некоторые работают с Arduino IDE., @Chris Stratton

Если у вас мало оперативной памяти, старайтесь избегать создания полных копий линейно-развёрнутых списков. Кроме того, вы написали //implement modulus for position: этот оператор уже реализован в C++, и вы можете написать newRow = (newRow+1)%16 и т. д. Но учтите, что для достижения желаемого результата числа должны быть беззнаковыми., @Edgar Bonet

Вам *действительно* нужна сложность и раздутость связанных списков?, @Majenko

Использование макроса F для Serial.print позволит сэкономить несколько байт. Serial.println(F(“example”));, @Gerben

Вам не нужен связный список для определения соседей ячеек сетки; это довольно простая математическая операция с некоторыми ограничениями по краям. Грубо говоря, левое направление соответствует индексу -1, правое направление — индексу +1, верхнее направление — индексу -16, нижнее направление — индексу +16 и т.д., после чего проверяется ограничение по краям. Наличие связного списка для самой *змеи* в некоторой степени разумно, хотя вместо него, возможно, стоило бы использовать массив фиксированной длины с разностями индексов для следующего сегмента., @Chris Stratton

1 ответ

Лучший ответ:

@*Paul* · Accepted Answer · 2018-05-06 19:23-00:00

16x16 = 256

Итак, существует 256 возможных мест, куда можно поместить кусочек змеи. Максимальная длина змейки составит 256 (полностью заполнит доску).

Таким образом, если мы возьмем массив байтов (0-255) длиной 256 байт, мы сможем полностью отобразить змею.

С каждым шагом (если только змея не съела немного еды) вы продвигаете ее голову вперед на один шаг и удаляете последнюю часть.

Так что если мы сделаем новую голову значением "snakeLength" и сделаем каждую часть тела -1 каждый раунд. Мы получим этот эффект "затухания".

Например:

[ 6][5][4] (all -1, head down) [ 5][4][3]
[ 0][0][3]                     [ 6][0][2]
[ 0][1][2]                     [ 0][0][1]

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

Если голова столкнется с позицией, которая не равна 0, игра будет окончена. Для еды/яблока вы можете использовать значение x/y.

Если пробел не равен 0, сделайте его равным -1.

Преимущество этого в том, что вам не нужно выделять память во время выполнения и вы точно знаете, сколько ее используете. Эта настройка также должна помочь вам избежать постоянного «копирования» всего списка. По сути, вы можете пройтись по массиву и сделать -1 для всех, кроме тех, которые равны 0.