The sample graph contains a good example of this: if an Action provides a similar effect to an Item (e.g. a renewable resource like rupees in OoT), then the naive minimization skips those locations. And if the Action is then much slower than collecting the Item would have been, then the minimization fails.
Possible solutions:
Allow actions to be marked as skippable, and skip all actions not used in the initial run. Obviously this won't work if the action is required, but it could be a speedup otherwise.
Make a can_win_in_time function... it would be a full nested search, but ideally we could cache the states at each history step (we should do this anyway?)
Make minimize run a full nested search with allow_skips on, after clearing out all the locations we didn't use. Although, it doesn't have to be nested, technically we could just add a new ctx to the main search heap.
The sample graph contains a good example of this: if an Action provides a similar effect to an Item (e.g. a renewable resource like rupees in OoT), then the naive minimization skips those locations. And if the Action is then much slower than collecting the Item would have been, then the minimization fails.
Possible solutions:
can_win_in_time
function... it would be a full nested search, but ideally we could cache the states at each history step (we should do this anyway?)minimize
run a full nested search withallow_skips
on, after clearing out all the locations we didn't use. Although, it doesn't have to be nested, technically we could just add a new ctx to the main search heap.