If there were 5 units in each occupied 10x10 block, then there would be 4n sight checks. You don't check every unit against every tile in the block, you check every unit against every other unit in the block. Also, your 100n estimation for the blocks approach is off. The second rectangular blocks part was about eliding unnecessary sight checks. When deleting a unit, swap the unit in the vector with the last unit, then remove from the back. I've realized that the fastest solution is very simple. The data structure is not for speeding up individual 1-on-1 sight checks. By O(1) iteration I meant O(1) from one unit to the next. The data structure was about storing units in such a way that there is fast deletion and iteration. Just make it a periodic check when iterating through the table that if any of the pointers refer to dead units, to delete them from the vector before continuing. Yes, removing from the middle of a vector isn't optimal, but that doesn't matter because this is a one-time event any time a unit dies/leaves.
I think a more immediate optimization is clearing out dead units from the vector.
Meaning if you're checking, say, a 10x10 rectangle around every unit, that this only becomes more optimal at 100 units on the map or more. Depending on the size of P, this might not scale as well as you'd hope it only becomes more efficient once you have more units than P. Limiting it to a rectangle would trade-off O(n^2) for O(Pn) where P is the number of tiles in this rectangle. The problem is having to, per unit, check against literally every other unit on the map, is slow in principle. The problem isn't actually evaluating the line of sight. The point is that it's checking every unit against every other unit to work out whether or not they can see each other.
0 kommentar(er)
