BerryBots updates
You don't need to do that many line intersection checks. If you store your walls in a tree (i.e. r-tree or bucket kd-tree), or even a sorted list (sorting by one of the two axis), you can avoid needing to check every single wall by quickly ruling out large groups of walls that are too far away.
If your robot is using a pathfinding algorithm to navigate the walls, you could re-use the that structure to find which walls you need to check (if any) to avoid needing new structures to search walls (i.e. track the current pathfinding node, and use that node's information to know which boundaries to check on a tick if any).
To save per-tick iterations, you can also use a trick I've used and seen used in PIF implementations: Based on the minimum number of ticks away waves/walls are, you can skip ahead in your PIF history, ignoring all the ticks inbetween.
In other words... nah... you can more or less put the (# walls) term inside a log(n), and reduce the (# ticks per projection) to something significantly smaller too
Thanks for the ideas! I love the kd-tree/sorted list one. I might have to go back and optimize it in the main game engine.
I'd say for that purpose r-trees are more suited than kd-trees, but yeah. From what I've heard, it's very much standard practice to use r-trees or other structures for collision detection in game engines where you have a very large number of entities/surfaces/etc which you may want to perform collision detection with.
With regards to 'other structures', so long as things are in a bounded size region and the density variation of objects is not too extreme, rather than a tree you'd probably get better results taking a very simple approach: Divide the area into a 2d grid, scaled so that you have a no more than a few entities in each cell, and in each cell store a list of entities which are within that cell. The only reasons to use a tree instead of a coarse array, is when the density of collidable objects/surfaces varies significantly between areas (i.e. you don't want lots of cells that are near-empty with other cells that have thousands of objects)
