ID:146828   Jan 18 2005, 5:44 am This is the problem: I have two mobs standing a couple of turfs apart. They both have a pixel x/y offset on their turf. I know both the offset and the "real" x/y coordinates, ((turf.x-1) * 32 + mob.pixel_x), and of course the turf/mob location on the map. Now I would like to find out the following in a nice quick fashion: If you draw a straight line between the mobs from their exact location, which turfs does this line intersect? Should be simple, but I want it optimized! A bit more tricky: For every turf that the line intersects, I want to know where the line crosses a turf border, and returns the coordinates of that position, relative to the turf it's crossing at the moment. Something like: ``` +-----C-+-------+ | \-B__ | | | \ | | | -A | +-------+-------+ A = The mob B = I want the coordinates of this position, in this case something like (1,28) C = This position too, since the line keeps going... ``` I have most of it figured out myself, but I would like to discuss the way to do it best. The reason for problem 2 is of course that I would like to use DrawBox() to draw a line between two points. So, any ideas? /Gazoot
 <-> Jan 18 2005, 6:39 am The first thing you'll have to do is decide whether the X or Y direction is more significant. Pretty much any line-drawing algorithm does that first. From here we need a few conventions. For simplicity's sake, let's call the lower left corner of each turf 1,1 and the upper right 32,32, icon style. By convention, an obj or mob at pixel offsets of 0,0 is at position 17,17. Now I'll need two distances in pixels: pxd and pyd, both measured as atom2-atom1. ```var/px1 = ((atom1.pixel_x+16)&31) + 1var/py1 = ((atom1.pixel_y+16)&31) + 1var/tx1 = atom1.x + round(atom1.pixel_x/32 + 0.5)var/ty1 = atom1.y + round(atom1.pixel_y/32 + 0.5)var/px2 = ((atom2.pixel_x+16)&31) + 1var/py2 = ((atom2.pixel_y+16)&31) + 1var/tx2 = atom2.x + round(atom2.pixel_x/32 + 0.5)var/ty2 = atom2.y + round(atom2.pixel_y/32 + 0.5)var/nextx = 33var/nexty = 33var/dirx = 1var/diry = 1if(pxd < 0) {nextx = 0; dirx = -1}if(pyd < 0) {nexty = 0; diry = -1}var/slope,acc,jx,jy,incvar/turf/T = locate(tx1, ty1, atom1.z)var/turf/T2 = locate(tx2, ty2, atom1.z) // use atom1.z here too/* I'm only showing this half because it's a pain in the butt */if(abs(pxd) >= abs(pyd)) slope = abs(pyd/pxd) acc = slope/2 while(T && T != T2) jx = abs(nextx-px)*slope jy = round(abs(nexty-py)+1-acc) if(jx<=jy) // next turf is in x direction // find last pixel in this turf acc += jx-slope PushToList(output, T, px1, py1, nextx-dirx, py1+diry*round(acc)) // now move 1 pixel forward px1 = abs(32 - nextx) tx1 += dirx acc += slope-round(acc) if(acc >= 1) py1 += diry if(py1 == nexty) ty1 += diry py1 = abs(32 - nexty) else // next turf is in y direction // find last pixel in this turf jx = (jy-1)/slope if(jx > round(jx)) jx = round(jx)+1 PushToList(output, T, px1, py1, px1+dirx*jx, nexty-diry) // now move 1 pixel forward acc += (++jx)*slope px1 += px1+dirx*jx if(px1 == nextx) // this actually shouldn't happen because tx1 += dirx // the jx<=jy case should handle it px1 = abs(32 - nextx) acc -= round(acc) ty1 += diry py1 = abs(32 - nexty) T = locate(tx1, ty1, T.z) ``` I'm hoping I didn't screw any of that up, though likely as not I did. As you can see this is a pretty complex problem. The algorithm as it stands will correctly skip over a diagonal gap from one turf to another if need be. The part I did not show is where you repeat this for abs(pxd)
 <-> Jan 18 2005, 10:01 am In response to Lummox JR Lummox JR wrote: I'm hoping I didn't screw any of that up, though likely as not I did. As you can see this is a pretty complex problem. The algorithm as it stands will correctly skip over a diagonal gap from one turf to another if need be. The part I did not show is where you repeat this for abs(pxd)
 <-> Jan 18 2005, 11:45 am In response to Gazoot The main potential drawback I see is that you're not working with integer values, which are used for plotting pixels within an icon. y=mx+b is great in pure theory, but for integer math you need to use a few tricks. I also wouldn't worry about the multiplication part. For one thing, an if() is actually potentially slower (in machine code anyway). And since these are floating point values, the CPU is shunting those multiplications to an onboard coprocessor rather than doing a lot of heavy lifting itself. Lummox JR