targetting and LOS

[etaomyx]

According to the program I wrote (which had a bug that I just fixed, and probably has more) there are no disconnected visible squares:

xx####
xx?x.#
xx.!.#
xx#..#
##...#
#@...#
######

Hmm, so we differ on the tile I marked ?. But the slope of the line between the centers of @, ? is 16 / 4 = 4 / 1. And the slope of the line connecting @ with the lower-right-hand corner of the wall directly above @ is 3 / 1. So any tiles with a steeper slope than 3 / 1 should be obscured. Surely that means ? is not visible?

EDIT: Oops, we also differ on !. But the slope to ! is 3 / 2, which should be blocked by the wall two square up, one square right, which obscures tiles between 9 / 3 and 7 / 5?

[d_m]

Here's the diagram again:

xx####
xx?x.#
xx.!.#
xx#..#
##...#
#@...#
######

As I understand it, based on Eddie's description, the wall tile just north of @ only extends halfway (just to the center point and not beyond); thus, any squares east of straight-north will not be blocked by it. Since the north-east column is a single point with no area, it will only block squares along an exact slope (the x between ? and !).

Thus, since ! is no on the direct line between @ and the column, it is visible. And since the ? is east of the northern wall, and not on the exact diagonal of the column, it too is visible.

To be clear: this is not the suggestion to make each tile into a 4x4 grid and use the middle. Rather, it splits each tile into a 2x2 grid, and each of those grids is only filled if there is another contiguous wall. Thus in many cases a LOS can only be blocked if there are two walls present. E.g.:

+-----+
|@#xxx|
|.....|
|.....|
+-----+

+-----+
|@....|
|.#...|
|..x..|
+-----+

+-----+
|@#xxx|
|.#xxx|
|..xxx|
+-----+

P.S. Inevitably I found another bug. Newest version attached. At least no one on this board will ever mistake me for competent

[buzzkill]

[QUOTE=PaulBlay;20794]

The suggested changes would make the following situation *not* LOS.

######################M
@

Frankly I think targetable / LOS at that distance is just greedy. ;-)

I agree. There are always plenty of suggestions on how to make the game easier, making it a little harder just this once won't hurt that much.

[etaomyx]

To be clear: this is not the suggestion to make each tile into a 4x4 grid and use the middle. Rather, it splits each tile into a 2x2 grid, and each of those grids is only filled if there is another contiguous wall.

Ah I see, my example referred to a 4x4 grid system, sorry for not be more specific. I had thought the 2x2 system had been abandoned already; as you say, it suffers from potentially discontinuous shadows.

EDIT: Rats, my mistake.

[d_m]

But it's easy enough to manufacture an example of discontinuous sight in the 2x2 system as well:

Well, you're right about there being a discontinuity, although it's a different one than you marked--a contiguous group of 3 squares:

+----------+
|######xxxx|
|#....#xxxx|
|#....#xxxx|
|#....#...#|
|#@.#xxxxxx|
|####xxxxxx|
+----------+

I'm still not ready to give up 2x2; I don't find this discontinuity troubling (and imagine that the 4x4 system will also have similar cases). I guess we'll see what happens.

[Atanvarno]

To sum up, "wouldn't it be nice if"

* What you see is what you can hit with a spell (and vice versa).
* What you see can also see you (and vice versa).
* Standing directly next to a pillar should produce an expanding shadow.
* Reasonably fast code can be produced to implement the FOV, etc.
* No 'trick shots' required (or possible) to hit monsters that you can't target directly.

Is everyone agreed on the above (if they are possible)?

How does the current system specifically differ from the above?

Are any of those points not possible?

I will refer to these five points as (1)-(5). I will not say anything about (4).

I think it is important to decide what should happen, when A shoots an arrow at B and there might be monsters or walls in between. I see at least to different options:

(a) There are one or two natural paths from A to B (given by Bresenham's algorithm). If one of these is free, then the arrow hits B. If both are blocked, then one is selected and the arrow hits the first obstacle on this path.

In this system (5) is impossible. If we require (1), then we get a FOV satisfying (2) and (3), but it is very restricted and does not look very good. If we only want (2) and (3), then there are probably many possibilities.

We could get (5) by a hack: if the arrow (or spell) would hit something that could not be hit directly, then it will not hit, but it will drop on the floor (or the spell will do nothing). This would cause beam spells to have "holes".

(b) Calculate FOV for A treating monsters as walls. If B is visible, then the arrow hits B. Otherwise it hits something in between A and B.

FOV and "something in between" can be defined so that (1) and (5) are satisfied. If we also require (2), then we can't get (3). This leads to a very permissive FOV, and again there are small issues with beam spells.

[PowerDiver]

[QUOTE=PaulBlay;20794]

The suggested changes would make the following situation *not* LOS.

######################M
@

Frankly I think targetable / LOS at that distance is just greedy. ;-)

So you don't think you should be able to see the outline of a large lit room when you enter it adjacent to a wall?

This is a key question. If the M horizontally next to a # has an expanding cone of shadow, it cannot see the @. By symmetry, the @ cannot see all of the walls of the room. There is no way around this without changing one of those properties.

[Pete Mack]

[QUOTE=PowerDiver;20869]

So you don't think you should be able to see the outline of a large lit room when you enter it adjacent to a wall?

This is a key question. If the M horizontally next to a # has an expanding cone of shadow, it cannot see the @. By symmetry, the @ cannot see all of the walls of the room. There is no way around this without changing one of those properties.

Eddie, this doesn't make sense. Walls will always fill an arctangent-1 of LOS, because their surface is a straight line. The issue is whether the monster is (almost) flush with the surface. If he fills some fraction of the square, there will be some distance beyond which you will be mutually out of LOS.

[PowerDiver]

[QUOTE=Pete Mack;20870]

Eddie, this doesn't make sense. Walls will always fill an arctangent-1 of LOS, because their surface is a straight line. The issue is whether the monster is (almost) flush with the surface. If he fills some fraction of the square, there will be some distance beyond which you will be mutually out of LOS.

You have to start with the assumption that a monster in a square is at least as far forward as "flush with the surface" or you screw up the gameplay. Basically, if the monster or player doesn't want to be targeted he needs to take another step back.

I made that explicit with my initial description that walls extend half-way and the monsters are at the center, but taking up the center 4 of 16 sub-squares works too. IMO anything that changes this will turn out, after due consideration, to be broken in some way. In that diagram, you really don't want the M to be targetable if it is a death drake in a wall [that breathed at you last turn], but not targetable if it is a death drake in an empty square.

[buzzkill]

Given that each grid contains a 5x5 sub grid, instead of the previously discussed 4x4... (asterisks represent blank space)

*****   < player    *****   < horizontal     *###*   < corner
*@@@*               #####     wall           *###*
*@@@*               #####                    ####*
*@@@*               #####                    ####*
*****               *****                    *****

I think that PD's suggestion would work well, and could lead to some other interesting changes such as monsters of varying size, the larger ones being easier to see and therefore target.

tiny      medium    man       giant     massive
*****     *****     *****     *@@@*     @@@@@
*****     **@**     *@@@*     @@@@@     @@@@@
**@**     *@@@*     *@@@*     @@@@@     @@@@@
*****     **@**     *@@@*     @@@@@     @@@@@
*****     *****     *****     *@@@*     @@@@@

You would just have to target from the center of the attacker to any exposed area of the target. This would easily preserve the hockey stick in man vs. man combat. (just ignore the different sizes if that's too off topic)

EDIT: According to my calculations, a standard 1x2 hockey stick would work both ways.
a 1x3 hockey stick would be a border-line LOS situation for the person standing nearest to the corner. The other would have a clean shot.
a 1x4 hockey stick would yield no LOS for the one nearest the corner, and yet still a clean shot for the other.
I'm not really liking my own idea anymore.
All 'calculations' preformed visually, not mathematically, so my 'numbers' may be a little off.

[Pete Mack]

Aha, now that makes sense.

[jv123]

PD's suggestion here is excellent. But if we're doing something like this, then there's no need for walls (or monsters, or whatever) to only take up some internal part of each grid square!

The ONLY reason this was suggested was to get around the problem that, based on the OP's suggestion, single pillars would cast no shadow at all. But if we base our new visibility mechanism on PD's idea, this wouldn't happen.

So, here's how the approach would work. Wall segments, and all monsters and items, 'take up' their entire grid square --- there's none of this subdivision stuff. To check whether @ can see an M, we just ask this simple question: if we choose a point at random in @'s grid square, and a point at random in the M's grid square, what's the probability that we can draw a straight line between them, unobstructed by walls? If this probability is greater than some fixed percentage --- I suppose 50% makes sense --- then we say that the @ can see the M.

It's as easy as that! This is simple to explain, and intuitive. Of course, the difficulty is coming up with a good algorithm for calculating the answer quickly --- but that just needs some clever maths, and I'm sure one of us could work that out. We can also use this visibility percentage to modify the chance for ranged attacks to be successful, lower visibility percentages making a successful hit less likely, in the way someone suggested earlier in this thread.

We could always simplify this procedure, at which point it starts looking much more similar to PD's original idea. For example, we could check just 16 distinct lines:

• from the bottom-left corner of the @'s square to the bottom-left corner of the M's square;
• from the bottom-right corner of the @'s square to the bottom-left corner of the M's square;
• from the top-left corner of the @'s square to the bottom-left corner of the M's square;
• from the top-right corner of the @'s square to the bottom-left corner of the M's square;
• from the bottom-left corner of the @'s square to the bottom-right corner of the M's square;

...

• and from the top-right corner of the @'s square to the top-right corner of the M's square.

If more than 8 of these 16 lines are unblocked by walls, we could then say that the @ and the M have line-of-sight. I've attached a picture of the shadow that this produces behind a single pillar, the orange square. The lightness of the other squares is given by proportion of the square that's visible from the @, calculated using the 16-line method.

[PowerDiver]

All of this talk of subgrids makes me think people are missing the perspective of what is hopefully going to get coded in a not interminable timeframe.

The level of granularity is *ONE* grid. That's it. Finer granularities with monsters taking up multiple squares may happen in the distant future, but I sure won't offer to code it.

In the current framework, there are one or two atomic operations. Is square A visible from square B? Is square A targetable from square B? All the talk of subgrids is just about how to implement the primitives, and is not particularly relevant. The only thing that really matters is that the primitives lead to good gameplay.

I think the two primitives should be the same and symmetric, but I suppose that hasn't been conclusively decided. IMO a death drake in a wall that you can see can breathe on you if any death drake in any wall can breathe out of it. I don't see any way to reconcile that with LOS != targetable. In addition, gameplay appears to me to be much better with LOS == targetable.

I see a lot of the discussion as being a cry for finer granularity. IMO it doesn't belong in this thread, which should be about what should be done with the current level of granularity.

[Pete Mack]

That makes sense. And having considered it, I would like to solve the gordian knot as follows: a death drake in a wall far away should not be visible. If he is, then he's basically got the same LOS hack against @ that @ currently has against corporeal monsters with the hockey stick. As you say: it doesn't have to make physical sense, it just has to be good for game play.

I return to my previous position with the caveat that non-corporeal (PASS_WALL) monsters won't be visible unless ordinary monsters (entering a room) would be visible.

EDIT: on the other hand, this whole idea that LOS = targetable means that ESP will be that much more valuable. I'm not sure that this is a good thing...

[zaimoni]

I think we're all getting a little confused / off track here.

To sum up, "wouldn't it be nice if"

* What you see is what you can hit with a spell (and vice versa).
* What you see can also see you (and vice versa).
* Standing directly next to a pillar should produce an expanding shadow.
* Reasonably fast code can be produced to implement the FOV, etc.
* No 'trick shots' required (or possible) to hit monsters that you can't target directly.

Is everyone agreed on the above (if they are possible)?

Zaiband implements points 1,3,4,5. [Point 5 is "the projection algorithm is smart enough to calculate the trick shots for you and the monsters."] Point 2 is the "nobody can ambush worth anything" property; as such, I find it bad for gameplay.

How does the current system specifically differ from the above?

V implements: 3. It fails all of 1,2,5 (it is possible to have a visible monster that cannot be hit even with positional targeting). The current LOS algorithm is fast for the player alone, but will bog down on slower machines if forced to calculate for each and every square (that's why monsters don't use the LOS algorithm); I consider this to fail 4, but this could be debated.

Are any of those points not possible?

The main reason 2 is not trivially fixable in V, is that V implements LOS with a player-centric bitmapped cache that has pretty much nothing to do with projectability, and everything to do with eliminating visual weirdnesses. If LOS is defined in terms of targetability (e.g. Zaiband), then making 2 work is simply running two LOS checks and then picking one of logical-and or logical-or (logical-or is a lot more visually pleasing).