Targetting and LOS discussion wiki page

[Pete Mack]

diamond completely blocks view through diagonal gaps.

#@
M#

@ can't see M.

Ouch. I misunderstood "diamond". I thought it meant that the diamond was a diamond inscribed within the grid, then filled out with a convex hull. In that case, you can't see through:

 @ 
###
 M

but you can see through:

#@
M#

There must be some model that satisifies these additional desiderata... [goes looking for a simple geometry program...]

[zaimoni]

Reposting what I just put up on the roguebasin wiki:

I proceeded with Zaiband by first simplifying V's base projection algorithm; this stopped hockey pucks as a side effect. Cf. flow.c for end result. [V starts directly emulating fractional steps at the second step. Zaiband does so starting at the first step.]

If there are fixable problems with the initial projection path (offsets directly along an axis or primary diagonal do not admit fixing):
* Check for standard one-off trick shots that anyone can hand-calculate: abs(Δx)==1, abs(Δy)==1, or abs(abs(Δx)-abs(Δy))==1. If they are applicable, use them.
* If no standard one-off trick shot applies, fall back to [Tyrecius'] Permissive Field of View.
** We use rational tangent values as proxies for the actual angles.
** The simplified base projection algorithm admits trivial calculation of the upper and lower rational tangent values for both hitting the target square, and hitting the obstruction. Take the set difference and see if the resulting interval is nonempty.
*** empty: target square is non-projectable.
*** non-empty: use tangent angle summation and half-angle formulae to determine a suitable positional target. Retry the base algorithm. If this path is obstructed, repeat the Permissive Field of View correction.

Zaiband defines visibility as "illumininated, and projectable with a wand/rod of light".

I was pleasantly surprised that this automatic fixup gets all advocated properties except symmetry; the player need never calculate trick shots. Imposing either logical-or symmetry or logical-and symmetry would be a rote change.

[PaulBlay]

Ouch. I misunderstood "diamond". I thought it meant that the diamond was a diamond inscribed within the grid, then filled out with a convex hull. In that case, you can't see through:

I think it depends which page of the wiki you're on.

The only 'diamonds' in the Discussion:Talk page I put up are the ones you discussed and the ones in section 3.2 (See fig 6).

I think those are different to the diamond algorithm used by libtcod (which I don't know well).

[Pete Mack]

Additional desiderata:

6. Shadows shall not be disconnected. If a single grid wall casts a shadow at a some point, there must exist a (diagonally) connected path of shadow from the wall to the point. (In ordinary parlance: it always becomes easier to hide behind something as you get closer to it.)

6b. Let a, b be two grids which are both in shadow by a column at grid w of grid @. Then there must exist a continuous path from @ to W which is in shadow of both a and b. (This requires a lot more definitions to pose it in set notation, but it's still pretty straightforward.)

I think that 6 & 6b pretty much eliminate all the proposed models but the diamond algorithm applied to diamond (or cylindrical) shaped wall grids. (Model 5a in my earlier post.) I will try to prove it...


BTW:
6 (with diamonds but not with cylinders) implies ASC's will be only partially effective, if monsters are a bit smart:

##########
#W#D#P# #
##U#R#@# #
##########

Depending on permissiveness, T(D,@), or even T(W,@), but not T(R,@). Cutting down on possibilities, 4a (with diamonds, but not cylinders) is a model for T(D,@), but not for T(W,@).
4b is a model for both T(D,@) and T(W,@), with either diamonds or cylinders.

[Pete Mack]

Additional desiderata:

6. Shadows shall not be disconnected. If a single grid wall casts a shadow at a some point, there must exist a (diagonally) connected path of shadow from the wall to the point. (In ordinary parlance: it always becomes easier to hide behind something as you get closer to it.)

6b. Let a, b be two grids which are both in shadow by a column at grid w of grid @. Then there must exist a continuous path from @ to W which is in shadow of both a and b. (This requires a lot more definitions to pose it in set notation, but it's still pretty straightforward.)

I think that 6 & 6b pretty much eliminate all the proposed models but the diamond algorithm applied to diamond (or cylindrical) shaped wall grids. (Model 5a in my earlier post.) I will try to prove it...


BTW:
6 does not imply that ASC's will work, but only if the monsters are smart:

##########
#W#D#P# #
##U#R#@# #
##########

Depending on permissiveness, T(D,@), or even T(W,@), but not T(R,@). Cutting down on possibilities, 4a is a model for T(D,@), but not for T(W,@).
4b is a model for both T(D,@) and T(W,@) (and any (10) similarly situated monsters, up to d(M,@) <= 20 spaces away.)

[PowerDiver]

Additional desiderata:

6. Shadows shall not be disconnected.

Before you start onto this, let me give a warning. To someone with knowledge of real analysis, disconnected may not mean what you think it means. Unfortunately, I have forgotten too much to say anything specific with any certainty.

I am not saying your (6) is necessarily inherently bad when you define connected the way that any normal person would. However, it is my suspicion that the intuitive definition will lead to strangenesses somewhere else. The mathematics on mappings from a euclidean space to a discrete space can be very very strange.

[Pete Mack]

Yes, I can already see that, because the diamond model is not symmetric. I don't see how to fix it, but that doesn't mean fixing it is impossible. I suspect that forcing symmetry with a permissive combination will solve things. (In that case, there's some maximum length for single-pillar shadows. An unpermissive combination would give weird conical shadows, even at a distance--all very well for the sun and the moon, but doesn't make sense if you consider, say, 1/4 grid size as the diffraction limit.)

[zaimoni]

Before you start onto this, let me give a warning. To someone with knowledge of real analysis, disconnected may not mean what you think it means. Unfortunately, I have forgotten too much to say anything specific with any certainty.

I am not saying your (6) is necessarily inherently bad when you define connected the way that any normal person would. However, it is my suspicion that the intuitive definition will lead to strangenesses somewhere else. The mathematics on mappings from a euclidean space to a discrete space can be very very strange.

It needs translation when going into higher mathematics. A simple translation would be "for any given shadowed square, there is another shadowed square with distance one under V's distance function". (After other terms are defined, of course.)

Any non-sophist mathematician reading Pete's description should immediately realize he's not using connected in the technical sense, and should have little problem working up the required translations.

[PowerDiver]

It needs translation when going into higher mathematics. A simple translation would be "for any given shadowed square, there is another shadowed square with distance one under V's distance function". (After other terms are defined, of course.)

I don't think that is enough. It is not enough to define a topology in the model from scratch. I think you need to look at the topology in the model induced by the topology you start with and the transformation you are using. I think to make a consistent model, you need to enforce that every image in the model of a connected set [in particular a line of sight] remains connected.

Since no one has defined a formal mapping from Euclidean space to any of the models, there is nothing specific to talk about. I don't want to argue about details anyway. I was just warning that things can be a lot more complicated than intuition suggests. What looks like a problem may just be the natural result of consistency when the underlying math is counterintuitive.

I agree that Pete's (6), as he intended it, is a desirable goal, but it may be hard to achieve.

[Pete Mack]

You know, when all is said and done, Angband's definition of projectable and visible, minus the "hockey stick", isn't all that bad... Surely it just needs some tweaking?

[PowerDiver]

You know, I have confused myself now. Why don't you all just laugh at me, and then we can move on and pretend I never said anything about Pete's request about shadows.

[PaulBlay]

You know, when all is said and done, Angband's definition of projectable and visible, minus the "hockey stick", isn't all that bad... Surely it just needs some tweaking?

Well how about two tweaks.

1. When a 'project' hits something part way to the targeted grid, check whether the grid hit would be targetable if that grid was the target. That would stop 'trick shots'.

2. Allow Zaiband style flexibility ('diagonal starts') to avoid hitting walls early when not necessary.

??o
?x#
#x#
@.#

You won't meet many of the 'desired features' but you would get rid of two things that bug me most about the present system.

[Nick]

You know, I have confused myself now. Why don't you all just laugh at me, and then we can move on and pretend I never said anything about Pete's request about shadows.

Hey, I've already been laughing at the entire thread. And the other one.

[Donald Jonker]

Hey, I've already been laughing at the entire thread. And the other one.

I presume you're also the one laughing at the piles of arrows that stack up around my feet every time it seems I should be able to hit something, but can't.

Been playing solid for over a year + half; that's a long time to still not have an intuitive grasp of the targeting system. I don't think I'm that obtuse. Single biggest thing holding the game back, IMO. And once it's done for V it really should be ported to the variants.

[PowerDiver]

[QUOTE=Marble Dice;21223]Do you no longer feel that DFOV would make LOS very obvious, especially with the highlighting feedback on visible tiles?[QUOTE]

Highlighting would solve issues about what you can target. However, aeneas mentioned a death due to not understanding LOS. Presumably that was about what can target you *after* you move, and I'm not sure how to make highlighting solve that problem.