[lib] bresenham.lua - Draw lines on grids and calculate LOS

[kikito]

I needed a line tracer for the project I'm doing, and I could not find a generic one, so I've implemented one myself.

bresenham.lua implements Line Of Sight (LOS) and line drawing in a generic way. Here is its github repo:

https://github.com/kikito/bresenham.lua

Basically, if you have a map like this:

Code: Select all

########
#A     #
#      #
#   ####
#      #
#    G #
#      #
########

This library will tell you if there is a line between "A" and "G", in several ways.

Code: Select all

########
#A     #
# \    #
#  \####
#   \  #
#    G #
#      #
########

It only needs three things:

• The coordinates of the origin point (A)
• The coordinates of the "Goal" point (G)
• A function that takes two parameters (x,y) and returns true if the point at x,y is "passable" and false if it's "blocked"

Example:

Code: Select all

local bresenham = require 'bresenham'
...
local playerSeesEnemy = bresenham.los(player.x, player.y, enemy.x, enemy.y, function(x, y)
  return map[x][y] == " "
end)

Notice that the definition of "passable" might be very dynamic, even on the same game - A flying enemy considers crevasses as "passable", but a walking enemy might consider them "blocked". In a game with Bulletproof glass, the function that checks if the player "sees" an enemy is different from the function that calculates bullet shoots, because light can cross the glass, but bullets can't).

I'm sorry but I don't have time to make a pretty demo with graphics and everything. I hope this pitiful post gets the idea through. There is a bit more information on the library's README.

[MarekkPie]

Does this assume that the map must be equivalently-sized grids? Seems like also for any real-game scenario it would be O(n^2). How that compares to other options for line of sight, I don't know.

I think no one posted because you used Bresenham instead of One-Eyed Willie or Straight Shooter as the title.

[kikito]

Does this assume that the map must be equivalently-sized grids?

That is the most common scenario, although it is not "assumed". The only assumption is that the user wants a line whose coordinates are integers, not floats. It will not handle cases in which a body extends from 0.6 to 0.8, for example. In theory you could use it to draw/use pixels on the screen or a canvas, although in LÖVE that is not extremely fast.

Seems like also for any real-game scenario it would be O(n^2).

Well, that depends on the callback. The execution of bresenham is O(n), where n is related with the distance between x0,y0 and x1,y1.
If you do a brute-force callback, that checks all objects on each call, then yes, order will be O(n*m). Hopefully though your callback will be a bit more intelligent than that. If for example you limit your game to 1 entity per tile, it is O(n). In non-tile-based games, you could still use a spatial hash (like the one used by HardonCollider) and then do a "rough LOS phase" using the cells on the hash, only stopping to do a more detailed LOS check on the cells that are non-empty.

How that compares to other options for line of sight, I don't know.

It is efficient if you have some sort of underlying grid. It is also ok if you want to draw lines.

I think no one posted because you used Bresenham instead of One-Eyed Willie or Straight Shooter as the title.

Well, in this case I opted to use a searchable name. I was looking for bresenham algorithms and the ones I found were not very clean or generic. Hopefully this will help other people in the future.

[bartoleo]

one of my old projects
Porting of Field of Vision MRPAS + LoS + A*Star : viewtopic.php?f=5&t=1797

[kikito]

Yes, thanks for reminding me. I'm still thinking about wether I will need FOV on this project, but if I do, I will give yours a look.

[SiENcE]

Sorry for bumping up an old thread.

When i use this library, is it possible to not take the point i'm pointing from (the first point location) into account for the endresult?

[kikito]

Of course. Just ignore it in the function.

Code: Select all

local A = bresenham.los(2,2,6,6, function(x,y)
  if x == 2 and y == 2 then return true end
  -- else do something with x and y
end)

[SiENcE]

Oh ... yes it's so easy.

But I have to give it a true to ignore it.

Code: Select all

if x == x0 and y == y0 then return true end

Thanks! I like your libs.

[kikito]

Yes, I forgot to write the "true"

BTW, if you are doing line-of-sight computation, I recommend giving a look at the grid traveral algorithm used by bump. It will work better with things like visibility near corners etc. You can see a demo here:

viewtopic.php?f=4&t=77085&start=10#p168727

[SiENcE]

Thanks for this suggestion, i will take a look at.

So far your lib works quite good for my problem. I'm doing positional sound for my game. I got my sound matrix working but than i realized, that i can hear sounds behind a wall (sound emitter is on the other side of the wall).
The love2d documentation about sound sources is very very limited and I couldn't find good openal tutorials that go beyond the basics (The love2d wiki misses even the most important things like min max values or cartesian coordinate system).

I thought Openal has solutions for sound blocking objects...but I found nothing.

Now I use this lib to calc the visibility from emitter to listener.