Ok, didn't get a patch on the weekend obviously, and I still don't have one for you. But it is coming... less than 24 hours... sorry to 'tease', but I wanted to report some more results, and I'm to tired to get a patch ready tonight.
I can't break it anymore (can't crash the game), and I'm happy with the performance, so I'll package it up tomorrow night, and some other people can try to break it.
A quick note: it's Faster, not Smarter.
It's essentially the same algorithm as before, I just changed how the tests were performed, how the open & closed lists are implemented, and introduced some preprocessing to try and quickly determine if the target is unreachable.
That is what was really killing the path finder as it was, A* failing to find a path is the worst case scenario (for processing time), and when many workers are going for the same resources, they often block access to the 'destination position' another worker wants to go back to. That spot might be three tiles away, but because it's "blocked in" the resulting A* search exhausts 400 nodes trying to get to it, fails and picks the 'least heuristic' to go to (often where he is already standing), next update? repeat. This is what was causing 'the' Glest slow down.
I've played a few games through with the new path finder now, and I can report no sudden frame rate drops, and I was getting chronic frame rate drops before.
Here's some numbers from the log of my most recent timing test, 1 human, 3 AIs, a tampered with MagiTech techtree (to accelerate things a bit... I've been doing a lot of testing...), all on teams of their own, Teams 0 and 2 were hooked up to the shiny new annotated A*, teams 1 & 3 used the old A*. The 'average' and 'worst' are measured in 'clock ticks'.
23: Launching game
81:
Vanilla A* : Total Calls: 143, Average: 314, Worst: 23935.
Annotated A* : Total Calls: 129, Average: 86, Worst: 970.
111:
Vanilla A* : Total Calls: 366, Average: 1580, Worst: 43239.
Annotated A* : Total Calls: 341, Average: 76, Worst: 1930.
<snip>
261:
Vanilla A* : Total Calls: 2133, Average: 2290, Worst: 43239.
Annotated A* : Total Calls: 2337, Average: 41, Worst: 5946.
<snip>
411:
Vanilla A* : Total Calls: 3656, Average: 2803, Worst: 52071.
Annotated A* : Total Calls: 4701, Average: 28, Worst: 6039.
<snip>
651:
Vanilla A* : Total Calls: 7324, Average: 5329, Worst: 53211.
Annotated A* : Total Calls: 10736, Average: 18, Worst: 9355.
<snip>
831:
Vanilla A* : Total Calls: 8969, Average: 4044, Worst: 53211.
Annotated A* : Total Calls: 14464, Average: 18, Worst: 9355.
As you might imagine from the average call time, the speed up is rather substantial.
More details, and the all important patch, to follow tomorrow...
Perhaps some time in the distant future different conditions might affect movement or other qualities (like defence). For example if you were walking
knee deep in mud it's going to be slower than walking on hard ground. These things would need to be included in the pathfinding.
Yeah, that would obviously need to be taken into account by the pathfinder, I was thinking of doing influence maps (for better ai players) some point down the line, these too will need to be taken into account by the pathfinder, we can use the same mechanism, I'll make it (down the line) so the pathfinder can be handed one or more influence maps when asked to calculate a path.
Keeps it nice and 'generic'
Show Posts
:
