tag:blogger.com,1999:blog-5439941893980599296.post8767214310293426872..comments2023-09-24T07:49:19.084-04:00Comments on Games By Design Has Moved!: Range Checks - Approximation vs AccurateChristopher M. Parkhttp://www.blogger.com/profile/16719365007524426389noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-5439941893980599296.post-43288403145584948702012-09-09T13:49:59.110-04:002012-09-09T13:49:59.110-04:00@Keith (and Anonymous right above): I think it sho...@Keith (and Anonymous right above): I think it should be min*sqrt(2) + (max - min); min*sqrt(2) is diagonal distance, max-min is the cardinal distance. maybe that's the solution?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-80526420846761724142012-01-02T11:24:57.187-05:002012-01-02T11:24:57.187-05:00Maybe I'm missing something pretty basic (did ...Maybe I'm missing something pretty basic (did just get back to work for the year), but how is:<br /><br />"distance = min + (max - min);"<br /><br />not equivalent to <br /><br />"distance = max;"?<br /><br />and thus:<br /><br />"distance = x < y ? y : x"<br /><br />also, I'm assuming x means "abs(point1.x - point2.x)" and y means "abs(point1.y - point2.y)" but I'm not sure you intended that.Keith LaMothehttps://www.blogger.com/profile/00233241503840373341noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-18540578012790931062012-01-01T15:08:17.516-05:002012-01-01T15:08:17.516-05:00Very fast, accurate enough at longer distances:
m...Very fast, accurate enough at longer distances:<br /><br />min = x < y ? x : y;<br />max = x < y ? y : x;<br />distance = min + (max - min);<br /><br />This gets you the 45-degree diagonal distance (min) plus the remaining vertical or horizontal distance (max - min). Plus, it's two compares, three assignments, an addition and a subtraction.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-73713641767089111292009-12-08T12:21:20.591-05:002009-12-08T12:21:20.591-05:00Well, I had also thought to do something like that...Well, I had also thought to do something like that (as I do that sort of thing in a variety of other areas, such as precalculating deceleration rates based on distance to target, or Sine table, etc), but the problem is one of scale here. In a game with a maximum fixed size map, I could see that working very well, but here the possible range is -2 billion to +2 billion ion both the Z and Y directions. Generally plays stick to the -80 thousand to +80 thousand on the range of ship positions, but even that is way to huge to precalculate and store in memory.<br /><br />Unless I'm missing something about what you're suggesting, that would be 160,000x160,000 = 25.6 billion points just in that smaller area, and then it would need to calculate 25.6 billion x 25.6 billion (which is some astronomical number that I don't think has a name) in order to get all of the possible distances between points.<br /><br />Now, some of that might be able to be simplified out, certainly, by figuring out the x and y differences and then using some formula to determine the distance between the points. That could work, especially if I noted to consider anything greater than (say) 100,000 units distant to be equally "very far away." That would be only 100,000 precalculations and an array lookup into a 100,000-long array. And even that would only use something like 390kb of space in RAM, so it's absolutely negligible.<br /><br />I don't know a good formula for getting the distance between points based on and x and y differential, though. Anyone have any ideas on that?Christopher M. Parkhttps://www.blogger.com/profile/16719365007524426389noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-30982214680995144162009-12-08T10:45:08.071-05:002009-12-08T10:45:08.071-05:00What about a tradeoff memory-space against cpu-tim...What about a tradeoff memory-space against cpu-time?<br />Just make a table and lookup the value using a select-statement...<br /> <br />The pre-calculation of the table is done in a second, i recommend to /8 the precision.<br /><br />The lookup can also be done with a select-statement.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-67658021506160826492009-07-20T13:49:18.393-04:002009-07-20T13:49:18.393-04:00This is true, for relative distance comparisons, y...This is true, for relative distance comparisons, you can just use that method and it will be faster than the Sqrt method. However, often I am also needing to find a reasonably accurate actual distance to a location (to know if I am at all in range, etc), and that's where the least squares method that I linked to is really invaluable. It is super fast in general, so just using that all the time does plenty well enough for most of my purposes. The only time I use the Sqrt-based distance checks is when I need to very precisely know the distance between two points for some reason (which is almost never).Christopher M. Parkhttps://www.blogger.com/profile/16719365007524426389noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-90918901650535822592009-07-20T13:29:49.784-04:002009-07-20T13:29:49.784-04:00As Amit said, why bother using sqrt at all? Just c...As Amit said, why bother using sqrt at all? Just compare the distances squared. If all you need to know is which of a bunch of things are closest, or similar, doing the comparison with the squared values is perfectly valid, and much faster.Anonymoushttps://www.blogger.com/profile/17109535630739441404noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-19515533410170476122009-07-19T14:13:22.941-04:002009-07-19T14:13:22.941-04:00The other reason for not using the FPU is for sync...The other reason for not using the FPU is for synchronous operations in different CPU/FPU operations. Basically, different FPU and CPU architectures can have very slightly different results, given the inherent way that floating-point is calculated. When you are writing a synchronized simulation that has to run exactly the same on multiple machines at once, then even slight variances can add up over time and cause a desync. So there is a speed component to this, as well as a need for something that will run the same on any CPU architecture.<br /><br />Plus, these techniques work on smaller devices such as the Nintendo DS, which doesn't have an FPU. So there fixed-point math is really common in environments like that.Christopher M. Parkhttps://www.blogger.com/profile/16719365007524426389noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-44462231111284097882009-07-19T14:09:22.920-04:002009-07-19T14:09:22.920-04:00That's the one! Thanks, Anonymous, I've u...That's the one! Thanks, Anonymous, I've updated the article to just link to his original code.Christopher M. Parkhttps://www.blogger.com/profile/16719365007524426389noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-51210104382992743302009-07-19T13:51:46.210-04:002009-07-19T13:51:46.210-04:00Square root may be iterative, but it should be sen...Square root may be iterative, but it should be sent directly to your floating point processor, where it is a hardware operation.<br /><br />Actually, the whole distance function should be optimized into something that never gets off the FPU. Otherwise your compiler is broken.<br /><br />If this is really a speed issue, you should submit it to Microsoft as a bug in .NET.Fred Rosshttps://www.blogger.com/profile/14346595409269776793noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-16094429582302159892009-07-19T12:31:15.706-04:002009-07-19T12:31:15.706-04:00You might not need the Abs() calls; it seems that ...You might not need the Abs() calls; it seems that the arguments are always positive (except maybe you have overflow).<br /><br />If there's a fixed range I want to check against, e.g., code like “Distance(a,b) <= 30”, then you can gain some speed by replacing that with “DistanceSquared(a,b) <= 30*30”. Essentially instead of testing sqrt(xyz) <= pqr, you square both sides and test xyz <= pqr*pqr. Much cheaper :-)Amithttps://www.blogger.com/profile/12159325271882018300noreply@blogger.comtag:blogger.com,1999:blog-5439941893980599296.post-68334078880196684652009-07-19T11:54:14.618-04:002009-07-19T11:54:14.618-04:00Maybe from here?
http://www.flipcode.com/archives...Maybe from here?<br /><br />http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtmlAnonymousnoreply@blogger.com