Improve performance?

[user42]

To put my own two cents worth in, I'm pretty confident I've nailed the performance issues to be routing isuses.

I've noticed that some times, workmen get "stuck" on a corner - they're only two squares from where they are going but seemingly can't round that one corner - don't ask me why, routing and pathfinding's always been an ongoing concern back when I interested myself in warzone2100.

Be that as it may, the minute I sack that stuck workman, performance goes back to normal.

On the inversion, I've doubled my number of guards, workmen AND janitors all in one go, and did NOT get any noticeable performance drop.

[thekillergreece]

To put my own two cents worth in, I'm pretty confident I've nailed the performance issues to be routing isuses.

I've noticed that some times, workmen get "stuck" on a corner - they're only two squares from where they are going but seemingly can't round that one corner - don't ask me why, routing and pathfinding's always been an ongoing concern back when I interested myself in warzone2100.

Be that as it may, the minute I sack that stuck workman, performance goes back to normal.

On the inversion, I've doubled my number of guards, workmen AND janitors all in one go, and did NOT get any noticeable performance drop.

Any A.I has a lot pathfinding,pathway routing fault and problems. Prisoners dont seem to have...Only uncontrolled(Where you dont click them and sent them) doctors,guards,riot guards,workmen..We have to wait Chris to fix the problems or wait for beta stage

[Gondlar]

When I keep it running while not changing anything it will do much better.

Interesting, I've had the opposite experience: When I pause the game and go read the forums/wiki/whatever while keeping the game running for some time and then switch back to the game, it usually has heavy lags until I save/reaload. My best guess for that issue right now is some utility structure stacking up in a container, without ever getting deleted. That's only speculation though.

Be that as it may, the minute I sack that stuck workman, performance goes back to normal.

On the inversion, I've doubled my number of guards, workmen AND janitors all in one go, and did NOT get any noticeable performance drop.

Was any of those many employees stuck?
From my in-game experience it seems the path is calculated once when the movement starts and again when it is blocked somewhere. You can see that happening when you build walls: Your staff will try to walk through a newly built wall, then notice the way is blocked and turn around to walk around. On their next walk this does not happen again. This would lead me to the conclusion that staff stuck on a corner makes the game recalculate the path every singe step. On a large map, that surely would be a lot of work.

[JSwigart]

Short of using influence pathing as mentioned, or a path lookup table, it's still pretty easy to eliminate the worst case pathfinding issue in exchange for an instant path failure. Path searches are most expensive when there is no path to a goal, because the search ends up being performed exhaustively across all nodes. The way to eliminate this is to mark the nodes with 'group ids' by flood filling through the graph and assigning an id to all reached nodes, and then a different id to any other ungrouped nodes and flood filling from there, etc. What you end up with is 1 or more group ids being assigned to each tile in the environment, and any time someone wants to path, he would first verify the start and destination are the same group. If they are different, the path fails immediately and the full search is avoided entirely. If the start and goal are the same group, then there is a solution and the pathfinding may then be performed. Knowing these groups basically instantly has a number of behavioral benefits as well, such as having a trivially cheap way to ensure you choose resources(yard, workshop, canteen, etc), that is reachable, using matching group id, and opening up the possibility of people isolating groups of prisoners to different areas of the prison.

[prototype]

Interesting, I've had the opposite experience: When I pause the game and go read the forums/wiki/whatever while keeping the game running for some time and then switch back to the game, it usually has heavy lags until I save/reaload. My best guess for that issue right now is some utility structure stacking up in a container, without ever getting deleted. That's only speculation though.

I am not saying that the game will not slow down, I am saying that it takes longer before it slows down.
When I start a lot of jobs (building something) the game will slow down faster usually.
(at least that is what I subjectively feel is happening

[ashchap]

Flow fields

Just wanted to say I really enjoyed reading this, it sounds like a really good system. Would it still work for a moving target e.g a prisoner that needs to be searched or stopped from escaping?

What about when there are multiple targets but only one unit should travel to each target? For example when the prisoners go to the workshop, they could work at any machine but they each have to go to a different one. Or when the guards have to search a cell block, there's no point in all the guards going to the same search job. Or when the prisoners have to find the nearest toilet!

[Flint]

Alpha = Adding features

Beta = Fixing bugs (like bad performance)

Let them add content and worry about performance later, I assure you, the performance will be improved down the road.

~cheers

With every new added item you would have to have even fewer prisoners and staff, a big performance update needs to be done in a Alpha update.

[JASPer.Gamer.9.0]

When you're posting a suggestion, please post it in this format:

[Suggestion] - _________________________

OR

[Suggestion] _________________________

Taken from "How to post a Suggestion"

[paktsardines]

Jasper, the original post was a question not a suggestion. Your advice is not needed in this instance (also, it makes no difference where 'suggestion' appears in the title, as it'll be picked up by a search anyway).

But, on a positive note, at least it's not yellow.

[Elandryl]

Right now the game can become laggy with just 60 or 70 people walking around the jail. On a PC fitted to play Battlefield 3 in ultra-high details at 40fps. I guess we can say there's a bit of a lack of optimisation here. You shouldn't need a super-powerful computer to run such a basic engine. Hope they will work on it pretty soon, there's no point in building a huge prison if you can't actually play it.

[xander]

While your point that some optimization is required stands, I would like to respond to this bit in particular:

On a PC fitted to play Battlefield 3 in ultra-high details at 40fps. I guess we can say there's a bit of a lack of optimisation here. You shouldn't need a super-powerful computer to run such a basic engine. Hope they will work on it pretty soon, there's no point in building a huge prison if you can't actually play it.

You are comparing apples and oranges. A game that is meant to be played in "ultra-high detail" is a game that utilizes the GPU a great deal, but may not actually require that much CPU time. Assets controlled by the computer tend to be relatively simplistic, and there are likely to be relatively few such assets requiring attention at any one time. Even FPSes that boast crazy sophisticated AI units are not using that much CPU time to control any one unit, and there are rarely more than a few units that are doing anything in a given moment of time.

Prison Architect is graphically relatively simple and should not tax the GPU very much, but there are potentially hundreds of computer controlled assets, and the computer is being asked to do some relatively sophisticated "thinking" about how those units should behave. The most notable example is the pathfinding behaviour. Pathfinding is a mathematically difficult and computationally intensive problem, and can very easily use a great deal of CPU time. Could the pathfinding be optimized? Probably. My understanding is that the game currently uses a fairly simple implementation of the A* algorithm. This algorithm is pretty good, but there are some clever ways of further reducing the overhead of computing paths which could, if implemented, lead to significant gains in the future. It is also well nigh certain that the pathfinding could be parallelized, thus decreasing the amount of lag (though this only scales to the number of cores that Prison Architect has access to).

To reiterate, there are almost certainly places where the game could be optimized, *but* a machine that is optimized to play the latest FPS is not necessarily optimized to play a game like Prison Architect, and the fact that a given computer can play one game should not be used as an indication that it should be able to play another.

xander

[Elandryl]

Then compare Prison Architect to a game like Harvest, which can handle thousands of 2D units at the same time, all with an objective (pathfinding is easier since all units are flying), without a hint of lag. And Even if FPS use the GPU a lot, try to run them with an excellent graphic card and a poor CPU, and you'll notice they're quite taxing for the CPU too.

[xander]

Then compare Prison Architect to a game like Harvest, which can handle thousands of 2D units at the same time, all with an objective (pathfinding is easier since all units are flying), without a hint of lag. And Even if FPS use the GPU a lot, try to run them with an excellent graphic card and a poor CPU, and you'll notice they're quite taxing for the CPU too.

I am unfamiliar with Harvest, and it is a common enough word that Google is not helping me much. However, if it is the tower defense game that I played a few years ago, the units move, essentially, straight to their objective. Pathfinding is (mathematically speaking) trivial---it comes down to computing where each unit should move during each frame, which is a simple linear linear equation (<new position> = <current position> + (speed)*<direction to objective> --- which is one multiplication in some inner loop). In Prison Architect, each unit's path is computed using A*, which can be as bad as O(n^2), where n is essentially the width of a square map (the complexity of A* actually depends, I think, on the number of vertices in the graph, which is the number of cells on the map, which this scales as n^2, so, asymptotically, it is correct). That is for each unit, i.e. there is an O(n^2) algorithm being evaluated in some inner loop.

So, again, there are certainly places where Prison Architect could be optimized, but comparing it to other games is likely to be apples to oranges.

xander

EDIT: I should note that my area of study is fractal geometry and not graph theory nor algorithms, so the estimates above may be off. However, even if A* is somehow O(log(n)), it is still orders of magnitude more computationally intensive than moving an object along a straight line.

[MAdMaN]

I am unfamiliar with Harvest, and it is a common enough word that Google is not helping me much.

Did you use a related term such as game when searching? Searching for harvest game brings up Oxeye's Harvest as the first link.

[xander]

I am unfamiliar with Harvest, and it is a common enough word that Google is not helping me much.

Did you use a related term such as game when searching? Searching for harvest game brings up Oxeye's Harvest as the first link.

That was the TD game I referenced in my above post---I just wasn't sure if that was the right game. Sorry I was not more clear. I will edit the above.

xander