Создание инвентаря

Материал из Клуб любителей рогаликов
Версия от 09:09, 22 августа 2009; Sanja (обсуждение | вклад) (Первая версия)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Я знаю, что эта проблема затрудняет многих из вас. По крайней мере так было со мной, когда я начал собственный проект Roguelike-игры (Legend of Saladir). В этой статье я намерен дать вам некоторые инструменты для изготовления этих предметов, не собираясь при этом давать полный курс обучения по созданию инвентаря, может быть потом я смогу предложить вам больше программ/идей по этой теме.

Я предполагаю, что читатель данной статьи не абсолютный новичок (эй, вы же собираетесь начать делать свою собственную игру! :)) и имеет начальные познания в языке Си наряду с представлением об указателях. И, пожалуйста, простите мне мой плохой английский!

Без всяких дальнейших предисловий, давайте начнём определять основную структуру предмета для всех примеров в этой статье. Это просто пример, определенный здесь предмет не слишком полезен в реальной разработке :).

   typedef struct ITEMTYPE
   {
      int itemtype;
      int weight;
      unsigned int attributes;
   } Titem;

Итак, это просто структура данных, которая содержит всю информацию, необходимую для конкретного предмета. Каждый предмет в игре имеет аналогичную структуру.

Есть два основных метода создания списка предметов для игрока/монстра.

Вектор постоянной длины

Вы создаёте вектор из, например, 100 предметов. Очевидно, это имеет один большой недостаток, вы не можете нести более, чем 100 предметов если программист не изменит код и во-вторых этот вектор всегда занимает 100*sizeof(Titem) байтов памяти, даже если бы Вы несли только один предмет.

Структура информации для игрока будет выглядеть следующим образом:

   typedef struct PLAYERTYPE
   {
      char name[100];   
      int age;

      Titem inv[100];   /* массив инвентаря содержащий 100 предметов */
   } Player;

Итак, это структура, которая содержит всю информацию о нашем игроке. У вас также будут аналогичные структуры для ваших монстров/NPC'ов, они могут быть немного другими, но Вы можете использовать те же методы и для ваших монстров.

Итак, размер постоянный. Хороший момент в том, что делать дополнения и удаления в этот список просто, вы можете непосредственно индексировать. Тем не менее, вы не можете легко вставлять/удалять предметы в/из середины списка. Это потребует заново создать вектор с точки в которую вы добавляете. Это долго.

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

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

Динамическое распределение памяти со связанными списками

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

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

Теперь, сохраняя приведённую выше структуру игрока по большей части такой же, но внося изменения только в части списка предметов мы получим:

   typedef struct PLAYERTYPE
   {
      char name[100];   
      int age;

      InvList *inv;  /* указатель на начало списка */
   } Player;

Я слышу вы спрашиваете, что такое третье поле "InvList *" в структуре.

"InvList" тоже структура, она определяет ОДИН узел для списка предметов. Узел, это один сегмент динамического связанного списка. Посмотрите на эту картинку:

  +-------+      +-------+--+
  | start |----->| node 1| >---\    +-------+------+
  +-------+      +-------+--+   \-->| node 2| NULL |
                                    +-------+------+

Этот пример имеет сходство со связанным списком с ДВУМЯ узлами, первый блок названный 'start' содержит указатель в узел 1, сообщая, что первый узел списка - там. И вы также видите, что в 'узле 1' есть дополнительное поле, которое содержит указатель в СЛЕДУЮЩИЙ узел или 0 (NULL) если список на нём заканчивается.

Так что приведённая выше структура "Player" содержит просто УКАЗАТЕЛЬ в список предметов игрока. Это адрес памяти, хранящий первый узел списка, если в нём что-то есть (или NULL если список пустой!).

А сейчас сравните этот метод с методом вектора, который я показывал вам раньше. Если предметы сохранены в массиве, они будут сохранены в последовательном порядке в памяти ( 1-2-3-4-5-6-..) как один большой блок друг за другом. В случае связанных списков, список состоит из узлов, которые могут быть в памяти где угодно, порядок списка сохранен при помощи указателей, связывающих каждый узел с другими. Этот список назван как "однопроходный связанный список" ("one way linked-list") или "простой связанный список" ("single linked list"), что означает, что вы можете просматривать список только в одном направлении. Есть также список который содержит "предыдущую" и "следующую" связи. Это "двойной связанный" или "двухпроходный связанный" список. Но сейчас я не буду о нём говорить.

Теперь у нас есть структуры для ПРЕДМЕТА и ИГРОКА. Мы должны определить структуру для InvList, определяющую один узел списка.

   typedef struct node
   {
      Titem item;
      struct node *next;
   } InvList;

или так:

   /* определим указатель на элемент списка */
   /* так мы можем использовать "Ipointer" вместо "struct node *" */
   typedef struct node *Ipointer;

   typedef struct node
   {
      Titem item;
      Ipointer next;
   } InvList;

Я буду использовать первый метод.

Первая область в struct - фактический предмет, сохраненный в этом узле, и поле "следующий" содержит адрес на СЛЕДУЮЩИЙ узел, если такой узел существует. (NULL сообщает, что список здесь заканчивается).

Итак в основе это очень простая идея, требующая немного больше работы, чтобы поддерживать этот тип списка предметов, но это даёт некоторые преимущества, которые действительно хороши для Roguelike-игр. Вы можете использовать этот тип списка во многих местах. Например, я использую это в следующих ситуациях:

  • Список монстров на уровне
  • Список предметов на уровне
  • Список предметов, которые несёт игрок
  • Список предметов, которые несут монстры

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

Это практика может быть использована в МНОГИХ других ситуациях, а также и в других программах. Все зависит от вашего воображения и как Вы сможете сделать это решение полезным в конкретных ситуациях.

Тем не менее я должен указать, что этот метод "связанного список" создаст вам впоследствии некоторые проблемы. Подумайте о сэйвах. Вы должны создать программу, которая сохраняет каждый узел из списка и при загрузке вы должны будете построить список заново. Не такая уж большая сделка, но это снова создаст вам немного больше работы :)

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

Какие функции требуются для этого типа списков:

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

Инициализация списка

   void initialize_list(Player *player)
   {
      player->inv=NULL;
   }

Эта программа передает указатель структуре игрока и инициализирует указатель списка на NULL, сообщая, что список пока не существует. (так что игрок не имеет предметов в снаряжении!)

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

Добавление узла

Эта программа добавляет к списку узел. Я использую метод где последний вставленный узел будет помещен в НАЧАЛО списка (таким образом в поле Player->inv) и этот новый узел укажет на предыдущее значение Player->inv. Наподобие этого:

   int add_node(Player *player, Titem newitem)
   {
      InvList *newnode;
      /* выделить память для нового узла */
      newnode=(InvList *)malloc(sizeof(InvList));

      /* если newnode == 0 тогда память закончилась или что-то помешало */
      if(!newnode)
         return 0;

      /* теперь установите новый элемент в область, которую мы распределили */
      /* помните, "newnode->item" похожа на "newitem", оба определяют */
      /* "Titem" */
      newnode->item=newitem;

      /* если инвентарь игрока еще не существует */
      if(player->inv==NULL) {
         newnode->next=0;
         player->inv=newnode;
      }
      else {
         /* точка "next" поля "newnode" на старый инвентарь игрока */
         newnode->next=player->inv;
         /* обновляем указатель на первый узел в инвентаре */
         player->inv=newnode;
      }
      return 1;
   }

Функция возвращает 0 если добавление не удалось, иначе 1.

Удаление узла

Эта программа действительно зависит от факта как вы хотите удалить предмет из списка. Я создаю программу которая удаляет предмет по индексу. Например, вы можете захотеть удалить пятый предмет из списка.

Вот пример, это не оптимальная программа, но она должна быть легкой для понимания.

int delete_node(Player *player, int index)
{
   InvList *node, *tmp;
   int count;

   /* снова проверим начало если инвентарь существует */
   if(!player->inv)
      return 0;

   node=player->inv;

   /* если Вы пытаетесь удалить первый узел */
   if(index==0) {
      player->inv=node->next;
      free(node);

      /* мы сделаем возврат с успехом */
      return 1;
   }

   count=0;
   while(node) {
      /* запомним предыдущий узел */
      tmp=node;
      node=node->next;

      /* увеличить счетчик элементов в списке */
      count++;
      if(count==index) break;
   }

   /* при попытке удалить элемент за границами списка */
   if(monesko>count) return 0;

   tmp->next=node->next;
   free(node);
   return 1;
}

Удаление всего списка сразу

Вот полезная программа для удаления сразу всего списка. Обратите внимание как я просматриваю список.

   void free_list(Player *player)
   {
      InvList *tmp, *freethis;

      /* поместите начало инвентаря во временную переменную */
      tmp=player->inv;

      /* делать пока мы не достигнем NULL */
      while(tmp) {
         freethis=tmp;

         /* присвоить "tmp" следующему узлу, если здесь не следующий узел
            "tmp" будет содержать NULL */
         tmp=tmp->next;
         /* освободить текущий узел */
         free(freethis);
      }
      player->inv=NULL;
   }

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

КОЕ-ЧТО ЕЩЁ

Связанный список просто один из передовых типов данных (часто называемых абстрактными типами данных (Abstract Data Types), ADT), есть много других типов ADTs, которые могут быть полезны в программировании игр. Например, очередь и стек (Queue and Stack). Каждый из них имеет много применений и опять же много путей их осуществления. Некоторые объяснения.

Стек (Stack)

Стек является особым случаем списка. Новые предметы включаемые в стек всегда пойдут в конец списка и когда Вы берете что-нибудь это будет браться с конца. Итак, этот тип списка называется ПОСЛЕДНИМ ВОШЕЛ - ПЕРВЫМ ВЫШЕЛ (LAST IN FIRST OUT) (LIFO). Стек имеет много применений.

  +-+------+
  |3|данные| верх/конец стека (последний добавленный предмет)
  +-+------+
  |2|данные| 
  +-+------+
  |1|данные| 
  +-+------+
  |0|данные| начало стека
  +-+------+

Итак, пункты будут "наваливаться" в стеке. Когда вы берёте что-нибудь из стека, вы получите самый последний предмет.

Один пример из компьютерного мира. Мы хотим проверить является ли строка палиндромом: (строка читается одинаково как справо налево, так и слева направо (задом наперед))

  создаём 3 пустых стека символов
   state1:
   for each_char_in_string do
      put_into_stack1(текущий символ из строки)
      put_into_stack2(текущий символ из строки)
      count=count+1
   end_do

   state2:
   while stack_2_has_something do
      put_into_stack3(take_from_stack2())
   end_do

   state3:
   while stack_1_has_something do
      if take_from_stack1() equals take_from_stack3()
         palindrome=true,
      else
         palindrome=false
   end do

например, для слова "automatic" это будет выглядеть так:

   after state1
   stack 1 contains: automatic
   stack 2 contains: automatic
   after state2
   stack 1 contains: automatic
   stack 3 contains: citamotua
   в state3 мы берем из обоих стеков и сравнить их:
   ? a==c ?
   ? u==i ?
   и так далее...

Очередь (Queue)

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

       первый                                      последний
     +--------+--------+--------+--------+--------+--------+         +-------+
  <--| данные | данные | данные | данные | данные | данные | <-- add | новый |
     +--------+--------+--------+--------+--------+--------+         +-------+

Хорошим примером взятый из Реальной Жизни(tm) может быть ОЧЕРЕДЬ В БАНКЕ. Вы приходите в банк и в нужное вам окошко стоит длинная-длинная-предлинная очередь (сегодня пятница и банк скоро закрывается :), вы должны встать в конец очереди. Когда банковский клерк освобождается, он/она берёт следующего клиента из первой позиции очереди.

Конец?

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

Я благодарю вас за то, что вы прочитали это и извиняюсь за любые ошибки в приведённых мной примерах на Си, несколько могло вкрасться, поскольку этот текст был записан влёт без любой помощи компилятора Си (C-compiler) :)

Если у вас есть любые вопросы, идеи для моей игры или вы хотите сообщить о багах в моих примерах, пожалуйста свободно обращаётесь ко мне по email'у.

Также сходите на домашнюю страницу моего Roguelike-проекта: The Legend of Saladir.

Этот текст написан специально для секции разработчиков Roguelike-Новостей Darren'а Hebden'а (Darren Hebden's Roguelike News). Посетите великие страницы Darren'а в http://www2.krisalis.co.uk/wwwdheb/index.html.



Автор: Erno Tuomainen.
Источник: Creating Inventories.
Перевел: Дмитрий О. Бужинский [Bu], 19.05.2005.