So I have a A* implementation that works pretty well however there is one thing I am not able to wrap my head around.

This game is turn based and after the player moves, all the other entities move at the same time. The issue I am trying to figure out how to handle is preventing the entities from occupying the same tile at the same time. Since all the entities move at the same time (which is needed as there could be a few dozen being simulated and moving each one on their own would take away to long), how would I be able to make sure an entity would not occupy the same tile?

From my experience you just have two options for this:

1. Calculate the final position of every unit one-by-one. You can't avoid doing this if you want really good outcome because it is more work to predict every move to make an optimal move on every unit vs. doing every move one after another
2. Life with unoptomal outcomes. This is what most games do when it comes to wayfinding, for example in an RTS game. You move every unit to the desired point and if it is already occupied then stay at the nearest possible location

If it really takes that long to move every unit one-by-one than you must probably optimize your code or use a solution where you parallelize your code in some way to come to a good outcome. For example if two units are garantueed to not be able to move to the same location because you are grid based and the moving is capped for certain range, then you could parallelize their steps

Agree with Shaarigan,

If its turn based, time isn't an issue to calculate each units path one by one, in the order they move. This will enable them to be a bit smarter moving around each other. So calculate the hex they want to get to, the path (stored as vectors) and then evaluate each unit moving one hex at a time, if a hex is blocked recalculate the path again at that time.

One way to make sure all units move as they should (if they have different movement speeds, or terrain has different costs) is to create an “impulse chart”. This is a boolean table that breaks a turn down into “phases” based on the maximum units speed.

For example, if you have a unit with a movement of 12 hexes per turn, you would need to break the turn into 12 phases. A unit with a movement speed of 12 would move one hex per phase, while a unit with a movement of 6 would move every second phase. A unit with move 1 would move only on phase 6.

You then calculate the movement cost to enter a hex, and each unit ‘spends’ a movement point in each phase. For example, the unit with move 12 would enter a forest hex with a cost of 3 movement points on phase 3, but the unit with movement 6 would enter that hex on phase 6.

example: