Raytracing algorithms

ID:152427
 
Oct 31 2006, 3:12 pm
I was wondering if anyone around here came up with any decent raytracing algorithms. The only one I'm aware of is the one in Shadowdarke's Pixel Projectiles library.

Right now, I've encountered a teensy problem with visual events in Haven's output system. The way it's set up, you can "see" things happening at a distance well beyond world.view, provided the event's visual strength is stronger than world.view. For instance, you might see someone attacking someone else even if it's well off screen -- your character isn't assumed to be so narrow minded that he suddenly loses track of someone just because they're no longer ten metres away. This appears in the form of a text message: "You see someone hit someone in the arm!"

However, the problem here is that view() fails completely at those ranges. My aim is to raytrace between an observer and the source for visual events that are larger than world.view, so that distant observers can still witness them. Obstructions that block line of sight at range will obviously prevent someone from "seeing" anything at range.

In the meantime, you can still "see" visual events at range, but they are visible through walls and the like, which is rather game-breaking to say the least...
Oct 31 2006, 3:52 pm
Oct 31 2006, 5:51 pm
My Intercept() snippet in Post [link] may help. sgn() and sd_get_dist() are posted later on in the same thread, though you can probably figure them out for yourself. ;)
Nov 1 2006, 3:42 pm (Edited on Nov 1 2006, 3:50 pm)
In case anyone was shy because they figured I'm just asking for code (heh heh), here's my own implementation of a raytracing system:

proc/ring(distance = 6, atom/centre)
    distance = round(distance,1)

    var/min_x = centre.x-distance
    var/max_x = centre.x+distance
    var/min_y = centre.y-distance
    var/max_y = centre.y+distance
    if(min_x < 1)          min_x = 1
    if(max_x > world.maxx) max_x = world.maxx
    if(min_y < 1)          min_y = 1
    if(max_y > world.maxy) max_y = world.maxy

    var/list/L = list()

    for(var/atom/O in block( locate(min_x,min_y,centre.z), locate(max_x,max_y,centre.z) ) )
        var/range = get2Ddist(O, centre)
        if(range < distance+0.5 && range >= distance-0.5)
            L += O

    return(L)

proc/get_path_along_angle(distance = 6, atom/centre, angle)
    //0 (22.5)
    //45 (67.5)
    //90 (112.5)
    //135 (157.5)
    //180 (202.5)
    //215 (237.5)
    //270 (292.5)
    //315 (337.5)
    //360

    var/dir = NORTH
    switch(standard2bearing(angle))
        if(0 to 22.5)      dir = NORTH
        if(22.5 to 67.5)   dir = NORTHEAST
        if(67.5 to 112.5)  dir = EAST
        if(112.5 to 157.5) dir = SOUTHEAST
        if(157.5 to 202.5) dir = SOUTH
        if(202.5 to 237.5) dir = SOUTHWEST
        if(237.5 to 292.5) dir = WEST
        if(292.5 to 337.5) dir = NORTHWEST
        if(337.5 to 360)   dir = NORTH

    var/ring = ring(distance, centre)

    var/turf/nearest
    var/nearest_angle = 360
    for(var/turf/T in ring)
        var/direction = get_dir(centre,T)
        if((direction != dir) && (direction != turn(dir,45)) && \
            (direction != turn(dir,-45))) continue //should cut down on get_angle calls!
        var/new_angle = abs(get_angle(centre, T) - angle)
        if(new_angle < nearest_angle)
            nearest = T
            nearest_angle = new_angle

    if(!nearest) return list()

    return(get_line(centre,nearest))


proc/tracepath(distance = 6, atom/centre, angle)
    //Returns the furthest dense location along a line leading from the centre
    // towards the specified angle.
    var/list/line = get_path_along_angle(distance, centre, angle)
    if(!line.len) return null
    if(isturf(centre))
        line -= centre
    else
        line -= centre.loc

    for(var/i = 1, i <= line.len, i++)
        var/turf/T = line[i]
        if(T.density)
            return line.Copy(1,line.Find(T)+1)
        else for(var/atom/movable/O in T)
            if(O.density)
                return line.Copy(1,line.Find(T)+1)
    return line



//Utility functions from my toolkit

proc/get_angle(atom/src, atom/trg)
/*
Gets the angle from the src to the target in standard position;
that is, east is 0 and angles increase counter-clockwise.

This can later be changed into a bearing if desired (see the appropriate
proc, standard2bearing() ), but this method makes it much easier
to work with.
*/
    var/x_dif = trg.x - src.x
    var/y_dif = trg.y - src.y
    var/dist = sqrt(x_dif**2 + y_dif**2) //distance c = sqrt(a^2 + b^2)

    if(!dist) return 0

    var/ref_angle = arcsin(abs(y_dif)/dist) //angle in degrees from 1 to 90

    var/angle

    if(ispos(x_dif) && ispos(y_dif)) //Quadrant 1
        angle = ref_angle

    else if(isneg(x_dif) && ispos(y_dif)) //Quadrant 2
        angle = 180-ref_angle

    else if(isneg(x_dif) && isneg(y_dif)) //Quadrant 3
        angle = 180+ref_angle

    else if(ispos(x_dif) && isneg(y_dif)) //Quadrant 4
        angle = 360-ref_angle

    return angle

//Changes an angle in standard position to a bearing
proc/standard2bearing(angle)
    angle = normalise(angle)
    angle -= 90 //subtract 90
    angle = 360-angle //invert the angle

    return angle

proc/get2Ddist(atom/A as obj|mob|turf, atom/B as obj|mob|turf)
    return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) )

//Returns the similar angle in the range 0 - 359.99999...
proc/normalise(angle)
    while(angle < 0) angle += 360
    while(angle >= 360) angle -= 360
    return angle


This system is designed with a maximum range in mind. I'm not sure how to go about a pure raytracing algorithm, so it seems as though I'll need to do some reading...

I imagine it's exceedingly inefficient, but that's what you get from a programmer who hasn't had one iota of education for optimisation. This is why I was asking to see if anyone had anything better. =)


[edit]Oops, forgot get_line().

//This returns a precise list of turfs in a near-perfect
// line from point A to point B.  The turfs are presented
// in order of distance, so they can be used to follow a
// path.

proc/get_line(atom/A, atom/B)
    var/x_dif = B.x - A.x
    var/y_dif = B.y - A.y

    if(A.z != B.z) return(list())
    if(!A.loc || !B.loc) return(list())

    if(!x_dif && !y_dif) return(list(A.loc)) //prevent divide by zero errors

    if(abs(x_dif) > abs(y_dif)) //horizontal-tending line
        var/y_offset = y_dif/abs(x_dif)

        var/list/line = list()

        for(var/x_offset = 0, abs(x_offset) <= abs(x_dif),)
            var/x_pos = A.x + x_offset
            var/y_pos = A.y + (abs(x_offset)*y_offset)

            var/turf/T = locate(x_pos, y_pos, A.z)
            line += T

            if(x_dif < 0) x_offset--
            else x_offset++

        return(line)

    else if(abs(y_dif) > abs(x_dif)) //vertical-tending line
        var/x_offset = x_dif/abs(y_dif)

        var/list/line = list()

        for(var/y_offset = 0, abs(y_offset) <= abs(y_dif),)
            var/x_pos = A.x + (abs(y_offset)*x_offset)
            var/y_pos = A.y + y_offset

            var/turf/T = locate(x_pos, y_pos, A.z)
            line += T

            if(y_dif < 0) y_offset--
            else y_offset++

        return(line)

    else //diagonal line
        var/x_offset
        var/y_offset
        switch(get_dir(A,B))
            if(NORTHEAST) {x_offset = 1; y_offset = 1}
            if(SOUTHEAST) {x_offset = 1; y_offset = -1}
            if(SOUTHWEST) {x_offset = -1; y_offset = -1}
            if(NORTHWEST) {x_offset = -1; y_offset = 1}

        var/list/line = list()

        for(var/position = 0, position <= abs(x_dif), position++)
            var/x_pos = A.x + (position*x_offset)
            var/y_pos = A.y + (position*y_offset)

            var/turf/T = locate(x_pos, y_pos, A.z)
            line += T

        return(line)
Nov 1 2006, 3:56 pm
In response to Jtgibson
Try to set things up so you can drop the sqrt in get2Ddist - that is, compare it to squared values where applicable, etc. etc. Maybe create a get2Ddistsquare() proc, that returns the squared value of the distance to the object. sqrt() is slow.

And, of course, avoid ** like the plague - multiply the number by itself. I think you're already doing that, from what I looked at.

Store values that you're going to be looking at instead of creating them in if()s, etc. If they're going to be constant, that is. For example:

var/dup=distance+0.5
var/dlow=distance-0.5
for(var/atom/O in block( locate(min_x,min_y,centre.z), locate(max_x,max_y,centre.z) ) )
        var/range = get2Ddist(O, centre)
        if(range < dup && range >= dlow)
            L += O


Those are my two cents on optimisation. I'm not sure about how to build a better LOS algorithm, though.
Nov 1 2006, 4:08 pm
In response to Jp
Jp wrote:
Those are my two cents on optimisation. I'm not sure about how to build a better LOS algorithm, though.

I know about all of those, although for the most part I wrote that proc as a fire-and-forget sort of thing. It worked for my purposes and I wasn't trying to heavily optimise it (it was being called for bullets only, so it wasn't being used as much as a line-of-sight algorithm would be).

I'm talking more about the heavier-duty optimisations, like the ones that Lummox JR does. For instance, compare:

//My version:
proc/get_general_dir(atom/Loc1, atom/Loc2)
    var/dir = get_dir(Loc1, Loc2)
    switch(dir)
        if(NORTH, EAST, SOUTH, WEST)
            return dir

        if(NORTHEAST, SOUTHWEST)
            var/abs_x = abs(Loc2.x - Loc1.x)
            var/abs_y = abs(Loc2.y - Loc1.y)

            if(abs_y > (2*abs_x))
                return turn(dir,45)
            else if(abs_x > (2*abs_y))
                return turn(dir,-45)
            else
                return dir

        if(NORTHWEST, SOUTHEAST)
            var/abs_x = abs(Loc2.x - Loc1.x)
            var/abs_y = abs(Loc2.y - Loc1.y)

            if(abs_y > (2*abs_x))
                return turn(dir,-45)
            else if(abs_x > (2*abs_y))
                return turn(dir,45)
            else
                return dir



//Lummox JR's version:
proc/get_general_dir(atom/ref,atom/target)
  if(target.z > ref.z) return UP
  if(target.z < ref.z) return DOWN

    var/d = get_dir(ref,target)
    if(d&d-1)        // diagonal
        var/ax = abs(ref.x - target.x)
        var/ay = abs(ref.y - target.y)
        if(ax >= (ay << 1))      return d & (EAST|WEST)   // keep east/west (4 and 8)
        else if(ay >= (ax << 1)) return d & (NORTH|SOUTH) // keep north/south (1 and 2)
    return d


=P