Point Queries


Let's break it down mathematically for just a second here, ok?

For our purposes, a Discrete Point Set is a collection of objects which can be differentiated from each other somehow. We call each element in the set a Point.

Points themselves are unordered; the set may be infinite or it may be finite. An infinite DPS would be for instance the set of all 2-dimensional (x, y) coordinates within the unit circle on the real plane. A finite DPS could be the list of letters { A, B, C, D, E, F }.

DPS's in Your Game World

Often in the course of developing a game, you need to perform an action on or find something relating to an object or a group of objects. An explosion needs to know all the enemies in it's area-of-effect, or the player object needs to know if it's next to a treasure chest.

Because game objects are always discrete (i.e., they are a separatable thing) the game world can be thought of as a DPS. Note that this does not mean it only contains what you think of as your game objects; think for a second and you will realize there are lots of "non-object" things in your game world, too. If it's a 3D game, it contains for instance all faces on all 3D models, all velocity trajectories of all particles, and so forth.

Note also that when we say "Point" we don't mean just an N-dimensional point such as you may be used to thinking of; in fact we could even mean something that doesn't exist spatially at all, such as an AI routine or a store item price.

DPS Query

Let's grant that your game world is always an infinite DPS (we can argue this in the comments, if you like.) We will define a DPS Query as a function Q:

Q(x0, x1, x2...) : W -> R where R in FDPS, R = { P | P in W }

Where W is your game world (an infinite DPS), R is the result set, and FDPS is the set of all finite DPS's. So, a DPS Query takes as input some number of arguments and returns a finite set of things. The arguments could be a 3-dimensional point (X, Y, Z), along with a radius R, and the finite set of things could be all objects that are near enough to (X, Y, Z). You could name your query function something like:

set< object* > find_all_objects_near_to_point (double X, double Y, double Z, double R);

Now let's get rigorous: why W for the domain? Suppose some parameter xn being passed to Q were not part of your game world DPS. In this case, it's hard to imagine how this parameter would relate to anything in that same domain at all. To wit, if the point (X, Y, Z) does not exist in your game world, how are you finding things that are close to it? This is an interesting detail to ponder.

This is useful HOW?

Very likely, you already have a world class or module or something to that effect. I'm just encouraging you to think a bit mathematically when it comes to what kinds of functions you might put on it. In short, it gives you this rule:

Any public function of the World class that is a DPS Query is A-OK

For instance, you might well want a function like:

vector< object* > get_all_enemy_objects ();

In fact, this is a DPS Query. Once you see that fact, you realize that other query functions might be useful, such as:

vector< object* > get_all_enemy_objects_with_hp_less_than (double Value);

or:

vector< object* > get_all_enemy_objects_in_state (string State);

Now you know: these are all perfectly valid functions to have on your World class, because they are all DPS Queries.

Takin' it TOO FAR

You can extend the rule:

Functions on the World class that are NOT DPS's MIGHT BE BAD NEWS

Let's say you've got a function like:

void damage_all_enemies_in_radius (double X, double Y, double Z, double R, double DamageAmount, string DamageType);

That seems well and good. A Fireball spell might call it with damage type "fire" when it explodes. But by the above rule, we should perhaps rethink whether this belongs as a member function on World. True, it's handy. Also true: it's pretty specific!

In fact, we might give our head a check and think about whether it's really the World's business to hurt things in itself, or whether that action is better thought of as being done by the spell entity. Isn't the interaction between (burning hot plasmic air) and (orc flesh) better thought of as being direct, rather than being intermediated by the World class?

Advanced DPS Queries

We shouldn't stop with game objects. For instance, suppose that you've got an arrow that needs to fly through the air, and stick into the first wall it finds. If you've coded 3D before, you know that at some point you will probably be doing ray-triangle intersection.

We can imagine a DPS Query that does this, like:

vector< world_face* > get_ray_collision_faces (double X, double Y, double Z, double DX, double DY, double DZ);

The necessary intelligence to perform these collisions will live inside our World class. This is probably a good thing, and here's why:

We might find a world_face on terrain, buildings, or an object. World is going to be a collection of these things, understanding how they are laid out and interacting. The arrow we shoot need not be concerned that lava has now also been implemented, at least not directly. So the entity that needs to "know" about such things in terms of detecting arrow-collisions is also the entity that is responsible for managing these things in the first place, which is good design.

Final Notes: Finiteness, Ordering

A couple of things: remember that we are always returning a finite set of things, even though the game world is (uncountably) infinite. This limitation means we are going to package our query results into a vector<> or set<>, or we could create something special for iterating through as with a database engine. Not all DPS Queries would need to return their results packaged the same way, of course.

Now a note on ordering. We can of course order our results in any way we want, but sometimes we won't be able to, so it's important not to be part of the definition of DPS. An ordering is a linearizing operation, i.e., it takes things and puts them on a one dimensional line. Games are usually spatial and so many times, ordering does not really make sense. So some queries are going to have a natural ordering to their results, and some will not.

2011-01-25


◀ Back