Line Of Sight

by DarkCampainger
Determine if two atoms have a clear line of sight between them

About Line Of Sight

ID:929473
 
Aug 12 2012, 10:00 pm
In the above pictures, the black squares are mobs, the dark grey tiles are opaque walls, and the red areas represent the mobs' field of vision based on line-of-sight calculations. Blue areas represent overlap.


/* *********************************************************************

 .__    .__                       ____    _______.__       .__     __
 |  |   |__| ___   ____     _____/ ___\  /   ___/|__| ____ |  |___/  |_
 |  |   |  |/   \_/ __ \   /  _ \   _\   \___  \ |  |/ ___\|  |  \   __\
 |  |___|  |  |  \  ___/  (  <_> )  |    /      \|  / /_/  >   Y  \  |
 |_____ \__|__|  /\___  >  \____/|__|   /_____  /|__\___  /|___|  /__|
       \/      \/     \/                      \/   /_____/      \/

                Created by David "DarkCampainger" Braun

            Released under the Unlicense (see _Unlicense.dm)

                   Version 1.3 - September 25, 2012

            Please see 'Demo/Demo.dm' for the example usage
 
*///////////////////////////////////////////////////////////////////////


## Summary
#######################

"'  This library includes a InLineOfSight() process which allows you to
"'      to determine if two atoms have a clear line of sight between one
"'      another. It works by casting a line between the objects and
"'      searching along it for opaque tiles.
"'
"'  It's important to note that although the start and end points of the
"'      line consider the pixel-based center of each object, the actual
"'      search for opaque objects only considers full tiles.
"'
"'  The library also integrates range and field-of-view limitations to
"'      create more realistic sight lines.
"'

## Reference
#######################

/LineOfSight (/datum)

"'   This is the container type for the library. All global procs and
"'     vars are defined under it. You can access an instance of it via 
"'     the global variable [LOS], for example: [LOS.InLineOfSight(...)]
"'
//   Variables:
"'
::      iconSizeWidth (number)
::      iconSizeHeight (number)
"'         The width and height of each tile as parsed from the 
"'           world's icon_size variable
"'
//   Procedures:
"'
::      inLineOfSight(atom/source, atom/target, \
::                    sourceCenterX=null, sourceCenterY=null, \
::                    targetCenterX=null, targetCenterY=null, \
::                    parameter="opacity", checkContents=FALSE, \
::                    range=null, fov=null, fovX=null, fovY=null, \
::                    fovCos=null)
"'
"[         source:        atom to calculate sight-line for (required)
"[         target:        atom to test against (required)
"'
"[         sourceCenterX, Manually specify centers of atoms in pixels,
"[         sourceCenterY, as offsets from the bottom-left corner.
"[         targetCenterX, Do NOT include step_x/y in this value.
"[         targetCenterY: Example values for 32x32 icons:
"[                            Bottom-left: (0,0)
"[                            Top-right: (32,32)
"[                            Center: (16,16)
"[                        
"[                        If not specified, the centers will be 
"[                        determined from the bounding boxes.
"'
"[         parameter:     Manually specify variable to test if line of 
"[                        sight penetrates a tile. Default is "opacity".
"[                        Must be a variable that all turfs have. If
"[                        'checkContents' is true, must also be a
"[                        variable that all atoms have.
"'
"[         checkContents: Set to true value to also check the contents
"[                        of each turf along the line for atoms that
"[                        may block it. Defaults to false, which means
"[                        only the turfs parameter is checked. Note
"[                        that even if this is true, contents are
"[                        treated as affecting the whole tile and their
"[                        step offsets and bounds are not considered.
"'
"[         range:         Restrict the sight to a max range in pixels.
"'
"[         fov:           Limits the distance that the target can
"[                        be from the source sight vector, as it is
"[                        specified by the fovX and fovY arguments.
"[                        Note that this is half the size of the total
"[                        viewing arc, so to be able to see in 180
"[                        degrees, fov should be set to 90.
"'
"[         fovCos:        As an optimization, you can precompute the 
"[                        cosine of the desired FOV and pass it via
"[                        this argument instead of the 'fov' argument.
"'
"[         fovX / fovY:   Specifies the direction of the source atom
"[                        sight vector for FOV. If both fovX and
"[                        fovY are null, it defaults to the source
"[                        dir. If fovX is set and fovY is null, fovX
"[                        is expected to be a directional flag
"[                        (NORTH, SOUTH, ect). If both fovX and fovY
"[                        are set, they are expected to define a
"[                        vector (does not need to be normalized)
"'
"[         Returns:       True if there is a clear line of sight from
"[                        the source to the target. False otherwise.
"'
"'         This process returns whether or not one atom has a clear
"'           line of sight to another, optionally taking into account
"'           the atom's field-of-view and vision range.
"'
::      getCenterPixelX(atom/A, includeStep=FALSE)
::      getCenterPixelY(atom/A, includeStep=FALSE)
"'
"[         A:             The atom to calculate the center of
"'
"[         includeStep:   Whether to include step_x/y in the result
"'
"[         Returns:       The relative pixel offset of the center of
"[                        the atom. For a 32x32 icon_size, the center
"[                        will be (16,16) for a full bounding box.
"'
"'         This utility process determines the relative pixel center
"'           of an atom, taking into account its bounding box.
"'
::      getAbsoluteTileX(atom/A, customCenterX=null)
::      getAbsoluteTileY(atom/A, customCenterY=null)
"'
"[         A:             The atom to calculate the absolute center of
"'
"[         customCenterX, Pass the center of the atom, instead of
"[         customCenterY: calculating it based on the bounding box
"'
"[         Returns:       The relative pixel offset of the center of
"[                        the atom. For a 32x32 icon_size, the center
"[                        will be (16,16) for a full bounding box.
"'
"'         This utility process determines the absolute tile position of
"'           of an atom's center, taking into account its bounding box.
"'

## Version History
#######################

Version 1.3 / September 25, 2012

    Library is now released under the Unlicense
    Library data organized under /LineOfSight parent type
    Added getCenterPixelX/Y() and getAbsoluteTileX/Y() utilities
    InLineOfSight() has been renamed inLineOfSight()
    inLineOfSight() now has fovCos argument 
    Fixed bug with fovY argument
    Fixed bug with targetCenterX/Y arguments
    Optimized FOV calculation (Thanks Lummox JR!)
    Shortened and reformatted documentation
    Improved demo

Version 1.2 / September 20, 2012

    Added field of view and range constraints
    Improved accuracy and handling of floating-point error
    Adjusted demo so that the intended usage is more clear

Version 1.1 / August 13, 2012

    Improved handling of opaque source and target tiles

Version 1.0 / August 13, 2012

    Initial Release
Aug 13 2012, 7:31 pm
I haven't even downloaded it yet, but I must say - you are amazing.
Aug 13 2012, 7:35 pm
Thanks. I'm not sure I've earned such a compliment yet, but I'm glad you think this might be useful to you :)
Aug 13 2012, 8:50 pm
This makes me want to make a metal gear solid game(sneaking game)
Aug 14 2012, 11:08 pm
This was really cool. I had an idea however that it might be more useful if it established what the front of the mob was (Assuming this would be used for a mob that was human and had eyes) Because this doesn't really show a line of sight it shows a circle of sight. Essentially showing a 360 degree view of what the mob could be looking at if it could see in all directions. But in reality a normal person would only be able to see in front of them and in most instances where this would be used (Like say a stealth game for for NPC AI) the only important parts of the line of sight would be what the mob can visibly see logistically.
Aug 15 2012, 6:22 am
In response to Moussiffer
It's just a demo. You can still use the library to do exactly what you want, because the proc itself doesn't look at a "circle of sight", but a line between two points.

For example, you could modify the demo to check the angle_diff between the mob's dir2angle and atan2 between the mob and markers' positions. That's just my ProcLib way of doing it, but knowing DarkCampainger, there's probably a more simplified, efficient trig way to do it.
Aug 15 2012, 8:31 am
Like Kaiochao said, the library just provides a process to test a line of sight between two points. The demo happens to use the process to test against every pixel within a certain radius, but only because I felt it better illustrated the areas it sees as "within" and "outside" of the line of sight.

Typically you would start with a call to range(), a cone() process, or something similar and then use InLineOfSight() on the remaining targets. However, I can see a use for an InFieldOfView() process that also limits it by direction.

@Kaiochao: Yes, I have a little trick involving vector dot-products that makes the check very simple and cheap ;)
Aug 15 2012, 2:21 pm
Very useful! Thanks a ton, DC, nice work.
Aug 18 2012, 5:42 pm
Oh shit, this is cool as fuck. Nice job.
Sep 16 2012, 4:27 am
can somebody edit this so the area around is dark and the line of sight is the only seeable thing?
Sep 16 2012, 8:09 am
In response to Bumblemore
It's not meant to work like that. That's just a visualization included with the demo of the areas that would register as "in sight". In an actual game, that level of testing probably wouldn't perform too well. I've got an update I'll release probably later today that shows this better (it'll also have FOV and range built-in).
Jul 5 2013, 7:53 pm
I would love to use this for a game but it's too complicated you're coding can you make a simpler one or just send me one that is more simpled?
Jul 25 2016, 1:42 am
This is incredible!