If two agents are searching for the nearest object and one finds the object, I want the other to continue searching for a different object that hasn’t been “claimed”. For example, there is a forest of trees and each agent must find a closest tree. A tree can only be worked on by one agent at a time. Here is a gif of what I have so far:
Basically the agent searches for the nearest tree, once it finds one, it queues up a “claim” for that GridNode. All the queued claims are then added to a list of “claims” on their respective GridNode in a RegisterSafeUpdate call. I also have to immediately register a claim in the main thread so any agent that was searching when the RegisterSafeUpdate was called can know if the node it finds is in the process of being claimed, so it can start searching again.
Syncing all these “claims” is becoming a headache and its falling apart.
My plan now is to try using a thread safe collection from System.Collections.Concurrent so I can simply update the gridnode “claim” flags from any thread. Then any agent can know immediately while its searching using the XPath if the gridnode is claimed or not.
I’m sure other peolple have come across this problem, so I’m wondering what a good technique is. If it wasn’t obvious, I don’t have a lot of experience with multithreading or concurrency, so any advice would be much appreciated. Thanks!
My suggestion is to not try too hard to ensure it works even when multithreaded, that will just cause a lot of headaches. Instead assume that usually two agents will not find the same tree as the closest tree at the same time (their paths were searched in parallel), so what you would do is to search for the closest tree which is not currently claimed, and when that path has been calculated you check if the tree it found was actually not claimed by any other character in the meantime, if it was claimed, then you simply recalculate the path and hope for the best (which would under the above assumption usually work, in rare circumstances you might have to recalculate it more than once). You would still have to keep a list of claims though and the paths would have to check for them. I recently wrote some turn based utilities which might be applicable in this case, it keeps a list of nodes that are blocked for different groups of units like in a turn based game. It’s not really ready to be released yet, but I could send you a test version if you want.
Dang, it works so well if I just update the node claims in the GridGraph instantly (not in a RegisterSafeUpdate) with a List. The code is straight forward and all the agents behave exactly how I want and the agent count can scale up well.
That would cause a crash with multithreading at some point right? Couldn’t I just lock the threads and update the list, using a method like this: http://stackoverflow.com/a/1363187
Would the constant locking/unlocking as agents claim and release and search be a huge issue?
I’m only ever accessing my claims list in an XPath custom ending condition.
Also, your suggestion is essentially what I had before. Maybe I need to take another stab at it. My “claims” kept getting left behind by my agents so Im sure it was just some logical errors on my part.
thanks for the reply!
If you only need to lock it relatively rarely (not every node) then it should work fine with just locking on the list when you update and read from it.