Things interacting with things

Monkey Forums/Monkey Programming/Things interacting with things

Raz(Posted 2011) [#1]
Great title eh? :D

Anyway, let's say I have 4 different object types. For this example, they are all stored in their own lists.

Class GameThing
	Field Apples:= New List<Apple>
	Field Oranges:= New List<Orange>
	Field Bananas:= New List<Banana>
	Field Grapes:= New List<Grape>

	Method Update:Void()

	End

	Method Draw:Void()

	End
End


I want to check each item in each list to see if they collide with any items in any other list. My current thinking is for each item in each list, I have to check against each item in each list. So if each list has 50 items, that's (200 x 199 [don't check against self]) 39800 separate checks. Maybe I am naive to how much computers can do, but that seems like a lot even for standard rectangle collision checks.

Is there a better way of doing such a thing?


Warpy(Posted 2011) [#2]
If these things are organised in space, storing them in a quadtree would reduce the number of checks you need to do. I can whip up some code if that'd be helpful.


muddy_shoes(Posted 2011) [#3]
Some form of spatial partitioning is likely where you're heading, but there is a quick change that you can do while reading up on that and deciding what fits your purposes best:

I presume a collision A->B is the same as B->A so, if you have three elements, A, B and C in a list, once you've iterated from A and checked A->B and A->C you can skip to checking B->C when you iterate from B. Therefore you don't have to check 200x199, you need to check Sum(x-1,1,200) or 19,900.


Raz(Posted 2011) [#4]
That sounds very helpful to me thanks Warpy :)


Raz(Posted 2011) [#5]
Muddy: ahh yes, you're right. That halves the amount of checks already.


Raz(Posted 2011) [#6]
Also, this kind of brings me on to another 'problem'. What is the most elegant way of handling the following scenario.

A game, has a list of blocks (as a list object) and a player. For each game.update I run player.update which moves the player as required. I want to check the player against the list of blocks for collisions.

1) Should I run these checks within the game.update method?
Or
2) Should I pass the list of blocks to the player and check the list of blocks by going player.update(blocks) and doing the calculation within the player object.

1) Would mean lots of code within the game.update() method but not having to pass a list of blocks
2) Would mean no code within game.update but a list of blocks passed each update call.

Is there a better alternative to the above mentioned ways?


Shinkiro1(Posted 2011) [#7]
Hey,

if your apples, oranges & other stuff are derieved from a base class, like GameObject (below it's TEntity) you could have a CollisionManager Class:

Method Check( list:TList )
	Local e:TEntity, e2:TEntity
	Local SplitList:TList[] = SplitIntoAreas( list )
	UpdateTime()
	Local i:Int,counter:Int
	For i = 0 Until 4
	For e = EachIn SplitList[i] 'as suggested splits the list into areas (here 4)
'if your entity is not moving it has not to check against any other entity
		If (Not e.collision.moving) Then Continue
		For e2 = EachIn SplitList[i]
			If (e = e2) Then Continue
			If Not IsPossible( e, e2 ) Then Continue
			If DistanceOfPoints(e.x,e.y,e2.x,e2.y) < (e.radius + e2.radius)
'Collision occured -> tell the player and enemy about it, like setting collisionOccured to true			
			EndIf
		Next
	Next
	Next
EndMethod

(The above is actually BMax code)

The above Method of the CollisionManager gets a List of all Objects, splits this into 4 Chunks and then runs a loop to check each object against one another.
There are some optimizations though:
* most important: if your game is big, make a seperate List that only holds objects which are on screen.
* if (obj.IsAMovingObject() = False) -> Skip
* if (obj1 = obj2) -> Skip
* if obj1.CantCollideWith(obj2) -> Skip

The last one relies on 2 Methods of the CollisionManager:
'------------------------------------------------------------------------------
' Add a new Collision Possibility
'------------------------------------------------------------------------------
Const PLAYER:Int = 1
Const ENEMY:Int = 2
Const CLOUD:Int = 3

	Field Possible:Int[20,20]
	Method AddPossibility( typ1:Int, typ2:Int )
		Possible[ typ1, typ2 ] = True
	EndMethod


'------------------------------------------------------------------------------
' See if the 2 given Entities can collide
' Returns True if so, else False
'------------------------------------------------------------------------------
	Method IsPossible:Int( entity1:TEntity, entity2:TEntity )
		Return Possible[ entity1.typ, entity2.typ ]
	EndMethod

So you want that the player can collide with the enemy, but not with the clouds:

cm:CollisionManager = New CollisionManager
cm.AddPossibility cm.PLAYER, cm.ENEMY


The nice thing with this is you only have to call
cm.Check( list )

once in your update routine and you are done.
As mentioned above, if you have large worlds (+ 500 objects) it's best to make a seperate list for entities that are actually on screen.

Hopefully that can help you.

EDIT: Maybe this image will help you to better illustrate the concept: [url]http://dl.dropbox.com/u/2892658/forum/collision.png[/url]


Raz(Posted 2011) [#8]
Thanks Shinkiro, it looks very informative and I'll give it a proper look when I get home tonight :)


Raz(Posted 2011) [#9]
Shinkiro, that's brilliant :) Way more clever than anything I've done before and I look forward to getting it working in my game.