Зеленое счастье и никаких наркотиков!

пятница, октября 22, 2010

Один урок в неделю: Информационные структуры ч.1

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

Пожалуй начнем.

Первой структурой будет список (list), как наиболее употребляемая. Собственно теория из справки:
Списки – это структура с набором элементов, в которой неважен порядок загрузки и выгрузки элементов. Вы можете добавлять элементы в любое место списка, а так же можете узнать положение элемента в списке по его индексу (порядковому номеру в списке). Кроме того Вы можете сортировать элементы списка по возрастанию или по убыванию, и даже перемешивать элементы списка, если Вам нужно создать множество заданных элементов в случайном порядке (например, для перемешивания колоды карт в карточной игре). Внутренняя реализация списков выполнена с помощью массивов, однако работают списки гораздо быстрее, чем, если Вы будете использовать для этого обычные массивы.
 будем надеятся, что товарищи gamemaker_help на меня не будут в обиде, за эту, и другие цитаты в тексте :)
  Года три назад, имея на руках переведенную справку, я бы не понял что здесь написано, наверно потому что иногда проще понять метафорой. Представим, себе, что список это большая длинная комната по типу коридора, склад, в котором имеются ящички, стоящие на размеченном месте.
Мы можем помещать в ящик все что угодно, хотим цифру, хотим текст, а хотим и шоколадку можем положить. Самое интересное, после того как мы создаем наш список (list = ds_list_create();), в нем ничего нет. Т.е. это пустой коридор.
Мы можем положить в него ящичек с шоколадом (ds_list_add(list,choco);). Можем положить еще ящичек с орехами (ds_list_add(list,nuts);). Лично я люблю шоколад с черникой, а все любимые вещи мы обычно кладем, так, чтобы за ними не нужно было тянуться, поэтому, если мы захотим положить шоколад с черникой поближе ко входу, то это довольно легко сделать (ds_list_inset(list,0,bluebery);). Тем же способом, можно поставить между другими ящиками, ящик с молоком(ds_list_insert(list,1,milk);).
К нам на склад, может зайти медведь необразованный, и схватить что нибудь из первого попавшегося ему ящика (medvedTake = ds_list_find_value(list,1);). Образованный медведь, сначала найдет, что ему нужно (educatedMedvedFind = ds_list_find_index(list,nuts);), а затем возьмет это (educatedMedvedTake = ds_list_find_value(list,educatedMedvedFind);) если оно конечно есть, иначе он поймет, что этого нет (educatedMedvedFind == -1).
Нам может надоесть кушать шоколад, и мы его со склада уберем(ds_list_delete(list,1);), при этом все ящики, стоящие после него мы пододвинем на соседнюю позицию, влево. Еще мы можем, убрать все орехи, и насыпать вместо них изюм (ds_list_replace(list,2,raisin);).

Собственно, наиболее употребляемые функции списков я рассмотрел выше. Надеюсь все ясно:) Замечу, что некоторые функции никогда не применял, и пока не вижу в них необходимости.
Вы можете спросить, а в чем собственно преимущество списков над массивами? Мы же можем это все сделать с помощью наших любимых массивов! А я отвечу: - В том, что вы можете передавать список куда угодно и кому угодно. Это как ключ от склада. Даете кому нибудь ключ, а он забирает со склада что ему нужно, или если с добрым помыслом то докладывает что нибудь полезное :). Самое, на мой взгляд крутое, то, что вы можете в любой список положить еще один. Это как сделать дверь в стене нашего склада. 
Вообще, это преимущество всех динамических структур, обычно этому уделяется мало внимания, но я вижу ценность этих инструментов именно в этом. На практическом уроке вы, надеюсь, поймете это.

Следующей нашей структурой будет брат близнец списков - словарь (map).
В некоторых случаях Вам нужно будет хранить пары ключ-значение. Например, у Вас есть персонаж с некоторым набором предметов, а у каждого предмета есть параметр - количество. В данном случае предмет – это ключ, а количество этого предмета – значение. Словари – это набор таких пар, отсортированных по ключу. Вы можете добавлять пары в словарь, а так же искать значение по ключу. Ключи отсортированы, поэтому Вы можете находить следующий и предыдущий ключи. Иногда может понадобиться хранить ключи без значений, тогда в качестве ВСЕХ значений можете использовать 0. Для работы со словарями существуют следующие функции:
Собственно бумажным словарем пользоваться, думаю, умеет каждый. Словарь представляет собой список, где в качестве нумерации используется слово, или, более правильное название идентификатор. При этом слово может совпадать. На практике, мы можем использовать это на нашем складе.
Теперь, мы помещаем в наш склад те же сласти. В качестве нумерации, нам служат надписи на ящиках, а внутри мы кладем некоторое количество съедобностей. Т.е. помещаем 4 шоколадки в ящик, и подписываем его, чтобы не забыть (ds_map_add(map,choco,4);). Образованный медведь теперь может быстрее найти желаемую сладость(ds_map_find_value(map,choco);), прочитав подпись на ящичке :).
Более очевидное применение, словарей, во всем что связано со словами. Например, с помощью словаря, можно сделать поиск перевода для слова. Например сохраняем слово plum, и задаем ему значение слива (ds_map_add(map,"plum","слива")), а потом, когда нам понадобится перевод этого слова, мы просто поищем его в словаре.
из личного опыта: я так реализовал переменные в своем квесте на GML. Очень удобно было хранить переменные в словарях, а потом обращаться к ним с помощью имен, не тратя время на поиск и сопоставление названия значению в массивах.
Собственно, команды аналогичны спискам, и выполняют те же функции. Есть правда несколько других команд, но их будем рассматривать на практике, как столкнемся :).

Последними структурами, рассмотренными сегодня, будут стеки (stack) и очереди (queue). По сути, это одинаковые структуры, и разница у них небольшая но незначительная. Принято представлять себе эти структуры таким образом:
Очередь - представляется как... эээ... очередь :). Стояли в очереди в больнице? Так вот, особенность тут такая, вы можете поместить кого нибудь в конец очереди, или взять кого нибудь из начала. Еще вы можете спросить "Кто стоит первым?" или "Как звать того кто последний?". По научному такой принцип очереди называют FIFO (First-In First-Out), первым пришел, первым ушел.
из личного опыта: здесь вам не больница, и воткнуть что нибудь или кого нибудь в середину очереди, или в начало у вас не получится :). Очереди в больнице называются очереди с приоритетом (приоритетные очереди/priority), тут зависит, пройдет ли кто нибудь первым к врачу, от того, состоит ли человек в списки приоритетных граждан (инвалид, участник ВОВ),  у кого толще харя,  или шире жопа (простите за мой французский), или кто состоит в тесном знакомстве с врачем, ну еще как исключение, иногда удается пройти по записи.
Стек - за этим иностранным словом, кроется другой принцип очереди LIFO (Last-In First-Out). Кто первым пришел, тот последним и уйдет. На практике применяется во многих не очевидных местах, иногда в больнице, когда врачи принимают по записи, а вы записались на самое последнее место. В реальной жизни, вы сталкивались с этим, когда необходимая вам книга оказывалась в самом низу ящика с книгами. По правде говоря, стек очень мощная и полезная штука, с его помощью, например, организован вызов процедур и анализ выражений практически во всех языках программирования. Так что, если вы не были знакомым с дедушкой стеком, то самое время познакомиться. Я представляю его как стопку книг. Вы прочитали одну книжку, положили ее на стол, потом прочитали вторую, положили ее на первую, взяли вторую книжку, положили третью на первую, а потом положили вторую на первую. И чтобы достать первую, нужно достать вторую а потом третью. Короче все запутано, но попробуйте найти три книжки в доме, и сложить их в том порядке который я написал, и все станет на свои места.
из личного опыта: еще есть одна информационная структура, о которой не принято говорить как о динамической информационной структуре, хотя она обладает теми же свойствами и даже схожими функциями. Можете назвать это хаком(hack). У этого хака есть множество применений. Но в основном, конечно, они связаны с прямым назначением этих функций, но иногда удается положить туда что нибудь неординарное. Пользоваться этой структурой также удобно и полезно как и вышеперечисленными.
Теперь, поговорим о продолжении нашего урока. На самом деле мне не терпится приступить к его написанию и опубликованию :), но я подожду до воскресения. Речь пойдет об интерфейсе. Я очень люблю программировать интерфейсы. Это то, что игрок видит чаще всего, и с чем игрок взаимодействует больше чего. Мне нравится создавать оригинальные кнопки, ползунки, чекбоксы и прочее-прочее. Собственно, со всеми информационными структурами я познакомился благодаря программированию именно интерфейсов. Написал несколько движков для рисования и взаимодействия оконного интерфейса. Получил от этого массу удовольствия, а теперь хочу поделиться с вами опытом написания подобного.

Комментариев нет:

Отправка комментария