bresenham like LOS algorithm that works with corners?

[veethree]

So i'm playing around with an idea for a puzzle platformer where you can place a certain amount of tiles on each level to complete it (you have to get from point a to point b and maybe collect some shit before doing that). And i dont want the player to be able to place tiles when there are tiles between the player and wherever he is trying to place the tiles. My first idea was bresenham.lua by kikito. And it kinda works, But shortly after implementing it i was reminded that if you check for a line of sight with it, it sees right through something like this:
(Picture cause i forgot how to use words)

green square = player
red outline = players grid position
gray outlines = What bresenham sees
yellow square = tile the player placed

And that's not what i want. So i'm wondering if there's perhaps a way to modify bresenham to not do that, Or a different algorhithm perhaps.

.love controls:
WASD or arrow keys to move and jump
LMB = Place tile
RMB = Remove tile (only works on tiles you placed, and that is intended.)

Note that this is an early prototype. Also for some reason the .love crashed löve for me, Works fine when i just drag the folder to love.exe. Let me know if the same happens to you and i'll just post a .zip or something if necessary.
EDIT: Just tested the .love on my mac, Crashed there as well. You may have to extract the source to run it. Not sure what i did wrong here...

[markgo]

First find out which quadrant your LOS is. Let's say that you're in the first quadrant with a counterclockwise orientation:

Code: Select all

2|1
----
3|4

The first quadrant has this case where # is a solid:

Code: Select all

.#
.?#
@..

You (@) want your LOS to stop at ? and go no further. To do this, add an additional check for each cell if the top and right neighbors are solid. If they are, then you can't see inbetween them, and quit the LOS. For the other quadrants, transform the coordinates in the first quadrant to the respective one. This way, you can make a loop which handles all case with a transformation.

[kikito]

The typical bresenham algorithm is good for drawing pretty lines, but it's not "exhaustive"; definitively it's not a good choce for line of sight.

There's a bresenham supercover algorithm made by Roland Yonaba right here: https://github.com/Yonaba/Algorithm-Imp ... rcover.lua

I have not used it yet, but definitively this kind of algorithm is more appropiate for line-of-sight and path finding stuff.

[micha]

I thought about the super-cover idea, too.

But what does it do on perfectly diagonal lines between cell centers? Does it give the same result as the original Bresenham algorithm or does it make a "buffer" around the line?

[kikito]

I have not tried the algorithm, but in my mind, for a "perfectly diagonal" line the supercover should cover "the diagonal + 1 tile-border around the cells in the diagonal". So here's bresenham vs bresenham-supercover on a perfect diagonal:

Code: Select all

                     x                        xx
                    x                        xxx
                   x      +---------->      xxx
                  x                        xxx
                 x                         xx

[micha]

I'd count both solution as possibly correct, depending on the problem formulation. The question is, if cells are considered as closed intervals or open intervals. Veethree, you seem to consider them as closed intervals, because two diagonally adjecent cells touch each other. I will try and see, what the super-cover version of the algorithm really does. Now I am curious.

[Roland_Yonaba]

I have not tried the algorithm, but in my mind, for a "perfectly diagonal" line the supercover should cover "the diagonal + 1 tile-border around the cells in the diagonal"

Exactly.

@Kikito: By the way, would you be okay for a pull request to bresenham.lua providing support for supercover LOS ?

[micha]

Thank you, guys.

[kikito]

@Kikito: By the way, would you be okay for a pull request to bresenham.lua providing support for supercover LOS ?

By all means. Do you think you can remove some code duplication? In particular, this conditional? I know the original algorithm has the code duplicated, but that's because they pursue the total maximum efficiency possible in C (I actually asked the guy).

[Roland_Yonaba]

By all means. Do you think you can remove some code duplication? In particular, this conditional? I know the original algorithm has the code duplicated, but that's because they pursue the total maximum efficiency possible in C (I actually asked the guy).

Hmm. Not sure, but I'll take a closer look to that.