Object Comparing
BlitzMax Forums/BlitzMax Programming/Object Comparing
| ||
Okay I'm after a method of comparing objects with each other, so that I can run an algorythm to compare thier positions with each other's positions, like planet attraction maths, but I dont know how to do this in thier update() If I place a for loop in there it's real slow! naturally, this is what I've tried so far, cut right down
Type Body
Method Update(other:Body)
If other <> Self Then
x:+ other.x;
y:+ other.y;
Endif
End Method
End Type
' In the Loop
For local bod:Body = EachIn body_list
bod.Update(bod);
Next
Obviously this won't work, but I just can't think of another way? Thanks. |
| ||
| Hmm, what's the problem you are trying to solve? |
| ||
I have thousands of suns and I have an algorythm that compares each sun's position, the mass, everything and uses this to apply velocity to each body, but the algorythm needs nesting within the Body update() and then it needs to compare it's own variables with other Body variables, originally I had a for loop in the Update, that worked! But VERY slow, like this
Method Update()
For local bod:Body = EachIn body_list
If body <> Self Then
' Go ahead
x:+vx * delta.
gr = gravity * bod.mass / ( BLAH BLAH You get the idea
Next
Next
End Method
I need to somehow do away with the nested for loop and do it externally. |
| ||
| Is this for a game or some sort of realistic simulation? If it is for a game, I would think it would be easier to fake something that approximates the effect you want. So it would be much less CPU intensive. |
| ||
| Overload and use the compare method. |
| ||
| "I have thousands of suns"... whadda heck are you building? :) simulation? game? |
| ||
| HAHA, it's a simulation, but it can be setup to be a game easier enough :) It tops out at 10,000 suns, from there it begins to slow down, but it is quite amazing, but without sorting this problem out it's max is 300 and it's sloooooooow as hek. I've tried to Overload but it has undesirable effects, I'm not sure how to do it properly? I tried adding the sim code to the Overload and it didn't work properly. I might have to go back to C++ perhaps, find a type casting method? Thinking out aloud now. |
| ||
| Does it need to update them all each frame, or could you do the updates in batches per frame? |
| ||
| Can you use something like a bounding box or a shifted grid to only check those which are in the same sector? |
| ||
| Well, using this ancient method that Blitz uses, no offence to the creators but looping is an 80's way of game updating, it will have to update on every frame, idealy I need an Observer pattern, which tells objects to move only when they need too, but I dont know how to do that yet. Sector updating is essencial for a game yeah, but I dont think I'd do it, I tried flying a space ship around a cut down version to just a single solar system and it's frustrating, I couldn't even get the moon to orbit as a circle, always damn elliptoid. Plus after you sling shot a few planets your ship is practically un-controllable, no gameplay, bit like Frontier. Anyway, so no ideas lurking around? |
| ||
| I don't think there is another way around it other than multi threading, I would think, but that is just my guess. I have never done multi threading so might be talking out of my arse. back to looping. I don't know if you did it. You might want to check only plannets that have not been tested with each other. If you did, ignore me. an example:
a[100]
b[100]
for i = 0 until 99
for j = (i+1) until 100
process b[i] with b[j] both ways.
next j
next i
you might need to use link list directly to do it this way with Tlist. and you won't need to do this: If body <> Self Then should cut down processing time by about half. P.S it might be a good idea to check out Multithreading. |
| ||
| Isn' that the same problem like here? He solved it with an Event Scheduling Program (code is there). |
| ||
| I started thinking that instead of comparing each object with each other, you could (maybe?) have each object to first put their values into a "gravity field" (I'm thinking of some sort of 3 coordinate 'grid' ("cloth") that would have increases gravity values depending on suns). Then each object body would read the values from the "gravity cloth". That way each sun would not be directly affecting to each body, but each sun affect the "gravity field cloth". And then each body would not need to check each sun, but they could check the "gravity field" in their current position. This is quite high-level idea, and to be honest - I'm not sure yet how to make that work :) But the basic idea is that. Instead of: each sun -> affects each body You'd have: each sun -> affects one gravity field each body <- reads value from one gravity field Not even sure if that's possible to do in your case, but at least it would reduce the number of calculations dramatically... |
| ||
| Jesse: A friend of mine suggested that, but unfortunatly a) I rarely use arrays b) I dont know how to implement that method into my system, as in I dont understand what you mean by process bi with bj both ways, my friends system was similar and I didn't understand it. Volker: Looks interesting, I'm not entirely sure what it is, some kind of Event future creator pattern :P hehe. Game Producer: Every sun needs to effect every other sun because in real space, this is happening, for eg. the core of a galaxy has the highest concentration of suns, this combined concentration creates a massive combined gravitational pull, that is the only way to attract the outer suns and gasses, without those combined equations the galaxy won't form correctly. What you would get is localised orbits, in a way what would happen is you'd get tons of solar systems, no large bodies. |
| ||
| Exactly how many objects are we talking about? I update 3-5k objects in a few of my projects, granted the frame rate slows down to 12-15fps, but that's on an old 2.3ghz celeron and that includes rendering as well. And yes...using that old 80's method. :) |
| ||
| Between 6-10,000 but they are simple shapes, i.e. Dots :D I still use that old 80's method, I find it easier to work with. |
| ||
| Try taking out the render and just time the logic. Just for the hey of it. |
| ||
| Yeah I've tried that, the problem is the for loop in every object, checking it's own collisions, really slow. Thinking about this further, this IS a big problem, this has to be resolved in order to create any game, or simulation, image having a for loop in every bullet you fire, checking it's own collision, you can't do that! It would be slow and inefficient, this has to of been sorted out on here?! I reckon you need a completated Observer class. That has one for loop comparing all entities. |
| ||
| ... if it was a big problem in games you'd have thought somebody would have raised it before. There ARE solutions out there but, personally, I don't know what your issue is. You have a large number of objects to check collision with another large number of objects. Why can't you use a shifted grid solution? For a complex space simulation, to the degree you're doing it (and I have no idea about space simulations) then, perhaps, you need to look at using another language to do it. How about providing some runnable example code and seeing what people can make of it? |
| ||
| If your trying to build a realistic simulation of all the gravitational forces in a galaxy, then you might want to look at some faster language as tonyg suggested. BlitzMax is focused on game creation (of course its still applicable for other programming uses), so maybe you might want to create something that uses more imagination rather than precise physics to achieve a result that 'looks sort of right'. I think gameproducers suggestion is really good. |
| ||
| ... and check Influence Maps which might well help as well. |
| ||
Going back to your original post, is this something u kinda wanted (of course psudoish code):Type TBody Global AllBodiesList:TList = New TList Field WeightList:TList = New TList Function UpdateAll() Local b:TBody For b = EachIn AllBodiesList b.Update() Next End Function Method CheckGravity() Local b2:TBody For b2 = EachIn AllBodiesList If Self <> b2 Then 'retrieve the relivent info from the weight list, calculate and then store stuff as TWeights in the weightlist for each TBody object End if Next End Method End Type Type TWeights Field Body:TBody Field GravityEffect:Float End Type ' In the Loop TBody.UpdateAll() Basically the update all function goes through and runs the update method for every TBody, which cycles through each of the bodies again. each TBody then has its own list where it has a collection of TWeight type objects, which store the calculated gravity effect and the second body it relates to. |
| ||
| Also remember that your suns do not need to check against all other suns. Just the ones that haven't already checked. For example, lets say you have these 5 suns: 5 4 3 2 1 5 checks against all of them, then 4 just needs to check 3,2,1 and 3 just needs to check 2,1 and 2 just needs to check 1. 1 doesn't need to check. This will cut down the number of checks immensely. |
| ||
| TaskMaster: it is the same way I explained it above but I am guessing it doesn't really solve any problem. The Problem becomes apparent when you realize that both our example check the first sun gravity to the second but not the second to the first. Only the first gets afected by gravity from the second sun and not the second by the first. If you include both calculations in the sengle loop(which is the way it should be done in the single loop) then you are almost back to square one. That is where I also made the mistake. |
| ||
| The fundamental problem is unavoidable. If there are ten thousand suns then there are about fifty million pairs of suns. Dealing with all of them is going to be slow. I think the only hope is to, in typical game fashion, cheat your way through this. Perhaps each sun could be affected only by nearby suns. All others would be ignored. This is isn't really accurate but might be acceptable. |
| ||
| This is going to be slow no matter what the language. Some might give you an increase of speed, but 10000 * 10000 = 100000000 Thats alot of checks! Perhaps you could do something similar to a path searching. Have a list of suns that need checking. This could be done by setting a flag to unchecked or creating a checked linked list. Ontop of this list you could store a linked list for each sun that dictates which other suns are in its radius. These internal lists would be maintained on the fly. So if the moving of one sun updating has then made the sun go into the boundries of another sun, it would have to be added to that suns linked list. This would naturally cause that sun to set its flag to unchcked again. At some point with this method you are going to have to check EVERY SUN, but instead of doing expensive calculations to detect pretty much a collision; instead you could do a lesser intensive bounding box check. If it is deemed that a sun is within that bounding box, then do further calculations. You could also keep an array of "portals". Rectangular regions of space that suns can live in. To check what items are close to one sun, get the radius of the suns gravity. Find which portals that sun intersects with, then you only have to check suns that are in those portals. If you increase the physical size of the portals, you have to do more checking. If you decrease the physical size of the portals you have to do less checking! The process would continue until a count indicates that ALL suns have been checked. As with some physics and light systems, there has to be a maximum number of times a sun can check in one loop. Otherwise the process could go on for ever! With a system like this in place, it would be possible to create a neural net connecting the suns with their internal list. Sun A links to: --Sun B links to: ----Sun D links to: ------Sun F links to: --------Sun C ----Sun E --Sun C This is not a language problem, it is a coding problem. Any solution is going to move the strain away from teh CPU, but at the same time drasticaly increase the RAM usage. diagram of portals:  diagram of bounding:  With the example shown in the diagram you have instantly decreased the number of checks to less than 50% for one sun. |
| ||
| "Thinking about this further, this IS a big problem, this has to be resolved in order to create any game, or simulation, image having a for loop in every bullet you fire, checking it's own collision, you can't do that! It would be slow and inefficient, this has to of been sorted out on here?! I reckon you need a completated Observer class. That has one for loop comparing all entities." That's how I do it. Ofcourse I've only coded games with no more than a few 100 to a few 1000 objects active. Can't you just shrink the size of your universe? Let's be real here.... you're making a game. You can have your own rules, etc, etc. And is the end user experience going to be any less fun if you have fewer suns, planets, etc? And why not limit your space journey to only a few suns at a time and let the player teleport, fly, hyperspace, etc, to other quadrants when/if needed? You would have the same problem in any language. You're simply doing too much at one time. Alot of games "fake" their implied reality by cutting corners, tricks, etc. I suggest you do the same. ;) |
| ||
| MGE, hes not making a game, hes said above hes making a simulation. But yea, if he was making a gmae then as you say, use imagination rather than realism. |
| ||
| Yeah if you research this properly a simulator is not pratical for games, because like I've said before, all sun bodies effect each other, if you use Zoneing you are fudging it, which might work for a game, but ulltimatly it woud be bad for a simulation, the galaxy wouldn't form properly. Plus my new calculations (and design) have unleashed some new problems, even though i have time set to about a billion times that of actual time it would take hundreds of hours to create a nice looking galaxy :S it just stays looking like a cloud, and then it splits up and then slowly starts grouping again, then splits up! I gave up! |
| ||
| "I gave up!" Best too, people can spend their whole lives working on this kind of thing :) |
| ||
| Yeah tell me about it, my friend said how is your game coming along, I said I'm still trying to get me suns orbiting! his reply was, but that was two weeks ago! :S |
| ||
| How are you fudging it? If the sun's gravitational pull is out of reach of a particular sun, what is the point in checking it... |
| ||
| if it's a simulation... buy a faster computer :D Faster than [386SX - 4MB - Sound Blaster - Mouse] anyway... :P |
| ||
| I like game producers gravity 'cloth' it's the classic example of Einsteins view of gravity, space is a rubber sheet and the planets are steel balls that distort that sheet. Now place a large steel ball in the middle and the sheet distorts now drop in some marbles and watch them orbit the steel sun! So think of the sheet as an array of vectors, or just as a heightmap as you would use in a terrain model, now each sun would have it's own 'displacement' map or gravity field just add it to the gravity sheet and then work out which way the local downhill and move the sun's accordingly! Things to consider the resolution of the map, the maximum distance of a sun's effect, extremely large distortions or black holes! In theory you should be able to get a 'simulation' that mimics millions of suns without hitting the exponential sun to sun problem! |
   |