Re: new here, my lang project...

From: H. S. Lahman (h.lahman_at_verizon.net)
Date: 01/26/05 

Date: Wed, 26 Jan 2005 04:25:20 GMT

Responding to Cr88192...

>>>well, more like legacy data and tools in some ways...
>>>I don't control and I can't change the tools, I am stuck with what they
>>>generate and understand, and doing something different would be too much
>>>work.
>>
>>What sorts of tools and what are they generating? (I had the impression
>>you were manually coding C.)
>>
>
> well, primarily modellers (milkshape, ac3d, ...) and programs like quark
> (which do mapping). these tools were generally designed for quake-style
> games (quake 1/2/3, half-life, ...).

Never heard of them. What sort of models? [I assume you aren't doing
UML models. B-)] I gather these are sort of home-grown modding tools
of some sort?

>>>nope, quake was single-threaded all the way.
>>>
>>>the main power is a big main loop, that cycles through and calls all the
>>>related subsystems to cause them to do whatever, and the loop repeats.
>>>
>>>the main power of things is keeping the loop cycling fast (>30Hz is good,
>>> >50 is better, ...). 10 or 20Hz, however, is not so good, the game lags
>>>and things start getting jittery.
>>
>>That only works for primitive graphics, a dumb AI, and an RTS format where
>>one doesn't wait for the player. <snip threading issues discussion>
>>
>
>
> well, but all this is not how the games are done.

You meant, "... how these games are done", right? I can't imagine the
newer action/shooter games being single threaded.

>>>I don't really get it, however:
>>>my inheritence model is also outside the app code.
>>>
>>>it is basically just files and directories in the resources directory
>>>which define "classes", which serve to specify the search path for
>>>resources, specify scoping for the scripts, ...
>>>
>>>all this is dynamic, eg, no compiled code involved, and even fairly minor
>>>impact on the scripting. "classes as an abstraction for data" really. the
>>>masses of game resources are becomming large and difficult to manage or
>>>navigate, possibly eventually serving as an impediment to modders or
>>>such...
>>
>>OK, then I am thoroughly confused about what you were doing. B-) I
>>thought you were updating a Quake engine that was written in C.
>>
>
>
> no, I have had experience working with the quake engine.
>
> I have just written my own engine, which has mysteriously ended up looking a
> lot like quake, but is otherwise clean source and internally works somewhat
> different in many ways...

What I am asking about is how there can be no compiled code. I thought
the engine you were working on was in C.

You will also have to put some more words around the notion of an
inheritance model outside the app code in terms of files and directories.

>><snip answers to my questions>

>>What do you mean by 'physics engine'? Can you provide a couple of
>>sentences to describe what you think the subject matter and
>>responsibilities are? (I have my own vision, but that may be the
>>communication problem here.) Some of my questions above are a tad on the
>>facetious side, but the basic push-back isn't. I don't have a good
>>picture of what /you/ think is going on here and that stands in the way of
>>speculating on how to partition things.
>>
>
> well, it is difficult to explain.
>
> consider 2 skeletal models:
> each has a number of bones and each bone has a bbox. the positions and sizes
> of these bboxes depends on the model animation, and collisions can further
> effect the subsequent state of the model (excerting force or bending the
> model, telling the script what part of the model was hit and with what,
> ...).
> now, what if these bboxes interact in different ways with different objects
> simultaniously?...

OK, that's pretty much what I would have pictured but without any
mention of animation, scripts, subsequent state. If I swing a
two-handed sword at Fred's head, is it going to get stuck in an overhead
tree limb on the way? But I wouldn't expect the Physics subsystem to
know what Fred's head, a tree limb, or a two-handed sword were. Nor
would I expect it to understand the reason a particular bbox was
scheduled to move in a particular way. IOW, Physics would just
understand the positions for bboxes and their parent skeletal models.

I also think I understand why you are having problems with interactions.
  I think that is rooted in the time slicing. If I understand this
properly, Physics is handling an entire action, like swinging a
two-handed sword at Fred's head, until it is completed one way or
another (e.g., Fred's head is split or the sword gets stuck in a tree
limb, or Fred gets his shield up to block the move). If that is the
case, then Physics has too much to think about at once because too much
is happening in a full move like a sword swing when other objects are
moving as well. It is also making decisions about what to do after
there is a collision.

Now suppose you subdivide simulation time into time slices that are
roughly the graphics refresh period and let Physics only worry about one
such slice at a time. So a move like swinging a sword is broken up into
increments based on time slices. In that case a move increment /always/
goes to full completion but that increment is only the frame-to-frame
distance that would appear smooth in the display.

In that case there are only two possibilities for any given bbox
incremental move: there is nothing in the way (i.e., no other bbox
occupies the same end space) or there is something in the way (i.e.,
another bbox occupies some part of its space). All the Physics
subsystem needs to do is report when the bboxes collide to whoever is
managing their skeletal models. IOW, Physics basically does nothing
except check for collisions at the end of an incremental move.

That means that someone else has to manage movement at the level of full
sword swings. That someone -- let's call it the Move Manager subsystem
-- understands what bboxes are involved in a sword swing. Using that
knowledge they are responsible for the prediction portion above where
they define the set of incremental moves for each relevant bbox to get
the sword from its present position to the desired position after the
full swing. Then for each time slice they are triggered to send the
next set of incremental bbox moves to the Physics subsystem.

Once Move Manager has figured out the sword trajectory, it has nothing
else to do except pump out incremental moves to Physics. If there is
nothing in the way, the whole move will complete with the sword in
Fred's skull. When that happens Physics will report the collision. If
something like the tree limb or shield gets in the way prematurely, the
overall move is simply halted. Move Manager reports back to whoever is
managing the sword swinging entity that the blow was delivered or halted
by a collision. Physics will also report to whoever is managing the
Fred entity that there is now a sword buried in his head so that hit
points, etc. can be adjusted.

Note that things like bouncing the sword off a shield or separating
Fred's head from his body are not relevant to the actions so far. Those
will trigger the appropriate /next/ full move by Move Manager when it is
notified of the collision. That is, the bounce or whatever is a move in
itself triggered by the <premature> completion of the previous move.
Since the time slice is at the scale of the refresh rate, having both
bboxes occupying the same display space is not going to be noticed.

[You will also note that Move Manager as described here does things
(i.e., compute 3D trajectories) that are very close to the sort of stuff
Rendering may do. But that is not quite so. Move Manager is an excise
in analytic geometry for individual movements without regard to context.
  (The context is handled by Physics via detecting collisions.) Move
Manager also provides a translation from the game mechanics view of
"swing sword at head" into bbox movements in 3D space.]

What about the skeletal model and bboxes? Both Move Manager and Physics
(and Rendering) deal explicitly with these. So doesn't that seem to
contradict my advice about tailoring each subsystem to its subject
matter with its own views? Data like size and position will be shared
by each view, right? Data may be shared, but the view will not. The
invariant is that each subsystem has a notion of skeletal model composed
of a set of bboxes. But the specific behaviors they have and the
operations on them are quite different in each context.

> now, for a skeletal model, one needs:
> code to check between 2 skeletal models;
> code to check between a skeletal model and the map (eg: a bsp tree);
> code to check between a skeletal model and a bbox;
> code for a skeletal model and a trigger;
> ...
>
> and also has to deal with the case of multiple simultanious collisions.
>
> now, one can state that if I have a check for A->B, I also have one for
> B->A, but this just serves to halve the number of checks.

In theory one might have an N*(N-1) number of checks on bboxes. But one
only needs to check the M (M < N) that moved for collisions. One can
also get clever by assuming simplistic envelopes for the overall
skeletal models (e.g., cubes or spheres). If no point of the envelope
overlaps any point of any other envelope, you don't need to check the
individual bboxes. One can also use that to limit the bbox checks to
only those for the skeletal models whose simple envelopes overlap.

One of the nice things about isolating this particular flavor of Physics
to worry only about end position collisions is that one can focus on
this sort of local algorithmic optimization.

> now it is a hassle because one can't check for one without knowing the
> details of the other, eg:
>
> map and bones, both the map and skeletal code are involved, each bone is
> checked against the map, or vice versa.
> one could, say, split it up into a mass of bbox checks, or choose a more
> abstract structure (say, an obb-tree), but these are likely to hurt
> performance, and still the need for them itself hurts abstraction.

I am not sure what you mean by 'map' here, but I'll assume you mean
something like terrain obstacles (trees, walls, etc.).

The answer here is to provide the map entities as exactly the same sort
of skeletal models with bboxes as the non-map entities within the
Physics subsystem. They just don't move a lot.

>>As an example of where my preconceptions may be getting in the way, in
>>this of list of process steps the only one that I might regard as physics
>>is the detection of obstacles. Even that I would expect to be owned by a
>>Map or Terrain subsystem rather than by Physics.
>>
>
> well, collision detection is a major one, but increasingly compensation is
> also important.

Note that in the proposal above, compensation is handled outside
Physics. That's because the nature of the compensation (bouncing off a
shield vs. splitting a skull) depend upon the semantics of the colliding
bboxes in the game logic sense. That is, to decide the appropriate
response to a collision you have to know what sort of things collided.

And by keeping the increments that the Physics deals with limited to a
single time slice, it is possible to provide that separation. That's
because the compensation is essentially a new full move that will be fed
to Physics. Deciding what that move should be is done in the same
manner as deciding what the original move was.

>>>now, if one looks at it enough, it might also become apparent why things
>>>like ik/"ragdoll" are scary-looking. they have both combinatorial and
>>>integration related problems. not only that, but the renderer gets
>>>involved, the current state of a model/entity (positions, bounds, ...)
>>>are needed both by physics and rendering, and don't go well with the
>>>typical abstractions (eg: frames, state variables, ...). actually, it
>>>could probably be said physics is doing the heavy lifting and rendering
>>>is just along for the ride.
>>
>>Let the renderer have its own view of the entity. Some aspects of that
>>view, like position, will change as a result of game logic changes while
>>others, like bounds, are likely to be quite stable. Use messages to
>>synchronize things like position data with activities elsewhere.
>>
>
> maybe.
>
> position is at least easy, "state" would require a bit more (eg: the current
> positions and forces on the various bones for each model).

In the suggestions above one idea was that Physics was limited to /only/
thinking about position. The state was handled elsewhere. So one
didn't need to think about forces because of the time slice granularity.
  (One probably would have to think about forces in determining the
trajectory of the new move, but that would be Move Manager's union.)

[In reality, I think my solution is an oversimplification. I would be
inclined to separate out things like impact analysis into a different
flavor of Physics as a subsystem. It would be limited to dealing with
the "new moves" resulting from collisions. It would understand
rebounds, slicing, etc. to create the resulting trajectories for all the
bboxes involved in the collision based upon their properties and would
ripple outwards through the connected bboxes. In effect it would
replace Move Manager in the special situation of collisions for all the
involved entities.]

>>Let's say the Physics subsystem does detect obstacles to movement. The
>>presence of an obstacle in the path would be important to whoever is
>>managing the entity's movement, but I don't see why Rendering would care.
>>Rendering displays the obstacle but it isn't involved in movement. It
>>just renders the result of moving the entity to a new <probably
>>incremental on a path> position /after/ the path is adjusted around the
>>obstacle.
>>
>
> well, the rendering gets involved as often there is overlap in the
> representation of the model. the physics needs to look at the model in
> various details, and so does the rendering.

But to do that all Rendering needs to know is the new position of all
the bboxes and how they are displayed. It understands the display
viewpoint and deals with what's hidden and what's not, not Physics. The
algorithmic content may be physics of a sort, but it is quite different
than the physics that determines when moving entities collide.

> there is probably at least some reason why a lot of recent game developers
> are outsourcing the game physics to other companies...

The algorithms for determining something like how a shadow should look
from and arbitrary light source are nontrivial. So are algorithms for
determining what's hidden from view, trajectories for multiple bboxes
when swinging a sword, and a bunch of other stuff. Perhaps more
important is that the algorithms are computation intensive and they all
need the same CPU, so optimization is very important. IOW, that
requires a special skill set so it pays to specialize.

I will argue that the success of such outsourcing will be directly
proportional to the ability to isolate unique applications of physics in
the game context and properly encapsulate it. I would further argue
that that such algorithms should be highly reusable once they are
encapsulated. For example, once one agrees on the general invariant of a
skeletal model composed of bboxes and incremental movement at the
graphic refresh scale, then the logic for identifying collisions should
look exactly the same for any game. Similarly, the logic for computing
rebounds, slice depth, etc. around collisions should look exactly the
same (assuming a reasonable set of parameter values for strength,
rigidity, etc.).

*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions -- Put MDA to Work
http://www.pathfindermda.com
blog (under constr): http://pathfinderpeople.blogs.com/hslahman
(888)-OOA-PATH

Relevant Pages

  • Re: new here, my lang project...
    ... >> sizes of these bboxes depends on the model animation, ... or a two-handed sword were. ... Physics would just understand the positions for ... > collisions at the end of an incremental move. ...
    (comp.object)
  • Need help simulating collisions between rigid bodies.
    ... I'm working on the physics engine for a game that requires ... determine the results of collisions are quite beyond my knowledge. ... Given two rigid objects with arbitrary shapes, their linear and ... angular velocities, their masses, centers of mass, moment of inertia, ...
    (sci.physics)
  • Need help simulating collisions between rigid bodies.
    ... I'm working on the physics engine for a game that requires ... determine the results of collisions are quite beyond my knowledge. ... Given two rigid objects with arbitrary shapes, their linear and ... angular velocities, their masses, centers of mass, moment of inertia, ...
    (sci.physics)