How to handle range and circular radii?

[yufra]

My changes to the projection code in SVN2888 have (hopefully) eliminated the extra tile projection bug and improved the robustness of the projection and targeting system. Marcotte has pointed out that the way the range of talents and the circular radius projections are handled are currently inconsistent. For example, if the player is at (0,0) then a range 2 talent can hit (2, 0) just fine, but (2, 1) and (2, 2) are outside of range. A circular projection of radius two would hit all of those tiles, though. The issue is how range is rounded. Currently the targeting and projection code looks like this:

Code: Select all

					if typ.range == 1 then
						if math.floor(dist) > 1 then return true, false, false end
					else
						if dist > typ.range then return true, false, false end
					end

The range 1 hack is introduced precisely because of this rounding effect, and I made the conscious decision to at least let range 1 talents hit the diagonals. If the range is not 1, a strict comparison is made. In contrast, the fov circular grid code uses this:

Code: Select all

        case FOV_SHAPE_CIRCLE:                                                                  \
            h = (unsigned)sqrtf((float)(data->radius*data->radius - dx*dx));                    \
            break;  

The cast to an unsigned integer floors the radius instead of doing a strict comparison of distance. I think range and radius should be handled consistently in T-Engine, so the question is how should they be used? The two most viable options are to either floor both or round both. Marcotte pointed out that rounding the values is fairly easy by doing the following:

Code: Select all

C CODE:
        case FOV_SHAPE_CIRCLE:                                                                  \
            h = (unsigned)(sqrtf((float)(data->radius*data->radius - dx*dx))+0.5);                    \
            break;  
LUA CODE:
	if math.floor(dist+0.5) > math.floor(typ.range+0.5) then return true, false, false end

The flooring for Lua code is also obvious.

[Marcotte]

Just such that people can easily see the differences between the 3 methods (floor, ceil and round), here are what a radius-2 disk would look with each of them:

Code: Select all

floor   ceil    round
XXXXX     X      XXX
XXXXX    XXX    XXXXX
XXOXX   XXOXX   XXOXX
XXXXX    XXX    XXXXX
XXXXX     X      XXX

The "O" is the center of the disk, and the "X"s are where the projection hits.

[Grey]

Round all the way, baby. Technically it makes no sense in a game where diagonal movement costs the same as linear movement, but it looks the nicest and is the most intuitive to the player.

[tiger_eye]

a game where diagonal movement costs the same as linear movement

Good idea, make diagonal moves cost 14 game ticks (whereas a linear move takes 10)! I meant this as a joke, but does this actually make sense?

Back on topic: yufra, I don't think your two methods are quite equivalent. In the Lua method, you are given x and y (as dist) to check against a given radius distance. In C, you are given a radius distance and x, and you need to calculate y. I propose the following methods (and I agree: round all the way around!):
Lua

Code: Select all

if math.floor(dist - typ.range + 0.5) > 0

C

Code: Select all

h = (unsigned)(sqrt((data->radius-0.5)*(data->radius-0.5) - dx*dx) + 0.5);

[Marcotte]

C

Code: Select all

h = (unsigned)(sqrt((data->radius-0.5)*(data->radius-0.5) - dx*dx) + 0.5);

Simpler, and equivalent to your Lua code:

Code: Select all

h = (unsigned)(sqrt((data->radius)*(data->radius) + data->radius - dx*dx));

[tiger_eye]

Although it wasn't totally obvious, I concur 100% with Marcotte.

Use my Lua code:

Code: Select all

if math.floor(dist - typ.range + 0.5) > 0

and his C code:

Code: Select all

h = (unsigned)(sqrt((data->radius)*(data->radius) + data->radius - dx*dx));

Well done!

[Canderel]

I am working on (read as "thinking about") my implementation of Diablo 2 in T-Engine. The paladins have aura damage effects, and my thinking was to implement it so that the aura has a float radius, and then calculating the % coverage of the "edge" squares, to determine a % scaling for those on the edge of the radius.

It'll be something like this (though I'll get a formula for calculating the %'s)

2011-03-02_100738.jpg (20.81 KiB) Viewed 5495 times

This one is just thumbsucking numbers, but the real one will have proper numbers. Also if one could make the graphical feedback also fade with effectiveness, would be awesome.

[Frumple]

Also if one could make the graphical feedback also fade with effectiveness, would be awesome.

I've got zero coding ability, but I'd say try looking at the shining caves and whatever code controls the lightning in the place. It noticeably fades with distance from yourself and certain enemies. I can only imagine that could either inspire you or give you code to shanghai... whichever works.

[Canderel]

I was more referring to something like the screenshots in this thread, which was because of a bug, but the same concept... Where all squares that are "normal" have higher opacity, and the ones with lower effectiveness have lower opacity (more transparent)... Obviously more for the circles, but you understand... but those caves... man they are PRETTY.

[tiger_eye]

Hmm, I don't think the topic of this thread is 100% finished.

I noticed that the "FOV_SHAPE_CIRCLE_PRECALCULATE" option in "fov/fov.c:FOV_DEFINE_OCTANT" doesn't calculate radii consistently with the other methods. This is done in "fov/fov.c:precalculate_heights" near line 121:

Code: Select all

            result[i] = (unsigned)sqrtf((float)(maxdist*maxdist - i*i));

should be

Code: Select all

            result[i] = (unsigned)sqrtf((float)(maxdist*maxdist + maxdist - i*i));

It's just that, well, this isn't the end of the story...

If you want to see an example of the problem, just use "wild-gift/fire-drake - Devouring Flame". The target preview is correct (radius 2 circle), but the actual effect is wrong (5x5 square). If you use the corrected code above, then the affected area is a radius 3 circle (should be 2) .

[tiger_eye]

Performing `grep -r core.fov.distance game/` made me realize that many places in the code check range boundaries on their own, and practically none use the rounding method that this forum topic established. This has in-game consequences too. For example, it is possible to perform a ranged talent that you think is in range (because targeting uses rounded range), but falls short of that range when actually executed. I think we should define and use a universal "isInRange" function such as the one below. Calling this in the appropriate places in the code is beyond my comfort and confidence levels, because there are many places that appear to need modified and I'm not familiar with any of them.

Code: Select all

-- See if tiles (x,y) and (tx,ty) are within "range" of each other.
-- "range" can be a float.  If integer range is desired, then cast to int via "range_int = math.floor(range + 0.5)"
-- Note: 'dx*dx + dy*dy < (r+0.5)*(r+0.5)' is 100% equivalent to
-- 'floor(sqrt(dx*dx + dy*dy) - range + 0.5) <= 0', which was previously used.
function isInRange(x, y, tx, ty, range)
        if range < 0 then return false end
        if (x-tx)*(x-tx) + (y-ty)*(y-ty) < (range + 0.5)*(range + 0.5) then
                return true
        end
        return false
end

Below is a useful reference for how floating point ranges behave for small range. Note that "[]" are inclusive boundaries, "()" are exclusive boundaries, and "{}" are safe approximate boundaries. The three rows below correspond to ranges (0.5, 1.5], (1.5, 2.5], and (2.5, 3.5], respectively.

Code: Select all

(0.5, sqrt(2)-0.5)  [sqrt(2)-0.5, 1.5]
(0.5, 0.914}        {0.915, 1.5]
   .....                .....
   ..*..                .***.
   .*@*.                .*@*.
   ..*..                .***.
   .....                .....


(1.5, sqrt(5)-0.5)  [sqrt(5)-0.5, sqrt(8)-0.5)  [sqrt(8)-0.5, 2.5]
(1.5, 1.736}        {1.7361, 2.328}             {2.329, 2.5]
  .......                .......                   .......
  ...*...                ..***..                   .*****.
  ..***..                .*****.                   .*****.
  .**@**.                .**@**.                   .**@**.
  ..***..                .*****.                   .*****.
  ...*...                ..***..                   .*****.
  .......                .......                   .......


(2.5, sqrt(10)-0.5)  [sqrt(10)-0.5, sqrt(13)-0.5)  [sqrt(13)-0.5, 3.5]
(2.5, 2.662}         {2.663, 3.105}                {3.106, 3.5]
  .........             .........                    .........
  ....*....             ...***...                    ..*****..
  ..*****..             ..*****..                    .*******.
  ..*****..             .*******.                    .*******.
  .***@***.             .***@***.                    .***@***.
  ..*****..             .*******.                    .*******.
  ..*****..             ..*****..                    .*******.
  ....*....             ...***...                    ..*****..
  .........             .........                    .........

Above 3.5, floating point range behaves pretty smoothly.

[yufra]

We already have one... the canProject function from engine.interface.ActorProject. Ok canProject does a bit more than a simple isInRange, but I don't think it is worth adding yet-another-function for the performance gain. Basically you pass it the target declaration from the talent and it gives you a boolean (did we hit it?), then the x/y of what we hit and the x/y of where any radius effect should start from. I think it would be straight-forward to grep out for core.fov.distance and put in canProject in place for most talents. I think it would be useful to take a look at engine.interface.ActorTalents:getTalentTarget and possibly hard-code in a default target type (say {type="hit", range=self:getTalentRange(t), radius=self:getTalentRadius(t)}) if we find nil. That way the game targeting, talent action, etc can all use the same default. Thoughts?