Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Алгоритм змейки.


Автор: Innuendo 24.2.2006, 22:41
Здравствуйте.
Все знают стандартную игру - змейку... Помогите пожалуйста с алгоритмом- как запоминать изгибы змейки?
ну там всё ясно, при кушании длина возрастает, она всегда идет, при клавиша поворачивается, но вот как изгибы сохранять? smile

Автор: maxim1000 25.2.2006, 02:06
а не проще ли запоминать вообще все сегменты?
впрочем, если все-таки сохранять изгибы, то непонятно, в чем проблема:
храним направление поворота (вправо/влево) и расстояние до следующего изгиба...

Автор: Бегемот 25.2.2006, 02:51
Innuendo, вот что первое пришло в голову!
Допустим, каждая "часть тела" нашей змейки - это квадрат! Вся наша змейка перерисовывается через определённый промежуток времени, при этом она совершает движение в определённом направлении. Т.е. в один момент времени каждый квадрат змейки совершает движение, причём направление квадратов может быть и будет разным! Так вот для каждого квадрата змейки можно хранить определённую информацию. Эта информация, в самом простом случае, будет включать в себя координаты его верхнего угла, которые нам необходимы для отрисовки змейки, а также направление движения квадрата! Все квадраты змейки должны быть связаны между собой! Для примера, на языке C всё это можно реализовать с помощью двусвязного линейного списка!
Код

   enum MoveSnake {LEFT, RIGHT, UP, DOWN};
   const WidthSnak = 10;
   struct DataSnake
   {
      int Top;
      int Left;
      MoveSnake move;
   };

   struct ListSnake
   {
      DataSnake Data;
      ListSnake* next;
      ListSnake* prev;
   };

Как видишь, элемент списка содержит в себе указатели на предыдущий и последующий элементы, а также структуру Data, описаную выше! Структура Data содержит как раз то, очём я уже говорил - координаты и направление движения!
Изначально, мы имеем небольшую змейку(3-5 звеньев), все звенья которой совершают движение в одном направлении! Вероятно, у нас существует какой-то таймер, который через определённый интервал времени, перерисовывает наше пресмыкающееся. Так же у нас есть какая-то функция, которая обрабатывает нажатие клавиш! Так вот в этой самой функции, в случае нажатия клавиш, определяющих движение змейки, мы присваеваем определённому нами флагу нажатой клавиши нужное значение!
Код

MoveSnake FlagKeyPress;
void KeyPress()
{
   .........
   switch(d)
   {
      case 1:  FlagKeyPress = LEFT;    break;
      case 2:  FlagKeyPress = RIGHT;   break;
      case 3:  FlagKeyPress = UP;      break;
      case 4:  FlagKeyPress = DOWN;    break;
      default: FlagKeyPress = -1;
   }
}

Всё нажатую клавишу мы знаем! Теперь таймер! В таймере мы просматриваем с конца(т.е с хвоста нашей змейки) весь наш список и....первое: присваиваем каждому звену в поле move значение предыдущего звена поля move! Т.е. определяем направление его последующего перемещения! После чего перерисовываем звено на новом месте. Когда мы проходим весь список, т.е добираемся до головы змеи, проверяем состояние флага FlagKeyPress. Если его значение равно -1(в моём примере), то направление движения головы мы оставляем преждним, в противном же случае в поле move первого элемента списка записываем значение флага FlagKeyPress.
Ну, а вычисление координат одного звена и его отрисовка может выглядить так!
Код

   switch(list->Data.move)
   {
      case LEFT:  list->Data.Left -= WidthSnak; break;
      case RIGHT: list->Data.Left += WidthSnak; break;
      case UP:    list->Data.Top -= WidthSnak;  break;
      case DOWN:  list->Data.Top += WidthSnak;  break;
   }
   DrawSnak(list->Data.Left, list->Data.Top);

Автор: SoWa 25.2.2006, 07:59
Смотри исходник на Дельфи.

Автор: maxim1000 25.2.2006, 13:50
мысль об оптимизации:
вместо того, чтобы двигать все звенья, можно просто убирать последнее и добавлять одно вперед (а если змейка растет, то и последнее убирать не надо)
конечно, это работает, если все звенья одинаковые и не хранять какую-нибудь уникальную информацию (например, цвет фрукта, от которого они выросли smile)

Автор: SoWa 25.2.2006, 20:17
А разве в примере который я выложил не так?

Автор: maxim1000 25.2.2006, 22:48
Цитата(SoWa @ 25.2.2006, 19:17 Найти цитируемый пост)
А разве в примере который я выложил не так?

когда смотрел первый раз (и когда писал), показалось, что не так
посмотрел во второй раз
оказалось, меня сбили с толку строчки:
Код

   for i:=0 to Max do
        if i < Max then Parts[i]:=Parts[i + 1]
                else Parts[i]:=LastSnake;

думал, тут идет приравнивание на уровне структур
а потом вспомнил, что на самом деле все это - указатели

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)