Missiles

[Learner]

My special effect system that I'm working on (see a few threads down) handles projectiles and obstacles.

Projectile collision etc needs to be serverside before it is even sent to the client.

[KarenRei]

You're talking about missiles that *actually* get deflected? Sorry; I should have read better. My system deals only with cosmetics. For example, if you "heal summoned", the particles that fly off your hands won't sail right through a tree or another player on their way to a summoned critter. They'll go around (within reason). You can define an obstruction list for particles to bypass.

 

Anything that allows for deflection that actually prevents particles from reaching their target would indeed need to be serverside.

 

Schmurk:

 

Bresenham's algorithm with Wu antialiasing doesn't face the "skipping" problem. Is this what you were referring to? It indeed is a nifty algorithm that can be optimized to heck and back. Michael Abrash's version goes so far as to not use a conditional statement to determine when to shift by a pixel. In the case of a mostly horizontal line, ascending, every cycle he adds to the y value the overflow flag that you get from the remainder after you add your fixed-point fraction. The remainder automatically loops around, and overflow gets set by the CPU every time it happens. No branching, except for in the loop itself.

 

For the "cosmetic" collision avoidance, I use bounding cylinders. They're faster than bounding boxes so long as you compare the radius squared with the distance squared (less branching), and fit better to most shapes. As for complex shapes like trees, well, in general all you care about is the trunk. I have two types: fast ones (infinite height, always vertically aligned) and slower ones (truncated, arbitrary angles).

Edited January 5, 2007 by KarenRei

[Learner]

You're talking about missiles that *actually* get deflected? My system deals only with cosmetics. For example, if you "heal summoned", the particles that fly off your hands won't sail right through a tree or another player on their way to a summoned critter. They'll go around (within reason). You can define an obstruction list for particles to bypass.

 

Anything that allows for deflection that actually prevents particles from reaching their target would indeed need to be serverside.

 

Schmurk:

 

Bresenham's algorithm with Wu antialiasing doesn't face the "skipping" problem. Is this what you were referring to?

 

For the "cosmetic" collision avoidance, I use bounding cylinders. They're faster than bounding boxes so long as you compare the radius squared with the distance squared (less branching), and fit better to most shapes. As for complex shapes like trees, well, in general all you care about is the trunk. I have two types: fast ones (infinite height, always vertically aligned) and slower ones (truncated, arbitrary angles).

Exactly, without server side collisision processing etc, there will be no solid missles of any sorts. A spell effect can be allowed without the same limitations since it is magic. Since this thread is about missles like arrows, nothing can happen until something is available in the server that is fast an simple enought for the server to do a LOT since any delays affects everyone. So, what your doing for partical effects isn't critical for missles, but good to have client side.

[KarenRei]

My bad I only read the first few posts in the thread, then the last one to see why the old thread came back up. The first few talked more about fireballs and the like than arrows.

[Schmurk]

Bresenham's algorithm with Wu antialiasing doesn't face the "skipping" problem. Is this what you were referring to? It indeed is a nifty algorithm that can be optimized to heck and back. Michael Abrash's version goes so far as to not use a conditional statement to determine when to shift by a pixel. In the case of a mostly horizontal line, ascending, every cycle he adds to the y value the overflow flag that you get from the remainder after you add your fixed-point fraction. The remainder automatically loops around, and overflow gets set by the CPU every time it happens. No branching, except for in the loop itself.

I was just referring to the basic Bresenham algorithm with no aliasing. I don't know the Abrash's version but it should be (according to what you're saying) quite similar that I was talking about.

 

Anyway, I searched into some of my programs and I found an integer based algorithm that deal with any octant of the 2D space and that also correct the skipping problem. So if you're interested, just ask me.

BTW I don't think that the critical point here is drawing a 2D line because the complexity of such an algorithm is quite simple compared to the algorithm you'll need to detect collisions between the missiles and the objects. I'm not a specialist in collision detection but if Karen already done such things, you can reuse it easily I think

Well, in any case, my job atm in writing fast intersection algorithms for complex objects so it's quite close to the subject. So if you need any help on that, I can maybe help...

[KarenRei]

The basic Bresenham's algorithm is subject to skipping. You need a form of antialiasing to prevent it. Take a look at this Bresenham line:

 

http://graphics.idav.ucdavis.edu/education...rithm/img11.gif

 

Note the large area that it passes through near the end that doesn't get checked. You need antialiasing so that you check the pixels that would otherwise be skipped as well:

 

http://www.javaopen.org/j3dbook/text/images/Antialiasing.gif

 

Wu antialiasing is basically your typical Bresenham's algorithm, except you trace two pixels wide at a time. The pixel intensity (when actually drawing lines) is determined by the same remainder that tells the Bresenham's algorithm when to move up/down/side to side by one pixel.

 

Now, when I mention antialiasing, obviously we don't care about pixel intensity like we would if we were actually drawing a line. If the remainder is simply nonzero, we want to check it. But we need to check both the basic points gotten from Bresenham's algorithm, and the "nearby" pixel of relevance. So, what we need is something in between a standard Bresenham's algorithm and a Wu algorithm: you deal with two "pixels", but you treat them in the same manner. I suppose that another way to think of it would be as a Bresenham line with a thickness of two, starting with remainder 0 instead of 0.5.

 

The key to the Abrash algorithms' performance is branch reduction. In most implementations of Bresenham/Wu, you use if statements to check to see if the fixed point remainder has overflowed, and you typically have to use a temporary variable to hold the previous remainder's value to see if it's greater than the new one. Abrash's trick is given in that when a variable overflows, the CPU flags the overflow, and you can access the flag. Then you just need to add/subtract that flag to your pixel coordinates, making the only branch necessary be in the loop itself. Branches are significant performance hits for most modern CPUs. Actually, Abrash went even beyond this in one version of his algorithm. Instead of just using octants, he had special cases for lines that are very horizontal/vertical to allow for loop unrolling, and also special cases for very horizontal lines which used 16 or 32 bit writes to draw them -- but that latter case probably wouldn't be applicable to our situation.

 

To sum up: It all depends on how much performance you care about, but there's an awful lot you can do to optimize the algorithm beyond just a fixed-point implementation. As for collision detection in general: Fast bounding box/cylinder/sphere collision detection is trivial. Getting good performance out of true collision detection (say, between polys) is the real challenge. If you don't care to do that, then collision detection is a really simple task.

 

By the way, if you can't tell, I'm a big Abrash fan. I have been ever since I read his "Zen of Graphics Programming" back in high school. A lot of info in there is long dated by now (for example, how to tweak video cards to get the most Mode X performance), but the algorithms, and how he teaches one to derive good algorithms, are great.

Edited January 8, 2007 by KarenRei

[Entropy]

Your collision detection for the client side particles COULD possibly be used on the server as well (with some modifications).

Basically, we need a line between two tiles, which should check if it colides with anything solid. By solid I mean anything without transparency (a tree or bush would be ahndled as a solid object, can't shoot through the leaves).

 

How fast is your algorithm?

[Schmurk]

The basic Bresenham's algorithm is subject to skipping. You need a form of antialiasing to prevent it. Take a look at this Bresenham line:

 

http://graphics.idav.ucdavis.edu/education...rithm/img11.gif

 

Note the large area that it passes through near the end that doesn't get checked. You need antialiasing so that you check the pixels that would otherwise be skipped as well:

 

http://www.javaopen.org/j3dbook/text/images/Antialiasing.gif

I think there were a misunderstood between our posts, I know what is the Bresenham algorithm and what is aliasing and for the skipping problem, I was referring to the original Bresenham algorithm

And the Wu algorithm is not a solution for the skipping because it is not doing it very well. My idea in fact was more theoretical than practical because I was referring to discrete geometry. The lines drawn by the Bresenham algorithm correspond to lines in the naive discrete model which correspond to lines with a width of 1/2 iirc.

So to resolve the problem, I was thinking of lines in the Standard discrete model which correspond to lines with a width of 1. And that corresponds to add the pixels skipped in the naive model.

 

Wu antialiasing is basically your typical Bresenham's algorithm, except you trace two pixels wide at a time. The pixel intensity (when actually drawing lines) is determined by the same remainder that tells the Bresenham's algorithm when to move up/down/side to side by one pixel.

 

Now, when I mention antialiasing, obviously we don't care about pixel intensity like we would if we were actually drawing a line. If the remainder is simply nonzero, we want to check it. But we need to check both the basic points gotten from Bresenham's algorithm, and the "nearby" pixel of relevance. So, what we need is something in between a standard Bresenham's algorithm and a Wu algorithm: you deal with two "pixels", but you treat them in the same manner. I suppose that another way to think of it would be as a Bresenham line with a thickness of two, starting with remainder 0 instead of 0.5.

Yes sort of but nothing to do with Wu algorithm, it was just my own version

Anyway, I'll take a look at Abrash's algorithm because it seems really nice

 

To sum up: It all depends on how much performance you care about, but there's an awful lot you can do to optimize the algorithm beyond just a fixed-point implementation. As for collision detection in general: Fast bounding box/cylinder/sphere collision detection is trivial. Getting good performance out of true collision detection (say, between polys) is the real challenge. If you don't care to do that, then collision detection is a really simple task.

Basically, we need a line between two tiles, which should check if it colides with anything solid. By solid I mean anything without transparency (a tree or bush would be ahndled as a solid object, can't shoot through the leaves).

If you allow me to answer and according to what Karen said and also what I said earlier, it mostly depends on the objects you want to check collision with. If you want to have a precise collision detection with the objects' mesh, it can be done quite fast if you have the proper acceleration structures (BSP trees, regular grids...) but it will also requires a lot of preprocessing and it will be much more expansive than checking intersections with geometrical primitives likes boxes, spheres and cylinders.

Now, if you just want to have an approximation of the collision, the best way is covering your objects with boxes or spheres or cylinders. You also have to know that checking collision with spheres will be the fastest (distance between a line and a point), then it will be the cylinders (distance between two lines) then the boxes which involve much more tests. So I think the best way is having all kind of primitives in order to fit the objects' shape better (for example: a sphere and a cylinder for a tree, a box for a table...).

Then, since the line drawing algorithms we were talking about are incremental, you just have to check the collisions step by step with the objects inside the crossed tiles. You should also have to affect an ID for each line and store this ID into the tested objects in order to avoid testing several times the same objects if they are on many tiles.

IMO such an algorithm should be really fast but it has to be tested in real conditions because it depends a lot on your data structures. BTW, even if you have a lot of objects in your map, it will be really fast. The more you'll have objects and higher the chance will be to intersect an object and to stop the algorithm before reaching the destination. But you'll also have to avoid checking all the small objects inside the tiles (like flowers and such things) to speed up the process...

 

Anyway, maybe Karen can give you some benchmarks on collision detection between a line and boxes/spheres/cylinders if she already have implemented it in her particle engine. I'll also try to write some code on that to give you computation times...

[Schmurk]

Sorry to double post but finally I took some time this morning to wrote a little test program and here's what I obtained for boxes and spheres:

 

Searching collisions between 100000 lines and a box
68988 collisions detected in 0.009664 seconds
Searching collisions between 100000 lines and a sphere
69633 collisions detected in 0.003778 seconds

 

I didn't do it for cylinders because I was not really sure of my formula so if Karen has already did it, it should be better to use her code.

My laptop is quite slow (Celeron 2.6Ghz with a CPU cache of 128Ko and ~450Mo of RAM) and I had a lot of background applications so I think it should be faster on the server.

 

If you want to test it at home, here are the corresponding data structures and functions I used (I can also send you the whole file by mail if you want):

typedef struct {
 float x, y, z;
} t_vector;

typedef struct {
 float min_x, min_y, min_z, max_x, max_y, max_z;
} t_box;

typedef struct {
 float x, y, z, r;
} t_sphere;

int detect_box_collision(t_vector *origin, t_vector *direction, t_box *box)
{
 float t, x, y, z;
 if (origin->x <= box->min_x && direction->x > 0) {
t = (box->min_x - origin->x) / direction->x;
y = origin->y + t * direction->y;
z = origin->z + t * direction->z;
if (y >= box->min_y && y <= box->max_y &&
z >= box->min_z && z <= box->max_z) return 1;
 }
 else if (origin->x >= box->max_x && direction->x < 0) {
t = (box->max_x - origin->x) / direction->x;
y = origin->y + t * direction->y;
z = origin->z + t * direction->z;
if (y >= box->min_y && y <= box->max_y &&
z >= box->min_z && z <= box->max_z) return 1;
 }
 if (origin->y <= box->min_y && direction->y > 0) {
t = (box->min_y - origin->y) / direction->y;
x = origin->x + t * direction->x;
z = origin->z + t * direction->z;
if (x >= box->min_x && x <= box->max_x &&
z >= box->min_z && z <= box->max_z) return 1;
 }
 else if (origin->y >= box->max_y && direction->y < 0) {
t = (box->max_y - origin->y) / direction->y;
x = origin->x + t * direction->x;
z = origin->z + t * direction->z;
if (x >= box->min_x && x <= box->max_x &&
z >= box->min_z && z <= box->max_z) return 1;
 }
 if (origin->z <= box->min_z && direction->z > 0) {
t = (box->min_z - origin->z) / direction->z;
x = origin->x + t * direction->x;
y = origin->y + t * direction->y;
if (x >= box->min_x && x <= box->max_x &&
y >= box->min_y && y <= box->max_y) return 1;
 }
 else if (origin->x >= box->max_x && direction->x < 0) {
t = (box->max_z - origin->z) / direction->z;
x = origin->x + t * direction->x;
y = origin->y + t * direction->y;
if (x >= box->min_x && x <= box->max_x &&
y >= box->min_y && y <= box->max_y) return 1;
 }
 return 0;
}

int detect_sphere_collision(t_vector *origin, t_vector *direction, t_sphere *sphere)
{
 t_vector tmp = {sphere->x - origin->x, sphere->y - origin->y, sphere->z - origin->z};
 float x = direction->y * tmp.z - direction->z * tmp.y;
 float y = direction->z * tmp.x - direction->x * tmp.z;
 float z = direction->x * tmp.y - direction->y * tmp.x;
 if ((x*x + y*y + z*z) / (direction->x*direction->x +
					   direction->y*direction->y +
					   direction->z*direction->z) < sphere->r*sphere->r)
return 1;
 return 0;
}

 

BTW, I'm not a mathematician so there are maybe more simple formulas for the sphere collision detection but it's the only one I know.

[Learner]

What is needed for the server is 3D collision detect as a line and/or arc vs. lots of items (and not just bounding boxes) so you can shoot over a fence or under a tree without hitting the trunk.

 

So a basic 2D test of a line to lots of boxes would be the first step. Then if there is a possible collision, the 3D check needs to be done.

[Schmurk]

What is needed for the server is 3D collision detect as a line and/or arc vs. lots of items (and not just bounding boxes) so you can shoot over a fence or under a tree without hitting the trunk.

Yes of course, this is what we were speaking about. We were just saying that computing intersections between a line and a poly mesh is not recommended at all because it's too expansive. If you want to do something really fast, the better way is to use only boxes/spheres/cylinders but you'll have to store more than one box/sphere/cylinder per item in order to fit well the objects.

Unless you're willing to let the arrows really hit the objects and then stay on them?

In this case, I agree that you need a really precise collision detection

So it could be nice to also have a very simplified version of your objects in order to limit the intersections between the lines and the triangles. If you have a low number of triangles, then you will not need any acceleration structures and the resulting algorithm is quite simple.

I'll try this week to look at the objects' data structures in the client's code then I'll write you a simple algorithm to do that...

[trollson]

This is not a flight simulator; the information on the trajectory (or rather set of potential trajectories) are necessarily vague given the nature of the game. This makes any attempt to use detailed path analysis, 3D object collision, pointless.

 

You don't know exactly where the archer is, only that they are in a 0.5m square, or their stance when they fire the missile (crouched, leaning, half-steps etc). This could easily be an uncertainty of ±1 metre around the game-position.

 

The same uncertainly applys to the target point, which can be anywhere on the target's body, which may be anywhere within the game tile. Another ±1 m uncertainty.

 

The target and possibly shooter may be moving. The shot will occur at sometime during an interval due to the game resolution, as best chosen by the character (not the player); again, this adds to the uncertainly of the start/end positions.

 

The 3D models are only representative, and should not be treated as absolute shapes to the finest detail.

 

Other affects such as wind would be affecting both the exact positions of some obsticles, and the flight path of the projectile.

 

The skill of the shooter has to play a significant role in determining a hit, in overcoming obsticles; in a fantasy game this can result in achieving the apparent impossible: That tree or wall has a hole in it, which the master archer managed to use (again, 3D models are not absolute representations).

 

So, you are trying to determine what set of arcs exist between a pair of fuzzy blobs. This is not a point-to-point exercise, but is better handled by statistical models which are far cheaper computations, as I outlined above.

 

Where is the improvement in player experience from attempting a detailed and expensive collision model? They simply click on a target and see a missile fly from their avatar to either hit or miss. Their viewpoint is unlikely to appreciate that even a line-of-sight has been achieved, and due to time lags the path illustrated by the client (avatar to avatar) is unlikely to be the same as used on the server.

[KarenRei]

Schmurk:

 

Actually, I think we're thinking of the same thing, and just misinterpreting each other.

 

Entropy:

 

I wouldn't recommend using my client-side version for the server side for this task; it's not really what you're looking for. It's for cosmetic collision detection and object aversion. It does some things above and beyond what you need -- for example, particles find their way around objects, and end up on a new trajectory (which then generally is brought back inline with the desired trajectory). On the other hand, it exploits weaknesses in the human eye when dealing with many moving objects, as well as the speed in which the particles move compared to how frequently there are bounding boxes (it's not like a particle moves past five trees per frame) to avoid having to check for a collision *between* frames. Rather, my system uses quick bounding cylinder checks based on current location only (although it is easily extended to other shapes through inheritance) to see if it is in an area under the influence of something that it could collide with, and if it is, its velocity is shifted by a force gradient relative to its position.

 

While the bounding cylinder check is applicable for you, that's a trivial task to implement. To check for a collision between a point particle p with coordinates p.coords and a cylinder c with coordinates c.coords, radius c.radius, and predefined radius squared c.radius_squared, it's simply:

 

diff_x = p.coords.x - c.coords.x;

diff_z = p.coords.z - c.coords.z;

mag_squared = diff_x * diff_x + diff_z * diff_z;

if ( mag_squared < c.radius_squared )

handle_collision(p, c);

 

I agree with Schmurk: what we really need for this application is Bresenham's algorithm with extra width (depending on how you view it, 1 wide instead of 1/2 wide, or 2 wide instead of 1 wide). I'd recommend starting simple: just break the line up into octants. 0-45 degrees means go up once every cycle, and shift right whenever your remainder overflows. 45-90 degrees means go right once every cycle, and shift up whenever your remainder overflows. And so on. Start with remainder 0 in every situation, and check for collision both in your current location and the location next to you (in the first octant, that means one square right. In the second, one square up. And so forth).

 

To check for collisions in each "square", iterate through the objects in that square. All objects should have a bounding object (since this is C, a struct). You can standardize on one type of bounding object (say, cylinders) to reduce a branch, or you can have an entry in the struct to indicate what kind of bounding object it is, and then do custom checks. Another option would be to flag insignificant objects (say, flowers) as "no check". If the entry is not flagged as "no check", you've wasted a branch. If it is flagged, you save the time of two subtracts, one add, two multiplications, and break even on branches.

 

That's your basic algorithm. If it's not fast enough to meet your needs, you can easily improve the Bresenham's part. Two optimizations are: 1) Use assembly to get the CPU overflow flag, and use that instead of a storing temporary variable and a branch to see when you need to shift. 2) Add in more special cases instead of just octants so that you can do loop unrolling, cutting out unneeded branch statements.

[kibora]

Hmmm do we really need a complicated collision algorithm. Everything in EL is based on chances. Weapons have a fixed chance to break, there’s some chance you’ll create/fail an essence etc. It could be the same with obstacles. Here is the algorithm I am proposing.

 

In this algorithm I accept that we can find fairly easy all the objects that stay between the Shooter and the Target (I do not say it’s easy ). Its main advantage is that the server makes all the calculations in 2d space and all the 3d calculations are left for the client(s).

 

Things that need to be done on the server side:

1. Add a new property for every object (or perhaps type of object), which is the chance for an arrow to go “through” that object. Through doesn’t necessarily mean through it but it could also mean above, bellow or anything else you can think of.

2. Collision detection algorithm which does something like this:

 

struct 2dPoint

{

int x;

int y;

};

 

Object * CollisionDetection(2dPoint Shooter, 2dPoint Target)

{

Object * Obstacles[10];

int NumberOfObstacles = GetAllObjectsBetweenShooterAndTarget(Shooter,Target,Obstacles);

for(int i = 0; i< NumberOfObstacles; i++)

{

int Chance = GetObjectChance(Obstacles);

if(!Chance)

return Obstacles;

if(rand()%100 >= Chance)

return Obstacles;

}

return 0;

}

 

Things that need to be done on the client side:

The client will make all the not so important calculations:

1. The trajectory of the arrow in 3d space (this will be calculated by every client that is in range).

2. If the server decides that the arrow has hit an obstacle, all the clients in range will calculate for themselves the location in 3d space of the arrow (where it’s stuck). Still only the Shooter will send the calculated info to the server, so it gives it to other clients that get in range later.

 

Example 1:

 

 

There is a Tree and a Rock between the shooter and the target. There is a 70% chance that the arrow would go through the tree and a 30% chance that it would go through the rock.

There is a decent chance that the arrow would get to the target.

 

Example 2:

 

 

There is a House and a Wall between the shooter and the target. The chance that the arrow would go through the wall is 1% and there is no chance for it to go through the house. So CollisionDetection will return the object House.

[Entropy]

@trollson

 

 

I think you don't understand the idea of why I want detailed collision detection, rather than cylinders.

If you have a cylinder, and two players are sitting under a tree, and one fires at another, a cylinder would return a true collision.

A cylinder would also be diasterous for a fence or other long objects.

The collision is for the PATH, and is calculated instantly. Speed is not taken into account.

If the server says it is OK for player A to shoot at player B, then the arrow flies, and might go through some stuff on the client (if the target is moving). But what I care about is for players to be able to fire through some fences, under trees, from a ship to the ground and so on. That's why a vertex by vertex collision detection is needed (although the missile can be aproximated as a point).

[Schmurk]

But what I care about is for players to be able to fire through some fences, under trees, from a ship to the ground and so on.

My big question is do you need an exact collision system in order to compute the exact intersection point between a line and an object? I mean, do you need that the algorithm gives you the 3D coordinates of this intersection point, which face has been intersected on the mesh and others...?

If not, as I said it earlier, you just need to represent your objects as one or several 3D primitives on server side. But you need to use the correct primitives in order to fit your objects the best. Like this, you'll be able to shoot under a tree or through a window or whatever you want...

 

Computing the intersection between a line and a box/sphere/cylinder is much faster than between a line and a simple triangle. For a triangle, you need first to compute the plane equation of the triangle (unless you already have it) so 1 vector product then compute the intersection point between the line and the plane so 2 scalar products. And finally you need to look if this point is inside the face by doing 3 vector products and 3 scalar products. So you have a total of 4 vector products and 5 scalar products per triangle!

So I ask my question again, do you really need that?

 

That's why a vertex by vertex collision detection is needed (although the missile can be aproximated as a point).

I don't understand why you're talking about "vertex by vertex collision"? I maybe misunderstood but in this case, if you have a big triangle (for example a wall) and if you just test the vertices, you can easily shoot through the wall...

[trollson]

A cylinder would also be diasterous for a fence or other long objects.

I don't recall whether I advocated using cylinders in the past, but my current position, as described in the last couple of posts, is not to use any path/object intersections as would be understood from 3D modelling.

 

Rather I am advocating a heuristic approach, where the difficulty of the shot is just a simple line integral across a precalculated (2D) map; this difficulty is then resolved against the shooter's skill.

 

This is an order of magnitude simpler than any method involving objects, and given the degree of uncertainty in the scenario (lack of exact positions etc), gives results that are as good in the context of an RPG, allowing high skill to compensate for apparently "impossible" shots.

[Entropy]

@trollson

Yes, you weren't advocating cylinders, I grouped the answer to Schmurk in the same post.

It would not work as a predetermined 2d map because that would not allow for some paths (like some diagonals). Of course I could implement some simple hack in a day or two, but if we are going to have missiles, they are going to be more than a ranged meele attack The way I want to do it is have some actual tactics when you fire a missile, such as hiding beside trees, possibly at night, etc.

It is hard to explain exactly how I see it, but a simple 2d precalculated collision map won't work the way I want it.

 

@Schmurk

You till don't get it. You can NOT represent complex objects as simple primitives. Unless if having an arrow bounce off thin air is acceptable. For me this is not acceptable, and I want a very accurate collision detection.

Do you want to prove me wrong? Make a client side system where you would fire from some point to another, and check to see if the missiles can go there or not. Base that system on simple primitives, and I'll show you how bad it will be.

If your system works properly, I will pay you 1K USD (I am serious about it)!

[Schmurk]

@Entropy

I don't want to prove you're wrong. I was just wondering why you need an exact collision detection. I agree with you that the primitive solution is not perfect and does not allow to compute an accurate intersection but if you don't need it, you save a lot of time.

Anyway, if you say you need it, I trust you so I'll try to work on it during my spare time.

[trollson]

It is hard to explain exactly how I see it, but a simple 2d precalculated collision map won't work the way I want it.

Can you give any example scenarios that we can consider?

 

Its not a collision map, but a map of the difficulty or challenge in shooting through that tile; consider it as giving the reduction to your skill when shooting [4] through that square.

So a square fully occupied by a building or cliff could be given a rating of 100. A tree may give a rating of 20 in the square contining the trunk, and a lesser value around it. Giving an empty square a value of 1 would account for range.

This would still allow you to hide behind a tree, but also allow a expert archer to shot around or through a gap when the moment presented itself.

An archer with a skill of over 100 could shoot "through" the building to hit a character hiding on the other side. This is ok in a fantasy game; very high levels can do the seemingly impossible (infact they saw an open window and crack in the planking).

Should illumination affect the difficulty of the path? Certainly that in the target square comes into play, as you have to see your target. But for intermediate squares along the path? In fact it does, but only in conjunction with any obsticles in the way. Assuming you have an illumination map, this would give a multiplier to the difficulty map.

 

The line integral approach is cheap and easy; it does allow diagonal paths (for better effects use antialiasing, see [1]), and can also be used to determine damage absorption due to shooting through soft targets.

 

There are plenty of tactical aspects that can be represented and used from the simple 2D method; these would be no less correct than using a 3D trajectory/collision calculation.

My objection to the 3D collision method, besides its cost

[2]

, is that you don't have the information to determine a single path in the first place. You have assumptions which are due to the limits of the game model -- the position grid, limited animations, etc. These shouldn't be treated as precise values, but as centroids of potential positions.

 

If we consider the actors' locations as 1m fuzzy blobs around their graphical representations, then the arrow is really travelling between points in two such blobs; this defines a fuzzy tube between target and destination, and a hit is possible if there is

any

valid path for the projectile down that tube

[3]

.

 

Also, I don't see the end-user case for the expensive 3D solution...

If 2D obscuration/difficulty mapping is a quick implementation, why not use it for now and see how it goes? It can always be swapped out for a 3D method later, which would take more development and testing.

 

[1] Rather than using a black-white line to integrate along, use an anti-aliased one, where the grey value [0..1) is a multiplier to the difficulty map when integrating. So if the centre path clips (5%) a solid building (100), it doesn't block the path but contributes just a fraction (5) to the overall difficulty of the path.

[2] Having worked quite a bit in the field of HPC and simulations, sensitive issue. The heuristic approach is your friend if accuracy is not critical.

[3] For magical projectiles, of course, all conventional rules of trajectories are off; the magic missile will follow whatever path the mage gives it!

[4] To be pedantic, avoid using the term "firing" etc, unless talking about firearms (or possibly fire-related magic).

 

 

Updated 20070111T1800: Reworked with a bit more time.

Edited January 11, 2007 by trollson

[Entropy]

This would still allow you to hide behind a tree, but also allow a expert archer to shot around or through a gap when the moment presented itself.

An archer with a skill of over 100 could shoot "through" the building to hit a character hiding on the other side. This is ok in a fantasy game; very high levels can do the seemingly impossible (infact they saw an open window and crack in the planking).

 

This is EXACTLY what I want to avoid. I do NOT want a missile to go through solid objects. Doing that would make the archery skill WAY too overpowered and unrealistical.

 

Can you give any example scenarios that we can consider?

 

player on docks->ship->player on the other dock.

First player fires at second player. With a 2D map, the missile will stop in the ship (which is what should happen).

However, with a 2d map the missile would also stop in the ship even if the players is on the ship firing at the player that is on the docks. This is not acceptable, the missile should go.

 

My objection to the 3D collision method, besides its cost [2], is that you don't have the information to determine a single path in the first place. You have assumptions which are due to the limits of the game model -- the position grid, limited animations, etc. These shouldn't be treated as precise values, but as centroids of potential positions.

Yes I do. The starting point will be the center of the bounding box of the first player, and the destination will be the center of the bounding box of the second player. The center is always 'full of someone', we don't have models with holes in the center. Besides, the server will not compute the collision detection with the actors, just with the environment.

[trollson]

This is EXACTLY what I want to avoid. I do NOT want a missile to go through solid objects.

That is not what the 2D model is representing.

 

In the example the intervening tree represents partial cover, given that the archer and target are extended objects with uncertain position within the grid location. Some shots will hit the tree, some will find an open path to either side of the tree; this is determined by the archer's skill and luck.

 

With a 2D map, the missile will stop in the ship...

Again, this is by no means certain with the 2D model; it does not cause the missile to be stopped by the ship in either direction; it only provides a difficulty for the path.

 

However, are you thinking of assymetric paths? Perhaps a simpler example is of a defender behind a battlement.

 

In this case it is correct that the path between attacker and defender is not symmetric; the structure does not present the same difficulty to the defender's missiles as to the attackers.

 

This can be represented in the 2D model by factoring in distance to the difficulty of a tile at a range; by reducing the difficulty of tiles closer to the shooter.

 

Since the battlement is adjcent to the defender, it presents only a small additional difficulty to their shots, while having a much larger effect on the more distance attacker.

 

Other factors can always be including in determining the difficulty of the path (eg, height map), if their contribution to the model and tactics are worth the cost.

 

you don't have the information to determine a single path in the first place...

Yes I do. The starting point will be the center of the bounding box of the first player...

This is a significant approximation; participants as point objects on a quantised grid, not extended objects moving within some bounds. Using this as the basis of an expensive calculation is undesirable.

 

For example, it can introduce artifacts into the model; for example: If these points are at the same height, an otherwise trivial object at this height would block shots. So small objects or elements need to be filtered out, but that also needs cluster analysis to identify grouping etc.

[Entropy]

Yes, I understand what you mean, and it is a good idea to make the paths asymetric (THB, I didnd't think of that, but now I will).

However, what you want (probability instead of certainty) does not apply in the real world at macro scales. It applies only in the quantum world.

For example, a player behind a SMALL tree can still be hit, if the diameter of the tree is smaller than the diameter (aproximated) of the player. However, a player behind a house can not be hit, no matter how much you try.

 

So your idea can be applied in a 3d context (as kibora pointed out):

Each object can have assigned a 'passability' rate. A small tree or bush would have a rate of 50%, a small rock will have 100%, and a house will have 0%.

[trollson]

However, what you want (probability instead of certainty) does not apply in the real world at macro scales. It applies only in the quantum world.

We are not dealing with the real world, but with a simulation of an assumed "real world" with limited resolution for understandable practical reasons.

 

People in the real world exist in a continual space and are not confined to a discrete grid point.

 

Avatars in the simulation are placed on the discrete grid, but this is simply the nearest point to the character's "real" location. So there is an implicit uncertainty given by the grid resolution. This is normal for this type of representation (not just MMORPGs).

 

Player control of their avatars is also limited, not just in placement but in posture; we can stand and sit, but we cannot lean, crouch, reach, etc. It is not practical to support the entirety of postures a character can take, either in player control or animation. So this is another degree of uncertainty between the "true" posture of the character, and what the player sees and the simulation represents.

 

This is why I would put (estimate) a ~1m radius distribution on the starting point for any missile launched from an avatar -- the convolution of the uncertainties in position and posture, which are inherent in these systems.

If we chose the shape of our distributions correctly, and we have certain freedom here, convolution is just a simple addition.

Knowing this probability distribution, we can go back to the simple point-to-point trajectory and re-evaluate it.

 

First, both source and target have uncertainty; these two distributions are convolved to give the kernel, or fuzzyness, applicable to the trajectory.

 

An object in or near the path can represent a solid obsticle, a silhouette or shape of either block or pass (black or white). These are convolved with the kernel to give a measure on the path; they are blurred so that rather than black or white, they are grey and further extended.

 

Add up the contributions along the path to determine a total to determine the possible obstruction along the path.

"Adding up" isn't quite that simple. What you want is the probability of a projectile crossing the distance, so its a product integral of the chance of passing through each leg of the trajectory.

 

For example, given three obsticle on the path, measured to provide 30,40,50% cover, the total cover is 1 - 0.7 * 0.6 * 0.5 = 79%.

Now, for any avatar, its positional distribution will be the same, since this is determined by the resolutions of the game, and not the character. So any trajectory will have the same convolution kernel, and the "shadows" of all objects can be pre-determined.

 

This is where I suggest precalculating a map of these "difficulties". Since the end result is to be compared to a skill level, we may as well define the values in the grid as difficulties which can be added together, rather than require a more complex calculation at runtime.

I have already suggested using an antialiased path to account for partial crossings of tiles, which should be simpler than interpolation of the map values.

Moving from a 3D environment to a 2D map may lose some representation of altitude, but does offer a great runtime advantage. Most of the world is pretty flat, so where altitude comes into play is the exception rather than the rule, and can be treated as such; adding some modifier to the resultant difficulty seems appropriate.

 

In the end, all we want is a difficulty to compare a skill to; so what is the difficulty to shoot over one clear tile (range factor), or through a tile of 50% coverage?

[Entropy]

An object in or near the path can represent a solid obsticle, a silhouette or shape of either block or pass (black or white). These are convolved with the kernel to give a measure on the path; they are blurred so that rather than black or white, they are grey and further extended.

 

Add up the contributions along the path to determine a total to determine the possible obstruction along the path.

 

*sigh*

Like I said, this would NOT work in case you are on TOP of an object rather than near it, and the target is on the othe side.

If you are on top of the ship, the path is clear. If you are near the ship, then the ship is in between you and the target, so the path is obstructed.

This is a 3D game, so the path HAS to be 3d, or else many situations would be useless.

 

And even if this 2D model worked (which doesn't work as I want it to), who is going to take every single map and manually create the 2d grid of probabilities?