A common way of writing path finding AI for team coordination is to temporarily attach extra weight to an edge in the middle of the path taken by one of the characters. This makes other team members tend to favor paths which do not cross this edge. How can this be effectively implemented? The following are the requirements: - "base weight": exists for every edge and they never change - "weight modifiers": the modifiers attached by character X are only of interest to members of the same team as X. When another team uses the graph to run a path finding algorithm, they don't want another team to have left traces of their weight modifiers. - the solution should be as multi-threading friendly as possible There are two obvious solutions: 1. using a dictionary data structure for each team, holding a mapping "edge id" -> "weight modifier". During path finding with Dijkstra or A*, each weight lookup is replaced by summing the lookup of the base weight with any weight modifier for this edge that could be found in the map. - Problem: the more expensive edge weight lookup can increase algorithm complexity by a factor of O(log N) if we use a tree-based dictionary. A hash table is also likely to slow down considerably due to cache unfriendliness. This extra lookup time is also really wasteful since it's expensive to also lookup elements that don't exist in the dictionary, and this is the case for most edges since only a small percentage of edges will have modifiers attached to them. 2. modifying the graph directly, using mutex locks, and ensuring all members of a particular team are run in succession, so that the modified edge data is valid. After a team has finished, they reset the edge weights (for example by storing changes made in a dictionary data structure). - Problem: not very granular locking. Also difficult to implement things such as prioritizing AI characters close to the camera, since all members of a certain team must be run in succession. Both of the obvious solutions seem to have severe drawbacks. Are there any better ways of doing this?

Create a separate copy of the graph data to be modified for each team.

Hm, that might actually work... perhaps with some hierarchical graph layout I'll only need to duplicate parts of the graph.

Also if you limit the range of values the weight modifiers can have, you could pack them into a smaller space. For example, if you limit the modifiers to be a multiple of some value X, and limit the maximum modifier to 255*X, you can pack the modifier into just 8 bits and fit the modifier for 4 teams into a single word.

You might be able to do something which leaves a tag on a found path (implemented viz a link list off the nodes) that marks when the preceding objects (team members) were expected to traverse that node and adjust your cost mechanism to block moving into that node when the following object tests if it should enter that spacce at its estimated arrival time. The temporal tag might be a time instant or be a span of tim,e (make wider if the 'estimates' are not too accurate). After the alotted time for that object is up, the space would be available again for other objects to move thru.

As long as the movements are reasonably predictable it can work (subsequent objects avoid the spots where preceding objects are at node points at specific times).

If you have alot of parallel paths fairly open terrain) objects can move side by side.

Optimization might be to give slower/less maneuverable objects preference (since the faster ones can catch up when needed). Possiblly the objects closer to the target should be pathed fisrts -- if all move at similar speeds they then will vacate space as the ones farther back whould need them to move into,

Some added mechanism to the 'path' may require a null move (wait) cycle for a period of time if there are choke points (units have to halt to wait for a choke point to clear -- it has to be part of tghe path move directives generated for each unit). Possibly too a similar slowdown action to waste some time without halting....)