Package net.sf.gridarta.model.face

The face is the appearance of an object.

See: Description

Interface Summary

Interface	Description
FaceObject	Common interface for FaceObject.
FaceObjectProvidersListener	Interface for listeners interested in FaceObjectProviders related events.
FaceObjects	FaceObjects is a container for FaceObjects.
FaceProvider	This interface represents a lazy loader that provides images on demand.

Class Summary

Class	Description
AbstractFaceObjects	Abstract base class for FaceObjects implementations.
AbstractFaceProvider	Abstract Base class for FaceProviders which implements a memory sensitive cache.
ArchFaceProvider	Implementation of FaceProvider which reads images from the arch directory.
CollectedFaceProvider	Implementation of FaceProvider which reads images from the collected PNG archive.
ColourFilter	Class to filter images by simply applying a boolean OR operation.
DefaultFaceObject	A FaceObject stores information and meta information about a face and provides methods for accessing these.
DefaultFaceObjects	Abstract base implementation of FaceObjects.
DoubleImageFilter	An ImageFilter that produces double faces: the source image is drawn twice with a vertical shift.
EmptyFaceProvider	A FaceProvider that does not return any faces.
FaceObjectProviders	Provider for faces of GameObjects and Archetypes.
FilterFaceProvider	A FilterFaceProvider provides modified versions of icons provided by another FaceProvider by applying a Filter.
StretchedImageFilter	An ImageFilter that produces stretched faces.

Exception Summary

Exception	Description
DuplicateFaceException	Exception that's thrown in case a face name was not unique.
IllegalFaceException	Exception thrown to indicate that a face object is not acceptable.

Package net.sf.gridarta.model.face Description

The face is the appearance of an object.

This package contains classes for managing icons in memory sensitive caches. Currently, the keys to lookup the icons are Strings (usually the facename of an archetype), and lookup is done in HashMaps.

HashMaps are fast, but, of course, never as fast as an indexed array. Though, HashMaps are easier to maintain. In case someone complains about the usage of HashMaps instead of arrays in this package, I have documented my performance considerations.

How fast is String hashCode generation?

Extremely fast. Strings are often used as Hash keys, therefore a String's hash code is ached and only calculated the first time a it is queried. All subsequent invocations return the previously calculated, cached hash code.

How fast is HashMap lookup compared with Array indexing?

To index an Array gives a constant speed of O[array] = O(c) where c is the time it takes to address and offset. To lookup in a HashMap gives a performance of approximately O[hashMap] = O(2*c + log2(n)*c*2) where n is the number of HashMap entries. In general, a HashMap gives a very good performance, but not compared with an array when an index can be used.

How does lookup scale?

Lookup is used every time the code needs an image, which is nearly every time some painting is done by Java. Since maps are 2.5-dimensional structures, the lookup part of painting maps gives a general performance of O[paintLookup] = O(O[lookup] * x * y * z). For a map with the size 24*24 and an average tile coverage of 2 faces requires 24*24*2 lookups which is 1152 lookups. And let n, the number of HashMap entries, be 3688. If O[lookup] == O[array], the performance is O[paintLookup] = O(c * x * y * z) = O(c * 1152). If O[lookup] == O[hashMap], the performance is O[paintLookup] = O((2*c + log2(n)*c*2) * x * y * z) = O((2*c + log2(3688)*c*2) * 1152) = O((2*c + 24*c) * 1152) = O(c * 29952) It is a realistic assumption that the number of effective cycles required for performing a lookup in Java is always smaller than 10 times the performance. That means, a complete map paint lookup for the given example map takes less than 300,000 cycles when using a HashMap. Current CPUs execute about 5,000,000,000 cycles per second.

How often is lookup needed?

Repainting is done when a new tile was painted, the map scrolls, a map was loaded, hidden or otherwise gets completely refreshed, an archetype panel scrolls or a pickmap is used. Lookup does not happen more than 2-3 times per second, except for scrolling.

Other considerations

The design to generate artificial indices for faces has some flaws. Keeping several arrays in parallel to hold the same information can cause serious, eventually difficult to find bugs. Such a design also prevents the implementation of dynamic archetype handling, where arches and faces should be loadable, editable and un-loadable during editor runtime. The allocation of several large arrays also is a serious indicator for design flaws when using artificial indices, also these arrays need to be anxiously oversized to not get into ArrayIndexOutOfBounds trouble. The natural index of a face is its name, the object oriented index of a face is its own reference. Mapping face names to face references therefore is a good and clear design and very resistant against bugs or overflows.

Also, an archetype first naturally comes with a face name. To get an index for a face name, it is required to first do a linear search. Linear search is always wrong and averages to O(n * c) which is worse than HashMap performance. If the indices are sorted, a binary search with a performance of O(2*c + log2(n)*c*2), which is exactly what a HashMap does. That means, the term that best describes the usage of artificial face indices for increasing face lookup performance is "Augenauswischerei".

Conclusions

• Do not use the face number for face lookup, use the face name instead.
• Future: Refactor all code to eliminate artificial indices for faces and arches