Instance_System - hpgDesigns/hpgdesigns-dev.io GitHub Wiki

There are a few things an instance system needs to accomplish in order to function properly as a GM-like interface. Obviously, it must store instances for lookup and iteration, especially for event execution. However, there are more intricate aspects of the system that need to be considered.

The pinnacle of these is versatility in loops such as with(){} statements. That statement, along with numerous functions throughout ENIGMA, will require not only linear iteration of all instances, but fast lookup by ID as well as special iteration by object index. Moreover, it will require these one at a time on essentially random occasions. Couple this need with that of heredity, and it becomes necessary to give more serious thought to the system's makeup.

The central dogma of this system is keeping a unified iterator structure. This structure should contain the data member, followed by a pointer to the next and previous items. The data member comes first by design to promote efficiency with ID-based lookup, as so:

struct inst_iterator {
  object* inst;
  inst_iterator *next, *prev;
}

It is better that arithmetic be done to get the pointer to the next or previous item rather than to get the data; this way, ID-based lookup is slightly less taxing. Iteration, however, will not be affected, as both members are required during iteration either way.

The above graphic illustrates the iterator systems at the object-ID level. Note that this does not necessarily imply that every instance listed by iterator is directly an instance of the object given by that ID. The way ENIGMA is structured, heredity as implemented by GM is best emulated by listing all children under each object-ID list. As such, the lists can be redundant, as well as ambiguous, but for the purposes they serve, neither is a problem.

The instance lookup system adds another layer of complication, but overall is relatively simple. This structure is designed for quick, ID-based lookup, and non-redundant iteration of all instances. Structurally, it simply takes the list we see above and implements a "backbone," so to speak. Here, a red-black tree (given by std::map) is used as this backbone to provide lookup in logarithmic time, meaning a reasonable speed at finding instances while still promoting fast and simple insertion. A call to the find function will return, if present, a "with"-ready iterator for all instances.

In the case of with(int(100000..Infinity)), the data member of this iterator can be copied while the Next and Previous members can both be set to point to NULL, automatically marking the end of iteration after the id-requested instance. In the case of with(all), the map can be queried for begin() and the iterator can be copied as it appears and immediately be used to traverse the entire list. This is legal as this backbone enabled list is, as mentioned, neither redundant nor ambiguous.

The object_index based lists, however, are potentially both. To pull off heredity, an instance is, upon creation, added to each list representing the ID of an object from which it inherits. So, if block_destructible inherits from block_basic, it will appear once on both lists, which can be considered redundant. Likewise, iterating a list by object_index does not guarantee that the instances returned are solely of object_index, as they can also be children of such. This is the ambiguous part.

That mentioned, it is implied that changes in behavior due to heredity will flow by nature of this system and will not need accounted for in each function, such as instance_nearest(), or with().

Finally, a second set of these lists will need to be implemented, this time for each event. Keeping a list for each event reduces the number of calls to functions that simply return 0.

Three iterators are kept handy to get the event system and user code working.

1. instance_event_iterator points to the current instance for which code is being executed, This is modified primarily by the event system and is accessed in any functions affecting the current scope.
2. dummy_event_iterator stores any previous value of instance_event_iterator that needed pushed out of the way. (This is so rare an occurrence that a stack has not yet proven necessary, though it may in the future if we experience problems with instance_create() in a create event).
3. dummy_iterator this iterator always points ahead and behind to NULL. When an iterator to a single instance is requested, the instance is crammed into this and returned. As an unofficial standard, EDL functions should copy the inst member from their previous iterator before requesting a new one (or calling a function that will) if they intend to use it afterward.

A behavior that needs to be maintained in ENIGMA is that instance_destroy() mustn't invalidate iterators, nor cause access violations on further code executed before the object itself is destroyed. That in mind, it is essential that a central iterator stack be implemented. See Event System for further details.

Down the road, it may be thought frugal to replace ID-based lookup with pointer-based lookup, eliminating logarithmic lookup time in favor of a constant method. Looking at the above diagrams, implementing this change would require only that the red-black tree be removed. As such, this tree should be #ifdef'd out of the picture where necessary, leaving only a long list of iterator nodes. The rest of the system, including those iterators, remains entirely applicable. This switch, however, would compromise the generally well-sorted structure of the instance list. By prefixing instances created in rooms to the list and appending those created with instance_create() to the list, a pseudo-sort can be accomplished.

The system was chosen because precedence was given to CPU time over memory usage. Offering a variety of storage methods (by object_index as well as by id, and again for each event) while using an additional layer of pointers-to-iterators (the red-black tree) to maintain a uniform iterator (the central dogma of this system) saves on tail-chasing calls in each function or with() statement to determine the type of iterator and to resolve heredity. Without this, each time an iterator were incremented it would have to adopt a special behavior to filter desired elements or ensure (in the case of with(id)) that the iteration ceases when it is supposed to.

Also, again, ensuring that the first element in the iterator is the data element--which the "backbone" structure would otherwise have returned directly--prevents extra cycles that would be required by a double-dereference from the red-black tree; the compiler can treat tree[id]->data just as it would tree[id] if data were the only item stored.