Circle algorithm issues

ID:155723
 
Apr 5 2011, 7:27 pm
 
    getring(atom/M,radius)
        var/list/ring=list()
        var/turf/T
        for(T as turf in range(radius+1,M))
            if(abs(distance(T,M)-radius) < 0.5) ring += T
        return ring


This code returns turfs inside of a ring of a variable radius. The problem here is that if the radius is above 36, significant portions of the circle get chopped off and, as you increase the radius, it almost disappears completely. I'm using the getring() proc from AbyssDragon's BasicMath library, and I'm wondering if there is some way I can improve the algorithm? Or should I look into some other algorithm?
Apr 5 2011, 7:35 pm
I would check if range() is being cut off after a certain radius. If it is, try replacing it with block(), taking proper precautions for the edges of the map.
Apr 5 2011, 10:56 pm (Edited on Apr 5 2011, 11:27 pm)
Your distance proc is probably not working nicely with large tiles so it gets kind of messy. Here is an untested implementation of the "Midpoint circle algorithm", which should be both faster and more reliable:

proc/findCircle(turf/t, radius)
    var/list/result = new
    var/f = 1 - radius
    var/ddF_x = 1
    var/ddF_y = -2 * radius
    var/x = 0
    var/y = radius
    result += locate(t.x, t.y + radius, t.z)
    result += locate(t.x, t.y - radius, t.z)
    result += locate(t.x + radius, t.y, t.z)
    result += locate(t.x - radius, t.y, t.z)
    while (x < y)
        if (f >= 0)
            y--
            ddF_y += 2
            f += ddF_y
        x++
        ddF_x += 2
        f += ddF_x
        result += locate(t.x + x, t.y + y, t.z)
        result += locate(t.x - x, t.y + y, t.z)
        result += locate(t.x + x, t.y - y, t.z)
        result += locate(t.x - x, t.y - y, t.z)
        result += locate(t.x + y, t.y + x, t.z)
        result += locate(t.x - y, t.y + x, t.z)
        result += locate(t.x + y, t.y - x, t.z)
        result += locate(t.x - y, t.y - x, t.z)
    return result
Apr 6 2011, 1:41 pm
In response to Toadfish
This works really great, thanks!
Apr 6 2011, 3:11 pm
It's not too efficient, but you might want to check out my Shapes library.