Hello, Janek, I've studied a bit the scenario you propose and I've got some questions and proposals related to a possible implementation with Boost.MultiIndex. Janek Kozicki ha escrito: [...]
Imagine that we want to simulate 4 magnets (eg. from loudspeakers) falling down on a ground.
1. To speed up calculation we decide that magnetic interaction does not exist above some defined distance (so we avoid calculating magnetic forces between all magnets).
2. magnets can collide with each other and with the ground
3. we say that ground can collide with the mangnets, and also emits gravity to all of them with unlimited distance.
5. ground doesn't move.
Ok, so let's crank it out. First we name the bodies and the interactions using "bimap<id,std::string> names;". So it will be easier for humans to grasp. Remember that negative number is a group.
names:
id name 1 magnet 1 2 magnet 2 3 magnet 3 4 magnet 4 5 ground -1 all the magnets -2 groups of interactions happening through collision -3 groups of interactions happening through magnetic forces -4 groups of interactions happening through gravity
Why do you assign positive IDs to bodies and negative IDs to groups and groups of interactions? As far as I can see there's no need to use this kind of loose type checking, since IDs for different classes of entities are handled separately.
Now we examine the simulation at some particular point in time. Let's see what interactions are happenning here. We have some bodies colliding with each other (also a three body collision). We have some magnets close enough interacting through magnetic force. Let's say that bodies 2 and 4 are currently too far to interact megnetically.
bodies_involved group group_of_groups Interaction* instance 1,2 -5 -2 ... (collision) 2,3,4 -6 -2 ... (collision) 4,5 -7 -2 ... (collision with ground) 1,2 -8 -3 ... (magnetic interaction) 2,3 -9 -3 ... (magnetic interaction) 3,4 -10 -3 ... (magnetic interaction) 1,2,3,4,5 -11(*) -4 ... (gravity)
(*) -10 is in fact not necessary, because it duplicates information in -4.
During my calculations I must iterate separetely over all "collision" interactions, all "magnetic" interactions, and that (single) gravity interaction. Becuase different formulas govern collisions (Hooke's law), other magnetism (Maxwell's equations), others gravity (Newton's law).
(in fact gravity is so special that currently I do it differently, but let's now try it that way)
Also, my employer told me that "magnet 4" is really special, and I must answer if it will be damaged in this simulation, while others are not important. I must iterate over every interaction where "magnet 4" takes part to calculate something to see if it breaks. But it is simpler to iterate *first* over all "collision" interactions involving "magnet 4". because it's a different mathematical formula that will say if it will break or not. Then iterate over *other* categories with other formula. Also let's say that "magnet 2" is really dangerous for "magnet 4" if they touch each other I must instantly know this.
Now, the point is, that I think (not sure!) is that I should compress this information, to make it simpler (for the computer, not me :-).
So I will use that 'groups' container about which I started this
thread. It contains information already written above.
"bimap<id,group_id> groups;":
id groups it belongs to 1 -1 -5 -8 -11 2 -1 -5 -6 -8 -9 -11 3 -1 -6 -9 -10 -11 4 -1 -6 -7 -10 -11 5 -7 -11 -5 -2 -6 -2 -7 -2 -8 -3 -9 -3 -10 -3 -11 -4
And finally the interaction container will use just one index to identify things (the last column "group_of_groups"):
group_of_groups Interaction* -2 ... (collision) -2 ... (collision) -2 ... (collision with ground) -3 ... (magnetic interaction) -3 ... (magnetic interaction) -3 ... (magnetic interaction) -4 ... (gravity)
OK, here's one possible realization. Note that there are some divergences with respect to some initial assumptions you made, please verify whether they're acceptable: Say bodies are implemented like this: struct body { body(int id):id(id){} ... int id; }; and what you call groups of interactions I'll simply call interactions and model them like this: struct interaction { interaction(int id,int type):id(id),type(type){} ... int id; int type; }; where id is self-explanatory and type codes what you call "groups of groups", using for instance some mnemonic enum: enum{collision=0,magnetic=1,gravitational=2}; interaction i5(5,collision); Now, all the relationships between interactions and bodies can be represented as a multi-index container over pairs of (body*,interaction*): typedef std::pair< body*, interaction*
body_interaction_value_type;
typedef multi_index_container< body_interaction_value_type, indexed_by< hashed_non_unique<body_id_extractor>, hashed_non_unique<interaction_id_extractor>, ordered_non_unique<interaction_type_extractor> >
body_interaction;
where the custom key extractors (which are defined in the complete program attached) do what their names suggest. So, body_interaction has indices on body ID, interaction ID and type of interaction. Some remarks: * Unlike your approach, mine does not create any kind of entities for "groups of groups": instead, the type of each interaction is just an attribute of that entity. I don't see any need for having groups of groups assigned IDs as if they were interactions. * Indices are hashed so as to provide constant time lookup complexities. This works best under the following assumptions: - Each interaction does not involve many bodies (with the possible exception of gravity, which nonetheless can be dealt with with special methods, namely via index #2.) - Each body is not involved in many interactions. As always, only real measurements can tell whether this model can really scale up. In the following examples, assume we've got a container of type body_interaction called bi.
I need to: - iterate on all interactions no. -2, answer: -5 -6 -7
accumulate( acc,bi.get<2>().equal_range(collision),interaction_id_extractor()); This uses index #2 (grouping by type of interaction); note that each interaction will we visited as many times as bodies it involves: to eliminate duplicates a O(1)-complecity consists in accumulating the entries into a unique hashed set, which is what accumulate does (see the code attached for more details.)
- iterate on all bodies in interaction -2, answer: 1 2 3 4 5 (accidentally all bodies)
accumulate( acc,bi.get<2>().equal_range(collision),body_id_extractor()); As the previous, but we extract body IDs instead of interaction IDs.
- iterate on all bodies in interaction -6. answer: 2,3,4
print(bi.get<1>().equal_range(6),body_id_extractor()); We look for all entries with interaction IDs 6 (in O(1) time) and lists their associated body IDs.
- iterate on all interactions from group -2 that involve body 4, answer: -6 -7
print( bi.equal_range(4),interaction_id_extractor(), is_interaction_type(collision)); We (efficiently) list the interactions in whicj voy 4 is involved and filter according to the type of collision. This works on the assumption that body 4 is not involved in many interactions, as explained above.
- iterate on all interactions that involve body 1, answer: -5 -8 -11, -2 -3 -4
print(bi.equal_range(1),interaction_id_extractor());
- check if there is an interaction from group -2, that involves bodies 2 and 4, answer: yes it is -6
print( bi.equal_range(2),interaction_id_extractor(), bll::bind(is_interaction_type(collision),bll::_1)&& bll::bind(does_interaction_affect_body(4,bi),bll::_1)); We look up the interactions in which body 2 is involved and filter as appropriate. I don't really know if this approaches what you've got in mind. Depending on the type of queries you're going to make, it might be benefficial to include more indices, but looks to me like your basic needs could be covered with the model I propose. Complete example attached, compiled under GCC 3.2 HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo