Связные списки

Содержание

• Вступление
• Список и его реализация
  • Добавление элементов в список
  • Просмотр элементов в списке
  • Удаление элементов из списка
  • "Продвинутые" списки
• Существующие виды списков в UT
  • Actor
  • Inventory
  • Pawn
  • Navigation Points
  • Mutator
  • SpawnNotify
  • Другие виды списков (кратко)
• Автор

Вступление

Возможно многие из вас встречались с связными списками в программировании, в UnrealScript также возможна организация списковых структур. Одной из причин использования списков является отсутствие поддержки динамических массивов в ускрипте (однако возможно появление таких структур, см. интервью с Tim Sweeney). В настоящий момент списки довольно интенсивно используются в скрипте (инвентори, список мутаторов и т.д.)
Подразумевается что вы имеете неплохое знание ускрипта.

Список и его реализация

Кратко напомню что из себя представляет стандартный связный список.

Список представляет собой цепочку элементов, каждый из которых имеет указатель на следующий элемент. Дополнительно мы имеем отдельный указатель на начальный элемент списка, непосредственные данные хранятся в элементах списка. Последний элемент указывает на "пустой" объект (None). Преимущества такой организации - нет ограничения на количество элементов, легкость добавления/удаления элементов в списке. Основной недостаток - невозможность непосредственного обращения к любому элементу (мы же "знаем" только начало списка). Например чтобы добраться до последнего элемента списка мы должны пройтись по всему списку с самого начала.

Итак, обычный список состоит из следующих компонент:

1. Указатель на начало списка (отдельная переменная)
2. Элементы списка, каждый элемент содержит данные и указатель на следующий элемент

В ускрипте для объявления элемента списка вы должны создать отдельный класс, например:

// Отдельный элемент списка, разумеется необязательно наследовать
// от класса Object, подбирайте по вашему усмотрению
class ListElement extends Object;

var string SomeData; // здесь храним какие-либо данные
var ListElement Next; // указатель на следующий элемент списка

Указатель на начало списка вы объявляете в классе в котором ваш список и используется.

class SomeYourClass extends Actor;

var ListElement TopElement; // указатель на начало списка

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

Добавление элементов в список

• Добавление в начало списка

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

  // создаем новый элемент списка, ниже см. замечание NewElement=new (none) class'ListElement'; NewElement.next=TopElement; // меняем указатель начала списка на новый элемент TopElement=NewElement;

  Замечание: используйте строчку вида:

  new (none) class'ListElement'

  в случае наследования от класса Object, если ListElement обычный актор, то используйте стандартное:

  Spawn(class'ListElement')

  
  
• Добавление в конец списка

  Здесть есть два основных способа:

  • Просто пройти весь список от начала до конца и добавить новый элемент:

    // TempElement - просто локальный объект TempElement=TopElement; // обратите внимание на условие цикла While (TempElement.next!=none) TempElement=TempElement.next; // TempElement сейчас указывает на самый последний элемент списка // Теперь добавляем новый элемент TempElement.Next=new (none) class'ListElement';

    
    

  • Другой метод используется в стандартных скриптах (например при добавлении мутаторов). Как вы помните, ListElement - обычный класс и в нем могут быть объявлены функции, например:

    class ListElement extends Object; var string SomeData; var ListElement Next; // Функция в которой и будет производится добавление элемента в список function AddElement (ListElement NewElement) { // Если мы еще не в конце списка, то вызываем функцию // добавления для следующего элемента If (Next!=None) Next.AddElement(NewElement); // Если мы достигли конца списка, то добавляем элемент Else Next=NewElement; }

    Теперь, в вашем основном классе просто используйте код типа:

    class SomeYourClass extends Actor; var ListElement TopElement; ... TopElement.AddElement(new (none) class'ListElement');

    
    
• Добавление в середину списка

  Просто просмотрите список до нужного элемента и затем добавьте новый элемент:

  // Будем считать что SomeElement указывает на какой-либо // элемент в списке // Создаем новый элемент NewElement=new class'listelement'; // Вставляем новый элемент в список после SomeElement NewElement.Next=SomeElement.Next; SomeElement.Next=NewElement;

Просмотр элементов в списке

Наиболее естественный способ - при помощи циклов (for,while,do-until) просматривать все элементы списка с самого начала. Пример с while был рассмотрен выше, наиболее часто используется for:

local ListElement TempElement;

For (TempElement=ListElement; TempElement!=none; TempElement=TempElement.Next)
  // производим необходимые действия

Удаление элементов из списка

Разумеется "просто так" удалять элементы из списка нельзя - нарушатся связи и удаление элемента "разорвет" список. Намного проще - перестраивать связи, как это выглядит примерно показано на схеме (удаляемый элемент Element2):

Правда есть один недостаток - в памяти "висит" ненужный элемент, это нетрудно исправить для акторов - при помощи метода Destroy, на Object классы это не распространяется, т.к. их нельзя удалять вручную. Если элементы вашего списка - акторы, можно еще дополнительно задействовать метод Destroyed() который вызывается для всех акторов подлежащих удалению.

Вот пример кода осуществляющий перестройку связей без удаления самих элементов:

// В классе который использует список
// Element - удаляемый элемент

Function RemoveElement(ListElement Element) {
  Local ListElement List;

  // Если удаляется первый элемент то меняем значение
  // указателя на верхушку списка
  If (Element==TopElement)
    TopElement=TopElement.Next;
  Else
    // Иначе ищем удаляемый элемент в списке и меняем связи
    // по вышеприведенной схеме
    For (List=TopElement;List!=none;List=List.Next)
      If (List.Next==Element) {
        List.Next=Element.Next;
        Break;
      }
}

"Продвинутые" списки

Разумеется вы можете строить более сложные типы списков. Например ввести дополнительный указатель не только на следующий элемент, но и предыдущий. Тогда при просмотре списка и поиске нужного элемента будет тратиться меньше времени. Один из примеров такого рода списков - реализация истории сообщений транслятора в Operation: Na Pali. Здесь можно взять "базовую" реализацию такого рода списков, вы можете использовать в качестве основы в своем коде.

Существующие виды списков в UT

Рассмотрим уже имеющиеся списки в Unreal Tournament.

• Actor

  Описание: все акторы на карте образуют один большой список, обработка которого идет в native коде (хотя на самом деле это динамический массив, однако для простоты жизни :) будет считать этот массив списком). Базовым элементом является объект XLevel (тип Level, где Level в свою очередь является свойством типа LevelInfo), каждый актор имеет ссылку на Level и XLevel.

  Существование: данный список существует как на серверной стороне, так и на клиентской. Когда клиент "получает" актора, тот добавляется к списку. Когда соединение обрывается, актор удаляется из списка (как исключением bNetTemporary акторов).

  Добавление в список: актор автоматически добавляется к концу списка при вызове функции Spawn. Заметьте, что актор LevelInfo всегда первый в списке акторов.

  Удаление из списка: при вызове функции Destroy актор автоматически удаляется из списка.

  Просмотр списка: для просмотра списка в классе Actor определены специальные iterator функции. Они используются вместе с оператором ForEach по схеме: ForEach Iterator_Function(Params). ForEach по использованию аналогичен циклу For. Стандартно определены следующие iterator функции:

  • AllActors( class<actor> BaseClass, out actor Actor, optional name MatchTag );

    BaseClass - родительский класс (прототип) который вы ищете. Найденный актор возвращается в качестве параметра Actor. Если указан MatchTag то возвращаются акторы у которых определен этот тэг (Tag). Следует аккуратней использовать этот итератор, т.к. перебираются все акторы в списке (а их на уровне очень много, обычное дело 700-800 акторов на небольших DM картах). Как и в цикле For есть возможность прерывания цикла при помощи break;

  • ChildActors( class<actor> BaseClass, out actor Actor );

    Действие параметров аналогично AllActors, только возвращаются BaseClass акторы у которых свойство Owner установлено на ваш актор (ваш актор - актор класс в котором используется этот итератор). Скорость выполнения аналогична AllActors.

  • BasedActors( class<actor> BaseClass, out actor Actor );

    Возвращаются все BaseClass акторы у которых свойство Base установлено на ваш актор. Скорость выполнения аналогична AllActors. Мало применяется (если вообще применяется).

  • TouchingActors( class<actor> BaseClass, out actor Actor );

    Возвращаются все BaseClass акторы которые "задевают" ваш актор. Скорость выполнения довольно высокая, т.к. используется специальная хеш-таблица коллизий (collision hash).

  • TraceActors( class<actor> BaseClass, out actor Actor, out vector HitLoc, out vector HitNorm, vector End, optional vector Start, optional vector Extent );

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

  • RadiusActors( class<actor> BaseClass, out actor Actor, float Radius, optional vector Loc );

    Возвращаются все BaseClass акторы которые находятся в радиусе Radius от позиции Loc (если Loc не указывается то берется Location вашего актора). Скорость выполнения аналогична AllActors.

  • VisibleActors ( class<actor> BaseClass, out actor Actor, optional float Radius, optional vector Loc );

    По действию аналогично RadiusActors, только также проводится проверка на "видимость" актора из точки Loc. Скорость выполнения такая же как и у AllActors.

  • VisibleCollidingActors ( class<actor> BaseClass, out actor Actor, optional float Radius, optional vector Loc, optional bool bIgnoreHidden );

    Возвращаются все BaseClass акторы у которых установлено свойство bCollideActors=True. Опять используется collision hash, поэтому итератор выполняется достаточно быстро. Но при высоких значениях радиуса (около 900 и более) начинаются "тормоза" и лучше использовать итератор VisibleActors.

  • ZoneInfo.ZoneActors( class<actor> BaseClass, out actor Actor );

    Возвращаются все BaseClass акторы которые находятся в одной зоне с вашим актором. Скорость выполнения аналогична AllActors(!).

• Inventory

  Описание: обычный односторонний список. Список объявлен в классе Actor, поэтому другие акторы (в особенности pawns) имеют доступ к базовому элементу списка.

  Существование: на сервере. На клиентской машине этот список существует только для самого клиента-игрока, списки других игроков ему недоступны. Обратите внимание, в некоторых (довольно редких) случаях в сетевой игре список может "прийти" в неверном порядке и указатель на текущий элеммент списка может сместиться на прошлый элемент в списке, что приводит к "зацикливанию" при просмотре списка. Поэтому при использовании списка на клиентской машине вы должны проверять чтобы было не более 100 циклов. Пример этого смотрите в Botpack.ChallengeHUD, там прямо комментарием отмечен этот случай (функции DrawStatus, DrawWeapons).

  Добавление в список: в классе Pawn определена функция AddInventory, которая добавляет элемент в начало списка (добавление должно вызываться для сервера). Заметьте также, что функция Inventory.GiveTo автоматически вызывает AddInventory.

  Удаление из списка: для этого в классе Pawn определена функция DeleteInventory (опять же, удаление должно вызываться только для сервера). Если просто воспользоваться функцией Destroy, то удаление из списка вызывается в функции Inventory.Destroyed.

  Просмотр списка: для просмотра всего списка:

  Local Inventory Inv; For (Inv=somepawn.Inventory;Inv!=none;Inv=Inv.Inventory) // производим нужные действия

  Также можно воспользоваться функцией:

  function Inventory FindInventoryType( class DesiredClass )

  функция определена в классе Pawn, в ней используется вышеупомянутый цикл, функция возвращает ссылку на объект определенного класса DesiredClass (потомки не учитываются).

• Pawn

  Описание: обычный односторонний список из Pawn`ов контроллируемый в native коде. Базовый элемент списка объявлен в LevelInfo (свойство PawnList), ссылка на каждый следующий элемент - Pawn.NextPawn

  Существование: только на сервере в момент вызова BeginPlay() в GameInfo. Не доступен на клиентской машине и мутаторам в (pre/post)BeginPlay().

  Добавление в список: вызывайте AddPawn() на того Pawn`а которого вам нужно добавить. Добавление происходит в конец списка. Заметьте также, что Pawn добавляет себя к списку при выполнении PreBeginPlay(), так что реально вам не надо будет сталкиваться с AddPawn.

  Удаление из списка: функция RemovePawn() удаляет Pawn`a из списка. Аналогично Inventory, в функции Pawn.Destroyed() также производится удаление из списка.

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

  Local pawn p; For (p=level.pawnlist;p!=none;p=p.nextpawn) // производим нужные действия

  
  
• Navigation Points

  Описание: обычный односторонний список, ссылка на базовый элемент объявлена в LevelInfo.NavigationPointList

  Существование: только на сервере.

  Добавление в список: нельзя. Список генерируется редактором UnrealED.

  Удаление из списка: нельзя.

  Просмотр списка: что-то типа этого:

  Local NavigationPoint np; For (np=level.NavigationPointList;np!=none;np=np.nextnavigationpoint) // производим нужные действия

  Пример использования - см. релики (Relics). Кроме того, в NavigationPoint объявлены еще несколько списков используемые для навигации AI, однако здесь не рассматриваемые (AI вообще довольно сложная штука).

• Mutator

  Описание: мутаторы - это одно из лучших изобретений Эпиков :) Мутаторы объединяются в односторонний список, поэтому несколько мутаторов могут быть запущены одновременно (при этом они даже будут работать :)) Всего определено четыре списка мутаторов: damage, message, HUD и "просто" мутаторы. Ссылка на базовый элемент объявлена в GameInfo (BaseMutator, DamageMutator, MessageMutator), для HUD мутаторов в HUD классе (HUDMutator).

  Существование: "по умолчанию" мутаторы существуют на сервере, однако HUD мутаторы ДОЛЖНЫ быть клиентскими акторами.

  Добавление в список: при загрузке карты передается cледующий параметр:
  ?mutator=MutatorPackage1.MutatorClass1,MutatorPackage2.MutatorClass2,...

  В GameInfo.InitGame() сначала создается базовый мутатор (для UT это DMMutator), затем происходит разбор вышеприведенной строки и мутаторы добавляются к списку (функция AddMutator). Вот отрывок кода из Engine.GameInfo:

  MClass = class<Mutatoractor>(DynamicLoadObject(LeftOpt, class'Class')); BaseMutator.AddMutator(Spawn(MClass));

  
  

  • DamageMutators:

    Для того чтобы мутатор получал вызовы функции MutatorTakeDamage (функция вызывается при каждом получаемом "повреждении" Pawn`ов) нужно добавить его к списку Damage мутаторов посредством функции:

    Level.Game.RegisterDamageMutator(MutatorToBeRegistered)

    
    

  • MessageMutators:

    Данный тип мутаторов стал доступен начиная с версии UT 413. Для добавления в список message мутаторов нужно вызвать функцию:

    Level.Game.RegisterMessageMutator(MutatorToBeRegistered)

    После этого, мутатор будет получать вызовы функций MutatorTeamMessage, MutatorBroadcastMessage, MutatorBroadcastLocalizedMessage.

  • HUDMutators:

    Данный тип мутаторов стал доступен начиная с версии UT 413. Для добавления в список HUD мутаторов нужно вызвать функцию:

    RegisterHUDMutator()

    Затем, мутатор будет получать вызовы функции PostRender для рисования. Однако тут есть пара особенностей которые здесь не рассматриваются. (см. отдельную статью по HUD мутаторам).

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

  Просмотр списка: вряд ли вам это понадобится, но все же приведу "универсальную формулу" UsAaR`a :)

  Local mutator m; For (m=Level.Game.XMutator;m!=None;m=m.NextYmutator) // производим нужные действия

  Для обычных мутаторов:
  X - замените на "base", Y - уберите.

  Для damage мутаторов:
  X - "Damage", Y - "Damage"

  Для message мутаторов:
  X - "Message", Y - "Message"

  Для HUD мутаторов:
  Замените Level.Game.XMutator на "SomePlayerPawn.myHUD.HUDMutator", а Y замените на "HUD"

• SpawnNotify

  Описание: это очень полезный список специальных акторов - SpawnNotify. Более подробная информация http://unreal.epicgames.com/UTMagic.html.

  Как только актор спаунится или передается клиенту, в native коде вызывается функция SpawnNotification(actor) и актор добавляется к списку, указатель на базовый элемент находится в LevelInfo.SpawnNotify. Сам список - обычный односторонний список.

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

  Добавление в список: при вызове SpawnNotify.PostBeginPlay() элемент добавляется в начало списка.

  Удаление из списка: при вызове SpawnNotify.Destroyed() элемент удаляется из списка. Можете свободно использовать Destroyed() т.к. сам актор фактически не удаляется.

  Вся spawn notification система может быть временно деактивирована следующим образом:

  Local SpawnNotify Sn; Sn = level.SpawnNotify; Level.SpawnNotify = None; // производим нужные действия Level.SpawnNotify = Sn;

  
  
• Другие виды списков (кратко)
  
  

  • InterpolationPoint - двунаправленный список интерполяционных точек (например камеры игрока). Список создается в UnrealScript, но все остальные действия - в native коде.

  • Pbolt - плазма луч в альтернативном режиме стрельбы из PulseGun`a aka шафт. Обычный однонаправленный список, к тому же написан далеко не оптимальным образом.

  • Mover - однонаправленный список, причем у каждого элемента есть ссылка на базовый элемент. Используется для муверов которые следуют за другими муверами.

  • Actor.Deleted - список акторов которые удалены и "ожидают" когда их уберет мусоросборщик. Это происходит как только в списке будет 128 акторов, используется только в native коде.

  • SavedMove - однонаправленный список сохраненных движений клиента-игрока. В сетевой игре клиент должен сохранять список старых движений для отправки серверу (для избежания лага и на случай потери передаваемых пакетов). В классе PlayerPawn определены три ссылки: SavedMoves (начало SavedMove списка), FreeMoves (еще не "занятые" движения), PendingMoves (следующее движение которое будет передаваться на сервер). Подробнее смотрите класс SavedMove и функцию PlayerPawn.ReplicateMove()

  • Menu.ParentMenu - ссылка на предыдущее меню в Unreal (помните? То самое, зеленое). Вряд ли вам понадобится иметь с этим дело. Разве что в УТ такую менюшку приделать :)

  • ListElement - двунаправленный список, класс определен в UTServerAdmin. Достаточно мощное средство для хранения данных.

  • UWindowList - очень "продвинутый" список, который хранит различную информацию в системе UWindow (см. соответствующий пак).

  • UWindowWindow - также очень сложный список, хранит систему менюшек в UT.

Автор

Автор: Shadow
Mail: shadow_m777@mail.ru

Большая часть материала основана на туториале Linked Lists Part 1 (вся глава "Существующие виды списков в UT") c сайта CHiMERiC.
Автор: UsAaR33
Mail: usaar33@yahoo.com
Web: www.usaar33.com

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