ID:146828
 
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:
  1. 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!
  2. 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
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) + 1
var/py1 = ((atom1.pixel_y+16)&31) + 1
var/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) + 1
var/py2 = ((atom2.pixel_y+16)&31) + 1
var/tx2 = atom2.x + round(atom2.pixel_x/32 + 0.5)
var/ty2 = atom2.y + round(atom2.pixel_y/32 + 0.5)

var/nextx = 33
var/nexty = 33
var/dirx = 1
var/diry = 1
if(pxd < 0) {nextx = 0; dirx = -1}
if(pyd < 0) {nexty = 0; diry = -1}

var/slope,acc,jx,jy,inc

var/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)<abs(pyd), swapping all the x and y vars except in the order they're put into PushToList(). (You'd still switch x and y for the second pair of coordinates, but then you'd have to swap their order so the new x comes first.)

I suppose in theory it's possible to do this with lists in a way that doesn't require quite as much complexity in the var names and could perhaps reduce the complexity of the algorithm, but it may or may not be an improvement. In that form, you'd have a single list storing alternating copies of px1,py1, tx1,ty1, dirx,diry, jx,jy, etc. An index could point to the main direction's offset in the list, while another points to the secondary direction. Baiscally you'd be swapping one form of complexity for another if you did that.

Lummox JR
In response to Lummox JR (#1)
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)<abs(pyd), swapping all the x and y vars except in the order they're put into PushToList(). (You'd still switch x and y for the second pair of coordinates, but then you'd have to swap their order so the new x comes first.)

Wow, thanks a lot Lummox. Looks like a nice algorithm... I'll use it if mine fails. :) I was thinking of a bit more "pure" mathematical approach, something like:

1) Calculate slope of line (k)
2) Find out in what direction to go (addx, addy)
3) Use some simple rewrite of y=kx+m to find the intersection with the turf edges
depending on slope and direction. (I rather do lots of if than a multiplication!)
4) Detect in what direction to go for the next turf
5) Set new coordinates to position in next turf
6) Repeat until destination reached.


From the tests I made, it seems like this method is not as complex as yours. But do you see any drawbacks with it? Have I missed something?


/Gazoot
In response to Gazoot (#2)
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