daily pastebin goal

3D Distance

Zeda Jan 13th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Okay, so when you calculate how far to move your ship each iteration, you'll end up with a value to add to each coordinate.
  2. I'm assuming you are doing this with a look-up table based on the angle at which you are facing.
  3. You said the biggest change was 255 which is an 8-bit value. Perfect.
  4. So I'm calling the amount you move each iteration (deltaX,deltaY,deltaZ).
  5. I'm sorry, I know this is in conflict with some of your other notation.
  7. Anyways, suppose that coordinates are 24-bit integers. (actually smaller, they'll be on [-1000000,1000000]
  8. Your coordinats are (x0,y0,z0).
  9. The object against which to compare is (x1,y1,z1).
  11. In the program overhead, if MapData is not empty, compute for each item:
  12. (x0-x1)^2+(y0-y1)^2+(z0-z1)^2
  13. Call this value and call it d2 (distance squared). Keep this value for each item somewhere! It will need 44 bits, so a 48-bit integer (6 bytes) for each item in mapData will suffice.
  14. DO NOT compute the square root
  16. Every time a new object is added to MapData, you'll need to compute this value.
  17. If the object starts at the same place as an existing object, you can just copy this value. No need to calculate.
  18. If the object starts at a small offset from an existing object, somewhat faster math can be used to calculate this value.
  21. So, let's get down to business <s>to defeat the huns.</s>
  23. With this precomputed value, we'll now be able to compute distance a lot faster.
  24. Whenever you move, you'll need to update d2 in every object in MapData:
  25.     d = deltaX*(x0-x1)+deltaY*(y0-y1)+deltaZ*(z0-z1)
  26.     d = d + d
  27.     d2= d2+ d
  29. The computations require:
  30.     3 of:
  31.         Subtracting 24-bit integers
  32.         Multiplying the resulting 24-bit integer by an 8-bit value to get a 32-bit integer
  33.     Adding each of these 32-bit integers together.
  34.     Doubling this 34-bit value
  35.     Adding this to the 48-bit value, d2
  38. Whenever you want to compare a distance, don't compute the square root! For example, if you want to see if the object is within 10000 units:
  39.     if (d2<=100000000){     //10000*100000
  40.         //Do something
  41.     }
  43. Let me know if you encounter a situation where a square root is necessary! I can either:
  44.     -Restructure the code so that it doesn't need a square root
  45.     -Create a fast square root algorithm that'll work on integers.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand