Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[omg_scout]

...

I think you might have confused my O(3n) and O(2n) example with O(n^3) and O(n^2) - understandably, since generally, all the constant factors and smaller terms are dropped to simplify things. You could get the former by refactoring your code a little bit. You won't get the latter without changing the design.

Indeed I misread. I took it to be O(n^3) which is often being written as O(n3) . Point for you.

...

How'd you manage to flip the big O types? (...)

Design changes, information flow changes. Job picking algorithm can easily vary from O(1) to O(n^2), depending on your design.

[Telgin]

To be clear on that, Toady does explicitly optimize the game as he develops.  I'm reminded of a devlog where he stated that moving around in towns was unbearably slow after adding werecreature transformations because the game had a very naive algorithm of checking current forms whenever actions were taken.  I believe he fixed that by caching a lot more things than looking them up at the time they were needed.  A classic example of trading memory for CPU cycles.

How much he does this sort of thing is anyone's guess, though, and what the complexity classes of his algorithms are is also anyone's guess.  He seems to use libraries to handle as much stuff as he can though, so I'd expect most things like list searches to be using very good algorithms.

[GreatWyrmGold]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

[Lamiales]

nvm

[MrWiggles]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

[Zarat]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

Yes, but the whole point is it doesn't have to be that way.

[MrWiggles]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

Yes, but the whole point is it doesn't have to be that way.

So, you're saying that that dwarf fortress can be infinitely large (in terms of item count and embark size) and old?

[GreatWyrmGold]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

I wasn't advocating that side of the argument, merely explaining it. Humans are amazingly illogical at times.

[Zarat]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

Yes, but the whole point is it doesn't have to be that way.

So, you're saying that that dwarf fortress can be infinitely large (in terms of item count and embark size) and old?

Not "infinitely" large, obviously, since the universe can't do infinitely large, but sufficiently large such that the average modern desktop would have no problem with thousand year embarks bigger than anyone could possibly ever want.

[GreatWyrmGold]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

Yes, but the whole point is it doesn't have to be that way.

So, you're saying that that dwarf fortress can be infinitely large (in terms of item count and embark size) and old?

Not "infinitely" large, obviously, since the universe can't do infinitely large, but sufficiently large such that the average modern desktop would have no problem with thousand year embarks bigger than anyone could possibly ever want.

Either you are unaware of the sheer complexity of DF or you think everyone has supercomputers. And that DF is multithreaded.

[Zarat]

Why is it a generally held belief that ToadyOne doesnt do any optimization as he works?

Because DF still has FPS problems. Also, new features tend to increase CPU load on average.

FPS issues will always persist though. A larger enough and or old enough fortress will slow down any computer.

Yes, but the whole point is it doesn't have to be that way.

So, you're saying that that dwarf fortress can be infinitely large (in terms of item count and embark size) and old?

Not "infinitely" large, obviously, since the universe can't do infinitely large, but sufficiently large such that the average modern desktop would have no problem with thousand year embarks bigger than anyone could possibly ever want.

Either you are unaware of the sheer complexity of DF or you think everyone has supercomputers. And that DF is multithreaded.

No, no, and no.

You're overestimating the complexity of DF and underestimating modern computing power and, most importantly, the benefits of algorithmic improvements. Keeping track of millions of objects and updating their positions, checking for collisions, updating various states, etc. is not as big a deal as you seem to think it is. Temperature, fluid, and weather simulations need not grind FPS down significantly at all.

Even if it was multithreaded, again, even in the best possible imaginary case, that wouldn't yield speedups of more than 2-4x for most people, which is nothing. It's great if you have nowhere left to go, and you want a more responsive UI, but otherwise not usually worth the trouble for most applications.

[MadocComadrin]

Actually, once you get into the 10s of thousands, it *does* become a big deal unless the only work you have to do on them is simple calculations. Nevetheless, as long as Toady is putting thought into his overall design architecture, individual algorithmic changes can wait until things become a bit more permanent.

[GreatWyrmGold]

There's dozens of things DF is keeping track of, at a low estimate, from the temperature of every rock you mine to how the dwarf's attributes and personality affect his or her actions. And it's only getting more complex...

[Zarat]

Actually, once you get into the 10s of thousands, it *does* become a big deal unless the only work you have to do on them is simple calculations. Nevetheless, as long as Toady is putting thought into his overall design architecture, individual algorithmic changes can wait until things become a bit more permanent.

Yeah, it becomes a slightly bigger deal if you have to update every single one of the millions in real-time.

Fortunately that's not the case - though even then it's still doable.

I don't think there is any overall design architecture. I think that's (part of) the problem. For one, there'd be very little way to plan it out in advance given the additions that have been made.

There's dozens of things DF is keeping track of, at a low estimate, from the temperature of every rock you mine to how the dwarf's attributes and personality affect his or her actions. And it's only getting more complex...

Uh-huh. Having played DF for a while and poked around with a decompiler I have a pretty good idea of how complex it is.