Need algorithm!

This isn't a BlitzMax specific issue really, so I thought it best to post here.

Here's my problem:

I have two lists.

I need every object in list A to check to see if it collides with every object in list B.

The problem is, the two lists can share common objects.

In worst case scenario, List A is identical to List B.

For example:

In the worst case scanario, both lists contain these four objects:

O1
O2
O3
O4

If I were to loop through list A and have a loop inside that which looped through list B, then I would end up doing 16 compares (4*4), when all I really needed to do was 10 (4 + 3 + 2 + 1).

It's not really the number of compares which is the main problem though. It's that I need to collide each set of objects only once. But if I have two identical list like that, then I would end up collding each of them twice, which would cancel things out!

Anyway I hope I explained the problem adequately. I'm sure Mark had to solve this problem in Blitz 3D to do collisions there.

For i=1 to 4
for j=i+1 to 4
compare object i with object j
next
next

1 compare with -> 2,3,4
2 compare with -> 3,4
3 compare with -> 4
4 compare with -> none of them

Is that what you mean?

EDIT - oops sorry posted to early I think I misunderstood your problem.

Matty:
Yeah, think of these as objects in a linked list that could be in any order, and there may be only one duplicate, or all of them duplicated. The lists for example could be:

List 1:
2
1
3
5

List 2:
4
5
1

Because 5 and 1 are in both lists, there will be duplicate compares.

What about setting a flag/flags on the first pass then check for the results of that so that you can only do the collision once if there is a second occurance.

or give a unique id to each object and track which ones you've compared with which in an array?

what about, similar to what puki suggested, creating a bank in the style of a 2 dimensional array similar to this:

Dim HaveICheckedThesePairs(MaxElementsList1,MaxElementsList2)

and prior to performing your collision check (or whatever you are hoping to do) check if the current pair have already been checked.

It will still mean you are looping through, at worst, the number of elements^2 but you at least only perform your 'collision check or other intensive routine once per pair.

Perhaps a 2D array where you set a flag for each comparison. Object 10 & Object 12 = flag(10,12) + flag(12,10). Or use the lower value for the first parameter to avoid having to set two flags.

Perturb:
Too cumbersome. Would need to use two arrays and keep empty spots in arrays at the end or search the arrays for empty spots each time a sprite is added and removed. Would confuse uers looking to make changes to the system as well.

Puki:
That's similar to perturbatio's suggestion. One alternative I considered which is also similar though would be to keep a list for each sprite of the sprites that have been collided with it. But that would require me to loop through that list to check it with each collision. Might not be fast and definitely not elegant.

Hm... Maybe there's something to the array idea. I wouldn't need to keep an array around all the time, with specific id's for each sprite. Maybe I could build the array each time I go to do the collisions with the current set of sprites. Or maybe I can convert the lists to arrays and try to do something with that. Hm.

Eh, I said it first?

an alternative might be TMap.

Hm, on second thought, I'm not sure that dynamic array idea would work. The array thing only works if each sprite has a specific index associated with it.

If you can think of a way to use Tmaps for this I'm all ears, but I don't see how they'd be of much help. They'd make searching the lists for a specific value faster, but I want to avoid that searching.

You have two lists: ListA and ListB which contain references to instances of T_Thing. An object can be in either or both lists. You want to efficiently compare each member of ListA to each member of ListB. You dont want to compare members of A to A or B to B unless they are also in the other list.

My suggestion has two requirements:

1) A flag in T_Thing - say MemberOfListA. This will simply indicate which members of ListB are also in ListA.
2) (if not already) A unique Id or memory address such that between any two items one is considered 'higher' than the other. It doesn't matter which is higher just that they are in some order. It is *not* required that the lists be sorted by this Id.

Algorithm:

//  First some initialisation.  This is only required if the membership of ListA or ListB has changed since last pass

//  Set MemberOfListA off for all objects in ListB
foreach (T_Thing item in ListB)
  item.MemberOfListA = false

//  Set MemberOfListA on for all objects in ListA
foreach (T_Thing item in ListA)
  item.MemberOfListA = true

//  Now when we process ListB we'll know which objects will be checked anyway because they are also in ListA

//  Nested comparison loops
foreach (T_Thing A in ListA)
  foreach (T_Thing B in ListB
    if A.Id == B.Id
      continue  //  Don't compare to self
    if B.MemberOfListA and B.Id < A.Id
      continue  //  The test will be performed the other way around
    if TestCollision(A, B)
       ...      //  Handle a collision

That's it. It still considers a * b items but only calls TestCollision the minimum number of times as requested. This is worth doing if the cost of TestCollision is relatively high.

Consider also doing a cheap initial collision test such as just bounding rectangles before a more expensive full test such as pixel perfect.

If you have some moderate to large number of items in one or both lists then there are much better approaches. For example pre-sorting the lists according to the bounding rectangles (say X order within Y order) and doing a skip list process. Probably the best for large cases would be Quad-tree (2D) or Oct-tree (3D). You spend some time preparing the data structure but more than make up for it by the comparisons that you don't have to perform.

Hope this helps.

Is there something wrong with doing this?:

SuperStrict

Graphics 640,480,0

Type TSprite
	Global SpriteList:TList
	Global _IDCounter:Int = 0
	Field ID:Int
	Field X:Float
	Field Y:Float
	
	Function Create:TSprite(X:Float, Y:Float)
		If Not TList(SpriteList) Then SpriteList = New TList
		Local tempSprite:TSprite = New TSprite
			tempSprite.X = X
			tempSprite.Y = Y
			tempSprite.ID = GetUniqueID()
			SpriteList.AddLast(tempSprite)
		Return tempSprite
	End Function
	
	
	Function GetUniqueID:Int()
		Local result:Int
			result = _IDCounter
			_IDCounter:+1
		Return result
	End Function
End Type


For Local i:Int = 0 To 100
	Local tempSprite:TSprite = TSprite.Create(RndFloat()*640, RndFloat()*480)
Next


While Not KeyDown(KEY_ESCAPE)

	For Local s:TSprite = EachIn TSprite.SpriteList
		DrawText(s.ID, s.X, s.Y)
	Next
	
	Flip
	Cls
Wend


GCCollect()

End

Then they all have unique ID's automagically assigned to them without the user needing to know anything about it.

PGF:
That seems like a pretty nice solution. Unless someone comes up with a better one I think I'll go with that.

Just before you posted that I thought I'd come up with a solution that involved looping through each list once and comparing if the pointers were less than those in the oppposing list, but that only worked for my initial test case, and did not work for others. I thought it seemed absurdly simple. Apparently it was.

Thanks! :-)

Perturbatio:
If all I needed was a unique ID, I could just use the sprite's pointer. The problem isn't with that, it is with keeping those id's small enough to be indexes in an array, and that means "defragging" the array so you know what numbers haven't been used.

Also even though whatever algorithm I use will be "hidden" from the user, it won't truly be hidden, because I go under the assumption that I, or they, will need to modify the system at some point and then I'll have to remember how it works, or they'll have to figure it out. :-)

Oh man, I feel like a complete idiot! I've just been wasting our time!

Each collision set has a set of sprites in it. And those sprites CANNOT be in more than one set at a time! Each set contains sprites with a specific collision ID. And as each sprite can have only one collision ID, it can only be in one set!

The ONLY time duplicate tests becomes an issue is when the user specifies that they want all sprites in a set to collide with eachother. And since that is a special case, and the ONLY one, all I need to do in that case is that standard nested loop where you change the starting point of the inner loop each time, which coincidentally is what Matty first suggested.

ARGH! :-)

I figured this out when implementing PGF's suggestion. I was trying to decide what to name the variable in the sprite and trying to see if I could just work around it, and I realised that I could just use the CollisionID to determine if the sprite was in ListA or ListB. Then I realised what an idiot I was. :-)

Providing solutions to problems that you don't really have - Story of my existence.

PGF

PGF:
It's a good solution though. I'll want to remember that one. It may not be useful for this case, but there are lots of times you want to compare things in one list to things in another and the objects can be duplicated between lists.