Elevation advantage for ranged units.

[sanderd17]

In real life, ranged units have a bigger range when they're on higher terrain. This isn't the way in 0AD currently.

I made a little test file in GeoGebra: https://dl-web.dropbox.com/get/Public/ballistics.html?w=AADi1kWPjqurVoqz9VK8_xLRdovP4XtWbUlIMEcNKHovdw (the original version is added as attachment, just rename .zip to .ggb and open in GeoGebra). You can drag around two units (S and T) to change the distance from each other and relative elevation, both have a minimum and maximum range. You can change the ranges by dragging them over the x-axis. And there are checks to see which unit can hit which according to the formulas explained below.

I took a paraboloid (or a parabola in the 2D program) to calculate the maximum range of a unit. The height a unit can shoot is the same as the distance a unit can shoot to a target on the same level. So that defines the parabola, where s.x and s.y are resp the horizontal and vertical coordinate of the shooter.

f(x) = -( (x - s.x )² / range) + range + s.y

But the code to check if a target (t) is inside the range of a shooter (s) is just as simple.

-(t.x - s.x)² / range + range >= t.y - s.y

or in 3D (with z the vertical coordinate):

-((t.x - s.x)² + (t.y - s.y)² )/ range + range >= t.z - s.z

Of course, checking if the target is outside the minimum range is just reversing the inequality.

So I wonder, if the formulas are that easy, are there other reasons why the ranges are still with a fixed distance instead of a paraboloid?

I'd like to test this in game, but I have no clue where I can find the range calculation. So if someone wants to give me a clue, please do.

ballistics.zip

[k776]

Bring this up in IRC. Point to this thread. If the consensus by developers is yes, then go ahead and make a ticket at trac.wildfiregames.com

[Zeta1127]

It was planned for there to be a height bonus for units in garrisoned structures (the Britons special tech, Turos Maros, was planned to improve that), so I don't see why there shouldn't be a height bonus for units on higher terrain.

[alpha123]

I actually thought of bringing this up after noticing just how important terrain is in Starcraft II. I say go for it. I was also considering not allowing units to shoot too far up. So if some archers are on very high ground they would not be able to be shot by units on regular ground level. I'm not sure if that's going too far however.

[sanderd17]

Better version of the file: https://dl-web.dropb...WbUlIMEcNKHovdw

Me wanting to add ballistic trajectories saw that there were some problems. I brought sqrt(2) twice in the calculation, instead of once. So in the end, it differed a factor two. The correct test to see if units are inside the range is this:

(t.x - s.x)²  <=  2*range*(s.y + range/2 - t.y)

(I also changed some numbers to different ides, to avoid divisions and extra operations)

or in 3D:

(t.x - s.x)² +(t.y - s.y)² <= 2*range*(s.z + range/2 - t.z)

This means realistical units can only shoot half as high as they can shoot far on flat terrain.

The ballistic trajectories added are done via the numerical method to solve a root for a bi-quadratic function. I could have done it by hand, but to calculate the real trajectories, you get complicated functions, with lots of operations. So probably not doable in the game for every arrow. Using the numeric methods in the draft does mean that, if the unit is almost out of range, it won't find a trajectory. And there are also some sign problems (S can only shoot upwards and forwards, not downwards), so sometimes you have to imagine the mirrored trajectory.

You would need this to calculate obstructions though (I heard people want walls and buildings to obstruct arrows), so I'm not throwing it away for now. But the complicatedness of the real traject shows in some way how really simple a basic range check is.

@K776: what's the best time to be on IRC? When are the most developers active?

@Zeta1127: You can easily add custom height bonusses. If you change the check to

(t.x - s.x)² +(t.y - s.y)² <= 2*range*(s.z + heightBonus + range/2 - t.z)

Then it will be exactly like 's' is always 'heightBonus' higher.

@alpha123: It uses exact physics (hopefully now without mistakes), so the hight a unit can shoot is certainly limited (to exactly range/2).

ballistics.zip

Edited June 3, 2013 by sanderd17

[sanderd17]

It gives some nice results.

Here you see a screenshots where skirmishers were attacking other units below them, but the other units had to run up the hill to attack back the skirmishers. The skirmishers were rather safe.

There is still a problem with the implementation I've noticed.Something I haven't figured out results in an error.

Oh, and this is the trac ticket with the patch so far: http://trac.wildfiregames.com/ticket/1960

[Lion.Kanzen]

Nice, I love archers, one day this archers can massacre a tiny group of Spartites.

[idanwin]

Cliffs will get a totally new meaning in 0AD!

Me likez.

[sanderd17]

I've been thinking about stuff, and this are the results:

Shooting range

A little update on the shooting range:

For me, the patch is ready for inclusion. It now even draws the right ranges in developer overlay (yay). Though a bit imprecise, but good enough I think.

https://plus.google....=CIni7qimwKC8fg (green lines are drawn by the software, I drew the yellow highlights by hand)

You even see little bumps or holes influencing the ranges (with the iberian towers), if the elevation differences are bigger, the range is completely deformed (see the towers on the ridge). And it turned out to be more of an elevation disadvantage to low units, than an elevation advantage to higher standing units. But anyway, ones disadvantage is another-ones advantage.

Line of sight, the formula

Now, I've been thinking about line of sight based on elevation and obstructions.

This is a lot more difficult, as it's not the highest unit that has the most advantage (I can see the a village from the top of a mountain, but I can also see the mountain from the village). But elevation has some play in it. You can hide behind a cliff or mountain.

So what I've been thinking of, is calculating how big a square meter seems when you stand somewhere.

First of all, the appearance of size diminishes squared with the distance (imagine you're in the center of a sphere, double the radius, the surface of the sphere will be 4 times as big, but still fill your entire view).

Next to that, it also depends on the angle at which you're looking at it. To be exact, it's directly proportional to the cosine of the normal on the surface and your viewing direction. But, if there's a building on it, you aren't watching the ground any more, so you should take an other angle, so if there's a building, I'll just take this cosine = 1. Note that the cosine is equal to the dot product between normalized vectors.

To summarise, checking if one tile can be seen is done by the following formula:

V * N / dist² > value

or for a building

1 / dist² > value

Where V(x,y,z) is the normalized vector from the point you're watching to your eyes, and N(x,y,z) is the normal on the surface, also normalised. And * is the dot product. N can be pre-calculated, as the terrain always stays the same, and there's just a finite number of tiles you're able to see.

Calculating V is more difficult, as for normalizing it, you need to calculate the length, which implies you calculate a square root. Next to that, you need to give the unit a height, so his eyes are above the ground. If his eyes are on the ground, he can't see flat terrain, as the cosine would always be zero. I was thinking about first taking a generic 2m for a unit (some average between cavalry and infantry), and 5m for a building. Later on, I'd like to see a <height>x</height> property in the xml files, to give a better interpretation to the viewing ranges, and it could also be taken into account for the shooting range.

Next problem is the 'value'. That's some property of a unit, but we still need to interprete it. Say you have flat terrain and a unit with height h, it should still be able to view its normal range. So we calculate what the value should be.

V ~ ( -range, h, 0) (vector from a point at distance range, for a unit with height h)

V = (-range, h, 0) / Sqrt( range² + h² ) (divide with the length to have a normalized vector)

N = (0,1,0)

value = N * V / dist² = h / (Sqrt( range² + h² ) * range² )

As you see this is again a formula with a square root, it should best be cached (there will be a lot of units with the same height and range).

Line of sight, the algorithm

Until now, we have two extra caches, and still a lot of extra calculation work. Calculating V still requires a sqrt calculation, and some 15~ish native operations (addition, multiplication ...) for the whole comparison (according to a fast count I did). While the current circular comparison only requires 4 native operations. Also, the current comparison has a very regular patter (a simple circle), and this is used to optimize code. While there's no pattern to be found with the method explained above.

So there's only one way to solve this (at least as far as I can see it now), that's getting rid of unit based LOS updates to get rid of most checks. And use a continuous fill algorithm. For the entire region.

The algorithm would need two usable collections (arrays, hashes, attributes of a tile, something else) per player. Those are "VisibleTiles" and "BorderTiles". And two collections (TilesToCheck and CheckedTiles) to work with.

As initialisation, all tiles with a building on it, or a unit standing there, owned by that player are added to the "TilesToCheck" collection. Since we don't need to have a single point, we also need that CheckedTiles collection to not do double work.

Then we loop through the "TilesToCheck" collection until it's empty.

• The tile is checked for visibility via the formula mentioned above, for all units and buildings around the tile (all units and buildings in general, or use some selection to only test the nearest ones)
  
• If the tile is visible and not yet in the "VisibleTiles" collection, it is added to that. It is also removed from "BorderTiles" if it was in there.
  
• If the tile is not visible, it's added to "BorderTiles" and deleted from "VisibleTiles" in case this was needed.
  
• If the tile changed state (e.g. from Visible to Border, or the other way around), all the neighbouring tiles are added to the TilesToCheck collection, unless it was part of the CheckedTiles collection
  
• This tile is added to the CheckedTiles Collection
  

Once it's initialised, at each simulation step, we just need to copy all the BorderTiles to the TilesToCheck, and let the loop run. The border of the visible region will be adapted as units move . All the tiles inside the region won't need to be checked anymore, and all the tiles further outside the border also won't need to e checked. In the best case (when the border doesn't change), you only have to test all tiles on that border.

There are some problems with it though. The algorithm won't notice created holes. If you all start in one point, and the units spread out, so that the center point would become fogged again, the algorithm wouldn't notice that. I have no I idea how many times this happens, I assume not too often, and I don't think it's a big problem (any enemy units that got there had to pass your vision line anyway). So I would probably leave it that way.

A nice addition would be the "Don't look though walls". When you see the tile that became visible had a building on it, you could just make the tiles with the building visible, but don't add them to the "TilesToCheck" collection, or to the BorderTiles. So that way, further tiles won't get checked and you won't be able to see further through the wall. Now, this would only work if the wall is long enough. When a unit's view range reaches a tile at the end of the wall, the fill algorithm would go around it and start filling behind the wall anyway. It might or might not give a strange effect. That's to be investigated. (anyway, one more reason to build long walls

So, I'd like to hear your thoughts on the feasibility of this (getting rid of Unit based LOS) and how this would affect the rest of the game (e.g.single units can't suddenly get an enemy in their view, or at least, this can't be tested).

And to Lion: Of course you love Archers. But Leper said there were already too many Archers working on the 0AD.

Edited June 10, 2013 by sanderd17

[Flamadeck]

The ballistic trajectories added are done via the numerical method to solve a root for a bi-quadratic function. I could have done it by hand, but to calculate the real trajectories, you get complicated functions, with lots of operations. So probably not doable in the game for every arrow. Using the numeric methods in the draft does mean that, if the unit is almost out of range, it won't find a trajectory. And there are also some sign problems (S can only shoot upwards and forwards, not downwards), so sometimes you have to imagine the mirrored trajectory.

You would need this to calculate obstructions though (I heard people want walls and buildings to obstruct arrows), so I'm not throwing it away for now. But the complicatedness of the real traject shows in some way how really simple a basic range check is.

Since the calculation of one arrow does not really depend upon another you could parallelize it.

Let it run on the GPU using OpenCL.

Alternatively you could also implement the equation as an animation, have archers two poses 1 for max length and one for higher, and do other things to limit the number of operations.

[Flamadeck]

@sanderd17

What if you would go a different way.

Go the other way. Make buildings visible dependent on what tiles are visible! With of course making only the building, or part of the building visible depending on the tiles visible. Should solve most issues to to tackle the problem this way.

Edited June 16, 2013 by Flamadeck

[sanderd17]

For your arrows, I've never programmed on the GPU. So that's nothing for me (yet).

And about the buildings. It's not possible to only make half of a building visible. This is because the inside of a building is not textured (it's completely transparant in fact). So it would give strange problems with being able to look through the walls. Currently, the building is made visible when the tile in the middle of the building is visible.

[sanderd17]

Btw, the patch with all the gui stuff (can be seen in these screenshots: https://plus.google.com/photos/105567941221792569561/albums/5887468574070508289?authkey=CIni7qimwKC8fg) is now in trac.

You can test and comment if you like.

http://trac.wildfiregames.com/ticket/1960

[fabio]

Hi, sanderd17, your patch really looks great! A couple of question here:

• the bonus range (also reported as (+x)) is the mean value in all the directions? Maybe the "Bonus range" could be changed to "Mean bonus range", to make clear that it's not a constant circular bonus;
  
• to make it even obvious it would be nice to show on the selected unit the actual range, maybe also including the minimum range. I remember other games doing so: Panzer II example with maximum range (red points) and minimun range (yellow points, hardly visible here due to zoom). Close up of minimum range.
  

[sanderd17]

The bonus range is the mean range for buildings, or the range in the direction of the unit for untis.

I've made it adaptable, so f.e. units with turrets that can only turn for a limited angle, can query for that angle, and it will take the mean over that angle.

When should I use the "mean bonus range" terminology? On the building placement tooltip? Or on the attack selection hoover?

I'm not good with UI design. So if could suggest the UI in more detail, that'd be great.

Edited June 18, 2013 by sanderd17

[fabio]

The bonus range is the mean range for buildings, or the range in the direction of the unit for untis.

Nice!

I've made it adaptable, so f.e. units with turrets that can only turn for a limited angle, can query for that angle, and it will take the mean over that angle.

What do you mean with adaptable? Are there units with turrets currently (IIRC there is no turret support)? Another related question: when a unit fires he must be always at a 0 angle with the target or he can also fire with a limited angle? If the former the bonus range should report only the bonus for the 0 angle, since the latter will never be used.

When should I use the "mean bonus range" terminology? On the building placement tooltip? Or on the attack selection hoover?

I'd say only on the building placements, where there is space. In the attack selections there are already many numbers and adding more text would complicate too much the tooltip.

I'm not good with UI design. So if could suggest the UI in more detail, that'd be great.

I like the Panzers example with the red and yellow points (it's useful when playing, you'll get an indication of when a unit will start firing and can help you choosing to advance or retreat). But this should be discussed, do we really want this? What about when selecting more than one units, all the range should be shown or we should not shown anything?

[sanderd17]

What do you mean with adaptable? Are there units with turrets currently (IIRC there is no turret support)? Another related question: when a unit fires he must be always at a 0 angle with the target or he can also fire with a limited angle? If the former the bonus range should report only the bonus for the 0 angle, since the latter will never be used.

I mean, when the selction between Building and Unit is made, a function is used to get that range. Instead of just using a boolean switch, I've added the angle as an argument. For units, the angle is 0, and for buildings, the angle is 2PI. There is currently no turret support, but if it ever comes, you can query any other angle, and it will calculate the mean range over that angle.

I'd say only on the building placements, where there is space. In the attack selections there are already many numbers and adding more text would complicate too much the tooltip.

Is good to me.

I like the Panzers example with the red and yellow points (it's useful when playing, you'll get an indication of when a unit will start firing and can help you choosing to advance or retreat). But this should be discussed, do we really want this? What about when selecting more than one units, all the range should be shown or we should not shown anything?

Well, if you enable the range overlay in debug mode, you can see those circles (at least for the buildings, it only shows the vision range for the units). They're just not very pleasing to the eye. So the code to get the coordinates exists. It's just a matter of drawing it nicely (which isn't for me either).

And it could be a bit CPU intensive too. Although that wouldn't be a problem if you can only show it for one unit at a time.

[Flamadeck]

For your arrows, I've never programmed on the GPU. So that's nothing for me (yet).

And about the buildings. It's not possible to only make half of a building visible. This is because the inside of a building is not textured (it's completely transparant in fact). So it would give strange problems with being able to look through the walls. Currently, the building is made visible when the tile in the middle of the building is visible.

I meant things like walls that consist of multiple sections, by uncovering a piece of the wall you don't want that the whole wall suddenly becomes visible, especially if it's a very long wall.

Drawing the range overlays, with modern OpenGL features can actually be done mostly, completely on the GPU.

Also calculating the arrow paths can also done this way using OpenCL on the GPU.

(OpenCL works on CPU and GPU)

Modern GPU's have massive parallelism that you can exploit not only for graphics but for physics and other things too.

The calculation of the arrows path and physical stuff is a good example of a parallelizable workload that you can run very well on the GPU.

[gab]

Modern GPU's have massive parallelism that you can exploit not only for graphics but for physics and other things too.

The calculation of the arrows path and physical stuff is a good example of a parallelizable workload that you can run very well on the GPU.

I saw some truly impresive/efficient real-time calculations of fluid physics using the GPU( by the ecole normale supérieure in France ) :

a clever use of the GPU could really make some aspects of the game( including your great patch )a lot faster...

(but it require peoples able to code it...)

[sanderd17]

I'm out anyway, because my GPU isn't supported by OpenCL (and can't be supported).

[Loki1950]

Making it GPU dependent drops lots of people from playing not all GPU's support OpenCL at this time and I think not for several years will they.

Enjoy the Choice

Edited June 18, 2013 by Loki1950