The only code I have at the moment is a test program. I have yet to actually integrate it to the game I'm making.
I thought about keeping the portals in mind when calculating the heuristic value of each node. This would require me to do some pre-processing before each job, basically some pre-computed heuristics between portals based on the goal node. However, this is a similar problem to path-finding in itself, which means that I the pre-computing could get very very slow with many portals, possibly eliminating the gain from using the heuristics later completely (in an extreme case of course).
I have plans for some pretty advanced path-finding optimizations later, but for now, I'll just stick with Dijkstra's then. However the paths I get from Dijkstra's are pretty random and blocky, which might result in the path not being followed optimally by units since they aren't limited to 4 or 8 directions like the path-finding is. I think I need some kind of tie-breaker, but how is this implemented? I want a more straight line between corners. Currently (assuming 8 neighbors per node) it first only walks diagonally until it gets to the same X or Y as the target and then walks axis-aligned to the target, like this:
The light blue/teal node is the goal.
I obviously want it to move in a line towards when moving across larger spaces. How would I accomplish this? Obviously, such a path would have the exact same cost, but simply not be selected because the path above is the path it would find first.
