5 ms·

Depends on the game, really. Take a look at minecraft and dwarffortress - they are both cpu-bound due to 1. Simulating a large world using complex entities and

Depends on the game, really. Take a look at minecraft and dwarffortress - they are both cpu-bound due to 1. Simulating a large world using complex entities and voxels 2. Being single-threaded with no clear way to make them multi-threaded Minecraft in particular is a pretty interesting problem since it only simulates the part of the world that's within a radius of a player, it would make sense to have each player's machine simulate their own part of the world and the server to somehow merge those together.

stephengillie 14y ago
Good point. This is most obvious on Minecraft. Minecraft, to me, is a visual 3d database -- digging dirt doesn't remove something, it merely changes the value for that block in the database -- from "dirt" to "air" -- which changes how the game's algorithms act. And the game still ships with "developer graphics" which would have been easy for a TNT to run.
duaneb 14y ago
> Minecraft in particular is a pretty interesting problem since it only simulates the part of the world that's within a radius of a player, it would make sense to have each player's machine simulate their own part of the world and the server to somehow merge those together. I can't imagine people would trust each other enough to allow them to simulate themselves.
cousin_it 14y ago
Simulating a large world seems like a textbook example of an "embarrassingly parallel" problem, doesn't it? At least that's true for cellular automata.
- MichaelGG 14y ago
  I think the problem comes from that the world is a large mass of interconnected mutable state. You don't know if updating a particular object will update another. Think of a player crouching on a plank that another player just phasered. If you continue simulate the first player's movement "crawl forward" by itself, how do you integrate the result of the plank being disintegrated, causing the player to fall? The first player's simulation outcome depends on multiple inputs, but they aren't findable directly from that player's perspective. You have to first simulate the phaser beam to know the plank is gone to know the player is falling now, not crawling. And then imagine that with far more complex rules and a few hundred thousand objects having similar interactions, each one possibly modifying any other one.
  - Evbn 14y ago
    If you limit communication to "speed of light" , then each tick involves only local message passing, which is easily parallelizable.
kibwen 14y ago
I never got the impression that DF was single-threaded due to theoretical constraints, only that the game was originally single-threaded and that refactoring to make use of multiple threads is just too difficult for a lone developer on such a sprawling codebase.

stephengillie 14y ago

Good point. This is most obvious on Minecraft. Minecraft, to me, is a visual 3d database -- digging dirt doesn't remove something, it merely changes the value for that block in the database -- from "dirt" to "air" -- which changes how the game's algorithms act. And the game still ships with "developer graphics" which would have been easy for a TNT to run.

duaneb 14y ago

> Minecraft in particular is a pretty interesting problem since it only simulates the part of the world that's within a radius of a player, it would make sense to have each player's machine simulate their own part of the world and the server to somehow merge those together. I can't imagine people would trust each other enough to allow them to simulate themselves.

cousin_it 14y ago

Simulating a large world seems like a textbook example of an "embarrassingly parallel" problem, doesn't it? At least that's true for cellular automata.

MichaelGG 14y ago
I think the problem comes from that the world is a large mass of interconnected mutable state. You don't know if updating a particular object will update another. Think of a player crouching on a plank that another player just phasered. If you continue simulate the first player's movement "crawl forward" by itself, how do you integrate the result of the plank being disintegrated, causing the player to fall? The first player's simulation outcome depends on multiple inputs, but they aren't findable directly from that player's perspective. You have to first simulate the phaser beam to know the plank is gone to know the player is falling now, not crawling. And then imagine that with far more complex rules and a few hundred thousand objects having similar interactions, each one possibly modifying any other one.
- Evbn 14y ago
  If you limit communication to "speed of light" , then each tick involves only local message passing, which is easily parallelizable.

kibwen 14y ago

I never got the impression that DF was single-threaded due to theoretical constraints, only that the game was originally single-threaded and that refactoring to make use of multiple threads is just too difficult for a lone developer on such a sprawling codebase.