OpenXcom Forum
Contributions => Programming => Topic started by: grrussel on November 07, 2012, 10:43:51 pm
-
I am looking at how to speed up OpenXCOM on very large battlescapes (because those are the most fun!) with large populations of AI actors (about 154 civilians, some large but uncertain number of Aliens) for terror missions.
Firstly, its really slow in the Alien turn. Minutes per AI turn.
Some observations: it never seems to peg the (or a) CPU at 100%. Perhaps timer driven actions with idle periods? The structure of the game loop is still opaque to me ;-)
I ran the OSX "Instruments" profiler over this. One hotspot showing up is the volume of memory allocations performed (huge) despite the relatively small overall memory usage. I have greatly reduced one instance of this pattern of quickly allocating, and then deleting, objects - in a case where the allocation is not (usually) needed, it can be avoided unless needed.
-
Could you try my A* pathfinding code from GitHub? It takes away some allocations and speeds up the pathfinding, which should be a lot with that many actors.
(same username, branch should be obvious)
-
Will give it a go!
Although, the path finding is not yet a huge component according to the profile I just got with some recent changes to the game loop - namely, removing an SDL_Delay call, and calling flip on the screen 1 time in 4 as SDL drawing calls were dominating the runtime. It seems to be about 10%
I think that not going for 100% CPU usage is fine normally, but here I want to do a lot of processing as quickly as possible.
-
Sigh. Ignore the first patch, seems to make a huge memory leak.
-
About the pathfinding:
I don't understand, why don't we use a simple Dijkstra-algorithm for pathfinding?
It's very-fast, (perhaps the fastest) and guarantees to find a path if there is any, and it guarantees to find the SHORTEST (/quickest) path!
EDIT: Hmm, it seems karvanit's version is very similar to Dijkstra-algorithm...
-
The pathfinding that is currently used in openxcom IS supposed to be a (modified) Dijkstra algorithm. I copied it from code I used in another game of mine (which is also 2D tiles, but without different levels in height) and that one was again a copy-paste from a pathfinding tutorial in a book about Artificial Intelligence and it claimed it was Dijkstra for 2D square tile games... so...
But if that A* algorithm is faster and less memory consuming, I'll be happy to replace it some time.
-
actually AI shouldn't be using pathfinding extensively. Otherwise there's something wrong with it:)
Dijkstra grid filling should be limited with TUs of unit, and if I remember right - Daiky used pathfinding without any limit so it runs even thru tiles where unit won't get in even 2 turns. How about limiting? It may help in some cases.
-
Yeah, openxcom just isn't an example of optimized code. Which is probably normal, you first get all features in and then start looking how to optimise it, which probably includes things as limiting certain checks in a smaller area, where they now go through the whole map or through all units. Field of view checking and lighting are also areas where I know there's room for improvement.
-
About the pathfinding:
I don't understand, why don't we use a simple Dijkstra-algorithm for pathfinding?
It's very-fast, (perhaps the fastest) and guarantees to find a path if there is any, and it guarantees to find the SHORTEST (/quickest) path!
EDIT: Hmm, it seems karvanit's version is very similar to Dijkstra-algorithm...
A* (https://en.wikipedia.org/wiki/A*) is based off Dijkstra (like most algorithms of the sort), I think it's the most popular pathfinding algorithm right now.
-
A* is like Dijkstra, but smarter about which node to examine first. This is what I have implemented in my patch.
Using a TU limit in the pathfinding needs to take care, so we find the part of the path we can walk within the limit (we still want that).
Simply finding all tiles reachable within X TUs is done as pure Dijkstra in my code, but it has no callers for now.
-
A* (https://en.wikipedia.org/wiki/A*) is based off Dijkstra
You're right. I forgot about it. I've even learned about it within the AI-course on the Univ., but that was quite a few years ago. :)
-
A* or any pathfinding used in AI? What for?
AI doesn't care on particular paths, it must work with final points, nodes, not "paths". Pathfinding is needed only for final action.
-
You misunderstand it. We are not talking about the AI in OpenXcom, we're talking about AI in GENERAL.
A* algorithm is taught in the AI topic on the university. (at least on ELTE - Hungary)
-
This topic is about performance drop in "hidden movement" screen in openxcom, so I guess you've misunderstood it.
I've researched pathfinding by my own, and I bet I know this subject quite well.
The point is - what creates this drop - I doubt it's pathfinding, because there's no need in pathfinding for xcom AI at all. I believe it's something else.
-
My point is: Nobody claimed that pathfinding is part of the OpenXcom-AI.
-
huh? reply #1.
-
You're right! That's an implicit statement. :)
Then a correction: "I did not claim that pathfinding is part of the OpenXcom-AI." :)
-
The point is - what creates this drop - I doubt it's pathfinding, because there's no need in pathfinding for xcom AI at all.
Of cource it is used. Every time anything wants to from point A to point B pathfinding is used, that's what creates the path (intermediate positions) that any moving unit uses.
-
karviant, where did you get that from? pathfinder is needed only in final stage, when acting, not when estimating "what to do next".
-
Ok, my bad. It is used in the BattlescapeState code, but only at the end.
The visibility calculations are O(N) though, in the number of Battleunits, and they are run every step of every moving unit.
-
A new memory allocation reduction patch.