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

New issue

Open

opened 2024-10-10 16:20:15 +00:00 by BlakeRain · 0 comments

BlakeRain commented

2024-10-10 16:20:15 +00:00

(Migrated from github.com)

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.

No labels

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

bans-minecraft/bans-automata#1

No description provided.

Rows
Columns