Precalculating mouse zones?
Blitz3D Forums/Blitz3D Programming/Precalculating mouse zones?
| ||
| I have a bunch of points on the screen, around 120 of them. At any given time, I will want to know which of them the mouse pointer is nearest to. Clearly I can do this by calculating the distance, but that 120 calculations every frame or two, and since the points never move, it seems like a waste really. So I'm just wondering if anyone has any good pieces of lateral thinking which might enable me to precalculate or speed this up in some way. The points are relatively equally spread out, but they're not in an easily recognizable pattern, so I don't think I can do it purely mathematically as I could if it was a squared grid. I suppose I could precalculate every pixel in a 800x600 array too, but that seems like memory overkill, huh? :P Any other ideas on making this fast? |
| ||
| Wow! Interesting problem! Here are some ideas: A cheap and dirty solution might be to divide the screen up into a small number of sectors, and have a hardcoded list of which points the mouse might be closest to in each sector, then calculate the distance between each of them. For a slight optimization you can cheat and forego taking the squareroot if you're comparing distances. Or you could determine the bounding boxes for each point's area of control. Then you'd need to get a list of all the bounding boxes which contain the mouse and check the distance between the mouse and each point. Instead of checking distances, you might be able to rely on the fact that the areas each point controls will be separated by a line. A straight line. A line that you can use mathematically to figure out which of two points the mouse is closest to. If you wouldn't mind, post a screenshot of your 800x600 precalculated array. I find this kind of problem easier to deal with if I can visualize it. :) |
| ||
| A way crazier idea! This relies on the fact that areas of control will be polygons, and I can't imagine them having any concave parts. Instead of starting from scratch each frame, assume that the mouse hasn't moved far and keep track of the polygon the mouse was in last frame. Keep track of each polygon's neighbours (for each edge.) When the mouse leaves the polygon, guess which edge it left via (by figuring out which two radii it's between) and check if it's in that polygon. If the player moves the mouse extremely quickly, you might have to chase it through several polygons. |
| ||
| You would be surprised how fast a distance calculation is Syb. This on my computer takes between 1 and 2 milli-seconds and it's doing 10,000 distance checks. I can't measure any lower really. Delay 100 x# = 100 y# = 200 Dim array(10000,1) For loop = 0 To 10000 array(loop,0) = Rand(0,800) ; x co-ord array(loop,1) = Rand(0,600) ; y co-ord Next time = MilliSecs() For loop = 0 To 10000 d# = Sqr( (array(loop,0)-x)*(array(loop,0)-x) + (array(loop,1)-y)*(array(loop,0)-y)) Next Print "Time taken = " + (MilliSecs() - time) |
| ||
| Some interesting thoughts there, Octothorpe, thanks for those. I'll see if I can find a good way to represent the zones as an image so that I can post that. I guess a different color for each zone would work. Thanks for bringing that to my attention, Ross. It does seem that it's probably overkill to optimize this. If a 2200 can do 10,000 checks in one millisecond, then I probably don't need to worry about doing 100-150 of them on anything greater than a 486DX. I can even optimize it further because - as Octothorpe mentions - I don't need to Square Root if I'm comparing like with like. In fact, in BlitzMax, I have to go up to 1,000,000 calculations before it actually takes 1 millisecond. |
| ||
| I'm sure this is crying out for a binary partition (Quadtree)treatment (like a BSP but even simpler since it will only be in 2D) In essence, make a binary tree that holds the coords of each of your 120 points and walk the tree to home in on the coord you are nearest to. |
   |