The main reason I wrote my own pathfinder was speed. The original pathfinder was taking up about one third of the total AI turn time, and so I figured that it was the area that I should focus on the speed things up. I don't think there was anything majorly wrong with the original pathfinder; but the thing is, I knew it was taking up a lot of time, and I had no way of understand what all that time was being used for. I don't think the pathfinder was intrinsically slow; but rather it was just very hard for me to tell how it should be used to get the best performance. With my rewritten version it is easier to use it in a way that doesn't slow things down. The main big advantage of my pathfinder is that it is possible to set a maximum path length after which the pathfinder will stop looking. In the original pathfinder, even if you just want to know if you could get somewhere in 1 move, it would search the entire map just to tell you that you can't get there at all. Also, with my pathfinder I have finer control over when it should reset, and when it shouldn't. For example, in CvUnitAI::AI_load I create a new pathfinder instance to use for the boat so that I don't have to clear path results we've already found for the unit itself. That way, the unit can use the unit's cache, and the boat can use its own, new, cache. That's the type of stuff which gives the new pathfinder its speed increase. Aside from those type of things, I don't think the core of the new pathfinder is actually a bit improvement. The current pathfinder uses around 1/9 of the turn time (as opposed to 1/3). (To measure that, I'm just using the in-game profiler thing; with various functions flagged with
PROFILE_FUNC().) But as I said, I suspect most of that speed improvement actually comes from better use of the pathfinder rather than from improvements in the pathfinder itself.
I've always just assumed that Firaxis did a good job with their implementation...
I use to assume that as well. I don't anymore. There's a heap of Firaxis code in the game which is complete trash. And I don't just mean poor AI or whatever, I mean poor programming. A couple of examples that come to mind are the original implementation of CvUnit::planBattle, which worked by trying random combinations of combat events until it found one with the correct end conditions (ie. the correct team winning the battle with the correct amount of sub-units left.) And the implementation of anything which involved sorting a list, which they always did it by looping through the list to find the smallest (or largest) element, extracting that to put in the new list, and repeating that process until they've done the whole list - kind of like an inside-out version of insertion-sort. Those kinds of things are not good...
Sometimes I think Firaxis programmers must have been paid per-line or something. I just don't know why else they'd want to nest so many if statements and so on. ... Anyway, the crux is that I no longer assume that the original Firaxis code is good.
Are you able to successfully reuse the cached path across multiple calls to GeneratePath? If so, are you completely confident that the cache isn't stale when it is reused?
[...]
Have you thought about replacing FAStarNode with your own implementation? Does anything in the game core prevent us from using our own class/struct?
One tricky / annoying thing about making this new pathfinder is that it does not replace the pathfinder used by the UI. (ie. the paths that are highlighted when the human player is trying to issue a move command.) As far as I can tell, it isn't possible to use my new pathfinder for the UI, because that's handled somewhere inside the .exe. -- So, because of that, the new pathfinder had to be programmed so that it gives
exactly the same results as the original pathfinder; so that the path shown by the UI will accurate represent the path that the unit actually uses when ordered to move. (There are still some rare cases where the unit doesn't go where it said it was going to go; but that isn't my fault, believe it or not; that's a separate problem.) So, that's basically the reason why I'm using the same FAStarNode structure - it's allows me to share code between the UI pathfinder and my pathfinder.
As for reusing cache; absolutely yes. That's a core part of getting good performance from the pathfinder. You're right that I don't check for every possible way the cache could become invalid; but I'm pretty confident that it works correctly anyway, because:
- The cache is not used for the actual move itself. That's done using an isolated instance of the pathfinder. (See CvSelectionGroup::groupPathTo).
- The UI doesn't use my pathfinder anyway, and so any bad-cache problems you might see on the screen are not the fault of my pathfinder anyway.
- No game events can take place during the AI's decision making process. So nothing can move or whatever to block the AI's path while it is still using its cache.
That said though, the cache clearing system is not rock-solid. There could potentially be some obscure cases which cause the AI to reuse an invalid path which I haven't thought of; but hopefully that kind of stuff will be picked up by asserts in debug mode or something. (For example, originally the pathfinder was not cleared when the AI declared war - but some combinations of defensive pacts and so forth would confuse the AI into trying to move somewhere it wasn't allowed to go anymore... that was picked up in debug mode, and thus fixed.)
If I understand your code correctly, it looks like you are using a hash table (node_map) to find adjacent FAStarNodes. Even though it's theoretically O(1), that hash table must have some cost. Couldn't we pre-allocate an array of FAStarNode*[mapWidth * mapHeight] and find the nodes by looking them up in the array by plot index? Do you see any drawbacks to such a change?
That sounds fine; and it would probably be a bit faster. It would use more memory though. In particular, the memory usage would scale badly on big maps. (But there are many
many things in this game that scale badly on big maps...) I'm not really sure how much the hash function costs, but I expect it would be pretty cheap.
What do you think about using a binary heap or D-heap for the open list instead of a linked list? Inserts would be more expense, O(log n) instead of O(1), but the search for the best node would be O(1) instead of O(N).
I reckon that would probably be worth doing. I was originally going to try to speed up the open list search thing, but I decided to just leave the pathfinder alone for awhile to work on other stuff, because I was already satisfied with the speed of the pathfinder. But I do think there are probably some decent gains to be made with something like that. (Although, I dont' know what a D-heap is!
)
What do you think about implementing a two or three tier path finder? I am kind of boggled by the thought. On large maps it would really help to break the problem down into chunks. Theoretically it would be great, but getting the heuristics right for the larger chunks could be a nightmare. If the hueristics could be pre-computed to some extent that would be very helpful (ie this chunk has water, this chunk has mountains). Then the real problem would be changing conditions. Hrm, it sounds rather complicated...
Yeah, I don't think we need that. I don't think even the very biggest civ4 maps are big enough for a two-tier system to make a significant speed improvement. ('Huge' maps are around 128x80; which is significantly smaller than the examples they were talking about in Patrick's tutorial.) I'm sure it would make it faster, but I don't think it would help so much that it would be worth spending a day of programming on.
[edit]
It just occurred to me what a "d-heap" is. I don't know why it sounded so foreign a few minutes ago...
By the way, I hadn't read those articles. The first one looks familiar; so might have read that some time ago, but I'm pretty sure I haven't seen the others before. I don't actually remember how I learnt about A* in the first place.
By the way, I'm pretty sure that the peace treaty alert problem that you mentioned is also fixed. I didn't put it in the changelog because I didn't actually test it properly, but my guess is that the problem was caused by BUG not having accurate info about when leaders "refuse to talk"; and so by restoring the "!" thing on the scoreboard, I expect that the peace treaty problem is probably fixed as well.
from the forest more than the +3
from the plantation. You might notice he is also using watermills rather than cottages, so apparently he wants that city to be focused on productivity. Maybe later he'll decide to go for the plantation later, but I don't think it's a bug.
