I can only think up an A* algorithm that uses path nodes for 1 entity. If I were to expand on this by increasing the number of active entities within a set world boundary, there will be many different A* algorithm generated paths for the entities to follow. Each path then will have to share the same nodes within the world, otherwise all the entities must wait until the active entity finishes its path, clears its path nodes, and it's the other's turn to start walking the other entity's own path.

I'm trying to solve the problem where two paths share some common path nodes. I can't have one node of one path have a parent of another node of another path; in other words, I can't have two path nodes have their parents intertwined together, otherwise it would be catastrophic, but much less than more than 2 entities active.

I could make one entity move until the entity reaches its target, wipe the path nodes in the world clean, then recalculate a new A* path for the other entity, but that wouldn't be realistic. I have also thought upon having the A* algorithm be embedded inside the entity structure, but the path nodes problem easily hinders this.

How do you solve this? Or in other words, how do I solve the problem of sharing same path nodes for different A* paths?

After a path is constructed, I copy the steps of the path to a path vector and hand that off to the entity, freeing up the pathfinder system to find a path for another unit.

Do you continuously copy the steps of the path to a unit's path vector, free up the pathfinder's system, repeat for the next unit, and so on?

I can think up one possible situation that if the first unit's path vector contains a path that overlaps the path of the second unit, the overlapped area of the two paths will contain path nodes that are unusable. Especially when the pathfinder has to start in the same game cycle tick.

A potential solution to this is to mark nodes as having a higher cost when they are likely to be occupied by other units, thereby causing A* to path around them. You also might want to solve this in your path-following logic rather than your path-finding logic. Getting unit avoidance to work well at the A* level is tricky and requires a lot of 4-dimensional math; path-following is a much easier place to handle the issue.

I just generate one path, hand it off to the unit that requested it, generate another for the next one, hand it off. If there are collisions along the route, it's not really the responsibility of the pathfinder to handle them. The pathfinder just finds a path. The path execution system that actually moves units is where the responsibility lies to resolve collisions, either by having one unit delay while another paths through, or by calling a local path solver (not a full path-find) to try to find a local solution to a blocked path.

Now, I suppose you could include fields in your nodes to mark them as blocked at a certain time, t. I'd probably implement this as a vector per node and incorporate the time-stamped block as part of the heuristic, to steer units around the blocked node. After a path executes a node step it would be responsible for clearing out any time blocks. Going this route just seems a bit overly complex to me, given that local collision resolution typically works well enough.

Pathfinding is plagued with the same kinds of temporal simulation complexities that physics are, with the additional burden of prediction. You probably aren't going to ever build the "perfect" pathfinder; about the best you can hope for is one that works "good enough" for your particular scenario.

As a last resort you could always cheat completely and let units pass through each other =)