Things interacting with things
Monkey Forums/Monkey Programming/Things interacting with things
| ||
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? |
| ||
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. |
| ||
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. |
| ||
That sounds very helpful to me thanks Warpy :) |
| ||
Muddy: ahh yes, you're right. That halves the amount of checks already. |
| ||
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? |
| ||
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] |
| ||
Thanks Shinkiro, it looks very informative and I'll give it a proper look when I get home tonight :) |
| ||
Shinkiro, that's brilliant :) Way more clever than anything I've done before and I look forward to getting it working in my game. |