Improve performance?

(previously 'DEVELOPER') Private forum for registered community members. To register, please visit www.prison-architect.com/register.

Moderator: NBJeff

Elandryl
level1
level1
Posts: 48
Joined: Sun Sep 29, 2013 12:43 pm

Re: Improve performance?

Postby Elandryl » Mon Sep 30, 2013 7:40 pm

MAdMaN wrote: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 Harvest game, yes. Pretty good game, by the way.

Of course, the units' IA is simpler in Harvest (even if there's also an IA for all your thousands of towers, to choose wich unit they should be aiming at), but still, I don't think that Prison Architect has many reasons to be far more taxing for the CPU than a game handling thousands of units in real time. Or than any RTS handling hundreds of units in real time, like Starcraft II or the far more taxing Supreme Commander. No, sorry, but modern CPUs should all be able to handle Prison Architect's engine quite smoothly. Us beeing debating about optimisation is the proof they don't.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Re: Improve performance?

Postby xander » Mon Sep 30, 2013 8:45 pm

Elandryl wrote:I don't think that Prison Architect has many reasons to be far more taxing for the CPU than a game handling thousands of units in real time.

Suppose that an addition or comparison takes no time, a multiplication takes 1 second, and that an O(n) algorithm takes n seconds (obviously, the actual times for each of these operations will vary, but the ratios are approximately correct for large n). The Harvest "pathfinding algorithm" consists of an addition and a multiplication. Thus the CPU requires (0+1)*(k) = k seconds to compute. That is, it would take 1,000 seconds to compute paths each frame.

The pathfinding algorithm that Prison Architect uses, A*, is (again, I believe) O(n), where n is the number of squares on the map. The smallest map is 80x80=6400 squares. Thus computing paths for k units requires 6400*k seconds to compute. That is, it could take 640,000 to compute paths for 100 units in each frame (does PA recalculate paths every frame? Probably not---but it would still have to wait 64 frames between recalculations to approximate the Harvest "pathfinding" efficiency). Now, the big-O notation refers to asymptotics, i.e. how the time scales in the limit, and I believe that this is a "worst case" estimate, but the general orders of magnitude should be approximately correct. Please compare 1,000 to 640,000. Do you understand now how complex algorithms can require much more CPU power?

To be fair, the more intensive part of Harvest might be target selection. Suppose that each tower targets the nearest unit. Thus for each tower, the game needs to go through each enemy unit, compute distance (which can be done with two multiplications), and do a single comparison for each enemy unit. CPU time would come down to 2*(towers)*(enemy units). With 1000 enemies and 100 towers, this would be about 200,000 seconds (which begins to approximate the above estimate for PA---the orders of magnitude are similar).

Moreover, while it has been years since I played Harvest, and I don't really recall the details very well, but I do have a distinct memory of it lagging incredibly badly when there were a lot of units on the screen. I can't possibly tell you how many units (either my towers or enemy units) caused problems, but it is clear to me that Harvest can and does tax a modern CPUs as much as Prison Architect (at least, under the right circumstances).

It should also be noted that IV have produced a game (two games?) in which hundreds, if not thousands, of AI units require pathfinding: Darwinia and Multiwinia. However, like Harvest, the maps are fixed and the paths are straight lines to an objective (either the place to which the player ordered a unit or a waypoint as defined in the map). The comparison between Darwinia and Harvest might be apples to apples. Between Harvest and Prison Architect? Apples and oranges.

Elandryl wrote:Or than any RTS handling hundreds of units in real time, like Starcraft II or the far more taxing Supreme Commander. No, sorry, but modern CPUs should all be able to handle Prison Architect's engine quite smoothly. Us beeing debating about optimisation is the proof they don't.

I have not played the most recent Starcraft, nor have I played Supreme Commander, but I have played the original Starcraft. First off, you are pretty limited in terms of units. Any one player gets---what---200 control, max? Unless you go out of your way to manufacture zerglings, you can have at most 400 units at any one time (overlords and other flying units don't count, as their pathfinding is trivial, as per Harvest). Moreover, the player can only select 12 units at a time, the maps are static, and the AI does not have to select objectives (more or less---patrols could muddy this, and units will chase enemy units if they get close enough, but these are boundary cases). There are a lot of easy optimizations that can take advantage of all of these factors which may not be possible in Prison Architect. Again, apples to oranges, though the comparison is a bit better in this case.

As I have said over and over again, I am not disagreeing with your basic point that Prison Architect can get pretty laggy and that quite a bit of optimization really does need to happen before the game can be considered complete. You won't get any argument from me on that point. Many ideas for optimization have been floated above, some of which are quite interesting. Rather, my point is that you shouldn't expect Game X to perform well simply because Gamy Y performs well, and Gamy Y is superficially more complicated than (or similar to) Game X.

xander
Elandryl
level1
level1
Posts: 48
Joined: Sun Sep 29, 2013 12:43 pm

Re: Improve performance?

Postby Elandryl » Mon Sep 30, 2013 10:49 pm

xander wrote:I have not played the most recent Starcraft, nor have I played Supreme Commander, but I have played the original Starcraft. First off, you are pretty limited in terms of units. Any one player gets---what---200 control, max? Unless you go out of your way to manufacture zerglings, you can have at most 400 units at any one time (overlords and other flying units don't count, as their pathfinding is trivial, as per Harvest). Moreover, the player can only select 12 units at a time, the maps are static, and the AI does not have to select objectives (more or less---patrols could muddy this, and units will chase enemy units if they get close enough, but these are boundary cases). There are a lot of easy optimizations that can take advantage of all of these factors which may not be possible in Prison Architect. Again, apples to oranges, though the comparison is a bit better in this case.


Well, 15 years have passed since the first Starcraft. In Starcraft II, no more "12 units" at a time, you can launch a hundred units simultaneously if you wich. So can the seven other players. Through ramps, mazes, so you need a true pathfinder, updated at every frame because, unlike in PA, the units DO collide between themselves. That's thousands of units with a pathfinder updated at every frame. And the thing runs at 60fps on a decent computer. And that's a hundred time worse in Supcom, with each player launching thousand of units on a 60x60km map. Do you really think that's less taxing for a CPU than making a pathfinder for 60 units that just have to avoid walls?

xander wrote:As I have said over and over again, I am not disagreeing with your basic point that Prison Architect can get pretty laggy and that quite a bit of optimization really does need to happen before the game can be considered complete. You won't get any argument from me on that point. Many ideas for optimization have been floated above, some of which are quite interesting. Rather, my point is that you shouldn't expect Game X to perform well simply because Gamy Y performs well, and Gamy Y is superficially more complicated than (or similar to) Game X.

xander


Well, I see your point, But Prison Architect isn't a new revolutionnal kind of game. The problems it faces with pathfinding have been existing for twenty years, and they all have been solved a long time ago. Optimisation, my friend.
User avatar
MAdMaN
level4
level4
Posts: 899
Joined: Mon Jul 19, 2004 4:12 pm
Location: Manchester, England

Re: Improve performance?

Postby MAdMaN » Mon Sep 30, 2013 10:55 pm

Elandryl wrote:Well, I see your point, But Prison Architect isn't a new revolutionnal kind of game. The problems it faces with pathfinding have been existing for twenty years, and they all have been solved a long time ago. Optimisation, my friend.

With Chris programming the engine from scratch it's reasonable to assume he isn't using any already existing pathfinding code.
Elandryl
level1
level1
Posts: 48
Joined: Sun Sep 29, 2013 12:43 pm

Re: Improve performance?

Postby Elandryl » Mon Sep 30, 2013 11:01 pm

Well, whatever the cause, the point of the topic was to draw attention on this problem, cause playing Prison architect as a slideshow isn't just an anomaly, it's a real pain in the ass.
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Re: Improve performance?

Postby xander » Tue Oct 01, 2013 12:01 am

Elandryl wrote:Well, 15 years have passed since the first Starcraft. In Starcraft II, no more "12 units" at a time, you can launch a hundred units simultaneously if you wich. So can the seven other players. Through ramps, mazes, so you need a true pathfinder, updated at every frame because, unlike in PA, the units DO collide between themselves. That's thousands of units with a pathfinder updated at every frame. And the thing runs at 60fps on a decent computer. And that's a hundred time worse in Supcom, with each player launching thousand of units on a 60x60km map. Do you really think that's less taxing for a CPU than making a pathfinder for 60 units that just have to avoid walls?

I didn't say it was less taxing, only that the comparison was not an apples to apples comparison.

Elandryl wrote:
xander wrote:As I have said over and over again, I am not disagreeing with your basic point that Prison Architect can get pretty laggy and that quite a bit of optimization really does need to happen before the game can be considered complete. You won't get any argument from me on that point. Many ideas for optimization have been floated above, some of which are quite interesting. Rather, my point is that you shouldn't expect Game X to perform well simply because Gamy Y performs well, and Gamy Y is superficially more complicated than (or similar to) Game X.

Well, I see your point, But Prison Architect isn't a new revolutionnal kind of game. The problems it faces with pathfinding have been existing for twenty years, and they all have been solved a long time ago. Optimisation, my friend.

Again, I don't disagree (other than to note that the sentence "Optimisation, my friend," is both really condescending and naive at the same time). The game needs optimization. No one is arguing that. If all you said was "Prison Architect lags like crazy when there are a lot of units running around. This needs to be improved before the game is released," I doubt that anyone would object. I certainly wouldn't. They only objection I have to anything that you have posted is that you keep implying that because other games that have superficially similar problems to solve are super-smooth, PA should be super-smooth, as well.

Aside from the fact that studios like Blizzard have far greater resources to throw as the superficially similar problems, it is quite likely that the problems that IV are trying to solve are not identical to the problems solved in other games. Yes, there is room for improvement, but comparisons to other games (unless you really understand what is going on under the hood) are spurious at best.

xander
Elandryl
level1
level1
Posts: 48
Joined: Sun Sep 29, 2013 12:43 pm

Re: Improve performance?

Postby Elandryl » Tue Oct 01, 2013 12:14 am

xander wrote:Again, I don't disagree (other than to note that the sentence "Optimisation, my friend," is both really condescending and naive at the same time). The game needs optimization. No one is arguing that. If all you said was "Prison Architect lags like crazy when there are a lot of units running around. This needs to be improved before the game is released," I doubt that anyone would object. I certainly wouldn't. They only objection I have to anything that you have posted is that you keep implying that because other games that have superficially similar problems to solve are super-smooth, PA should be super-smooth, as well.

Aside from the fact that studios like Blizzard have far greater resources to throw as the superficially similar problems, it is quite likely that the problems that IV are trying to solve are not identical to the problems solved in other games. Yes, there is room for improvement, but comparisons to other games (unless you really understand what is going on under the hood) are spurious at best.

xander

Think what you want about my sentence about optimisation, that's your problem. For the rest, we mostly agree. The point is not to compare Introversion to Blizzard, it was simply to state that you won't make me believe that it's actually normal for a game like Prison Architect to fail to run smoothly on a decent computer when other more complex games do, that's all. Of course it's an alpha problem, but the point about this forum is specificaly to discuss about what should be modified or upgraded in the next alphas, right? I'm sorry, but for a professionnal dev team, making an efficent pathfinder for 60 unit is NOT the next step in the future of videogame development, it's just doing something that dozens of games have been able to do quite smoothly for the past ten years.
User avatar
MAdMaN
level4
level4
Posts: 899
Joined: Mon Jul 19, 2004 4:12 pm
Location: Manchester, England

Re: Improve performance?

Postby MAdMaN » Tue Oct 01, 2013 12:28 am

Elandryl wrote:I'm sorry, but for a professionnal dev team, making an efficent pathfinder for 60 unit is NOT the next step in the future of videogame development, it's just doing something that dozens of games have been able to do quite smoothly for the past ten years.

And how many of those games have opened up their code so that other developers can use their pathfinding algorithms?
User avatar
xander
level5
level5
Posts: 16869
Joined: Thu Oct 21, 2004 11:41 pm
Location: Highland, CA, USA
Contact:

Re: Improve performance?

Postby xander » Tue Oct 01, 2013 12:40 am

Elandryl wrote:...when other more complex games do...

Do you know that they are actually more complex? If so, please share.

For instance, a quick Google of the algorithms involved in Starcraft 2 indicate groups of units traverse vastly simplified networks with some flocking and queuing algorithms thrown in to avoid collisions, speed things up a bit, and make things look pretty. This means that
  • Paths are not computed for individual units. Units generally move in groups, thus a groups of units share the same path. One could argue that the player could order units around one at a time, but the reality is that a person almost certainly can't order units around fast enough to do what Prison Architect is doing. Units in Prison Architect don't move in groups for the most part. Collisions aren't really a problem, so the flocking and queuing behaviour are irrelevant.
  • Pathfinding happens along a simplified representation of the map, which is aided by the fact that the maps are static. Fewer nodes means much more efficient pathfinding. It is conceivable that the internal representation of maps in Prison Architect could be simplified (i.e. paths could be taken to go from one room to anther, rather than from one grid cell to another), but then the computational load is shifted to defining the interiors of rooms, dealing with multiple points of entrance, and so on. It might result in improved performance. It is hard to say from the outside, since the graph nodes have to be recalculated with some regularity. Dynamic maps are a bitch.
These two things are enough to argue that the pathfinding problems that IV are trying to solve in Prison Architect are significantly different from those that Blizzard was trying to solve in Starcraft 2. Which problems really represent the more complex game? *shrugs* It is hard to say without really understanding the internal representations of maps in both games, how paths are found, how paths are followed, and so on.

Elandryl wrote:...the point about this forum is specificaly to discuss about what should be modified or upgraded in the next alphas, right?

Okay, so what would you modify or upgrade?

You keep stating that other, more complex games run better, but you have yet to actually explain how those games are more complex, how you think they have solved the problems that Prison Architect is trying to solve, or why the comparison is valid. Making spurious apples to oranges comparisons to other games doesn't actually add anything to the discussion.

xander
User avatar
paktsardines
level5
level5
Posts: 1752
Joined: Mon Oct 01, 2012 11:10 am
Location: Australia

Re: Improve performance?

Postby paktsardines » Tue Oct 01, 2013 4:10 am

For instance, a quick Google of the algorithms involved in Starcraft 2 indicate groups of units traverse vastly simplified networks with some flocking and queuing algorithms thrown in to avoid collisions, speed things up a bit, and make things look pretty.


Exactly. Prison Architect is far more complex than Starcraft, so to compare it to starcraft is pointless. To clarify, starcraft units do not:

. Act under their own free will. That is, they do not have a hierarchy of needs to be constantly evaluated and acted upon.
. Need to constantly plan and evaluate escape options.
. Need to constantly evaluate contraband smuggling options.
. Have a mood than needs to be evaluated/adjusted every time events occur.
. Have to work out which direction to dig.
. Eat bacon

Every one of which adds a layer of complexity that Starcraft doesn't have.
acegamer08
level3
level3
Posts: 425
Joined: Sat Feb 23, 2013 6:13 pm

Re: Improve performance?

Postby acegamer08 » Tue Oct 01, 2013 4:20 am

eat bacon....really?

that's "complex"...lol
5hifty
level4
level4
Posts: 589
Joined: Sun Aug 18, 2013 8:22 am

Re: Improve performance?

Postby 5hifty » Tue Oct 01, 2013 4:21 am

acegamer08 wrote:eat bacon....really?

that's "complex"...lol


only if you want it to taste good
Elandryl
level1
level1
Posts: 48
Joined: Sun Sep 29, 2013 12:43 pm

Re: Improve performance?

Postby Elandryl » Tue Oct 01, 2013 7:48 am

paktsardines wrote:
For instance, a quick Google of the algorithms involved in Starcraft 2 indicate groups of units traverse vastly simplified networks with some flocking and queuing algorithms thrown in to avoid collisions, speed things up a bit, and make things look pretty.


Exactly. Prison Architect is far more complex than Starcraft, so to compare it to starcraft is pointless. To clarify, starcraft units do not:

. Act under their own free will. That is, they do not have a hierarchy of needs to be constantly evaluated and acted upon.
. Need to constantly plan and evaluate escape options.
. Need to constantly evaluate contraband smuggling options.
. Have a mood than needs to be evaluated/adjusted every time events occur.
. Have to work out which direction to dig.
. Eat bacon

Every one of which adds a layer of complexity that Starcraft doesn't have.


Ok, I get it. We should contact the NASA, cause honestly, only a machine that can handle rocket launch calculations might be able to deal with such complex behaviors (especially bacon).
User avatar
paktsardines
level5
level5
Posts: 1752
Joined: Mon Oct 01, 2012 11:10 am
Location: Australia

Re: Improve performance?

Postby paktsardines » Tue Oct 01, 2013 8:00 am

Actually, I think you'll find rocket launch calculations are even less CPU intensive than running starcraft.
User avatar
peardude
level1
level1
Posts: 47
Joined: Fri Jul 26, 2013 3:22 am

Re: Improve performance?

Postby peardude » Tue Oct 01, 2013 11:35 am

acegamer08 wrote:eat bacon....really?

that's "complex"...lol


Have you seen how they eat bacon? They eat it with spoons!

Return to “Community Members”

Who is online

Users browsing this forum: No registered users and 16 guests