Missiles

[trollson]

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.

Solved using the asymmetric path described above.

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?

You'd never do it manually, you'd develop a translation program to generate the 2D map of difficulties (not probablilities by this stage) from the 3D elm. Developing this application is a one time cost, plus some additional parameters for each 3D object type (finite set).

This allows object types to be consider as other than solid (clothes line, curtains). The 2D map can still be edited to accomodate exceptions (invisible or illusionary walls etc).

2007-01-22: Rather than continue fruitless posts, I'll just append here and be done:

 

trollson: You have no idea how hard making a program like that would be.. And how time consuming to go through all the maps and manually edit stuff.

I've been doing this stuff professionally for 20 years now, so I have a pretty good idea As I said above, there is no need to do any manual editing of the maps -- but it is possible to do so to accomodate situations outside the normal model; exceptional situation.

The asymetric path would not work properly with a 2d aproximation, and would leave room for a lot of 'arrow stops in mid air' or 'arrow passes through whole ship' scenario.

This is noncense. The 2d model can give you an end square for the missile, if you wish to interpret it that way. The actual blocking object can even be left upto the client if it has no other impact on the game, or randomly determined on the server from a candidate set on that tile. There is still the case of off-course and over-shoots, and hitting bystanders...

 

What the 2d model gives you is a measure of difficulty for a path; something that is needed in an RPG (unlike a FPS). How does calculating a single 3D trajectory tell you this? Consider two valid paths of equal length:

1. Across an empty field.
   
2. Through a tangled forest
   

Both cases the single trajectory gives a clear path; but shot (2) is a far harder shot than (1), and should require a greater degree of skill. This needs to be represented in the simulation.

 

The other example takes the first person viewpoint: From the FP view you see the upper body of your opponent behind a wall; so you click on them to shoot. You miss, because the arrow hits the wall. It will always hit the wall, because only one path is considered. There is never an opportunity to hit the opponent in the head, no matter how high your archery skill. An FPS would let you target parts of the opponent; so long as you can see some part of them you have an opportunity to score a hit; can EL be extended to support this?

 

Finally, targets should also be allowed to be objects; this allows for interesting scenario additions -- hit the rope/lever/button to drop the portcullis etc.

Edited January 22, 2007 by trollson

[Schmurk]

The idea of trollson seems really nice and should be better than a 3D collision detection. I've made a little test to see how fast can be the collision detection between lines and a polymesh. I've done the test on the file ship1.e3d with 10,000 lines and it took around 1.3 seconds. Here's a screenshot of the result: ray_collision.png (the red lines correspond to the collisions)

 

To do it, I've used the ray triangle intersection algorithm of Möller and Trumbore and the computer I used is an AMD Opteron of 2.2 Ghz with a processor cache of 1MB.

 

So it's up to you to decide if it's fast enough for your needs. I can send you the code by email if you want to test it.

 

EDIT: just done another test and if you use face culling, you reduce the time to 0.9 seconds for the ship and the 10,000 rays. But you can use this only if all your objects are closed and I'm not sure it's the case...

Edited January 16, 2007 by Schmurk

[Entropy]

trollson: You have no idea how hard making a program like that would be.. And how time consuming to go through all the maps and manually edit stuff.

As for the 3d vs 2d, I really see no advantage of the 2d, except that it would be faster.

However, if Schmurk's calculations are right, then we are OK. It would be very rare to have more than 10 arrows flying each second, so the CPU impact should be minimal (yes, in the real life it would be slower than his test, because there are various factors such as collision vs multiple objects, not just one, cache trashing, and so on. But it is still fast enough).

 

The asymetric path would not work properly with a 2d aproximation, and would leave room for a lot of 'arrow stops in mid air' or 'arrow passes through whole ship' scenario.

[ttlanhil]

It would be very rare to have more than 10 arrows flying each second, so the CPU impact should be minimal

not if projectiles are good weapons. unless a bow/arrow has a highish cooldown. during one of the PK events, if bow&arrow isn't slowed down or made weak (in which case there's not much point working on it, because people won't use them) you could have dozens of archers behind the front-line fighters. or even on their own (the numbers in existing PK capture-the-flag events means this isn't crazy)

 

plus the safety factor of being at range means players would like to hunt with them, plus EL's player base is growing... so assuming >10/sec probably isn't a safe idea

[Schmurk]

I agree with ttlhanil that there will be much more than 10 arrows per second. IMO, having 100 players (and maybe more) in all draia that fire an arrow at the same time should happen easily. Anyway, this has to be tested in real conditions to see what it does...

 

I worked a little more on my program and now I transform each ray by moving it in the object's space if this one is translated/rotated. Then I test if the ray collide the bounding box and in this case, I test the triangles. There's not a big impact on the resulting computation time compared to what I gave you yesterday so it's ok.

 

So now the next step I think is to test it on a real map with a lot of different objects and an algorithm that walks through the tiles. I didn't spend a lot of time on the client so I didn't understand yet how all the data structures work but with a little more work I can try to do it. BTW, can I find somehwere a documentation about these data structures? I took a look at the doxygen doc on the CVS but it seems to be quite old and it don't helped me a lot...

There's also something else that I'm wondering. Are the data structures the same on the server and in the client? I ask this because some of the data structures in the client are optimized for the display (vertex arrays for example) but I suppose that this is not very important for the server. And in the client, I didn't find the way to know the objects that are on a tile. I just saw that each map has a list of tiles and a list of objects but no links between them. Am I right?

TY for your answers...

[Entropy]

@ttlanhil

 

When I said <10/s I meant normal circumstances. Of course it is entirely possible that sometimes there would be more than that, although I highly doubt that it will happen too much, especially because of a big cooldown on the missiles (otherwise they would be too powerful). The arrows will also be expensive, sort of, so you won't typically go hunt rabbits with them.

 

@Schmurk

That would be appreciated.

Now, when we have that on the server, it will be very important to do it fast (duh). Which means that we might have to load the 3d objects in a separate structure (at runtime, possibly).

 

This structure will be cleaned and only the meaningfull objects will be placed in it. For example, there is no point in having small bushes, branches, small stones, etc. The elimination could be based on the bounding box, for example if the total volume is too small, but the object is not very long or wide (such as an wall) it can be eliminated.

Also, objects that are big but under 1 meter in hight (from the ground, so that also applies to some big but buried objects) can be removed.

 

If you can come up with a new data structure to optimize that, let me know.

[Schmurk]

Ok np, it should not be too difficult

If all the objects are loaded at runtime, the structure will be static so it will be easier to optimize it.

 

When you say that small objects have to be removed, does this also include the small objects that are above 1 meter from the ground? If these objects have to be kept, then the height test should be enough...

[Entropy]

Unfortunately, the list can't be static. We are planning to have some semi dynamic maps in the future (Q2 of 2007).

As for the small objects above from the ground, I guess that we can remove them, but they have to be smaller than the normal objects that we remove.

For example, a rock on the ground can be removed if the volume of the bouding box is under, say, 100 CC (cubic centimeters). But an object that is higher off the ground can be removed only if it's bounding box is 50 CC or less.

 

Of course, we will have to determine those values based on testing and so on. Furthermore, we can add a flag for some objects to never be removed from the ecuation, or some to be always removed.

[Schmurk]

Ok, I think I've finished the data structure and I've taken in account all your remarks.

The structure should be enough dynamic for your needs but it can be tuned again if necessary.

 

So here's how it works:

- each map is composed of a height map which is the one stored in the e3m file and a tile map which is equal or smaller than the height map. The available values are 1 map tile for 4, 9, 36 height tiles (i.e. 2x2, 3x3, 6x6).

- each tile of the tile map has a sorted list of the objects which cross the tile, from the bigger to the smaller.

- a map has also the list of all the objects it contains and the data of the objects is shared outside of the maps.

- the object lists in the map as well as in the tiles can be reduced according to the heuristics you proposed, i.e. the objects that have a height below 1 meter (depending on the height map of course) and the objects that are too small are removed.

 

I don't know how much memory you can spend on that but here is what I obtained after loading all the maps:

- for height map = 36 * tile map : 90 MB without heuristics, 80 MB with them

- for height map = 9 * tile map : 160 MB without heuristics, 140 MB with them

- for height map = 4 * tile map : 270 MB without heuristics, 240 MB with them

- for height map = tile map : 850 MB without heuristics, 750 MB with them

 

Now, I'll start coding the collision algorithms and I'll see if the size of the tile map has a big impact on the speed of the detection...

 

EDIT: replaced Mo by MB, french reflex

Edited January 20, 2007 by Schmurk

[Schmurk]

I have great news, I have finished the system and it works very well and really fast

I have tested many configurations and you can count around 10ms for 100 shots. I've tested with the different sizes of tiles and there's not a big difference so the best is to take the cheapest.

 

I've also configured the system in order to detect collisions with the ground (height map) and here's is a little example: ground_collision

 

And here is an example where rays are shot all around a position: collision_test_c2m14

For this last one, there were around 400 rays and it has been done in around 40ms.

 

Now, I'll try to comment the code a little and I'll put it online in order you can get it...

[Entropy]

EDIT: replaced Mo by MB, french reflex

 

Mo is fine, the octet is actually more correct than the byte (an octet is always 8 bits, a byte can be more or less, depending on the machine architecture).

 

Anyway, what do you mean by tile map?

each map is composed of a height map which is the one stored in the e3m file and a tile map which is equal or smaller than the height map. The available values are 1 map tile for 4, 9, 36 height tiles (i.e. 2x2, 3x3, 6x6).

 

Do you mean by that a collision map? As in, collision tile map? So a 2x2 height map area would be translated in one collision tile? If so, I think a 3x3 ratio would be best, we have 1GB of RAM on the server, and currently only 220M taken by the server (this will grow in the future with the dynamical maps and stuff).

 

How is the sorted list of objects stored? As an array of words (containing the ID of the object), or as a separate list, and the tile is a pointer to it?

 

Anyway, great work so far!

[Schmurk]

Anyway, what do you mean by tile map?

each map is composed of a height map which is the one stored in the e3m file and a tile map which is equal or smaller than the height map. The available values are 1 map tile for 4, 9, 36 height tiles (i.e. 2x2, 3x3, 6x6).

 

Do you mean by that a collision map? As in, collision tile map? So a 2x2 height map area would be translated in one collision tile? If so, I think a 3x3 ratio would be best, we have 1GB of RAM on the server, and currently only 220M taken by the server (this will grow in the future with the dynamical maps and stuff).

Yes exactly. A collision tile can contain 2x2, 3x3 or 6x6 height map tile.

 

How is the sorted list of objects stored? As an array of words (containing the ID of the object), or as a separate list, and the tile is a pointer to it?

There's a static array of objects pointers in the map structure and each object is allocated separately in order you can add/remove objects or move them easily in the array when you need to reduce it.

typedef struct {
 char file_name[80];

 int height_map_size_x;
 int height_map_size_y;
 unsigned char *height_map;

#ifdef TILE_MARKS
 unsigned char *marks;
#endif // TILE_MARKS

 int tile_map_size_x;
 int tile_map_size_y;
 collision_tile *tile_map;

 int nb_objects;
 collision_object *objects[MAX_MAP_OBJS]; // <--- the object array

 unsigned int current_test_id;
} collision_map;

Then the collision tile structure contain the same type of array but this one is reallocated in order to avoid the waste of memory. So here each object in the array of the tile points on an object in the array of the map.

typedef struct {
 int nb_objects;
 collision_object **objects;
} collision_tile;

When loading the maps, the array in the tile is resized by clusters and at the end it's resized to fit the exact number of objects. But it's easy to keep the cluster system in order to add objects dynamically. I will test it to see the memory impact...

 

Anyway, great work so far!

TY

[Schmurk]

I've removed a remaining bug that I've seen this morning and I've tested the cluster system to see if it has an impact on memory occupation. It seems to work very well without any additional memory so it's ready for the dynamic maps

 

I've commented the code a little and I've put all here in order you can test it.

 

If you want to use it in your code, you'll maybe have to merge some of the data structures with yours. Actually, to use it, it's really simple. Just load a map with load_collision_map(...), then use search_collision(...) to shot a ray and detect collisions. At the end, you can free the memory with empty_collision_map(...) and free_all_collision_objects_data().

 

If you want that I change or add something in the code, just tell me...

[Learner]

I've removed a remaining bug that I've seen this morning and I've tested the cluster system to see if it has an impact on memory occupation. It seems to work very well without any additional memory so it's ready for the dynamic maps

 

I've commented the code a little and I've put all here in order you can test it.

 

If you want to use it in your code, you'll maybe have to merge some of the data structures with yours. Actually, to use it, it's really simple. Just load a map with load_collision_map(...), then use search_collision(...) to shot a ray and detect collisions. At the end, you can free the memory with empty_collision_map(...) and free_all_collision_objects_data().

 

If you want that I change or add something in the code, just tell me...

The memory storage MUST be efficient ... the server will never call empty_collision_map(...) and free_all_collision_objects_data() on static maps.

[Schmurk]

The memory storage MUST be efficient ... the server will never call empty_collision_map(...) and free_all_collision_objects_data() on static maps.

I agree, this is why I said at the end. But as the server is always running and it never ends, well you don't need to call them... I just like doing things clean

[Entropy]

Ok, I have to think of it, see if there are any problems, or any improvements. Do you have ICQ or YIM? If so, send me a PM with your contact details.

[Entropy]

Ok, one other thing I came with.

We need to strip down the 3d object format for the server. As you know, the 3D format we use has a lot of data the server doesn't need, such as u/v and normals.

 

But I was thinking to take this further, thinking of your primitive aproximation idea. While primitive aproximation won't work, a hybrid method should work fine. So the idea is to strip pretty much all the unnecesary vertices.

 

For example, if we have veritces closer than, say, 20 CM, we can remove them all and replace them with only one vertex.

 

Or, sometimes, big objects such the walls have multiple vertices that are there for u/v purposes only (so we can have two tectures for example), but would be totally unnecesary when it comes to collision detection.

 

So a new 3d format might be needed, with, hopefully, only about 10% of the data needed by the original 3d object (which would save a lot of memory).

[Schmurk]

Ok, one other thing I came with.

We need to strip down the 3d object format for the server. As you know, the 3D format we use has a lot of data the server doesn't need, such as u/v and normals.

For the moment, only the vertices coordinates and the faces are loaded in memory so it's ok.

 

But I was thinking to take this further, thinking of your primitive aproximation idea. While primitive aproximation won't work, a hybrid method should work fine. So the idea is to strip pretty much all the unnecesary vertices.

 

For example, if we have veritces closer than, say, 20 CM, we can remove them all and replace them with only one vertex.

 

Or, sometimes, big objects such the walls have multiple vertices that are there for u/v purposes only (so we can have two tectures for example), but would be totally unnecesary when it comes to collision detection.

 

So a new 3d format might be needed, with, hopefully, only about 10% of the data needed by the original 3d object (which would save a lot of memory).

Even if it seems easy, surface simplification is not a simple task. It needs an appropriate data structure and quite complex algorithms.

However, there are free libraries that offer it, like GTS for example. I'll try to make a little program this week to test it and if it works, I'll post some screenshots of simplified objects...

[Entropy]

Yes, I know that only the faces and vertices are loaded, but since a ton of objects will be loaded at the start of the server, having a special format would save some time (since the files are smaller, and slightly less processing has to be done).

 

And I know that surface simplification is not simple, but we are not striving for visual niceness here, we just want to merge all the nearby vertices into one, which is considerably easier (also, no u/v coordinates are needed, which makes it even more simple).

[Schmurk]

And I know that surface simplification is not simple, but we are not striving for visual niceness here, we just want to merge all the nearby vertices into one, which is considerably easier (also, no u/v coordinates are needed, which makes it even more simple).

I agree but if the simplification is not done well, some corners on the objects can be removed and the collision detection will be affected. I already tried to make such a simple algorithm in my job because I need it and I saw that it's not so simple to do. Testing the distance between two vertices is not enough, you also have to control the normals on the surface.

 

[EDIT]

For example, you can have small edges around the corner of an object that will be removed and can cause some problems whereas you can have a lot of coplanar vertices that will not be removed because the distance between them is enough to keep them...

[/EDIT]

 

Anyway libraries like GTS already do the job very well so we just have to use it to generate new objects and save them in a new file format that will be used only by the collision system. I'll work on it this week...

Edited January 22, 2007 by Schmurk

[nathanstenzel]

Excuse me, but I am curious.

Are you guys talking about having a different structure for storing data on a 3D object and using the same 20x20cm game squares and then doing collision detection against all the 3D objects stored in the game squares in the path?

 

Will the missiles have a blurred arc going to the object and then making a bag poof effect upon impact to avoid needing to determine exact impact location on the struck creature/object/ground? The color of the arc would be the color of the missile averaged down its length, the way I figure it. An arrow made of crystal would make a nice shatter on impact.

 

I have only done a small amount of playing with 3D object storage stuff back about 10 years ago. I hope my questions are not too annoying and might actually help some.

[Entropy]

We are still discussing the implementation details, we might go for BSP trees, depending on how the test results are.

As for the arch, I am not sure we can do that, since we have small distances in the game, it's not like you can fire an arrow at 100M.

 

The game squares are 50x50 cm, btw. 20 cm is the height.

[The_Piper]

In international competitions bows are used for distances like 90 m, 70 m, 50 m and 30 m.

 

Longbows, like used in the battle of Crecy, 1346 AD, were used to shoot across distances of 200 meters, using an extreme ballistic curve, of course.

 

Heres the link to the german wikipedia about longbows, the english one doesnt have that details http://de.wikipedia.org/wiki/Langbogen (or im too blind or too sleepy or both )

 

Tactics about bows:

 

Aim at a target and shoot at it, that would be a horizontal line, should be easy to calculate (yes, still somehow a ballistic curve, but hey, this is a fantasy world).

 

Or mass archery, using an extreme ballistic curve. You have loads of archers, aiming not at a specific target, you have loads of enemies attacking you, just fire, some arrows will hit at least an unspecific target, but at least, some enemy down.

 

How to implement it?

 

Horizontal line: You have your bow + arrows equipped somehow, you see a deer, just click on it and fire an arrow at a given speed. Depending how fast the deer is, you kill it or the arrow flys away and ends in a stone or tree. Or just at a random noob passing by

 

Ballistic curve: Somehow you adjust the angle for shooting the arrow, then fire, dont aim at anything specific and the arrow flies. Like defending Fort Baarg and the enemies are lining up far away, its a nice method to send them some welcome greetings

 

Basically i see missiles flying to places which i cant see right now. If i miss the deer, no idea where the missile would stop.

 

Which may cause the problem that a certain idiot is standing in the middle of the Whitestone map and just is firing arrows in the air just for fun.

 

Well, just some thoughts, as usual

 

Piper

[Puntif]

The game squares are 50x50 cm, btw. 20 cm is the height.

 

So if you can see about 24 game squares away that means you can shoot up to 1200 cm or 12 meters. I think a straight line would be a decent approximation of the first 12 meters of the flight of an arrow.

 

But will an arrow that misses the target have a chance to hit something else? Will we see arrows that originated from some archer far away or will an arrow that misses its target be assumed/forced to hit a surface near to the target and not continue for a great distance? If not, would these glimpses of arrow trajectories need to show some arc?

[Entropy]

Piper, I think you are missing the point. Of course a bow can go further, but in EL it can't because you can see only like 9 meters away or so.