Difference between revisions of "Thread:User talk:Voidious/BerryBots updates/reply (9)"
m (Reply to BerryBots updates) |
m |
||
| Line 1: | Line 1: | ||
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. | 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 | + | If your robot is using a pathfinding algorithm to navigate the walls, you could re-use 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. | 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 | + | In other words... nah... you can more or less reduce both the (# walls) term and the (# ticks per projection) term to much smaller numbers. |
Latest revision as of 01:09, 15 August 2013
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 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 reduce both the (# walls) term and the (# ticks per projection) term to much smaller numbers.
