Archived

This topic is now archived and is closed to further replies.

Oluseyi

Physical Systems Manager?

Recommended Posts

Disclaimer: This is still an idea being thought through. Several physics problems occur within the context of a video game simulation, from simple collision detection to the resolution of complex forces. Most of us are also familiar with the "skipping" that occurs when hit-testing moving objects, arising due to the discretizing of time and animation on a per-discrete interval basis. There are also questions of magnitude - how to manage the interactions of large numbers of objects, especially when fairly realistic physics are desired in dynamic environment. I''ll introduce my concept with a fairly common example: collision detection. Ignoring for now the number of spatial dimensions, if we have n objects and iterate through each of them testing for collisions against the other n-1 objects, we come up with n(n-1) tests. Wasteful. That number can be cut roughly in half by considering that a collision between A and B is the same as a collision between B and A. Okay, but maintaining a list of which objects have been tested against which becomes a rather complicated task, especially if the number of objects is dynamic. A solution under consideration is the idea of the physical sumulation manager, a construct designed to maintain state information on the physical properties of all registered objects. Naturally, there needs to be some sort of interface for the manager to communicate with the objects - base class PyhsicalObject (I don''t employ the habit of prefixing my class names with "C"). A PhysicalObject maintains position, direction, acceleration, mass and velocity (instantaneous, derived from the acceleration) information, and a counter until the next state change. This is an important concept. If an object is in an "empty" environment and will not collide for the next x cycles, why update it until then? If, however, another object within the same locale undergoes an abrupt change (preemptive modification), then a check is made and the value of x recomputed. In high-change situations this may be counterproductive, so this functionality will be optional. Another interesting idea is the concept of locales. A locale is meant to represent a region within which objects may influence each other; a room would be a logical locale. However, locales may also be dynamic "volumes" that relocate along with objects, though this is likely to be very processor intensive. The real purpose for all this, however, is nut just to provide a coherent framework for physics simulation, but also to provide a base for "physical reasoning." My pet project at the moment is a sports simulation - basketball (to be followed by either soccer or tennis, then maybe football... you get the picture). Locales are ideal structures for trivial rejection of cases for collision detection, but would also serve on a per-player basis in sports to define the limits of a player''s "awareness." A lot of these ideas have not been entirely thought through, and I''d love to get some critiques. Timkin encouraged me to start a separate thread for this discussion; please feel free to comment and even rip the idea to shreds if necessary. Thanks. [ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ] Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
Intersting ideas.
I haven''t done anything with collision detection yet, besides an object hitting the side of the veiwable area and bouncing off, but I would still like to hear if any of these ides you proposed are successfull. I will eventually be getting to collision detection in my programs, but I''m going at a slow pace because of lack of time.

Keep up the good thoughts.



EAX

Share this post


Link to post
Share on other sites
Various solutions to this problem already exist. E.g.

sweep and prune: maintain sorted lists of the x, y and z upper and lower bounds of all objects. Objects only collide if they overlap in all three dimensions, and they only can enter this state when the upper bound of one swaps with the lower bound of another, a smple check done each time the objects are resorted. This approach works well with objects that don''t move much as the (re-)sorting is relatively quick.

uniform grid: divide thw rorld into grid squares (or cubes), place every object in one and only test objects in the same or adjacent grod squares. Works well for objects all about the same size.

hierachical hash table: like uniform grid but uses a hierachy of volumes/intervals, each half the size of the previous one. The tests for whether objects need to be tested are a bit more involved but result in pretty fast code. Deals better with objects of widely varying sizes than uniform grid.

time-step methods: work out a time line for pairs of objects to see whether they get near enough for testing over a time interval. If so note the time and do collision tests then. If not do not retest until the end of the interval. The calculations are more complex but they need to be done only infrequently instead of every frame/game loop. Deals well with objects which may be missed by other methods, such as a bullet and plate of glass. Does not cope well with objects with complex dynamics, as the prediction is then difficult. Also does not deal well with a high frequency of collisions, especially contact, as then the expensive prediciton calculations have to be done too often.

All of this is well researched and documented in published papers. The starting point I use for these is:

http://www.ams.sunysb.edu/~jklosow/quickcd/QCD_resources.html


John

Share this post


Link to post
Share on other sites
johnb, thank you for the information! I''m thinking of a hybridization of time-step methods, modifying them to cope with objects of wildy varying dynamics and properties. Turning back to my example, consider basketball: 10 players in two teams of 5 each, a rectangular court divided into nearly arbitrary sections - paint, inside/outside the arc, front/backcourt - one ball, two rims & backboards. Add in a desire to allow athletic actions like jumping out of bounds to catch a ball and throw it back in bounds and you see that while existing time-step methods are extremely useful and the basis of my analysis, they may require significant modification to suit the situation.

Thanks for the link though; I''ll be sure to check it out.

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
I suspect that the main issue with implementing the physics manager is with the method that determines when state changes are tested for, as previously mentioned.

I believe that the critical factor in chosing the method is one of object density in the environment. In areas of low density - where presumably interactions occur infrequently - predictive methods can be used to determine probable interaction times. In high density areas where interactions occur very frequently, an exhaustive search would be the worst case scenario that computationally, but guarantees the best results for ensuring physically realistic interactions between objects.

So, why not split the domain based on density. In the lowest density areas use a linear (or possibly non-linear if acceleration is non-constant) prediction of state trajectory to determine interaction times. In high density areas, do a frame by frame test for interaction using your preferred technique (exhaustive, constant grid, heirarchical mesh, etc.).

Comments? Thoughts?

Timkin

Share this post


Link to post
Share on other sites
Interesting. Seems a bit daunting though. Anyone have any experience with Havok or similar packages? It might save a good deal of blood, sweat and tears to start with an existing package. If you literally copy from it then that would be ethically and legally questionable even if it is just the data structures you are copying and not the code. It is a little differant to go through and say do I need this feature or not, do I need this information or not, is this a good way to interface to the program or not. As an example if you were going to build a car you would draw upon what you know of existing cars. When it comes to the exact engineering and design details you would hopefully do your own work, but you wouldn''t "discover" on your own that you needed a frame.

Share this post


Link to post
Share on other sites
Timkin, I think that''s an excellent suggestion, and will probably yield the best results in terms of accuracy and performance.

LilBudyWizer, in an ideal situation I would be able to play with Havok and even peruse the code, but since it''s a closed-source proprietary solution... There isn''t even a trial to play with. However, I entirely plan on taking your advice. Before writing a single line of code I''ll peruse pretty much every physics library available (full attribution, thankyouverymuch)

Anyway, I''m off to play with a few havok demos...

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
My thoughts were that there might be some commerical programmers with access to Havok here. Since the goal is not copyright infringement you really just need a high level view of how it fits into a game. One big question is what is the scope? Specifically what are the boundaries between it and other subsystems and then what are the interfaces for crossing those boundaries? It wasn''t so much a concern that you would rush off and write code. That is to me a valid way of working out a design, but only after you have the big picture in place.

So one of the first questions is who is doing scene management? Is it your graphics engine, game engine or physics engine? I view the game engine as the supervisor that coordinates all the subsystems. So that seems like where the scene management should be. Some of what you are talking about sounds more like scene management to me though. So are those parts actually in scope? Or should they be partitioned off into helper classes for use in other subsystems to ease interaction with the physics subsystem. One of the biggest problems I see is that dynamic objects is not all that you can collide with. So you are not just going to have to track all the moving objects, but everything. Once you start doing that then you start dragging in the entire game. So it seems it would be better, at least initially, to limit it to basic physics. As an example given a convex hull and a density function calculating the mass or given two objects and two points in time do they collide and if so what is the net result of the collision. It seems that would be a significant acheivement by itself. You could then grow from there based upon feedback or personal experience actually trying to use it in a game.

Share this post


Link to post
Share on other sites
Hmm, interesting questions indeed. I haven''t fully thought out the scope of this. The way I saw it was that the entire physical systems manager would be a helper entity of the game engine, via the physics engine (the physics engine being a subsystem of the game engine). The game engine would register objects with the manager, which would then be instructed which operations to perform on which objects and when (and where, as in which locales). This would allow the game to dynamically scale up or down the level of simulation in various areas of the game map.

Scene graph management will thus be done by the game/graphics engine, with specific regions modified by the manager. I will also start with management in open environments with relatively few objects (static and dynamic) and build up and out from there.

Please keep the comments, critiques and suggestions coming; this is starting to take shape.

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
As far as predicting when interactions might take place, aren''t you having to make pretty broad guesses? I mean, certainly static objects will be easy to predict, but dynamic objects will be a little more difficult -- particularly a human controled actor. Throw in a few AI controlled actors and you''ve got increasing potentials you''d need to deal with. You may be able to quickly determine the possible positions a game actor may be at a given future time, but the farther that time is in the future, the greater the area that actor may cover. Eventually these potentials will overlap. Assuming that they can affect each other, you''d need to revaluate the overlapping potentials to recast the net, so to speak, at the time frame indicated by this intersection. I would imagine defined paths (like projectiles or balls or other passive objects) would have a slightly different effect in the scheme in that their position can be precisely predicted.

I''m thinking more and more about this as I''m writing and it seems very interesting... if a new item is spawned in the simulation (a weapon is fired, for example) then you''d check if it''s inside a potential position and re-evaluate that potential if it is...

I''ve already got a collision manager in my game... I wonder how hard it would be to implement something like this...
Not that collision detection has been a speed problem -- I''ve only ever got like 5-20 objects to think about.

Share this post


Link to post
Share on other sites
Not exactly a clear thought, but a thought none the less. That thought is having pure abstract base classes where the abstract methods retrieve data. The physics engine contains all the physics "knowledge" which includes when it needs information, but not necessarily how to get that information. You might then provide helper classes that actually store the data. So perhaps the physics engine uses the bounding information as though it is a tree. You have abstract methods that are appropriate for navigating any tree, i.e. first, previous, next, last child, parent, etc. You then provide a class for actually storing the heirarchy the makes for a minimum of code when used. All the user has to do is make sure those functions return the right value. So you have a bounding sphere data type that isn''t optional because that is what the method returns. The unknown part is where the model is and how it is stored. The user has to provide the ability to actually find the model. If they use your helper class then that is about all they have to do. Otherwise they may have to translate data types and do a bunch of other things. The point being that it is simply if they want it to be, but flexible if they need it to be.

Share this post


Link to post
Share on other sites