Strip miner AA is getting too big, and loop has no yields #6

New Issue

BlakeRain · 2023-12-23T11:09:47Z

BlakeRain commented

2023-12-23 11:09:47 +00:00

Currently our scan of the open set has a significant time complexity, as we're iterating over the open-set twice far too often.

while #open_set > 0:
  for other in open_set:
    -- Check if fScore is lower

The inner for-loop is used to find the node with the lowest fScore in the open set. This can get very expensive as the open set expands in size. We are seeing this start to manifest in the bots as a Too long without yielding error being raised from the runtime.

To address this, we need to make a couple of changes:

Use a min-heap or priority queue for the open set, ordered by the fScore. This way we can pop a node from the min-heap (or priority queue) and know that it is the lowest scoring node. This adds a bit more cost to each insertion, but will massively reduce the amount of processing required for the bots to path-find.
Trim the AA of the strip miner to remove redundant parts of the AA. This could either be a manual scan of the AA to remove branches that are no longer required. Alternatively a TTL could be added to AA nodes, effectively giving the bot a short-term memory.

Currently our scan of the open set has a significant time complexity, as we're iterating over the open-set twice far too often. ```lua while #open_set > 0: for other in open_set: -- Check if fScore is lower ``` The inner for-loop is used to find the node with the lowest `fScore` in the open set. This can get very expensive as the open set expands in size. We are seeing this start to manifest in the bots as a `Too long without yielding` error being raised from the runtime. To address this, we need to make a couple of changes: 1. Use a min-heap or priority queue for the open set, ordered by the `fScore`. This way we can pop a node from the min-heap (or priority queue) and know that it is the lowest scoring node. This adds a bit more cost to each insertion, but will massively reduce the amount of processing required for the bots to path-find. 2. Trim the AA of the strip miner to remove redundant parts of the AA. This could either be a manual scan of the AA to remove branches that are no longer required. Alternatively a TTL could be added to AA nodes, effectively giving the bot a short-term memory.

BlakeRain added the

bug

label 2023-12-23 11:09:47 +00:00

BlakeRain self-assigned this 2023-12-23 11:09:47 +00:00

Sign in to join this conversation.