Ah, that's interesting! As I say, I heard Bressenham wasn't necessarily the best for this, but don't know if there's any received wisdom other than that. (I don't know what, eg. rougelike games do. I did find someone who'd made their own rules for line-of-sight on a hex, but that included facing.)
I automatically assumed that there should be no hidden information in the sort of game I imagined, that what happens shouldn't depend on which way round the map is, or which order the objects are instantiated. I think most existing games, even really good ones, mostly gloss over this: if you're tracing the path of zombies to hero, it doesn't really matter what configuration the rear zombies end up in if they're obstructed.
When I'm dealing with zombies with two choices of which way to move, or a choice of which of two zombies to move into a particular square, when it really does have to be one or the other, I thought choosing clockwise/anticlockwise consistently was the best choice.
For line of sight, I think (but am not sure) that the algorithm gives a consistent choice of the spacing of the vertical steps, other than for the =/>= question when the diagonal passes through the centre of a side.
There's also the question of corners like
A . and A # and A #
# B . B # B
For a line, the diagonal is ok, but for line-of-sight you probably need at least one of the diagonal squares to be empty.
In both cases you're faced with a square on either side of the line, and do you need either or both? One solution is to require both. If you're always traversing the line the same direction, you can choose always the clockwise or anticlockwise side of the line.
My suggestion was to keep a running tally of both sides, and mark the line-of-sight valid if EITHER all the >= squares OR all the > squares are clear.
Simon improved that by saying it should be able to switch over, eg.
A # .
. . B . .
. # C # .
. . D
A would be able to see B (DOWN) and C (DOWN, UP) but not D (DOWN, UP, DOWN). He hypothesised that this would be equivalent to saying "Suppose each square is full, and you're looking from a small circle size epsilon in the centre of one square to a small circle of size epsilon in the centre of the other square. Is there an unblocked line." (It's a little different for hexes because of the jutty corners, but I think ok.)
This seemed to fit my intuition of what ought to be possible, though I haven't stress-tested the idea yet.
FWIW, I think DND miniatures say if you can trace a LoS from any corner of A to any corner of B, but I don't remember how that deals with corners.
It sounds like that might be applicable to your question too. Did you conclude anything at the time?
no subject
Date: 2008-09-20 01:37 pm (UTC)I automatically assumed that there should be no hidden information in the sort of game I imagined, that what happens shouldn't depend on which way round the map is, or which order the objects are instantiated. I think most existing games, even really good ones, mostly gloss over this: if you're tracing the path of zombies to hero, it doesn't really matter what configuration the rear zombies end up in if they're obstructed.
When I'm dealing with zombies with two choices of which way to move, or a choice of which of two zombies to move into a particular square, when it really does have to be one or the other, I thought choosing clockwise/anticlockwise consistently was the best choice.
For line of sight, I think (but am not sure) that the algorithm gives a consistent choice of the spacing of the vertical steps, other than for the =/>= question when the diagonal passes through the centre of a side.
There's also the question of corners like For a line, the diagonal is ok, but for line-of-sight you probably need at least one of the diagonal squares to be empty.
In both cases you're faced with a square on either side of the line, and do you need either or both? One solution is to require both. If you're always traversing the line the same direction, you can choose always the clockwise or anticlockwise side of the line.
My suggestion was to keep a running tally of both sides, and mark the line-of-sight valid if EITHER all the >= squares OR all the > squares are clear.
Simon improved that by saying it should be able to switch over, eg.
A # . . . B . . . # C # . . . DA would be able to see B (DOWN) and C (DOWN, UP) but not D (DOWN, UP, DOWN). He hypothesised that this would be equivalent to saying "Suppose each square is full, and you're looking from a small circle size epsilon in the centre of one square to a small circle of size epsilon in the centre of the other square. Is there an unblocked line." (It's a little different for hexes because of the jutty corners, but I think ok.)This seemed to fit my intuition of what ought to be possible, though I haven't stress-tested the idea yet.
FWIW, I think DND miniatures say if you can trace a LoS from any corner of A to any corner of B, but I don't remember how that deals with corners.
It sounds like that might be applicable to your question too. Did you conclude anything at the time?