Non-Blocking AI Routine
Monkey Forums/Monkey Programming/Non-Blocking AI Routine
| ||
| Hi, I'd like to ask for suggestions on the best method to proceed. I'm porting an old game to Monkey in order to learn Monkey better. My game has an AI that uses a Minimax tree (well, actually Maximin tree, since it's not zero-sum) to determine what move to make. Additionally, it builds the tree recursively. The problem lies in that the AI routine can theoretically take seconds to complete, which means that rendering/updating would be blocked during that time. On another platform, I might create a worker thread to do the work, but not all Monkey targets support that approach, and I'm not sure Monkey is mature enough for that route yet. I thought of implementing it via an asynchronous/timesliced ("DoWork()") method, but I think I would have to convert my existing recursive algorithm into an iterative one. That's feasible, I guess, but I rather like how it's working now. And I don't really look forward to rolling my own chunking method. Any other suggestions? Thank you in advance. |
| ||
| Yes, replacing your recursive method with an iterative one is a must. You could use time measurement to let your routine return after 20ms for instance. Just remember the last state and continue there. |
| ||
| I did this in Detective Chess where it runs a recursive algorithm that can take several seconds. You just have to create your own stack. If you are calling a single function recursively, the easiest thing to do is make a class that holds a copy of each local object/value in that function. Then make a stack or array of instances of that class. You can quit temporarily after any partial iteration, and all you need to remember is which one you were pointing at. (I didn't allocate new ones, just wrote over the current one when I re-entered at that depth.) You can do x number of calculations per render/update and then quit until the next render/update. Usually you'll want to draw a progress bar too. |
   |