Straight(ish) lines

Page: 1 2
ID:153799
 
Jan 7 2003, 11:55 pm
How do you determine a straight line from point A to point B? It must be the straightest line possible in a tile-based system - no 45 degree bends. I know this is fairly easy to do, I just can't remember how it's done.
Jan 8 2003, 12:07 am
There's a pretty easy algorithm for this, but rather than copy and paste it here, I'll just point you to my library which contains it--http://www.byond.com/hub/AbyssDragon/BasicMath

-AbyssDragon
Jan 8 2003, 5:06 am
In response to AbyssDragon
AbyssDragon wrote:
There's a pretty easy algorithm for this, but rather than copy and paste it here, I'll just point you to my library which contains it--http://www.byond.com/hub/AbyssDragon/BasicMath

That's a pretty cool library. Nice functions in there.

Might I make a few suggestions though?

  • getcircle() uses distance(), which takes a slow square root. You should add distancesq(), for squared distance, and compare that to a predetermined value of rsq=radius*(radius+1). If distancesq()<=rsq, the turf belongs in the circle. getring() obviously relies on the square root; I think there are ways that could be made a lot faster, but they're not worth going into here.
  • getcircle() and getring() both rely on range(), not xrange(), so they'll fail for large radii. range() might be faster, so for safety's sake just do a quick check: if(isnum(world.view) && (world.view<<1)>=radius) use range(), but otherwise use xrange().
  • In allclear() you loop through var/mob/M, but in fact you can simply use var/atom/M to the same effect; I think this is safer. This might also be better done as a turf proc, rather than a global proc.
  • Your sign(x) code isn't the most compact in the world; it can be compacted further.
return ((x<0)?-1:((x>0)?1:0))
...becomes:
.=x<0?-1:(x?1:0)
I count 13 bytes saved. I don't know if that can be compacted further, but it strikes me it might just be possible to nest the operators as x?x>0?1:-1:0, which would save 2 more bytes. The feasibility of that depends on how well DM could handle this without choking; it does have some bugs in operator precedence rules (see my recent Bug Reports post) and it's funny about : in particular.

  • In xrange(), you can use min() and max() to save some unnecessary if() statements--and unnecessary vars:
var/contents[] = list()
if(center && center.z)
  for(var/turf/T in block(locate(max(center.x-range,1), max(center.y-range,1), center.z),\
                          locate(min(center.x+range,world.maxx), min(center.y+range,world.maxy), center.z)))
    contents += T
    contents += T.contents
return contents
That if() check was important too, because for the range to work right the atom has to exist and it has to be somewhere. It wouldn't be unheard of to call xrange(src.loc,100) or such, and have src.loc end up null--or to call xrange(src,100) in the same circumstance, where the atom exists but its coordinates are 0,0,0.

Lummox JR
Jan 8 2003, 5:34 am
In response to Lummox JR
That's a pretty cool library. Nice functions in there.

Might I make a few suggestions though?

[snip]

Thanks! The library's pretty old, so I admit that it's not all my best code. I'll try to update it sometime soon, though. Your suggestions should help me out a lot in that... saves me some thinking at least.

-AbyssDragon
Jan 8 2003, 12:31 pm
In response to Lummox JR
Your sign(x) code isn't the most compact in the world; it can be compacted further.
return ((x<0)?-1:((x>0)?1:0))

...becomes:

.=x<0?-1:(x?1:0)

I count 13 bytes saved. I don't know if that can be compacted further, but it strikes me it might just be possible to nest the operators as x?x>0?1:-1:0, which would save 2 more bytes. The feasibility of that depends on how well DM could handle this without choking; it does have some bugs in operator precedence rules (see my recent Bug Reports post) and it's funny about : in particular.


I still can't for the life of me understand why you think that smaller, cramped, and more complicated code is better. Not everyone who reads code is as good of a programmer as the one who wrote it -- actually, it's better to assume that they aren't nearly as good of a programmer -- and, with modern computers, the only times you need to optimise the efficiency of certain functions are if they wind up being inefficient and/or will be used over and over again. (Granted, in a math library, efficiency is extremely important... but I'm speaking in general.)

Bit-shifting, for example, has been declared to be pure evil in the programming courses I've been in, unless it is necessary to save memory that would ordinarily be wasted, or you're using non-standard numbers of bits (i.e. if you're representing multiple different variables with the bits run together to minimise the number of bytes needed).

In BYOND, since low-level memory management is not much of a concern, I generally see very little use in hyper-optimising everything. As long as it runs, it runs quickly, and it runs without errors, I don't see why it needs to be made so that it takes as little CPU time as possible, sacrificing readability and sanity to do so. When you want to edit something you or someone else has worked on, if they don't have crisp, clean, very readable code, it takes just as much time learning what the heck they're doing as it does to actually apply the modifications.
Jan 8 2003, 12:43 pm
In response to Spuzzum
I agree with your post in general. I will point out, though, that it's not bad to do some exercises now and then to stay in practice, because sooner or later you will have to optimize something. :)
Jan 8 2003, 12:54 pm
In response to Gughunter
Fortunately, I'm not at much of a disadvantage in that field... I lack full schooling, being more-or-less self-taught aside from the courses I took in high school (which basically reinforced my knowledge -- I didn't learn much aside from how to use the STL libraries and some basic stylistic restrictions), but I do have what I immodestly consider to be a natural aptitude. (Though it does make me think, "What would I have become if my dad didn't get my first PC in '93?" You know, when 75MHz was state-of-the-art and people could rack up $50 phone bills for playing Red Baron against each other on their 6400 baud modems.)

(I'm a little miffed at my Computer Science teacher, too. I only got a 3/5 ("good; you might be suited to a career in this field") on the AB level AP exam; all of the CS theory that appeared on the exam I had to teach myself, because the teacher didn't give me any resources other than the sample test. (Had I taken the A level exam, I would've been guaranteed a 5/5 ("excellent; you should look into a career in this field".))
Jan 8 2003, 1:40 pm
In response to Spuzzum
Cramped, more complicated code is generally considered worse. That particular sign(x) suggestion did not appear as useful as the other suggestions to me. That said, if the compilier used magic elves I'm not sure about for a performance increase, a few comments could fix the readability and sanity problems.

Optimizing a library is worthy of some effort. Less efficient methods can generally be used if they are not called frequently. However, since the uses for a library are unknown, those methods could be a painful bottleneck in someone else's project. At the library level, you can't be exactly sure what you can get away with.
Jan 8 2003, 2:15 pm
In response to AbyssDragon
Heh, serves me right for not looking at my existing library collection. =P

Thanks Abyss!
Jan 8 2003, 6:25 pm
In response to Spuzzum
Spuzzum wrote:
I still can't for the life of me understand why you think that smaller, cramped, and more complicated code is better. Not everyone who reads code is as good of a programmer as the one who wrote it -- actually, it's better to assume that they aren't nearly as good of a programmer -- and, with modern computers, the only times you need to optimise the efficiency of certain functions are if they wind up being inefficient and/or will be used over and over again. (Granted, in a math library, efficiency is extremely important... but I'm speaking in general.)

You missed the point. The library actually says that the existing sign(x) might be the most compact code in the world. I was demonstrating that it can be done even more compactly. I don't think cramped or complicated or more complicated code is better (although I hate it when whitespace is overused; that can be just as bad).
Smaller, however, yes, but in terms of statements and lines, not bytes. Smaller code--or perhaps it's closer to say shorter code--means you're closer to the ideal elegant solution.

I value simplicity a lot; most types of optimization enhance both simplicity (not necessarily to look at, though) and speed. Some, like loop unrolling, I think are impractical and painful and should only be used as last resorts to eke out speed from a stubborn routine.

Bit-shifting, for example, has been declared to be pure evil in the programming courses I've been in, unless it is necessary to save memory that would ordinarily be wasted, or you're using non-standard numbers of bits (i.e. if you're representing multiple different variables with the bits run together to minimise the number of bytes needed).

I couldn't disagree more on this point. Multiplication is time consuming even in floating point; although in an interpreted language like DM I suspect the loss isn't as great, why multiply when you can bit shift for the same result?

Bit twiddling is fast--perhaps not as fast in BYOND, but I imagine still faster than multiplication--and for lots of operations the easiest way to do something. My use of it in directional procs is particularly valuable. Because BYOND treats directions as bit flags, bit twiddling is extremely powerful there.

In BYOND, since low-level memory management is not much of a concern, I generally see very little use in hyper-optimising everything. As long as it runs, it runs quickly, and it runs without errors, I don't see why it needs to be made so that it takes as little CPU time as possible, sacrificing readability and sanity to do so. When you want to edit something you or someone else has worked on, if they don't have crisp, clean, very readable code, it takes just as much time learning what the heck they're doing as it does to actually apply the modifications.

This is why comments help a lot, to be sure.
But for the most part I have no intentions in my code of sacrificing readability; usually the operations I do are straightforward, and it's why they're done that might need some explaining. That recent get_precise_dir() rewrite, for example, was a good idea for several reasons: It collapsed a really complicated series of if/else blocks and turn() calls into a couple of lines. That made it more readable (and at least as clear) and faster. The &=3 and &=12 might not have made much sense, though I could have always written that 3 as NORTH | SOUTH and so on.

Readability is important. Granted. And as I said, I value simplicity: An optimization that vastly complicates the code, even while making it run faster, usually isn't worth doing in my book. But I consider it ludicrous to count bit twiddling on that level; indeed, it alone can often be the simplest and most readable path to a solution.

On optimizing in BYOND: I've found that even small projects can bog down the CPU if they do a single repetitive operation enough. Big ones will be worse. For example, what I suggested about using a squared distance in get_circle() was pure practicality. There are other ways the algorithm could be optimized further, but probably to only slight benefit and at the cost of severely complicating the code. Yet, doing a square root n*n times is a vast waste, and the more the proc is called the worse it gets. Instead, it makes a lot more sense to compare square distance (which is easier to find) to the squared radius; or rather, an approximation of (radius+0.5)**2 for a fudge factor.

The ring code I didn't suggest that for, but in hindsight that too can be improved; the abs(distance()-radius)<0.5 comparison, which is hugely wasteful because of the square root, can be changed:
var/rsq=radius*radius
var/mindsq=rsq-radius      // this is a little less than (radius-0.5)**2
var/maxdsq=rsq+radius      // this is a little less than (radius+0.5)**2
var/dsq=distancesq(T,M)
for(T as turf in xrange(M,radius))
  if(dsq>mindsq && dsq<=maxdsq)
    ring+=T
For a couple of quick calculations up front--that don't really detract from readability or simplicity--you can find a ring without doing a bunch of time-consuming square roots. The bigger the ring you look for, and the more often you look for a ring, the more square roots you'd have to do.

Lummox JR
Jan 8 2003, 6:34 pm
In response to ACWraith
ACWraith wrote:
Cramped, more complicated code is generally considered worse. That particular sign(x) suggestion did not appear as useful as the other suggestions to me. That said, if the compilier used magic elves I'm not sure about for a performance increase, a few comments could fix the readability and sanity problems.

That wasn't for performance or readibility; that was because of the comment about the original being the most compact in the world. 'Tweren't.

Optimizing a library is worthy of some effort. Less efficient methods can generally be used if they are not called frequently. However, since the uses for a library are unknown, those methods could be a painful bottleneck in someone else's project. At the library level, you can't be exactly sure what you can get away with.

Exactly why I think putting optimizations in such procs is useful--particularly when it comes to ones that would be called often, like get_circle(), get_ring(), or xrange(). (In fact I'd write a turf-only companion for xrange() that could be used in get_circle() and get_ring().)

Those could be further optimized, too. For example in calculating a circle, instead of looping through every turf or calling distance() (or in my case, distancesq()) so many times, you could keep track of the squares as you went along via x,y coordinates. block() would be useful for building the circle by blocks at a time, and for the ring as well; however some care would have to be taken when going over the edge of the map. But going this far would complicate the code. Considering this is a library and not a tutorial, making the extra modifications could be worthwhile. For a tutorial I wouldn't recommend such a thing. The result could be a blinding fast circle proc that can execute at about twice the speed of a similar proc.

Lummox JR
Jan 8 2003, 8:15 pm
In response to Lummox JR
Just to be clear, I was supporting the optimizations. I just focused on the section Spuzzum quoted in my first paragraph and possibly did not provide enough of a transition for my second.
Jan 8 2003, 8:17 pm
In response to ACWraith
ACWraith wrote:
Just to be clear, I was supporting the optimizations. I just focused on the section Spuzzum quoted in my first paragraph and possibly did not provide enough of a transition for my second.

I got that; it wasn't clear to me at first but I did see it.

Lummox JR
Jan 8 2003, 9:13 pm
In response to AbyssDragon
Since you said you might update the library I have a suggested function to add. It would return a list of turfs roughly contained within the shape of a square that is rotated 45 degrees. The shining force series used such a shape as the base of movement possabilities (it assumes that one diagonal movement counts as 2 moves: one horizontal and one vertical)
A size of 0 (meaning all the squares you could reach with 0 moves) would result in the center square:
*

A size of 1 would result in a plus type shape:
 *
***
 *

A size of 2 would result in a shape like this:
  *
 ***
*****
 ***
  *
Jan 9 2003, 6:00 am
In response to Lummox JR
Lummox JR wrote:
Spuzzum wrote:
I still can't for the life of me understand why you think that smaller, cramped, and more complicated code is better. Not everyone who reads code is as good of a programmer as the one who wrote it -- actually, it's better to assume that they aren't nearly as good of a programmer -- and, with modern computers, the only times you need to optimise the efficiency of certain functions are if they wind up being inefficient and/or will be used over and over again. (Granted, in a math library, efficiency is extremely important... but I'm speaking in general.)

You missed the point. The library actually says that the existing sign(x) might be the most compact code in the world. I was demonstrating that it can be done even more compactly.

Wasn't aware that he said that -- misunderstanding on my part. =)

I generally don't look at the source code for libraries beyond a simple once-over when I download them, and that comment probably wasn't ingrained into my memory. (Yes, that "once-over" occurs at every successive upgrade. =))


I don't think cramped or complicated or more complicated code is better (although I hate it when whitespace is overused; that can be just as bad).

Personally, I think whitespace is the Great Whatsisname's gift to mankind... it just makes everything so much easier.

For example, 
var/x=sqrt((able+bravo)*log(charlie,2)**3)
var/y=((delta+echo)*(foxtrot**4)**2)
...versus: 
var/x = sqrt( (able + bravo) * log(charlie, 2)**3 )
var/y =     ( (delta + echo) *    (foxtrot**4)**3 )


The second is just far more legible as far as I'm concerned.



The rest of your post I'm just going to nod about, because after the clarification I see the page you're on.
Jan 9 2003, 6:30 am
In response to English
var/list/L = list()
for(var/turf/T in range(distance))
if((abs(T.x - src.x) + abs(T.y - src.y)) <= distance) L += T
return(L)

=P
Jan 9 2003, 8:05 am
In response to Spuzzum
Spuzzum wrote:
Personally, I think whitespace is the Great Whatsisname's gift to mankind... it just makes everything so much easier.

For example,
var/x=sqrt((able+bravo)*log(charlie,2)**3)
var/y=((delta+echo)*(foxtrot**4)**2)
...versus: 
var/x = sqrt( (able + bravo) * log(charlie, 2)**3 )
var/y =     ( (delta + echo) *    (foxtrot**4)**3 )
The second is just far more legible as far as I'm concerned.

Hrm... I can see lining up mathematical bits that way as being helpful only if the formulas are very similar. In this case they're pretty close to similar, so I guess that passes. Still I'm usually more of the opinion that the math will either be understood or it won't, and those who get it won't need the whitespace to see it.

But there are occasional cases where I'd consider the whitespace to be of vast benefit. Bit twiddling can especially be one of those cases, particularly if parentheses begin to dominate the code.

Lummox JR
Jan 9 2003, 8:06 am
In response to Spuzzum
Spuzzum wrote:
var/list/L = list()
for(var/turf/T in range(distance))
if((abs(T.x - src.x) + abs(T.y - src.y)) <= distance) L += T
return(L)

That'd have to be range(distance,src), of course.

Lummox JR
Jan 9 2003, 1:13 pm
In response to Spuzzum
I started thinking about that sort of thing as I was explaining it but I decided to be lazy and let someone else think about it. Thanks Spuzzum ;)
Jan 9 2003, 3:02 pm
In response to Lummox JR
Is there any reason why code can't be optimized AND readable?
Page: 1 2