'Self-aware' classes?
-
Hi guys... long time reader first time poster. Please be gentle. I avidly create games in VB.net. Being a hobby programmer I give my games away for free. Since I'm a hobbiest without formal training I do try and educate myself on proper programming principles and follow them when programming such as OOP. There are however some things I have obviously missed being self-taught that perhaps I would know if I were formally educated. Once such issue that has really been my bane is how different classes (from now on referred to as objects) 'know' about each other WITHOUT programming specific interaction (stay with me here... please...) Okay imagine this, you have a space game and the following objects clsShip clsMissile clsAsteroid clsSpaceJunk Now each one of these objects has a Health, X,Y and Z private members and properties that are all inherited from clsSpaceEntity for argument sake. Now one way of programming collision between them would be to code out the following logic in the main game loop for each ship in a list of ships check each clsMissile in a list to see if it collides with it and if so, reduce health check each clsAsteroidin a list to see if it collides with it and if so, reduce health check each clsSpaceJunka list to see if it collides with it and if so, reduce health ... and so on and so on for every object next ect ect ect... Now this might seam okay if your talking about the simple example above but some of my games have tens or even HUNDREDS of objects that interact in this basic way. Now my question to the experienced programmers out there. Is there a way in OOP to do the following... for each thing that inherits from clsSpaceEntity check against every other object that inherits this type (except itself) and if they collide then reduce health next ? This sort of ability for a type of objects/class or whatever to be 'aware' of another and how they are the same/different and interact would save me tonnes and tonnes and TONNES of coding. Any assistance/help or feedback on this would be very appreciated. Thank you for your time, sorry for the long read.
-
Hi guys... long time reader first time poster. Please be gentle. I avidly create games in VB.net. Being a hobby programmer I give my games away for free. Since I'm a hobbiest without formal training I do try and educate myself on proper programming principles and follow them when programming such as OOP. There are however some things I have obviously missed being self-taught that perhaps I would know if I were formally educated. Once such issue that has really been my bane is how different classes (from now on referred to as objects) 'know' about each other WITHOUT programming specific interaction (stay with me here... please...) Okay imagine this, you have a space game and the following objects clsShip clsMissile clsAsteroid clsSpaceJunk Now each one of these objects has a Health, X,Y and Z private members and properties that are all inherited from clsSpaceEntity for argument sake. Now one way of programming collision between them would be to code out the following logic in the main game loop for each ship in a list of ships check each clsMissile in a list to see if it collides with it and if so, reduce health check each clsAsteroidin a list to see if it collides with it and if so, reduce health check each clsSpaceJunka list to see if it collides with it and if so, reduce health ... and so on and so on for every object next ect ect ect... Now this might seam okay if your talking about the simple example above but some of my games have tens or even HUNDREDS of objects that interact in this basic way. Now my question to the experienced programmers out there. Is there a way in OOP to do the following... for each thing that inherits from clsSpaceEntity check against every other object that inherits this type (except itself) and if they collide then reduce health next ? This sort of ability for a type of objects/class or whatever to be 'aware' of another and how they are the same/different and interact would save me tonnes and tonnes and TONNES of coding. Any assistance/help or feedback on this would be very appreciated. Thank you for your time, sorry for the long read.
Of course you could write a method in your baseclass for each object which takes the list of objects and performs a collision test on each one. Then you would just have to go through your objects and call the method. But if you think about it, this is just a refactored version of what you had before. You would gain nothing. What you need is something out of the old algorithm and data structure box. The problem begins with using simple lists. If you have n objects in the list, you will have to do n^2 collision tests. When the number of objects gets larger, this very quickly becomes very slow. If you have only 10 objects, you must do 100 collision tests. For 100 objects it would already be 10000 collision tests and for 1000 objets it would be a million. You need a way to reduce the number of tests. For example, you can have a sorted or an unsorted list. It's obvious that things are easier to find in a sorted list than in an unsorted one. By being sorted, a list can offer additional information which makes searching or testing the objects easier. But graphical objects usually are not lined up, so a sorted list will be of little help. They are distributed over a plane (2D) or in a volume (3D). Now, what could be the right data structures which can hold additional information on how the objects are aligned to each other? The answer: Trees. For 2D graphics usually quadtrees are used. The objects must be sorted into the tree according to their positions. Then you can easily find objects which are close enough to each other and you must only test those for collisions. But, as always, there is one catch: When an object is moved, it must be taken out of the tree and inserted again according to its new position. Unfortunately you will have to deal with this as well. So here you have it: Search for quadtrees (2D graphics) or octrees (3D graphics) and you will probably find a million pages discussing this stuff. And you will see that those trees are not only good for collision detection. Good luck!
And from the clouds a mighty voice spoke:
"Smile and be happy, for it could come worse!"And I smiled and was happy
And it came worse. -
Of course you could write a method in your baseclass for each object which takes the list of objects and performs a collision test on each one. Then you would just have to go through your objects and call the method. But if you think about it, this is just a refactored version of what you had before. You would gain nothing. What you need is something out of the old algorithm and data structure box. The problem begins with using simple lists. If you have n objects in the list, you will have to do n^2 collision tests. When the number of objects gets larger, this very quickly becomes very slow. If you have only 10 objects, you must do 100 collision tests. For 100 objects it would already be 10000 collision tests and for 1000 objets it would be a million. You need a way to reduce the number of tests. For example, you can have a sorted or an unsorted list. It's obvious that things are easier to find in a sorted list than in an unsorted one. By being sorted, a list can offer additional information which makes searching or testing the objects easier. But graphical objects usually are not lined up, so a sorted list will be of little help. They are distributed over a plane (2D) or in a volume (3D). Now, what could be the right data structures which can hold additional information on how the objects are aligned to each other? The answer: Trees. For 2D graphics usually quadtrees are used. The objects must be sorted into the tree according to their positions. Then you can easily find objects which are close enough to each other and you must only test those for collisions. But, as always, there is one catch: When an object is moved, it must be taken out of the tree and inserted again according to its new position. Unfortunately you will have to deal with this as well. So here you have it: Search for quadtrees (2D graphics) or octrees (3D graphics) and you will probably find a million pages discussing this stuff. And you will see that those trees are not only good for collision detection. Good luck!
And from the clouds a mighty voice spoke:
"Smile and be happy, for it could come worse!"And I smiled and was happy
And it came worse.Thank you so very much for taking the time to reply. The largest problem I have at the moment is actually my physics routine increasing in ms/tick at a dramatic rate. This physics routine calculate the gravity between EACH space entity. As a dense rock or even a ejection pod has density (as well as the blackholes [warpholes] and planets etc). I have optimised this routine many many times to keep reducing the time it takes but it's near 'perfect' for my level of knowledge. I would love to have more then 100,000 objects in my 'universe' however any more then that and I start to suffer noticeable lag. I wonder if the quadtree method will assist with this problem. I'll look into it! Thank you
-
Thank you so very much for taking the time to reply. The largest problem I have at the moment is actually my physics routine increasing in ms/tick at a dramatic rate. This physics routine calculate the gravity between EACH space entity. As a dense rock or even a ejection pod has density (as well as the blackholes [warpholes] and planets etc). I have optimised this routine many many times to keep reducing the time it takes but it's near 'perfect' for my level of knowledge. I would love to have more then 100,000 objects in my 'universe' however any more then that and I start to suffer noticeable lag. I wonder if the quadtree method will assist with this problem. I'll look into it! Thank you
Ahh, gravity. If only Newton had not invented it. Then everything would be much lighter :) I see some room for optimization already. 1) It's a game. You don't have to be overly precise. For many problems even a physicist tends to cut some corners because after a certain point precision is lost due to rounding errors anyway. You could, for example, ignore every object if it is too far away and even precalculate this distance individually, depending on each object's mass. 2) You have large objects with a strong gravity field (planets, black holes and the like) which probably don't move around very much. You also have very small but mobile objects like ships. Why not sweep the smaller objects under the rug and calculate gravity only for the big chunks? The small objects should have little to no significance anyway. 3) If the big objects are static and don't move, you might as well precalculate a map of local gravity vectors with a resolution that fits your needs. Looking up a value in a map is far less an effort than calculating the value at every frame.
And from the clouds a mighty voice spoke:
"Smile and be happy, for it could come worse!"And I smiled and was happy
And it came worse. -
Hi guys... long time reader first time poster. Please be gentle. I avidly create games in VB.net. Being a hobby programmer I give my games away for free. Since I'm a hobbiest without formal training I do try and educate myself on proper programming principles and follow them when programming such as OOP. There are however some things I have obviously missed being self-taught that perhaps I would know if I were formally educated. Once such issue that has really been my bane is how different classes (from now on referred to as objects) 'know' about each other WITHOUT programming specific interaction (stay with me here... please...) Okay imagine this, you have a space game and the following objects clsShip clsMissile clsAsteroid clsSpaceJunk Now each one of these objects has a Health, X,Y and Z private members and properties that are all inherited from clsSpaceEntity for argument sake. Now one way of programming collision between them would be to code out the following logic in the main game loop for each ship in a list of ships check each clsMissile in a list to see if it collides with it and if so, reduce health check each clsAsteroidin a list to see if it collides with it and if so, reduce health check each clsSpaceJunka list to see if it collides with it and if so, reduce health ... and so on and so on for every object next ect ect ect... Now this might seam okay if your talking about the simple example above but some of my games have tens or even HUNDREDS of objects that interact in this basic way. Now my question to the experienced programmers out there. Is there a way in OOP to do the following... for each thing that inherits from clsSpaceEntity check against every other object that inherits this type (except itself) and if they collide then reduce health next ? This sort of ability for a type of objects/class or whatever to be 'aware' of another and how they are the same/different and interact would save me tonnes and tonnes and TONNES of coding. Any assistance/help or feedback on this would be very appreciated. Thank you for your time, sorry for the long read.
In answer to your specific question, the only way you can do what you are asking is to have some sort of collection containing all of the objects you want to check for collision - so the simplest would be an array of dsSpaceEntity that you iterate over.
For i = 0 to sizeOfArray
For j = i to sizeofArray
if Hascollided(Array(i), Array(j)) Then
doStuff(i,j)
End If
Next
NextBut as you say, with a large number in the array this will take time. Using a more complex structure might help. One of the simplest things you can do is eliminate the need to test for collisions as soon as possible. If each object has a left, right, top, bottom property then if the Top of one is lower than the bottom of another, no more testing is required. Do these tests first so you don't do anything more complex unless you have to (for example I have objects with complex shapes, so checking collisions is very time consuming - but I first check for a small number of large rectangles, only looking at the detail level after eliminating as may as possible by other tests. You can also use a radius and center point for each object - and simply calculate the distance between the center points - eliminating further checking if this distance > sum of radii Assuming that MOST collision tests are negative, it is worthwhile doing many tests, eliminating as many as possible as early as possible - e.g. test the top vs bottom, then left vs right, then distance apart - if the two objects fail all three tests there's a fair chance they've collided - so do any further tests (depending on your shape's complexity) And hey, why not post some of your games for us to play comment on the code:)
MVVM# - See how I did MVVM my way ___________________________________________ Man, you're a god. - walterhevedeich 26/05/2011 .\\axxx (That's an 'M')