Bresenham FOV - Precision math in Java

[eyenot]

I implemented Bresenham in Java but There's a problem, spaces (wall tiles) on either side of a narrow passage a certain number of steps away from the character in every cardinal direction, are not getting lit. Spaces closer to and further from the character are lit down the same passage, so it stands out as obviously "wrong".

I think maybe some precision was lost or something. Here's the code:


public void bresenham(int aX, int aY, int bX, int bY) {
// (called numerous times to light up spaces between the character and
// all points along the perimeter of the visible viewport)

boolean steep = ( Math.abs(bY-aY) > Math.abs(bX-aX) );
if(steep) {
// uses the classical binary XOR swap algorithm to swap two values

aX ^= aY;
aY ^= aX;
aX ^= aY;

bX ^= bY;
bY ^= bX;
bX ^= bY;
}

int deltaX = bX - aX;
int deltaY = bY - aY;

int offsetX = (deltaX > 0) ? 1 : -1;
int offsetY = (deltaY > 0) ? 1 : -1;

double error = 0;

if( deltaX == 0) {
int y;
for (y = aY; (offsetY*y) <= (offsetY*bY); y += offsetY) {
boolean result = steep ? plot (y, aX) : plot (aX, y);
if (!result) return;
}
} else {
double deltaError = (double) deltaY / (double) deltaX;
int x;
int y = aY;
for (x = aX; (offsetX*x) <= (offsetX*bX); x += offsetX) {
boolean result = steep ? plot(y,x) : plot(x,y);
if(!result) return;
error += Math.abs(deltaError);
if( error > 0.5 ) {
y += offsetY;
error -= 1.0;
}
}
}
}

[Krice]

On 20 huhti, 01:07, eyenot <eye...@gmail.com> wrote:
> I implemented Bresenham in Java but There's a problem, spaces (wall tiles) on either side of a narrow passage a certain number of steps away from the character in every cardinal direction, are not getting lit. Spaces closer to and further from the character are lit

The angle is so small that the ray will stop in earlier tiles.
It's a classic problem with line drawing fov.

[eyenot]

So it's not something that can be improved with more precise math functions?

[Krice]

On 23 huhti, 22:45, eyenot <eye...@gmail.com> wrote:
> So it's not something that can be improved with more precise math functions?

It might be possible, but I don't know how. I think some have
solved it by transforming the tile map data itself to higher
precision and then downscaling it back to fov map. It can be
somewhat slower than using imperfect routine first and then
fixing problem areas with special routine.

[Kusigrosz]

The Bresenham line algorithm doesn't require floating-point operations;
an exact integer version exists. IIRC there is a pseudocode example on
Wikipedia.

I think the artifacts you observe may be the result of the way the
algorithm is used to compute FOV, not the precision of the algorithm
itself.

--
To send mail, remove 'AU' from the address
You see here a scroll labeled "DESUeIkNQvM"

[Krice]

On 24 huhti, 11:28, Kusigrosz <Kusigr...@AUtorun.itvk.pl> wrote:
> I think the artifacts you observe may be the result of the way the
> algorithm is used to compute FOV, not the precision of the algorithm
> itself.

How would you use it? Because if there is a long narrow corridor
then the precision of the map is not good enough to lit all tiles.
None of the rays reach the unlit tile even it should be visible.

[Martin Read]

Krice <pau...@mbnet.fi> wrote:
>How would you use it? Because if there is a long narrow corridor
>then the precision of the map is not good enough to lit all tiles.
>None of the rays reach the unlit tile even it should be visible.

Y---*---*---*---*---*---*---*
| | | | | | | |
| A | | | | | | |
| | | | | | | |
########################X####
#############################
##########################B##
#############################
#############################

To compute the visibility of the tile containing B with a direct
Bresenham raycasting approach, calculate a line from A (the centre
of the visibility source's tile) to X (the "near corner" of the
target tile), not B (the centre of the target tile).
--
\_\/_/ turbulence is certainty turbulence is friction between you and me
\ / every time we try to impose order we create chaos
\/ -- Killing Joke, "Mathematics of Chaos"

[Martin Read]

Martin Read <mpr...@chiark.greenend.org.uk> wrote:
>To compute the visibility of the tile containing B with a direct
>Bresenham raycasting approach, calculate a line from A (the centre
>of the visibility source's tile) to X (the "near corner" of the
>target tile), not B (the centre of the target tile).

Addendum: Both lines require exactly the same degree of precision.

[Krice]

On 25 huhti, 21:25, Martin Read <mpr...@chiark.greenend.org.uk> wrote:
> To compute the visibility of the tile containing B with a direct
> Bresenham raycasting approach, calculate a line from A (the centre
> of the visibility source's tile) to X (the "near corner" of the
> target tile), not B (the centre of the target tile).

Didn't get any of that. There are no corners in tiles in simple
2D map typically used in roguelikes.

[Gerry Quinn]

In article <1cddb561-0506-4572-b2fd-3aaee721f632
@t16g2000yqt.googlegroups.com>, pau...@mbnet.fi says...

It's simply a modelling choice. There are no tiles either, after all,
just data.

If your data is considered to be representing square tiles, the
implication is that you can model corners if you want to. For example,
if you don't like the aesthetics of the FOV results from calculating
visibility only from centre to centre.

- Gerry Quinn

[Krice]

On 1 touko, 15:06, Gerry Quinn <gerr...@gmail.com> wrote:
> It's simply a modelling choice.

I'm curious to know how that actually works. Didn't quite get
it from that explanation.

[numeron...@gmail.com]

You can access finer angles and fix the above mentioned artefacts in raycasting by calcualting your FOV out to a wider range (like x2), but stopping if you reach the edge actaul desired FOV.

-Numeron

[Gerry Quinn]

In article <6714c706-1f50-41a5-96a7-21abb0d6e011
@m7g2000vbg.googlegroups.com>, pau...@mbnet.fi says...

I guess there are different ways. In Lair of the Demon Ape I treated it
as there being a lantern in the centre of the square of the player
character. Any wall square casts a shadow as if it were a solid opaque
square. The shadow is calculated by drawing a line from the lanterb to
each corner of the wall square. Any square whose centre is in shadow in
not in FOV.

Obviously in the interests of efficiency I do the calcularion in
concentric squares outward from the centre.

I added a subsidiary darker FOV for squares that are beside a square
that is in FOV. You can see a monster on these but not target it, and
they are drawn a little darker.

Overall I think this FOV model looks well.

- Gerry Quinn