Как создать пользовательскую структуру данных списка игровых объектов - PullRequest
1 голос
/ 02 марта 2010

Я пишу игру на Flash (игрок 10), и мне нужно найти хороший способ управления списком объектов / объектов / актеров в игре (персонаж игрока, препятствия, враги и т. Д.). У него есть следующие требования:

  • Iterable
  • Объекты, добавляемые и удаляемые во время итерации.
    • Аргумент для функции remove () будет объектом для удаления, а не индексом.
  • [необязательно] Объектам может быть присвоено имя, и они могут быть получены с его помощью.
  • [необязательно] Сортируемый, поэтому некоторые объекты обновляются раньше, чем другие.

Как бы я это реализовал?


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

  • Массив с объектами (записями).
  • Хеш-карта (индекс), которая связывает имена с индексами массива.
  • Еще одна хэш-карта для привязки объектов к их индексам (для удаления путем передачи объекта для удаления).

Удаление сущности сделает соответствующую запись нулевой. Время от времени массив нужно уплотнять (удалять пустые места), иначе он станет слишком большим. Для этого требуется перестроить хэш-карту, чтобы указать на правильные записи (но можно ли это сделать эффективно).

Мысли? Будет ли это хорошо работать? А как сделать сортировку и добавить / удалить при переборе частей?

Ответы [ 6 ]

2 голосов
/ 03 марта 2010

Звучит так, будто вы хотите связанный список.

  • Вы можете перечислить список от начала до конца или закончить до начала
  • Чтобы добавить в коллекцию, просто добавьте начало или конец (просто меняя 2 указателя, очень быстро!)
  • Если сами объекты действуют как узлы связанного списка, то вы можете удалить объект напрямую (просто поменяв четыре указателя, очень быстро!)
  • Связанный список можно отсортировать в O (nlongn) с помощью сортировка слиянием
1 голос
/ 18 апреля 2011

Я использую класс Manager, который я создал, для управления группой объектов, которые могут быть назначены любому «списку» на основе строки. то есть вы можете назначить его «врагам» и «ALL_OBJECTS». Класс использует pop () для почти мгновенного удаления (и использует объект, а не индекс для удаления, как вы хотели).

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

public class AvGlyph extends Object
    {
        // vars
        internal var signatures:Array = [];
        private var _attachment:Object;

        /**
         * Constructor
         * @param attachTo An Object to set as the attachment for this
         */
        public function AvGlyph(attachTo:Object)
        {
            _attachment = attachTo;
        }

        /**
         * Dissolves this, destroying reference to _attachment and fully detaching itself
         */
        public function dissolve():void
        {
            _attachment = null;
            AvGlyphManager.fullyDetach(this);
        }

        /**
         * Basic getters
         */
        public function get attachment():Object{ return _attachment; }

        /**
         * Returns an Array containing all signatures applied to this
         */
        public function get allSignatures():Array
        {
            var a:Array = [];

            var i:String;
            for(i in signatures) a.push(i);

            return a;
        }
    }

И это менеджер для этих:

public class AvGlyphManager
    {
        // properties
        private static var _glyphs:Array = [];

        /**
         * Attaches an AvGlyph to a specified list
         * @param glyph The AvGlyph to attach
         * @param signatures Signature Strings used to represent categories
         */
        public static function attach(glyph:AvGlyph, ...signatures):void
        {
            var i:String;
            for each(i in signatures)
            {
                if(!_glyphs[i]) _glyphs[i] = [];

                if(!glyph.signatures[i])
                {
                    glyph.signatures[i] = _glyphs[i].length;
                    _glyphs[i].push(glyph);
                }
            }
        }

        /**
         * Detach an AvGlyph from a specified list
         * @param glyph The AvGlyph to detach
         * @param signature Signature Strings used to represent categories
         */
        public static function detach(glyph:AvGlyph, ...signatures):void
        {
            var i:String;
            for each(i in signatures)
            {
                var n:uint = glyph.signatures[i];

                if(n == _glyphs[i].length - 1) _glyphs[i].pop();
                else
                {
                    _glyphs[i][n] = _glyphs[i].pop();
                    _glyphs[i][n].signatures[i] = n;
                }

                if(_glyphs[i].length < 1) delete _glyphs[i];
            }
        }

        /**
         * Detach an AvGlyph from all previously specified listings
         * @param glyph The AvGlyph to detach
         */
        public static function fullyDetach(glyph:AvGlyph):void
        {
            var i:String;
            for(i in glyph.signatures) detach(glyph, i);
        }

        /**
         * Returns a Array of all AvGlyphs that have been attached with a specified signature
         * @param signature A signature String used to represent a category
         */
        public static function getGlyphs(signature:String):Array
        {
            if(!_glyphs[signature])return [];
            return _glyphs[signature].slice();
        }

        /**
         * Trace a tree of signatures and their children
         */
        public static function traceTree():void
        {
            trace('a');
        }
    }

Использование просто:

В вашем классе, скажем, Zombie.as, вы могли бы.

public class Zombie extends Sprite
{
    private var _glyph:AvGlyph;

    /**
     * Constructor
     */
    public function Zombie()
    {
            _glyph = new AvGlyph(this);
        AvGlyphManager.attach(_glyph, "enemies");
    }
}

Отсюда вы можете в любом месте приложения / игры использовать:

AvGlyphManager.getGlyphs("enemies");

Который вернул бы массив глифов, перечисленных в разделе «враги». Доступ к самому Зомби осуществляется просто через glyph.attachment. Так что в цикле через все ваши объекты это будет что-то вроде:

var li:Array = AvGlyphManager.getGlyphs("enemies");

var i:AvGlyph;
for each(i in li)
{
    trace(i.attachment);
}

Удаление, вероятно, будет простым, если вы быстро взгляните на AvGlyphManager. Также есть:

AvGlyphManager.fullyDetach(glyph);

Что чрезвычайно полезно, когда вы хотите полностью удалить объект.

1 голос
/ 02 марта 2010

Если вы ищете какие-то другие (и производительные) структуры данных для AS3, в прошлом я находил их довольно удобными:

Структуры данных по многоугольникам

1 голос
/ 02 марта 2010

Похоже, это то, что вы ищете:

http://gamedev.michaeljameswilliams.com/2008/09/20/actionscript-3-collection-class/

Это коллекционный класс для AS3, который расширяет массив и добавляет функции, такие как add () и remove (), а также некоторые действительно полезные функции сортировки. Я использовал его, и он работает хорошо, не было никаких проблем. Надеюсь, это то, что вы ищете, и это полезно для вас.

0 голосов
/ 02 марта 2010

Мое текущее решение заключается в использовании класса EntityManager, который поддерживает словарь всех сущностей, а также массив активных элементов. Первый используется для извлечения сущностей по id. Последний используется для цикла обновления, который выглядит следующим образом:

var len:int = actives.length;
for(var i:int = 0; i < len; i++)
{
    var entity:Entity = actives[i];
    if(!entity.isActive)
    {
        actives.splice(i,1);
        --len;
    }
    else
    {
        entity.update();    
    }
}

Я бы предложил создать интерфейс для вашего менеджера сущностей, реализовать что-то, что работает, а затем вернуться и исправить это позже, если вам нужно повысить производительность или добавить функции.

0 голосов
/ 02 марта 2010

Подумайте над этим: подойдет ли вам массив или словарь? Да, они не слишком быстрые, но они просты в использовании (и соответствуют вашим требованиям).

Если вы правильно разделите свои объекты в соответствии с путями кода, которые они выбирают (то есть статическими объектами, объектами, снарядами), у вас, как правило, будут довольно маленькие списки динамических объектов и большие списки статических объектов.

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

Потому что в конечном итоге это то, что имеет значение: Тратьте свое время на создание игры, а не на структуру данных. :)

Или, может быть, я неправильно понимаю ситуацию?

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