Pathfinding problem

[KGB]

SnotlinG,

Check out game 47731 (Darklords117).

My Ranger stack is sitting on a bridge in the lower middle section of the map. Select this stack and then click next to the city Ensifrum (down the road where the enemy Assassin sits). Notice the path that gets returned moves through the swamp/woods due to Ranger/Scout in the stack but ends up in the middle of those areas due to running out of moves. Now instead click on the road way 7 squares up from where it turns north (use the grid to get 7 squares). The path now returns that it can move there and I still have 2 moves left (thanks to a Dwarf in the stack)! This is a MUCH further move than the original path I got when I clicked next to the city.

Somehow the A* algorithm isn't taking into account reduced movement of 1 on hills from Dwarves.

KGB

[SnotlinG]

This is due to the Flyer in your stack. The flyer dont get benefit of the dwarf pathfinding cost 1, so the calculated path wont use the dwarf pathfinding to base its decision. In this case due to the low movementpoints of the dwarf it would have been better to do so, but its not within the current functionality of the pathfinding algorithm, since I then would need to take into consideration remaining movepoints of all units in the stack etc. For in the case the Flyer happened to have less movepoints left, it would be bad for the stack to go the "dwarf-path"...

Its a tricky one this one, but this is the current solution for stacks including flyers.

[KGB]

SnotlinG,

I've worked with the A* algorithm before myself. So I'm reasonable familiar with it.

When you are calculating paths, it's supposed to expand nodes (squares in the map case) in all directions and calculate the move cost. But you can define the cost to be anything you want. Right now it appears you are defining the cost as the cost for a unit to move there (2 for fliers, X for land units based on terrain bonus) and taking the lowest value.

But if instead you changed the cost to return the minimum amount of movement points left for any unit in the stack (ie the fewest points left for any unit in the stack) and tried to maximize that (ie select the one with the most points left) wouldn't that solve the problem?

KGB

[SnotlinG]

Without spending too much time investigating it I think your solution would solve the issue. But my problem is the "cost" associated with it.
I would then need to store remaining move for all units in the stack on all nodes, and when checking each node I would need to lookup the movecost as many times as units in the stack. Im afraid this would make the function notably slower (I havent tested this though).
But this is the main reason why I havent gone down that road yet. Since the current solution also works pretty well, it is just in very rare cases it gives some not 100% optimal path.

Anyway, this is one thing I will add down on my todo-list for optimization and investigate more properly when I get the time

[Chazar]

Well, it would be enough to compute for each different move behaviour in the stack, so in most cases it would just double the time.

All land units often move at the same speed, so it would suffice to calculate just for the land unit with the lowest move and flyer with the lowest move. This is a common combination, and dealing with it would already help a lot, even when ignoring non-leading terrain specialists like scorpions.

[SnotlinG]

Yes its a good point, but do you think it would be worth the double wait-time for path calculations for fixing this (quite rarely happening) issue?

[Chazar]

Well, I personally only experience a long wait time for pathfinding if and only if there is no possible path, so if only there would be a way to shortcut the pathfinding algorithm for impossible paths...

So maybe I am not using the slowest hardware to play, but even if I would, I would welcome such an optimisation: I spend a lot of time to optimise my turns. Even if pathfinding would be slow for me, it would still be faster overall than me trying out to split up the stack to increase overall range - which I actually do for mixed stacks, at least if they contain a hero. So while it might annoy real-time players, I would guess that most hardcore strategy gamers would welcome improved pathfinding, if the wait time only increases for mixed stacks.

[KGB]

SnotlinG,

I too think it's worth it. I play on both fast and slow (5 year old PC) hardware. Even on the slow PC, the path finding completes immediately other than the impossible case Chazar mentions (likely this means there is a bug in your algorithm that isn't marking nodes as 'visited' and you are in an endless loop revisiting squares you already checked).

However due to cases like the Scorpion (as Chazar notes) or differing boat types/sea unit mixtures, you can't just compute 3 (land, air, water) types of moves. You have to compute one for each unit which means worst case 8 different calcs which will still happen instantly.

KGB