1
\$\begingroup\$

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:

  1. 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.
  2. 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.

Edit

This is what I ended up with (after reading Kromster's answer):

  1. Update the data
  2. Take requests out from the queue and start a thread for each request.
  3. For each frame: check if all threads have finished.
  4. 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.

\$\endgroup\$
  • \$\begingroup\$ For the record, I'm pretty sure that a collection of 'atomics' is just as unsafe as any collection. Unless you synchronise access to the collection, it will remain unsafe. \$\endgroup\$ – zcabjro Aug 10 '16 at 15:45
  • \$\begingroup\$ Yes, using containers should be unsafe if you modify the container. However, reading/writing to an atomic stored inside a simple array should be safe, should it not? As long as you don't change the array's structure, your only concern should be the values inside array. If they are atomic, I suppose you are safe - or did I misunderstand something important? \$\endgroup\$ – MyNiceDisplayName Aug 11 '16 at 10:18
0
\$\begingroup\$

I would expect all pathfinders working in threads while the rest of the game is busy with other things unrelated to map changing. So map structure could be locked from updates and be in read-only mode while pathfinders do their work.

Of course such system is handy when you do have several lengthy paths to build on each tick or other tasks that can be parallelized (think at least thousands of non-cache-friendly agents on a map).

\$\endgroup\$
  • \$\begingroup\$ Ok, so you mean a loop like this? : 1. Update data. 2. Take requests out from the queue and start some threads. 3. For each frame: check if all threads are done. 4. When all threads are done, go back to step 1. With a solution like this, there might be times when you have only one or two threads running - so we won't be keeping all the threads busy all the time.. However, considering that we won't have to do synchronisation, I guess it is worth it? \$\endgroup\$ – MyNiceDisplayName Aug 9 '16 at 18:25
  • \$\begingroup\$ ... after some testing, I guess that's the best way to do it after all. Thank you! \$\endgroup\$ – MyNiceDisplayName Aug 9 '16 at 20:26
  • \$\begingroup\$ Ah okay. If you've effectively made the container immutable and its contents atomic, I don't see a problem. Apologies for the confusion! \$\endgroup\$ – zcabjro Aug 11 '16 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.