Page 1 of 1
How to handle range and circular radii?
Posted: Tue Mar 01, 2011 11:58 pm
by 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.
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 12:08 am
by 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.
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 12:37 am
by 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.
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 1:01 am
by tiger_eye
Grey wrote: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);
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 1:29 am
by Marcotte
tiger_eye wrote: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));
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 4:23 am
by 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!
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 8:09 am
by 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 5497 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.
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 12:06 pm
by Frumple
Canderel wrote: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.
Re: How to handle range and circular radii?
Posted: Wed Mar 02, 2011 1:36 pm
by 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.
Re: How to handle range and circular radii?
Posted: Wed Mar 09, 2011 5:19 am
by 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)
.
Re: How to handle range and circular radii?
Posted: Sun Mar 20, 2011 4:52 pm
by 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.
Re: How to handle range and circular radii?
Posted: Sun Mar 20, 2011 5:17 pm
by 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?