Jump to content
  • Advertisement
Sign in to follow this  
luca-deltodesco

Not sure how to name this. bitfields and searches.

This topic is 2519 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

a set of listeners like:
Listener = { { Type } , { Type } )

and a set of objects like:
Object = { Type }

The problem:

-----------------

Given two Object's, does there exist a listener which is valid for the pairing of types, where a set of object types xs, is valid for a set of listener types ys if xs and ys have a non-empty intersection.

~ so for example:

listener = ( {A,B,C}, {D,E} )

object1 = {A,D}
object2 = {B}

then the listener is valid for the pairing of object1/object2 since {A,D} n {D,E} != 0, and {B} n {A,B,C} != 0

------------------

We can encode the set of types in a bitfield (assuming for now that we don't care about the limited number of types such an encoding would allow) which makes it very easy to check for the 'validitity' of a pairing, (x&y)!=0 replacing xs intersect ys != 0

But the main issue is how can we store the listeners to make such a search effecient? (Compared to say, having a list of all listeners and iterating them checkign each one to see if it's valid)

Share this post


Link to post
Share on other sites
Advertisement
It's not a homework problem smile.png

# So far, the only ways I can think to solve this are having all listeners iterated through to search for a match

# Or alternatively (and a lot messier) to have a hash table indexed by two Type numerical id's (unique integer for each Type) to the set of listeners which are valid for that specific pair. Then instead of iterating all listeners to search for a match, we instead for each possible pairing of single Type's from the two Objects, look for a valid listener in that table entry.

Whilst a lot messier, that 'could' reduce the number of listeners that have to be matched but it's rather ugly, and it doesn't particularly work well when the two Objects are large since the number of possible pairings explodes. Especcially since I also intend to allow the 'any' type and set subtraction so that an object could have Type set equal to ANY - {A,B} for instance, and if ANY is large the number of pairings will be huge.

Taking the example before:

listener = ( {A,B,C}, {D,E} )




[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

object1 = {A,D}[/font]



[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

object2 = {B}[/font]




we would have entries in the hash table A/D, A/E, B/D, B/E, C/D, C/E for the listener (assuming we order the two id's on lookup)
and when looking for a listener between object1 and 2, check all listeners found when looking up A/B,B/D in the table

Share this post


Link to post
Share on other sites
From what I see:
listener = union of all elements, so L = { A, B, C, D, E }

To test if there's a "pairing", we make another union of object1 and object2: { A, B, D }

The we test for each element in listeners. 'A' in L, 'B' in L and 'D' in L.


Though I don't really understand the problem statement and the example isn't helping much. Is there a less abstract explanation? The term 'listener' is somewhat confusing to me since listeners are never a set of pair of sets, that I could recall.

Share this post


Link to post
Share on other sites
Perhaps another example:

L1 = ({A,B},{C})
L2 = ({B},{D,E})

o1 = {A}, o2 = {B}, o3 = {C}, o4 = {C,E}

then:

for o1/o2: L1 is not valid (both o1/o2 have a non-empty intersection with {A,B}, but we need one object for each of the listener type sets) and L2 is not valid.
for o1/o3: L1 is valid (o1 for first type set, o2 for second type set) and L2 is not valid.
for o1/o4: L1 is valid (o1 for first type set, o2 for second type set) and L2 is not valid.
for o2/o3: L1 is valid (o2 for first type set, o3 for second type set) and L2 is not valid.
for o2/o4: L1 is valid (o2 for first type set, o4 for second type set) and L2 is also valid (o2 for first type set, o4 for second type set)
for o3/o4: L1 is not valid like with o1/o2, and neither is L2

-------------------------

The context is we have a set of objects taking part in the simulation, and we have a set of listeners which listen for events occuring between two objects matching it's set of types.

so when we have o1 = {A,B} we're saying object 1 is both of type A and of type B
and when we have a listener ({A},{B,C}) we're saying we want to listen for an event occuring between an object of type A, and an object that is of type B or C

Share this post


Link to post
Share on other sites
Actually, perhaps it would be best to store on the objects those listeners with which it is compatible (as these should not change frequently), and in the search for compatible listeners between two objects the two sets can just be intersected (with the extra logic to check one can be assigned to both sides of the listener) and do it like this. It would also be more general to do it like this if I want to generalise the type assignments more.

so in the last example, the objects would be given as a pre-computation o1 <- {L1[L]}, o2 <- {L1[L], L2[L]}, o3 <- {L1[R]}, o4 <- {L1[R],L2[R]}

Share this post


Link to post
Share on other sites

The context is we have a set of objects taking part in the simulation, and we have a set of listeners which listen for events occuring between two objects matching it's set of types.

so when we have o1 = {A,B} we're saying object 1 is both of type A and of type B
and when we have a listener ({A},{B,C}) we're saying we want to listen for an event occuring between an object of type A, and an object that is of type B or C


Ah...

We have n object types and m listeners.

Each listener can be represented with a matrix, for example ({A}, {B,C}}: ABC
A.xx
B...
C...

As such we will have m matrices. If such matrices are sparse, we can efficiently represent them with an edge list. If encoded using bitsets, the total memory size will be m * n^2/8 bytes.

Querying for membership is not a O(1) operation, it's a simple lookup in a 3D array, but we need to perform m of them. When testing what A interacts with, we need to test each matrix/set.

But we can change this representation a bit. First, let each matrix look like this (for listener1 = 1, listener2 = 2) ABC
A.11
B...
C...

ABC
A..2
B..2
C...
We can now merge matrices. A B C
A. 1 12
B. . 2
C. . .

Now, instead of encoding matrix as a bitfield, each entry in matrix becomes a bitfield. In last example, the entry at AC would be "11000......". Meaning, A->C invokes listener1 and listener2.

We haven't reduced the space, but queries are natural now. If we are given two objects, A and B, we just query the field at (A,B) and get a list of listeners that should be invoked.

If space is not an issue, we can represent this as an array:bitfield matrix[N][N];

If using bitfield, the solution is not optimal, since for each entry, we need to test m bits. If instead we represent listeners with a list, we get optimal result. O(1) lookup + O(m[sub]a,b[/sub]) listener invocations.


If matrix is large and sparse, it can be represented with a set or map. Lookups will then likely be either logn or amortized O(1), but at potentially great reduction of memory.

Share this post


Link to post
Share on other sites
That is essentially the second solution i made in my second post, only instead of a matrix I had a hashtable with two-keys being the two Types, but the issue being that Objects are composed of multiple types not just one, so you'd have to to take each pairing of the types in the two objects and see for each pair from the matrix/hash if there is a listener.

eg the hash/matrix says that there is a listener for A/B and A/C, but given two objects that might be {C,E,F} {A,D} we would have to test each pairing like C/A C/D E/A E/D F/A F/D until we find a listener, or exhaust all pairings and find there isn't one.

My last suggestion (pre-computing listeners for each single object, and intersecting those sets when looking for one shared between two objects) would have much better performance assuming that the types the objects are composed of do not change frequently (which I believe to be the case in my situation)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!