Lategame lag is unplayable... suggestions?

[miauly]

1 hour ago, KittenIsAGeek said:

Assuming that you have a robust method of caching frequently traveled paths, your big-O would still be worse than linear because you'd have to 1) check if your path is in the cache, then 2) check if your partial path is in the cache, then 3) formulate your new path.  Generously assuming that 30% of the time you get a hit for #1, you're still looking at however many iterations it takes to determine if your path is already in the cache.

I did not suggest to cache paths, this won't work. Perhaps I was not that clear, so please let me rephrase once more.

What I would think might work is to "collapse" graph you need to solve by treating some parts of the map as "vertices" as opposed to just treating tiles as such. If we have for example a room of 4 tiles high, 16 tiles wide - it can be treated as one "tile" which is run on the floor by actors that only go on surfaces, rather than its single elements. For flying things it's more finicky and then there are dreckos, so the code will become way more elaborate. Then invalidation also is elaborate, so I'd say that anything containing automation on borders should fall back to default per-tile approach. So, all this combined, you could have a simpler "collapsed" graph where you "merged" room-like spaces into a single vertice each, and you go two steps - first navigate through a simpler one, then within a vertice. If you add paths through the "rooms" for non-flying actors to the cache, it's even faster but then more invalidation - needs to be tested on real maps.

I'd say that adding geometry to graphs could also help with flying actors like jetpacks and bugs. For example, if we cache open spaces as a set of joined rectangles (or even convex figures to catch even more cases, but then how do you find a convex figure in the first place, but then how much you invalidate when you found one? this all needs testing) and fly border-to-border, this should be faster than going over a "graph" with 8 edges per vertice where complexity is O(V+E) because it's cyclic (and then how good are the sets we use to keep visited vertices? because some implementations of sets may, I think, get this O higher when not tuned to the data representation).

Long story short, our eyes don't find paths magically either. Trying to solve a complex labyrinth just by looking won't work. The way our brains do it really fast is by learning patterns and applying them. And this could be coded.

I'd say the real issue here is not if optimizations are possible in principle, math-wise. The real restriction is probably developer time and added codebase complexity, the latter especially. Profit-wise the optimum probably is to just up the recommended setup to 3.5 Ghz.

[Cilya]

1 hour ago, miauly said:

What I would think might work is to "collapse" graph you need to solve by treating some parts of the map as "vertices" as opposed to just treating tiles as such. If we have for example a room of 4 tiles high, 16 tiles wide - it can be treated as one "tile" which is run on the floor by actors that only go on surfaces, rather than its single elements. For flying things it's more finicky and then there are dreckos, so the code will become way more elaborate. Then invalidation also is elaborate, so I'd say that anything containing automation on borders should fall back to default per-tile approach. So, all this combined, you could have a simpler "collapsed" graph where you "merged" room-like spaces into a single vertice each, and you go two steps - first navigate through a simpler one, then within a vertice. If you add paths through the "rooms" for non-flying actors to the cache, it's even faster but then more invalidation - needs to be tested on real maps.

Do you know an efficient and simple algorithm to decompose your graph into k-connected components ?

[Nightinggale]

I'm wondering. If we do some sort of cached graph and make cells remember which path(s) in the graph they can affect if movement abilities change, would we end up making matters worse by making door pumps force recalculations of graphs, which we won't use before they are recalculated many times?

 

Maybe the game should count how often dupes are moving on floors (not counting idle) and use that to cache shortcuts. The shortcut calculations could be done during the normal sleeping time where the CPU is generally more free. If a frequently used path breaks, just delete it and it will fall back to the current code. A new cached path will form within the next few cycles.

[miauly]

39 minutes ago, Cilya said:

Do you know an efficient and simple algorithm to decompose your graph into k-connected components ?

You don't need to. There's a difference between mathematically correct solutions and engineering. To optimize here, you need to look for things that are easy to grab, not make an advance in algorithms on graphs that's worth a paper in a good journal. Maybe the performance we see is even not due to the fact the algorithm is slow, but because the software framework that's in use only has suboptimal for this issue out-of-the box data structure implementations?

You think science, a practical engineer thinks hacks, and that's why things you use do exist. Facebook you use, for example, most of the times behaves consistently - your posts and comments get published and seen - although there's a CAP theorem out here that proves it can't be consistent. If you don't use FB per se, any large internet service can serve as an example.

Path finding is just one thing and there are many others to compute. But most of them unlike path finding can be solved by engineering and not math, that's what i meant by performance improvement on design step. Take for example gases - you design some set of rules for them and then you implement a simulation. Then you can find it can't be optimized with math and it's even proved to be unoptimizable by serious theorems - and at this point you can just change the rules. Does not work when you simulate real physics, but engineers do that all the time. That us why our vehicles run on wheels and not faster legs, and our aircrafts don't model birds. The engineering approach is to change the problem definition until you solve it within the bounds of the original task, in this case defined as "fun sandbox sort-of-physics-sim game running on X minimum hardware setup". In this original definition you can have any model of gases you like, performant ones too. And it does not mean that the resulting behavoir will be dumb. Surprisingly simple sets of rules can result in so complex behaviors scientists have trouble to decipher them. This is how nature works with evolution as an engineer. "Simple rules" book and sociology models are both good sources to become fascinated of such examples presented in them. 

All this is not to say Klei is doing a poor job. All the above is far from easy, and while math is not the constraint, profits are. You can only spend so much on implementation and then maintenance of your codebase, and this limits the complexity of the code you write as well as efforts you spend to design and test various approaches.

But to answer performance complaints here with a claim that this game is mathematically-proven-impossible to be faster is an incorrect way to address them. We are here to provide a testing by playing, that is to generate real bases and highlight issues that happen in them - and this is important because this is a abysmal subset of all possible combinations of everything (which is what math address usually unless it's applied science and not theoretical). And because this is such a small subset, there might be ways to grab real performance gains here by identifying issues that cause the most of the lag in this subset and then to tune them. Assess data structures, actual compiled implementation, locks, hacks, caches, shortcuts, and a lot of other tools for just those isolated issues that matter on real maps the most (or at least call it quits and recommend the hardware that can run actual bases on 30 fps). And this can only be done if we players submit here our complaints and our saves, because no testing team will have enough hours to invest to actually play as much as we all here combined do - in addition to actual testing of the new features, which they do way better than we do, trust me. I've worked with real QA, they are magicians when it comes to make things break and so in pointing bugs - but to point out what is important for user experience you need users. And that is why exactly I continue to complain on performance here.

PS. And just to clarify - what I describe here for caching I do just as an example to show why software optimization is not as restricted by math to allow for simply citing some paper in your defense and call the current situation the best possible. I do not intend this to be seen as an advice for Klei to actually look into, that would be just plain silly - to come up with any ideas on optimizations you need to first pinpoint your issues by careful benchmarking and debugging and I can't do that obviously, not to mention the experience you need to come up with solutions working in particular game development area. The only way I intend to help is to help keep the discussion on lags going and more maps and complaints posted, rather it being shut down with "there are papers that prove that ONI can only do 30 FPS on 4 Ghz".

[Cilya]

38 minutes ago, Nightinggale said:

Maybe the game should count how often dupes are moving on floors (not counting idle) and use that to cache shortcuts. The shortcut calculations could be done during the normal sleeping time where the CPU is generally more free. If a frequently used path breaks, just delete it and it will fall back to the current code. A new cached path will form within the next few cycles.

Classical pathfinding algorithms are not really compatible with shortcuts, as you don't really have a way to prevent the algorithm from re-exploring the path for which you have built a shortcut. That's why the decomposition in components is usefull: once you have your components, you can forbid the algorithm to go inside the components if there is nothing of interest inside, and take the shortcut instead.

Anyway, while this discussion is very intersting... are you sure that the pathfinding is not already optimized and that is a bottleneck ? The navigation graph is pretty small (thousands of vertices, or tens of thousands of vertices, unless you have jet suits to go everywhere) and paths are only computed very often so, theoratically, it should not cost that much.

Another problem with those heuristics is that they are working for 1-source-1-target pathfinding algorithm. While if you want the priority system to take the distance into account, you are likely to need a 1-source-several-targets algorithms (e.g. Dijkstra algorithm), where you will want to explore the whole graph.

 

18 minutes ago, miauly said:

You think science

 

I'm really curious about how you can guess what I think only from one question I've asked. And this question is actually extremely practical: how do you "collapse" your graph as you say. Not in an optimal way. Just give me any way, practical engineering or not. If you have one, it will certainly be an (approximate) algorithm to decompose the graph into k-connected components.

 

[miauly]

8 minutes ago, Cilya said:

And this question is actually extremely practical: how do you "collapse" your graph as you say. Not in an optimal way. Just give me any way

Out of the top of the head - find open walkable "rooms" as bordered by solid tiles, non-automated doors, unwalkable by duplicants floor height changes and ladders. Invalidate on ladders/automation constructions, phase changes of solid tiles, digging. For flying actors, convex open spaces. Exploiting this one to full can lead to funny zig-zag bouncing flying but why not really.

But again, this is all just speculation as we can't even tell if the reason is really in graph algorithm here. Maybe there's a hash set underneath with cache function being for some reason dramatically bad? If I understand correctly, you only get linear on acyclic if your set is linear, otherwise you are quadratic and that will be a disaster - and truly linear sets only exists in papers on graphs sadly. This particular reason is unlikely as it is an obvious one but there are other less obvious things that lead to a similar result.

[Cilya]

3 minutes ago, miauly said:

Out of the top of the head - find open walkable "rooms" as bordered by solid tiles, non-automated doors, passages making it non-convex, unwalkable by duplicants floor height changes and ladders. Invalidate on ladders/automation constructions, phase changes of solid tiles, digging.

 

If you are talking about removing vertices with degree 2, you are right it's not hard to do. But I wouldn't bet that it is not implemented already.

[miauly]

12 minutes ago, Cilya said:

Anyway, while this discussion is very intersting... are you sure that the pathfinding is not already optimized and that is a bottleneck ?

Exactly. And to find what is a bottleneck, real maps need to be analyzed by development team. That's why this discussion seems useful for me, not for suggestion of ideas on how to optimize path finding by people who have not that much information on how it is implemented, me included. 

[Nightinggale]

15 minutes ago, Cilya said:

are you sure that the pathfinding is not already optimized and that is a bottleneck ?

I'm not sure of anything in that regard, partly because I haven't found the pathfinding in the code. So far all I looked at has had some connection with buildings. For those who don't know we are encouraged to decompile. This isn't as tricky as it may sound because it's managed code meaning the decompiled code is fairly close to the original. All mod creators have decompiled the code as it's a requirement for figuring out how to mod whatever you want to mod.

It's a fair assumption to make though as pathfinding is usually the bottleneck in most games where pathfinding takes place.

[Cilya]

Strangely, the FPS drops is still huge when the game is paused. The game is perfectly fluid at start, but in my current game, I can't get past 20 images per seconds when the game is paused and barely above 10 otherwise. So it seems that an important part of the problem is not the simulation itself. Does the GUI need to constantly iterate through all the objects ?

[Nightinggale]

59 minutes ago, Cilya said:

Does the GUI need to constantly iterate through all the objects ?

Yes. At least drawing pipe ports does that. I wrote a lenghty bug report on it and how it does that even in cases when it isn't needed and how my modded code skipped a lot of the update code. That bug report is now labeled as fixed in next release. If we can tell a noteworthy difference remains to be seen, but every little bit helps towards faster code.

I don't know if there are other parts of the GUI code, which are CPU heavy for each frame, but I suspect it might be the case. However what the game does right now is actually not that interesting considering Klei is aware of the FPS issue and are unlikely to ignore it. For all we know the delayed release is due to wanting to fix the FPS issue prior to announcing the game as released out of early access. Performance is usually the last issue to fix before a release, meaning it would be normal for them to work on it right now.

It should be noted that this is done by the CPU, not GPU. ONI relies heavily on the CPU and memory, but not really the GPU. My guess is that you can switch to decent integrated GPU and not notice a difference from the framerate you see now. At least that's my experience from testing on integrated graphics. Don't expect higher framerates from integrated graphics either though.

[Gurgel]

And here I am doing late-game without lags on an old FX8350. At 20 FPS. Perfectly playable. No, it is not that I am getting old and are even slower than the game.

[geniusthemaster]

attached is my computer info. i have 4 cpu cores running at 3.1 gigahertz. you need this to run at 30 fps average during late game because of thousands of individual gas exchanges occuring within each tile. if you really need to get more fps you can gain a temporary boost by using the fill tool and replacing fast exchanging large bodies of gasses , and use debug mode to mop up as much loose liquids as you can cause that conpresses the gasses and makes them move faster.

DESKTOP-JH4FA1T.html

[Cilya]

I play with a better CPU and a better GPU than yours. Due to other player's tests (replacing all gases with vacuum) it is unlikely that the gas simulation as anything to do with the CPU bottleneck. Moreover, as I said, the FPS are also very low when the game is paused, and no gas/liquid simulation is done.

[Ashpoker]

ask yourself this question. Is it butter smooth in cycle 1000+ just like at the beginning ? if you answer no then there is a problem with performance. There is nothing more to say about it. And until this is fixed players will complain.

[BaloneyOs]

It's okay this is probably the reason why the game was delayed by more than a month  and we'll definitely see this fixed  because surely they won't release a builder game that punishes you for playing economies of scale 

[Aeglefire]

This is perhaps the largest issue I find with the game, and it's such a great game!  Love you Klei!