Fear that the value of performance is being underestimated

[woutske]

Hello everyone!

I am playing PA since the first month it came out and I really enjoy the game. But something is bothering me. For me, the game gets more fun once more prisoners arrive at my prison. I really love huge prisons with lots of rooms and places to manage. A huge problem for me is, the more prisoners join the prison, the more the fps declines; until it's almost unplayable.

I am a developer myself, and the problem seems to be in the pathfinding. This process does not seem to be threaded and seems to be calculating new routes too often. I understand the game is still in alpha, but what worries me is that they announced the game's release date is set.

I have the feeling that the value performance of the game might actually be underestimated, since it's running pretty great with smaller prisons.
I am not trying to complain about the actual performance, but about the current status of the roadmap and announced release.

What is your opinion about this (rather controversial) topic?

[lugaru]

People have requested that the game bakes in paths every once in a while, since in most prisons there are only so many paths. I mean I really like how unpredictable prisoner actions and movements are, but if the game itself drew some paths every once in a while that prisoners and guards tend to fall into it would probably free up a ton of processing.

[aubergine18]

They've stated they don't plan to do anything more about the large prison performance issues, which is a shame. Unless the code is massively horrendous, the pathfinder should be relatively straightforward to convert to multi-core threaded approach.

This game bakes my CPU temps more than anything else I've ever installed - from video editing software to resource hungry games like Cities: Skylines (with 65k concurrent agents) - due to its entire code base being limited to a single core.

[xander]

I am a developer myself, and the problem seems to be in the pathfinding.

That is likely a correct analysis.

This process does not seem to be threaded...

The path-finding routines do live in a separate thread, but all of the path-finding is done in one thread, yes. That being said, it is unlikely that you would see enormous gains in performance just by breaking the path-finding into multiple threads---in addition to the overhead of multithreading, the path-finding algorithm itself has high computational complexity and will rapidly eat up new cores as the map size is increased. Multithreading is not a magic pill for solving performance issues.

...and seems to be calculating new routes too often.

This is an idea that has not been brought up before, and you may be correct---I simply don't know. The dynamic nature of a prison seems to imply that paths really do need to be recomputed with some frequency, but it is possible that less frequent path-finding would help.

While I agree that performance is a moderately important issue (frankly, it isn't a big deal for me, since I don't really like building mega prisons, but I can definitely see the appeal for others), I think that the constant call for multithreading is a bit of a red herring. More efficient path-finding, pre-computed routes, network simplification, etc.---there are a lot of things that could likely be done that would be far more useful than splitting the path-finding into multiple threads.

xander

[aubergine18]

Maybe approach similar to Cities: Skylines would be of use...

1. Path is calculated at start of journey (this seems to be the way it's done in PA already from what I can tell, you can even do this via a Lua script in a mod)

2. Prisoner AI follows that path until it reaches a problem (locked door, blocking object, etc) and then decides what to do

Based on this, it would seem that both the pathfinder and the prisoner AI (possibly worker/guard AIs too) need to be multi-threaded and running on multiple CPU cores.

That being said, even if they remain single threaded it should still be possible to get a pretty decent performance boost if they are altered to run on different CPU cores.

[Robbedem]

Path finding is closely linked to assigning jobs based on proximity. Since they are working on the latter, it is likely that they are also improving the former. (at least I hope so)

[woutske]

I really hope so. Things like land expansion are currently not worth a lot, since the main reason for expansion will be more cells. But more prisoners and larger area will only increase the complexity of the pathfinding thus slowing down the game even more

[punchball]

I have the same issue and I really hope they do something about it although It sounds like they are not going too.

[RJenkos]

Turning fog of war off was a big performance booster for me. That allowed me to get up to and over 300 prisoners before it gets unplayable. Before I had a hard time playing at 200.

[xander]

Based on this, it would seem that both the pathfinder and the prisoner AI (possibly worker/guard AIs too) need to be multi-threaded and running on multiple CPU cores.

"Need to be multi-threaded"? Are you sure? Multi-threading is not a magic pill that improve performance. There are things to consider:

• The performance improvement expected by multi-threading is, under optimal conditions, proportional to the number of CPU cores available (let's ignore, for a moment, the existence of virtual cores, which may not get even that kind of optimal performance). An operation that takes t seconds with one core will take t/8 seconds with eight cores. On the other hand, the complexity path-finding using the A* algorithm (which is, I believe, essentially what Prison Architect is using) is O(|A|), where A is the number of arcs in the graph that must be searched (under worst-case conditions). Given the shape of the graph that must be traversed by an entity in Prison Architect, this is essentially the number of squares on the map, a number that scales like (approximately) x^2 as you buy land expansions. This is the complexity of finding a path for a single entity. Now multiply this by the number of entities that require paths. If you have a map that is (more or less) playable now with 500 prisoners, tossing another 8 cores at it *might* get you up to 1000 or 1500 prisoners (doubling the number of prisoners likely also doubles the size of the map). And this is under essentially ideal conditions, bringing me to my next point:
• Spawning new threads incurs overhead. Since paths need to be updated at varying frequencies (depending on obstacles and other changes to the environment), I don't really see a reasonable way of lumping different path-finding operations into lumps for threading, which either means that every operation gets its own thread (adding a lot of overhead), or you lump things into batches that may take longer than expected, or leave cores idling. In either case, you are not likely to actually observe the kinds of optimal gains discussed above.
• It bears mentioning also that multithreading is sometimes kind of finicky. There are different hardware platforms and software platforms to consider, some of which handle multithreading differently, and the task of maintaining multithreaded code is somewhat more difficult than maintaining nonthreaded code. Before one seeks to multithread, one should understand the scope of the problem being addressed, and have a good idea about how much of a performance increase one can *actually expect* by multithreading. It is quite possible that the gain in performance (which could be rather marginal) does not outweigh the downsides.

The long and short of it is that path-finding is not easy to do, and simply throwing more processing power at the problem is unlikely to actually help all that much. Yes, it would help some, but I doubt that it would make a great deal of difference for most players.

That being said, even if they remain single threaded it should still be possible to get a pretty decent performance boost if they are altered to run on different CPU cores.

I'm sorry, but that doesn't even make sense. A single thread means that everything is done on one core. In order to split things across multiple cores, you have to break them up into multiple threads, with each thread running on a different core. That is what multithreading means...

xander

[aubergine18]

In the case of the pathfinder, speed is important but not critical. If it takes a second for a thread to work out the path (which would be massively slow) the end-user won't really notice. The main thing is to keep the FPS nice and high to prevent screen stutter.

In the case of AIs those obviously need to get stuff done much quicker, so threading is less of a benefit there, but still beneficial none the less.

[RMJ1984]

Game should be balanced around running say 1000 prisoners. Even on pretty high end pcs. Game starts to run slow at about 200-250.

[MFWIC]

The amount of system ram seems to have the most effect on the game's performance for me. My typical prison is in the 15-1800 range and I don't usually have these issues on this computer with 32 gigs installed.

On my laptop that only has eight gigs, the same prison will run at about 5 fps.

[xander]

Game should be balanced around running say 1000 prisoners.

Why? Why not target 500 prisoners? or 2000? What is magical about 1000?

xander