a function to return circles

ID:1972331
 
Oct 25 2015, 11:16 am
(See the best response by Ter13.)
Code:
//Returns a list of turfs in the border of a circle
/proc/returnCircle(var/turf/origin, var/radius)
    var/list/circle = list()
    for(var/i = 0, i <= radius, i++)
        var/dx = i
        var/dy = round(sqrt((radius**2) - (dx**2)), 1)
        var/y = origin.y + dy
        var/x = origin.x + dx
        var/turf/P = locate(y, x, origin.z)
        circle += P
        y = origin.y - dy //repeat the process again to account for negative values that sqrt() doesnt return
        x = origin.x - dx
        P = locate(y, x, origin.z)
        circle += P
    return circle


Problem description:
So I am trying to code a thing the returns a circle with a given radius and origin. Posted is what I have so far, but it only returns the turfs on the perimeter. Short of having it run a check on every single turf in a square with side length of the radius, how would i return the contents of the circle?
Oct 25 2015, 11:49 am (Edited on Oct 25 2015, 12:04 pm)
Don't use sqrt. Use the square of the radius instead. It'll save you a lot of computational time. Running a quick check using the square distance for every single tile in the square is probably quite a lot faster than using sqrt on the outside tiles.

proc/getCircle(turf/origin,radius)
    var/ox = origin.x, oy = origin.y, oz = origin.z
    var/list/turfs = block(locate(max(ox-radius,1),max(oy-radius,1),oz),locate(min(ox+radius,world.maxx),min(oy+radius,world.maxy),oz)) //be careful of map edges
    var/len = turfs.len, count = 1
    var/mdist = radius*radius, turf/t, td
    while(count<=len)
        t = turfs[count]
        td = (t.x-ox)**2 + (t.y-oy)**2
        if(td>mdist)
            --count
            --len
            turfs -= t
    return turfs


return the contents of the circle?

Do you want the objects, or do you just want all the turfs? If you want the objects, you'll want to use obounds() instead of block().

Using the square distance also has an advantage of not having to check each tile twice.
Oct 25 2015, 11:56 am
ok. I see what your doing by comparing the actual dist squared to the turfs' distances squared, but are you not still just going through a square with side length 2*radius and checking every turf in it? I just might not properly understand what block() does.

Also, yes, I only want the turfs.
Oct 25 2015, 11:59 am
Best response
I see what your doing by comparing the actual dist squared to the turfs' distances squared, but are you not still just going through a square with side length 2*radius and checking every turf in it?

Yes. It will more than likely be computationally the fastest way to handle this.

There's nothing wrong with looping through every object in a list for processing provided you don't do any heavy lifting and you are only looping through things that stand a reasonable chance of being inside the circle.

My tile-based lighting engine uses an unoptimized version of this code, and it performs absolutely wonderfully with hundreds of fairly large lights blinking on and off every single frame:



I think you will be fine.
Oct 25 2015, 3:34 pm
what about:
/proc/returnCircleContents(var/turf/origin, var/radius)
    var/list/circleContents = list()
    for(var/i = 0, i <= radius, i++)
        for(var/j = 0, j <= radius, j++)
            if (((i - origin.x)**2) + ((j - origin.y)**2) <= radius**2)
                circleContents += locate(i, j, origin.z)
    return circleContents
Oct 25 2015, 4:09 pm
A variant of that is actually faster than what I posted above. Yours appeared to be A LOT faster initially, but that's only because there was a bug that made it not work.

proc/returnCircleContents2(var/turf/origin, var/radius)
    var/list/circleContents = list()
    var/ox = origin.x, oy = origin.y, oz = origin.z, rs = radius**2
    var/lx = max(origin.x-radius,1), hx = min(origin.x+radius,world.maxx)
    var/ly = max(origin.y-radius,1), hy = min(origin.y+radius,world.maxy)
    for(var/i in lx to hx)
        for(var/j in ly to hy)
            if (((i - ox)**2) + ((j - oy)**2) <= rs)
                circleContents += locate(i, j, oz)
    return circleContents


^10K iterations at 0.711 CPU seconds with 5 radius

vs:

proc/getCircle(turf/origin,radius)
    var/ox = origin.x, oy = origin.y, oz = origin.z
    var/list/turfs = block(locate(max(ox-radius,1),max(oy-radius,1),oz),locate(min(ox+radius,world.maxx),min(oy+radius,world.maxy),oz)) //be careful of map edges
    var/len = turfs.len, count = 1
    var/mdist = radius*radius, turf/t, td
    while(count<=len)
        t = turfs[count]
        td = (t.x-ox)**2 + (t.y-oy)**2
        if(td>mdist)
            --len
            turfs -= t
        else
            ++count
    return turfs


^10K iterations at 1.125 CPU seconds with 5 radius

(This variant had to be fixed because my pseudocode was broken)

So yeah, with a few changes, your method will wind up being a lot faster

vs:

proc/returnCircleContents(var/turf/origin, var/radius)
    var/list/circleContents = list()
    var/lx = max(origin.x-radius,1), hx = min(origin.x+radius,world.maxx)
    var/ly = max(origin.y-radius,1), hy = min(origin.y+radius,world.maxy)
    for(var/i = lx, i <= hx, i++)
        for(var/j = ly, j <= hy, j++)
            if (((i - origin.x)**2) + ((j - origin.y)**2) <= radius**2)
                circleContents += locate(i, j, origin.z)
    return circleContents


^10K iterations at 1.025 CPU seconds with 5 radius

(This variant had to be fixed because your pseudocode was broken)
Oct 25 2015, 4:15 pm
How do you do the 10K iterations and CPU seconds thing?
Oct 25 2015, 4:18 pm
Use the profiler. Press F1 in DreamSeeker. Server->Profile

mob
    verb
        testTer()
            var/turf/origin = locate(world.maxx/2,world.maxy/2,1)
            for(var/count in 1 to 10000)
                returnCircleContents2(origin,5)
        testSnail()
            var/turf/origin = locate(world.maxx/2,world.maxy/2,1)
            for(var/count in 1 to 10000)
                returnCircleContents(origin,5)


Just set up a blank project you use for testing.

Your results will vary based on the machine you do your testing on. If your machine is slower, your times will be higher than mine. If your machine is faster than mine, your times will be lower.
Oct 25 2015, 4:26 pm
Thanks!
Oct 25 2015, 4:58 pm
 
proc/getCircle(turf/origin,radius)
    var/ox = origin.x, oy = origin.y, oz = origin.z
    var/lx = max(ox-radius,1), hx = min(ox+radius,world.maxx)
    var/ly = max(oy-radius,1), hy = min(oy+radius,world.maxy)
    var/list/turfs = block(locate(lx,ly,oz),locate(hx,hy,oz))
    lx -= ox
    hx -= ox
    ly -= oy
    hy -= oy
    var/list/l = list()
    var/mdist = radius*radius, count = 1, x, y
    for(y in hy to ly step -1)
        for(x in hx to lx step -1)
            if(x*x + y*y<=mdist)
                l += turfs[count++]
            else
                count++
    return l


^10K iterations at 0.588 CPU seconds with radius 5

Locating each tile individually actually induces a 33% CPU overhead over using a single block and then iterating through the list backward (block returns in top-right to bottom-left order) using the return value of the block operation.

Not much point in further optimization, though, as it's already a pretty rough read.

x*x is faster than x**2 by a pretty wide margin to boot.
Oct 26 2015, 1:05 pm
nice, thank you again
Oct 26 2015, 2:01 pm
In response to Ter13
Ter13 wrote:
x*x is faster than x**2 by a pretty wide margin to boot.

Teeny weeny bit off topic, but I feel like little tidbits like this should be added to the Red Book. Areas where the compiler can accomplish the same thing but one way is vastly faster than the other.
Oct 26 2015, 2:29 pm
In response to Ter13
My only change here would be:

mdist = radius * (radius+1)

Using a strict radius, you'll get a circle-like shape but the ends will be pointy. radius*(radius+1) however is the floor of (radius+0.5)**2, which adds a little slack. The rounded edges to the circle look nicer.

The only place this change is potentially weird though is when radius is 1. At that point, the shape becomes a 3x3 square instead of a + shape. One simple way to alter that to that is to change the <=mdist to <mdist instead.