Intro
Computational Geometry is a field of Computer Science that focuses on efficient algorithms to solve problems involving geometric data, such as points, lines, and polygons.
In relation to Game AI, it can involve converting the game world into a data structure that can work for path planning. The process of discretization addresses things like
- Point containment
- line intersections
- triangulation- Breaking down a complicated polygon into more manageable shapes
Applications:
- Robotics: Path planning and obstacle avoidance.
- Computer Graphics/CAD: Mesh generation, modeling, and rendering.
- GIS: Geographic Information Systems (e.g., spatial searching).
- Autonomous Vehicles: Processing LiDAR data.
Difficulty
- floating point precision
- degenerate cases (collinear points, overlapping lines)
- algorithmic complexity
Floating-point vectors
Float variation
Floating point with Epsilon
- Epsilon- An area around the target value accepted as “close enough”
Edge cases and point of failure
Integer solution
- Multiply each float by a number (e.g. 1000) and cast to an integer
- This way keeps the fractional part of the float
- Can convert back to floats
When to convert?
- Overhead of converting to integers
- Do the conversion outside of the game
- Bake computational geometry data structures during the build process
- Baking process- after compiling the game, run some tools that prepare the data before deploying the game to a playable process
- In Unity, can bake computationally expensive things in order to cache/preserve the data until the game is run
- NavMesh
- precomputed lighting effects
Integer representation problem
- Overflow
- many languages don’t throw exceptions on an overflow
- Can reorder equation terms to avoid overflow