Re: LOS problem

On Sep 6, 3:22 am, Nate <n...@xxxxxxxxxxxxxxx> wrote:
I want to be able to use my LOS code for targeting. The beam should
avoid walls if possible. However, the algorithm I am using does not
allow "beam cycling." These paths should both work (@ is the player,
a space is a wall, # is the target square, and * is the beam):

There are three different problems that you may be trying to solve
here. (1) Can creature a target creature b? (2) What is the route that
the projectile will take (for graphical display purposes)? (3) What
creatures in the middle might be affected (you miss and hit the orc)?

(1) can best be solved by shadowcasting or permissive field of view
(described below). (2) and (3) are solved differently depending on how
you want it to work. For instance, it may be best to arbitrarily
choose one of the potential paths (that is unobstructed), and display
that. And if you are implementing a beam spell, it might be best to
damage only those on that path. On the other hand, you may end up
wanting to implement complicated cover rules and then arbitrarily
picking a path is insufficient.

Unfortunately, Bresenham's algorithm is suited to none of these
questions. It is asymmetric, meaning that there will be cases where A
can target B, but not vice versa (actually, worse because usually this
will end up biasing *against* those who have cover). It only finds one
particular line. And it is slow if you want to do it to large groups
of destinations. Basically, Bresenham's algorithm is for drawing
approximations of lines, and it turns out that it doesn't really work
well for roguelike games in general. The more complicated methods I
describe below are *much* better in every way except for complexity.
And even then, the complexity is well hidden inside a library that is
already written.

Your best bet may be to use shadowcasting. Conceptually, in
shadowcasting you can target a square if you can draw an unobstructed
line from the center of the source to any point in the destination
square. The downsides are that it is more complicated that Bresenham's
algorithm, and retains some asymmetries and anomalies. But there is an
excellent library that supports it (libfov):

http://libfov.sourceforge.net/wiki/index.php/Main_Page

This library already has the ability to do (1), and possibly (2) and
(3) above (I'd have to check the api). While the library is chiefly
oriented to doing FoV to a whole range of other squares, it also has
LoS functions for a particular destination.

My personal preference is for permissive field of view:

http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

This is where a destination square is targettable if a line exists
from *any* point in the source square to *any* point in the
destination square. This is completely symmetric, which is a very
handy property. And it makes the creatures on the map more aware of
what is going on around them, for instance automatically peeking
around corners. The disadvantage is that it is even more complex than
shadowcasting. Fortunately, there are libraries for this as well.

My library is called permissive-fov and is for C/C++:

http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive-fov

There has been a port of it to Python as well:

http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View_in_Python

Currently there are only general FoV operations for it rather than
specific LoS to a square, though doing LoS to a specific square has
been solved in principle and will be in the next release. The next
release is currently scheduled to be 'when I get around to it', which
would be sooner if you expressed interest in it being done.

-D

.

Relevant Pages

  • Re: LOS problem
    ... Bresenham's algorithm is suited to none of these ... shadowcasting you can target a square if you can draw an unobstructed ... LoS functions for a particular destination. ... there are libraries for this as well. ...
    (rec.games.roguelike.development)
  • Limited Knowledge Nodular Pathfinding
    ... At the moment it projects two beams randomly almost towards the ultimate ... the ultimate destination for example, the ai will miss one of the openings. ... if you reach an unseen square, ...
    (rec.games.roguelike.development)
  • Re: Limited Knowledge Nodular Pathfinding
    ... At the moment it projects two beams randomly almost towards the ultimate ... the ultimate destination for example, the ai will miss one of the openings. ... if you reach an unseen square, ...
    (rec.games.roguelike.development)
  • Re: An algorithm challenge
    ... Maarten Wiltink wrote in message ... > could just as easily have a bunch of objects representing the network, ... >> adjacent squares of each square, then use a recursive algorithm to run ...
    (alt.comp.lang.borland-delphi)
  • Re: Precise Permissive Field of View in Python article on RogueBasin
    ... permissive-fov and assume the maintainenance myself with your ... adapted into a line-of-sight algorithm that only checks if one tile is ... You have a source square and a destination square. ... bounding box on the calculation. ...
    (rec.games.roguelike.development)
Loading