Imagine a case where you have lots agents in a big world, who frequently need to calculate the shortest/best path from A to B. In this case it seems natural for me to create a pathfinding engine where each path request is performed in a separate thread. Similar to this example. Requests are stored in a queue, and when there are available threads to perform calculation the request will be taken from the queue and finally moved to a collection of calculated paths.
My problem is: how do you store and update the data that will be shared among all the threads? The threads needs access to some kind of map structure (could be a 2D array), and his data needs to be updated frequently. Using some kind of synchronisation mechanism would be too expensive, since we have several threads frequently reading from the data.
I have come up with two suggestions:
- Store the map structure as an array of atomics. This seems like a simple and effective solution, however we will give ourself a limitation: we can only use data that can be stored as an atomic type - which in most cases should be OK.
- Create two buffers containing a copy of the data, and keep a reference count for how many threads are currently using the buffer. First update buffer A, then for each new path request we let the thread read from buffer A. When there are no more threads accessing buffer B (RefCount==0) update buffer B and set it as the new active buffer. With this solution we can use any kind of data structure, but it will (depending on the calculation time) be slightly out of sync - which I believe should not be a big problem for pathfinding. If the calculations take a long time, it will be out of sync anyway.
What are your thoughts? I don't have too much experience in the field, so I'm not sure if there are any "popular" solutions to this problem.
This is what I ended up with (after reading Kromster's answer):
- Update the data
- Take requests out from the queue and start a thread for each request.
- For each frame: check if all threads have finished.
- When all threads are done, go back to step 1.
At step 1, all worker threads are idle.
When an agent needs to get a path from A to B, it will call requestPath(from, to), which will return a unique ticket. The ticket has an atomic(modified by pathfinder thread, accessed by agent) indicating whether it is valid or not. When the path has been caluclated, the ticket becomes valid and the agent can call getPath(ticket) to get the path.