Fio:Iterators
From Fio
"To iterate is humane, to recurse - divine!"
[edit] Iterator
Contents |
One Design Principle of Fio is:
- Rendering is a preorder iterating process; Picking is a postorder one.
while rendering is to draw the game world and picking is to dispatch mouse event so that the player can interact with the game.
In Fio we use a typical GoF Iterator:
template<typename T>
class Iterator{
public:
virtual ~Iterator(){}
virtual void first() = 0;
virtual void next() = 0;
virtual bool isDone() = 0;
virtual T current() = 0;
};
we can call first() to position an iterator to its beginning; next() to step to the next element in current iterating order. And when isDone() returns true, there's no element left to iterate. current() returns the element the iterator points to.
Armed with a preorder itor we can render the game with little effort
// draw root
drawComponent(surface, root);
// draw content
PreorderItor<Component*> pre(panel);
for(pre.first(); !pre.isDone(); pre.next()){
drawComponent(surface, pre.current());
}
The render itor should know how to iterate on the structure of the world and it begins from the root of the world.
[edit] Root of The World
In Fio, the world is orgnized in Composite pattern:
Component *<---------
^ |
----|-------- |
| | |
Leaf Composite --
Leaf classes are those components who have no child component, such as Button, Lable, Icon etc. Comosite classes can contain other component(s) - e.g. Panel, List, ListItem, GamePanel, Scene, Layer, Cell.
Using composite, the world is orgnized into a tree structure and the root is a panel. We start from main menu of fallout2 as an example:
root panel(main) ->(6) button
|->(1) cursor
when click a button to load a new game:
root panel(load) ->(1) cursor
and when the game loaded, it's more complex:
root panel(play) -> game panel -> scene -> glass layer ->* shadow
| | |->* floater messages
| |
| |-> roof layer ->* cell ->* tile
| |-> wall layer ->* cell ->* tile
| | |->* active object
| |
| |-> cursor layer -> hex cursor
| |-> tile layer ->* cell -> tile
|
|-> face panel -> inv button
| |-> pip button
| |-> option button
| |-> change weapon
| |-> skill dex
| |-> item panel -> item icon
| | |-> ap lable
| | |-> targeted lable
| | |-> weapon mode lable
| |
| |-> message list ->* list item -> lable
| |-> hp counter
| |-> ac counter
| |-> combat icon
|
|-> cursor
[edit] Preorder & Postorder
[edit] preorder
A preorder iterating process works just as the standard Painter's algorithm which is (though) mainly designed to solve the visibility problem in 3D rendering. The algorithm works like "a simple-minded painter who paints the distant parts of a scene at first and then covers them by those parts which are nearer. The painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order.". Here we draw the lower part of a screen - which is the root panel first. Then draw those ones higher than the root panel(or, the content of root panel) - embeded panel or other widgets - over their parent. The itor will traverse thru the hierarchy structure from root to leafs, layer by layer. This way the components pile up in correct order and the screen is rendered.
[edit] postorder
Postorder itor models kind of window system behavior. It's for event dispatching. When mouse is clicked, if the component under the cursor responds to the click, the event sinks here. Else the event dispatcher will have to look up further to find if the component's parent will take care of the click. The event might go to root panel and finally sink there if no one shows interest.
Postorder itor the reverse of preorder. The iterating starts from most specific/lowest component first and ends at more generic/higher ones in the tree of components.
[edit] intersecting
Component need to intersect with the cursor position to response to mouse event(named picking). For most widget components are rectangle shaped (Lables, Buttons, List, Panel, etc.), it's easy to decide if the cursor is inside or not. But for game objects(doors, street lamps, critters, guns on the ground, barrier, etc), we need pixel-level intersecting. The picking will not stop until it reaches a non-transparent pixel of the tile image of a component. See Frm format for details of image format.
[edit] Iterators: Policy v.s. Mechanism
There're itors who do the labor of stepping and there're ones who define the order of stepping.
[edit] Mechanism
Concrete iterator can:
- proivde an interface to iterating on data structures(vector, list, hash_table etc);
- hide off an algorithm(e.g. a Bresenham line itor).
For vector and list, we need 2 types of itor - forward and backward - to itor in different direction of the structure. A vector itor is enough for most non-leaf components.
There's a NullItor defined to act as a dumb itor whose isDone() always returns true. It's used for leaf components to ends further iterating.(kind of Null Object pattern)
[edit] Policy
Knowing how to iterating each component, we need preorder and postorder to iterating over the whole game world based on those concrete iterators to carry out the strategy of drawing or event dispatching.
It's a little tricky to pack preorder/postorder algorithm into the Iterator interace. Chap 2 of the GoF book describes an implementation of PreorderIterator.
[edit] Who Create?
Concrete itors will be created by component itself - who knows its own structure. A panel holds all its contents in a vector, so it can returns a forward vector itor for drawing and a backward vector itor for event dispatching. Buttons always return NullItor - there's no difference between forward and backward for a NullItor.
As said above, preorder and postorder itors are policies to be applied based on concrete itors. They both represent an algorithm or strategy. In Fio the drawing is performed by Fio:Painter; the picking is by Fio:Router.
- Note:
Drawing and picking happens in each game loop(20~30ms), it's too generous to create the itors each time when required. Component can do some caching to save some cpu ticks - return the saved itors, update only when contents changes(lable text changed, list scrolled, button removed from panel, etc.).
[edit] Isometric Iterator for Layer
Isometric Itor is designed to carry out the rendering and picking in a layer. It's a concrete itor - it hides away the isometric-stepping algorithm.
[edit] drawing
Drawing starts from the left top corner of the screen. We can easily map that corner from screen coords to a cell in the layer using the mapping formula. From this cell, we step to right. And when the right bound of screen reaches, we step to the next line of cells - compensate for each line(again check Jim Adams' article). While the itor marchs along, the cells far from the player got painted first and the nearer ones may cover on those further ones - the Painter's algorithm is implemented. When the lines of cells fills the whole screen, we stops. An illustrate of the drawing order of the cells(nearer walls covers the further ones at two of the corners):
For there may be cells just surrounding the edges of screen and only part of their tiles can be seen. These cells also need to be drawed or there might be holes left on the edges. It's easy - just inflate the screen rect to include those cells.
[edit] picking
Picking starts from the bottom for in the isometric world 'bottom' is nearer. It steps from left to right then steps to upper line when a right bound reaches.
[edit] i step out of the layer!
When a layer is scrolled to edges or it is too small in dimension to cover the whole screen, an itor might step out of the layer. This might happen when stepping any line of cells. Instead of implementing some complex edge tracking method, a simple approach is good enough:
When itor steps out of layer - don't panic, just keep stepping(call next()) until:
- step into the layer again;
- iterating ends.
This approach works for all conditions - scolling, small dimension, etc. And performances of different conditions are all the same.
