ID:195138
 
//Title: Cone of Effect
//Credit to: Lummox JR
//Contributed by: Jtgibson
//Special thanks to: Foomer (for suggesting its creation)


//This proc returns a "cone" in a given direction -- that is,
// when you use the cone proc, it'll return a list of all objects
// within a certain distance inside a cone leading from the source
// out to that distance.

//For example:
// cone(usr, NORTH)
// would produce a cone like so:

// X X X X X X X X X | X = included space
// X X X X X X X | O = user's space (also included)
// X X X X X |
// X X X |
// O |

//You can tweak the cone's acceptable list as desired. For
// example:
// cone(usr, NORTH, range(usr))
// would make a cone from all objects within range().
//The default is view().

//To make a cone out three spaces, just use:
// cone(usr, NORTH, list = view(3))

//And so on and so forth.


//Lummox JR's Hyper-Efficient Version
//It's all Greek to me, but it works. --Jtgibson

atom/proc/InCone(atom/center = usr, dir = NORTH)
var/d = get_dir(center, src)
if(d == dir) return 1
if(dir & (dir-1))
return (d & dir) ? 1 : 0
if(!(d & dir)) return 0
var/dx = abs(x - center.x)
var/dy = abs(y - center.y)
if(dx == dy) return 1
if(dy > dx)
return (dir & (NORTH|SOUTH)) ? 1 : 0
return (dir & (EAST|WEST)) ? 1 : 0

proc/cone(atom/center = usr, dir = NORTH, list/list = view(center))
for(var/atom/O in list) if(!O.InCone(center, dir)) list -= O
return list
I believe when I originally wrote the efficient version I made a mistake in the diagonal check. This line:

return (d & dir) ? 1 : 0

...should be replaced with:

return (d & ~dir) ? 0 : 1

Here is the reasoning behind the change: In the original code, this takes place in the if(dir & (dir-1)) block. This condition is true if dir is diagonal, because it will have two bits set. Say dir is NORTHEAST (5) and d is NORTHWEST (9). Then d & dir is 1 (NORTH). Without the change, this means that an object is considered inside the cone even if it's not in roughly the same direction as the cone itself. The cone's angle of effect goes from 90° to nearly 270°.

The new check is testing d against the two dirs that are not aligned with the cone. If the cone is facing northeast, then any of the westward or southward directions should be excluded. Leaving the upper unused bits aside, ~dir is effectively the same as turn(dir,180). So the new code says: If d has any components in a direction the diagonal cone doesn't face, then this object is not part of the cone.

The rest of the proc, where dx and dy are calculated, handles cases where the cone dir is a cardinal direction, and that code works fine.

There is a slight inconsistency in the diagonal version because the center is included in the result. Technically, I think both versions should include the center. To make both versions include the center, change this:

if(d == dir) return 1

to:

if(!d || d == dir) return 1

If you want both versions to exclude the center, make it two lines:

if(!d) return 0
if(d == dir) return 1
I wonder how Lummox comes up with this stuff =p. This version might make more sense in terms of how it works.

atom/proc/InCone(atom/center = usr, dir = NORTH)
switch (dir)
if (NORTH)
return ((center.y <= src.y) && (center.x >= src.x - (src.y - center.y) && center.x <= src.x + (src.y - center.y)))
if (SOUTH)
return ((center.y >= src.y) && (center.x >= src.x - (center.y - src.y) && center.x <= src.x + (center.y - src.y)))
if (EAST)
return ((center.x <= src.x) && (center.y >= src.y - (src.x - center.x) && center.y <= src.y + (src.x - center.x)))
if (WEST)
return ((center.x >= src.x) && (center.y >= src.y - (center.x - src.x) && center.y <= src.y + (center.x - src.x)))


I guess I should add support for diagonals too but it's clear enough how to handle it based on the algorithm above.

It also probably makes more sense to rewrite the inequalities in terms of abs (absolute value).

You know what we really need? A get_angle() proc.
In response to Toadfish
Toadfish wrote:
You know what we really need? A get_angle() proc.

You mean Lummox JR's arc tangent?

My ProcLib has plenty of procs in it that work with angles (0=EAST, +ccw) and bearings (0=NORTH, +cw), including atan2(x,y). I have yet to decide on a final naming convention for it, though, since they're all pretty much copy/pasted from my many small, unreleased projects.
In response to Toadfish
Toadfish wrote:
I wonder how Lummox comes up with this stuff =p. This version might make more sense in terms of how it works.

While in theory this code is conceptually easier to understand, I think anyone who's having trouble grasping my code would have trouble with all the conditionals in this, too. From a design perspective, a switch() form of a proc that handles directional stuff is always worse, because you're duplicating a lot of code needlessly. I cringe when I see a directional proc testing each direction specifically.
Very cool! Useful for everythimg from limited LOS to spell effects!
At the end of the day, I'd say it's your code that will be difficult to understand for a programmer going back to it months later (so difficult to correct or change). Repetitive, simple code is just... better from a practicality standpoint. A programmer needing to change or correct your proc will have a faster and easier time rewriting it, and this, I think, is where it fails.

That said, I really do sympathize with your post; the math-lover inside me appreciates an elegant, general solution.

If you have a get_angle() proc implemented (that properly skews the values for cardinal/diagonal directions to fit a large-tile-based map, I guess) the simplest and most elegant solution - but maybe not the most optimal - is probably just using that.
In response to Toadfish
Toadfish wrote:
At the end of the day, I'd say it's your code that will be difficult to understand for a programmer going back to it months later (so difficult to correct or change). Repetitive, simple code is just... better from a practicality standpoint. A programmer needing to change or correct your proc will have a faster and easier time rewriting it, and this, I think, is where it fails.

The code wasn't written with readability or maintenance in mind, though improving readability would be an easy task. I agree the use of bitflags could confuse a novice programmer, and some simple comments would clarify the whole thing. However I disagree that the code you presented is any easier to read; the long lines are, if anything, much harder to read because they can't be seen at a glance, and the sheer volume of subtractions and comparisons will not help.

From a maintenance standpoint your argument completely falls apart. With the repetitive approach, you've created some very long lines that are harder to read and for that reason, at least arguably harder to maintain. The overuse of <= and >= operators is, in my experience, a good way to get lost in code all on their own. The numerous subtractions are a great place to introduce sign errors. And the fact of the code being repetitive means 1) the copy-paste process a user goes through is more likely to introduce errors itself, and 2) making a change means changing all of the if blocks rather than just one place.

If you have a get_angle() proc implemented (that properly skews the values for cardinal/diagonal directions to fit a large-tile-based map, I guess) the simplest and most elegant solution - but maybe not the most optimal - is probably just using that.

Optimal is almost always elegant; I submit that using an angle approach is pretty unimportant unless the user wants to use a specific angle of effect (a cone angle other than 90°) or a very specific direction. For something closer to a 45° angle of effect with standard directions however, the current simple solution can be altered.

atom/proc/InCone45(atom/center = usr, dir = NORTH)
var/d = get_dir(center, src)
if(!d) return 1;
var/dx = abs(x - center.x)
var/dy = abs(y - center.y)
if(dir & (dir-1))
return (d & dir) ? (dx <= dy*2 && dy <= dx*2) : 0
if(!(d & dir)) return 0
if(dy > dx)
return (dir & (NORTH|SOUTH)) ? (dy >= dx*2) : 0
return (dir & (EAST|WEST)) ? (dx >= dy*2) : 0

That's not an exact 45° angle, but an approximation. The 2 should actually be arctan(22.5°) which is about 2.41, or sqrt((sqrt(2)+1)/(sqrt(2)-1)).
Like I said, the long lines can and should be greatly shortened with an abs() inequality, so I think that's a non-argument. The redundancy is a concern, but not necessarily a big one, since the lines are all analogical; a change applied to one line can be mechanically transformed to fit another line. I would also argue that, given the somewhat tangled case-by-case structure of your algorithm, in most cases wanting to expand or change it would require a large revision just as big (the cases are not congruent, however). It's also not exactly true that you avoid the need to check every specific direction, either; your case-by-case if statements are very much still there, compressed, in the last two lines.

The way my algorithm works is clearer, so in the case of a problem or the such it only takes a quick glance at the code to understand how things work. Your algorithm does pretty much what mine does - they are conceptually similar - but it approaches the issue in what to me seems like a roundabout way, that favors compression over clarity. Going back to the bit-flag algorithm you proposed a few months later, one will need a minute or two longer to 'get' it. Whereas an error in my algorithm would take the form of a sign ("copy paste") error, in your algorithm it would more likely be a conceptual error - and those are more difficult.

Extrapolated, you're looking at an exchange of difficult but non-redundant (perhaps even "elegant") vs. redundant but trivial. From a practicality perspective I prefer the latter, although the former is nice as to keep as a trick up your magician's sleeve.

Optimal is almost always elegant; I submit that using an angle approach is pretty unimportant unless the user wants to use a specific angle of effect (a cone angle other than 90°) or a very specific direction. For something closer to a 45° angle of effect with standard directions however, the current simple solution can be altered.

I like the angle approach because it's conceptually the most straightforward; you're taking a turf to represent the centre, drawing an axis in the direction you want from it, and checking if the line from the centre to a given turf is in an angle of 45 or less from that axis. The benefit isn't from any gain in accuracy, but from the language you get by having a get_angle() proc; you can write an algorithm that screams exactly what a cone is.
In response to Toadfish
Toadfish wrote:
Like I said, the long lines can and should be greatly shortened with an abs() inequality, so I think that's a non-argument. The redundancy is a concern, but not necessarily a big one, since the lines are all analogical; a change applied to one line can be mechanically transformed to fit another line. I would also argue that, given the somewhat tangled case-by-case structure of your algorithm, in most cases wanting to expand or change it would require a large revision just as big (the cases are not congruent, however). It's also not exactly true that you avoid the need to check every specific direction, either; your case-by-case if statements are very much still there, compressed, in the last two lines.

I'll grant that there are still some case checks in there, but they're minor and, more to the point, much easier to read than long lines.

The way my algorithm works is clearer, so in the case of a problem or the such it only takes a quick glance at the code to understand how things work. Your algorithm does pretty much what mine does - they are conceptually similar - but it approaches the issue in what to me seems like a roundabout way, that favors compression over clarity. Going back to the bit-flag algorithm you proposed a few months later, one will need a minute or two longer to 'get' it. Whereas an error in my algorithm would take the form of a sign ("copy paste") error, in your algorithm it would more likely be a conceptual error - and those are more difficult.

If your code did include the abs() calls, clarity would be improved for sure. But I don't concede the point that a conceptual error is harder to recognize than a sign error. From experience, bugs in the typo family are the worst to root out. Bear in mind, there was also a conceptual error in the initial code that, when my attention was called back to this thread, I was able to recognize and correct at a glance years after the fact. I believe a sign error would have been much more difficult to detect.

Extrapolated, you're looking at an exchange of difficult but non-redundant (perhaps even "elegant") vs. redundant but trivial. From a practicality perspective I prefer the latter, although the former is nice as to keep as a trick up your magician's sleeve.

My main issue with the switch() approach to directional procs is that I've seen a great deal of code written that way, most if not all of it bad, and it introduces enormous maintenance headaches in most cases. Your case for doing this proc that way has some points to it, but to me the inescapable problem is that this is an approach newbies should not be encouraged to learn. When it comes to directions, getting comfortable with bitflags or at least procs like turn(), get_step(), etc. is best. And when tucked away in a library, efficiency wins out over everything else.

I like the angle approach because it's conceptually the most straightforward; you're taking a turf to represent the centre, drawing an axis in the direction you want from it, and checking if the line from the centre to a given turf is in an angle of 45 or less from that axis. The benefit isn't from any gain in accuracy, but from the language you get by having a get_angle() proc; you can write an algorithm that screams exactly what a cone is.

To be honest if angles are under consideration I'd rather skip a get_angle() concept and go straight for the dot product. The problem with get_angle is the result should be expected within 0 to 360, and you have to consider the boundary where it transitions. E.g., you can't write if(abs(get_angle(a,b)-facing_angle) <= 45) and expect that to work unless facing_angle is far enough away from that boundary, so there will always be a disjoint condition. Depending on which boundary facing_angle is closest to, you'd also need to compare to facing_angle+360 or facing_angle-360, and the safest approach is simply to always check both.

The best-practice approach using actual angles would definitely be to use the dot product.

proc/InConeByDir(atom/ref, facing_dir, atom/target, fov=45)
var dx = target.x - ref.x
var dy = target.y - ref.y
if(!dx && !dy) return 1

// This can be done more efficiently with a couple of quick lists, but:
var cx = (facing_dir & EAST) ? 1 : ((facing_dir & WEST) ? -1 : 0)
var cy = (facing_dir & NORTH) ? 1 : ((facing_dir & SOUTH) ? -1 : 0)
if(!cx && !cy) return 1

// use dot product to compare angles
return (dx*cx+dy*cy) >= cos(fov/2) * sqrt((dx*dx+dy*dy)*(cx*cx+cy*cy))

proc/InConeByAtom(atom/ref, atom/facing, atom/target, fov=45)
var dx = target.x - ref.x
var dy = target.y - ref.y
if(!dx && !dy) return 1

var cx = facing.x - ref.x
var cy = facing.y - ref.y
if(!cx && !cy) return 1

// use dot product to compare angles
return (dx*cx+dy*cy) >= cos(fov/2) * sqrt((dx*dx+dy*dy)*(cx*cx+cy*cy))

In both of those procs, fov is the field of view which is the full angle of the cone, so you'd actually be looking at half that angle in either direction, hence the use of fov/2. The issue of readability for newbies could come up here as well, since plenty of them wouldn't be familiar with the dot product, but it's unquestionably better to use this than the method that has a hidden gotcha.
In response to Lummox JR
That's a very clever way to normalize both vectors with one call to sqrt()! I'll have to steal that for my line of sight library :)
much easier to read than long lines.

I think that, when you introduce abs() to the long lines, they are clearer than the bit-flag approach. I suppose it's a matter of taste?

I don't concede the point that a conceptual error is harder to recognize than a sign error. From experience, bugs in the typo family are the worst to root out. Bear in mind, there was also a conceptual error in the initial code that, when my attention was called back to this thread, I was able to recognize and correct at a glance years after the fact. I believe a sign error would have been much more difficult to detect.

A good point I didn't consider enough. What we should both concede is, that not all errors are equal. There are conceptual errors that are fundamentally simple to correct - these arise because the concept itself is understood - and vice versa. There are sign errors that are fundamentally simple to correct - these arise in various situations - and vice versa. An obscure sign error in a long, heavy calculation would be a lot more difficult to correct than a conceptual error in a circle-drawing algorithm that instead draws a square.

In this scenario, I believe a sign error in one directional case is fairly easy to spot, because you immediately see several analogical, symmetrical calculations so something seems off.

Discussing conceptual errors, I think the error you spotted, and the kind of error that would arise from your approach in general, is /not/ the kind of conceptual error that would be easy to fix. The reason for this is that it's not an error in the fundamental concept behind the algorithm, but a rather quirky error in a specific, quirky calculation (I might be exaggerating on the quirkiness of it here, since I'm not exactly used to bit operators). And, if anything, because both our algorithms have the same concept behind them, I would argue a conceptual error would be easier to fix in my algorithm - since it presents the concept itself more clearly and obviously.

Furthermore, you give the example of your fixing a conceptual error as an argument to your case, but I'd like to dispute that. The question that weighs on me is: why wasn't this error spotted in all the years this algorithm was in circulation? Surely enough people saw it when you first posted it, when Jtgibson posted it in his snippet collection, and when it was reposted here, that /someone/ would've noticed the error.

Well, a few answers come to mind, but obvious answer is that people saw the algorithm was complex to a degree that they weren't motivated to look at how it works, or, even worse, they were not able to understand how it works. I think if you originally posted my algorithm, even without abs(), and had some sign error in there, it would've been fixed years before.

And when tucked away in a library, efficiency wins out over everything else.

You called out me on my false assumption, so may I dispute one of yours? I think this is highly circumstantial, and clear, less-than-optimal code very often wins out, even in a library, as long as maintenance and expansion of the library is called for.

To be honest if angles are under consideration I'd rather skip a get_angle() concept and go straight for the dot product. The problem with get_angle is the result should be expected within 0 to 360, and you have to consider the boundary where it transitions.

That was my concern. I agree with your analysis, and good call on using the dot product, I definitely like that approach, and it is by far clearer.