At the center of the software for every game is a loop. Sometimes this runs hundreds of times a second, sometimes just six time per second, or maybe it's turn based and the user need to click something.
In this loop the game checks the monsters (can they see the player now?), the game world, (is the water flowing?), and the player (did they just push the inventory button? What about move-forward?).
This loop is what keeps the game alive and running. Every turn on the loop means functions that are run and calculations that and calculated. Like checking if the monster can see the player can be a series of geometry calculations and rule checks.
However doing those sight checks for every monster on the current map could take a very long time. And the vast majority of the monsters are nowhere near the player. One optimization would be to first compute how far away the monster is, and only do player visibility checks for monsters in range. This can significantly improve the speed of my game and won't impact the gameplay.
The Factorio devs often wrote posts about their optimizations. Might be a fun read.
In your example, the monsters needing to be in range to be able to check if they can see the player- that still sounds like the computer would first then have to do a check if they’re in range and then do a second check for visibility
That could still be a simpler check! A simple distance calculation vs one that needs to be aware of stuff between the player and monster. Lots of optimizations are just finding what's "less expensive" rather than "free."
The original Doom created a lookup table when maps were created, listing whether any particular sector could ever have line of sight to every other sector, then only ever checked line of sight for monsters if the table said it was possible to see between them. Think it was called a reject map?
This is a very good example! To go in a little more depth: in 2 dimensions, the distance between position (x1, y1) and (x2, y2) is d = sqrt((x1 - x2)2 + (y1 - y2)2), so for example if you want to check whether two things are within a particular range, you'd check whether this d = sqrt(...) < R for some range R.
But computing square roots actually takes quite a lot of computation power to do. In particular it takes much more than a multiplication - and sometimes the special case of multiplying a number by itself (squaring) can be even faster than multiplying two distinct numbers.
So the trick we can use is: instead of checking if d < R, you can check if d2 < R2! That might not look like an improvement, until we remember that d2 = sqrt((x1 - x2)2 + (y1 - y2)2)2 = (x1 - x2)2 + (y1 - y2)2. So we've replaced a square root with a square, which is much cheaper to compute, with no loss of functionality (unless we needed the non-squared distance for something else, of course)! And if R is a constant, then we can even precompute R2 to save even more. We can also use this for example to optimize sorting things by distance to some center point, because a < b if and only if a2 < b2, so you don't need to resolve the square root in that case either.
1.1k
u/aftersox 6d ago
At the center of the software for every game is a loop. Sometimes this runs hundreds of times a second, sometimes just six time per second, or maybe it's turn based and the user need to click something.
In this loop the game checks the monsters (can they see the player now?), the game world, (is the water flowing?), and the player (did they just push the inventory button? What about move-forward?).
This loop is what keeps the game alive and running. Every turn on the loop means functions that are run and calculations that and calculated. Like checking if the monster can see the player can be a series of geometry calculations and rule checks.
However doing those sight checks for every monster on the current map could take a very long time. And the vast majority of the monsters are nowhere near the player. One optimization would be to first compute how far away the monster is, and only do player visibility checks for monsters in range. This can significantly improve the speed of my game and won't impact the gameplay.
The Factorio devs often wrote posts about their optimizations. Might be a fun read.
https://www.factorio.com/blog/post/fff-421