modular design + threads *WARNING: LONG POST*

[DaleStan]

CmdKewin, I have but three words for you:

FIX!
YOUR!
SIG!

[webfreakz.nl]

@Dalestan:

You could also send him a PM!

[CmdKewin]

Yes, sorry everyone, I don't know how my default signature got pasted over here.


Returning On Topic.

Modular design is something you'll always have to look forward to,
But with only one "condition":

It's only good when you write something from scratch. Not when you've got something already complex AND working ("Don't fix if it ain't broken"). I say that by experience.

Unless you want to use some Refactoring tools, wich where, last time I checked, invented for doing just that. Good luck in finding an automated tool who Refactors Code just the way YOU want it.

I basically "could" give it a shot, but I can't promise ANYTHING. Mostly because i'd rather have full NEWGRF support before anything else. That, IHMO, is what should be OTTD's highest priority. Not easy, i know, but life is made of priorites.

[Korenn]

[...]However you did give me one idea. Drawing on the screen is really slow, so if it were given it's own thread, we could make the core run at a fixed speed (like now) and then skip a frame if the previous frame is not done drawing. The result from this would be that if a computer got problems keeping up the speed, it would start frame skipping instead of slowing down the game. In large network games, some clients might get problems keeping the speed, but if they start frame skipping to ensure that the core keeps the same speed as the server, they would not desync, like a core slowdown will. It would also speed up on multiple CPU computers as all the core functions can run on one CPU and the drawing can run on another. It could also mean that the settings could alter the framerate to slow down on purpose, like you say that you only want 5 fps in fast forward while you like the current framerate when not fast forwarding. This would make fast forward a lot faster and slow computers would benefit from this. Also computers running on battery would benefit from this as less battery power is needed to fast forward say a year[...]

This has as an added advantage that when all the code for drawing on screen is done by a separate thread, it's possible to move the whole thing to the GPU on future gfx cards which will make things a whole lot faster.

[Bjarni]

[...]However you did give me one idea. Drawing on the screen is really slow, so if it were given it's own thread, we could make the core run at a fixed speed (like now) and then skip a frame if the previous frame is not done drawing. The result from this would be that if a computer got problems keeping up the speed, it would start frame skipping instead of slowing down the game. In large network games, some clients might get problems keeping the speed, but if they start frame skipping to ensure that the core keeps the same speed as the server, they would not desync, like a core slowdown will. It would also speed up on multiple CPU computers as all the core functions can run on one CPU and the drawing can run on another. It could also mean that the settings could alter the framerate to slow down on purpose, like you say that you only want 5 fps in fast forward while you like the current framerate when not fast forwarding. This would make fast forward a lot faster and slow computers would benefit from this. Also computers running on battery would benefit from this as less battery power is needed to fast forward say a year[...]

This has as an added advantage that when all the code for drawing on screen is done by a separate thread, it's possible to move the whole thing to the GPU on future gfx cards which will make things a whole lot faster.

but the issue of locking the map array and vehicle array and so on while calculating what to draw. For the first time in a very long time I got an idea and then I have not figured out how to do it
We need somebody to get a plan that will work before work can start on such a task. If nobody gets such an idea.... oh well, the idea is nice

[bobingabout]

threading the graphics drawing routine is a great idea... almost as good as use the GPU for graphics. help prevent networking desyncs, would also help it run on older computer when 32bpp comes.

[Tron]

threading the graphics drawing routine is a great idea... [...]. help prevent networking desyncs, [...]

Nonesense.
Slow drawing is not in any way related to desynchronisation.
Desyonchronisation happens when the client and server do different things, which is always the result of a programming error.
Please do not spread disinformation.

[bobingabout]

well, it'd help it run on older computers atleast. because instead of lag, it would frame skip.

[Expresso]

Bjarni, how about cutting the job up in stages? How about cacheing things? (to keep locks to a minimum). You could fetch all relevant information first, and then do the actual work.

And errr... to keep threading complications to a minimum... how about a message system? That way the need to lock things belonging to other threads will be extremely limited. The only locks which should occur would be to read from or write to a message queue (1 message queue per thread). The other advantage would be the ability to handle messages when the thread is able to, not a moment earlier. I think the result of this could be: a) less impossible to find threading related bugs, b) better extensebility, c) less threading related latency because of locks.

[Bjarni]

Bjarni, how about cutting the job up in stages? How about cacheing things? (to keep locks to a minimum). You could fetch all relevant information first, and then do the actual work.

And errr... to keep threading complications to a minimum... how about a message system? That way the need to lock things belonging to other threads will be extremely limited. The only locks which should occur would be to read from or write to a message queue (1 message queue per thread). The other advantage would be the ability to handle messages when the thread is able to, not a moment earlier. I think the result of this could be: a) less impossible to find threading related bugs, b) better extensebility, c) less threading related latency because of locks.

now that is a lot of stuff to cache. This tradeoff might be too big on a single CPU system since it takes time to copy so much data for each frame

[Expresso]

now that is a lot of stuff to cache. This tradeoff might be too big on a single CPU system since it takes time to copy so much data for each frame

errr... not if you cache only relevant data (which you got as a nice reply message)... do you need the vehicle name in order to draw its sprite?

example situation: viewport wants to draw some vehicles.

step 1) send message to engine containing some information at which tiles the viewport is looking.
step 2) engine collects all relevant information (facing, sprite and position?) of all vehicles visible to the viewport, and sends a message containing that information back.
step 3) viewport renders according to reply (or from cache) (note: it only got information which is of some relevance, so it can blindly process that).

[Dextro]

Speaking about caching stuff, things like the list of vehicles and the list of stations should be chached and a trigger to add/del/alter the cache could be added to the functions that makes changes to it (thinking about build/sell/autoreplace/etc...).

I remember sometime ago someone speaking about an easy way to get how many vehicles a player has (probably about the subsidiaries patch) and it was hard to do is since what's in-game now makes a loop of every vehicle/station existing to provide the list, isn't that a big overhead?

[Bjarni]

Speaking about caching stuff, things like the list of vehicles and the list of stations should be chached and a trigger to add/del/alter the cache could be added to the functions that makes changes to it (thinking about build/sell/autoreplace/etc...).

I remember sometime ago someone speaking about an easy way to get how many vehicles a player has (probably about the subsidiaries patch) and it was hard to do is since what's in-game now makes a loop of every vehicle/station existing to provide the list, isn't that a big overhead?

it is and I wondered if I should try to do something about it

[Korenn]

[...]However you did give me one idea. Drawing on the screen is really slow, so if it were given it's own thread, we could make the core run at a fixed speed (like now) and then skip a frame if the previous frame is not done drawing. The result from this would be that if a computer got problems keeping up the speed, it would start frame skipping instead of slowing down the game. In large network games, some clients might get problems keeping the speed, but if they start frame skipping to ensure that the core keeps the same speed as the server, they would not desync, like a core slowdown will. It would also speed up on multiple CPU computers as all the core functions can run on one CPU and the drawing can run on another. It could also mean that the settings could alter the framerate to slow down on purpose, like you say that you only want 5 fps in fast forward while you like the current framerate when not fast forwarding. This would make fast forward a lot faster and slow computers would benefit from this. Also computers running on battery would benefit from this as less battery power is needed to fast forward say a year[...]

threading the graphics drawing routine is a great idea... [...]. help prevent networking desyncs, [...]

Nonesense.
Slow drawing is not in any way related to desynchronisation.
Desyonchronisation happens when the client and server do different things, which is always the result of a programming error.
Please do not spread disinformation.

interesting, I sense a disturbance in the development force

[TrueBrain]

[...]However you did give me one idea. Drawing on the screen is really slow, so if it were given it's own thread, we could make the core run at a fixed speed (like now) and then skip a frame if the previous frame is not done drawing. The result from this would be that if a computer got problems keeping up the speed, it would start frame skipping instead of slowing down the game. In large network games, some clients might get problems keeping the speed, but if they start frame skipping to ensure that the core keeps the same speed as the server, they would not desync, like a core slowdown will. It would also speed up on multiple CPU computers as all the core functions can run on one CPU and the drawing can run on another. It could also mean that the settings could alter the framerate to slow down on purpose, like you say that you only want 5 fps in fast forward while you like the current framerate when not fast forwarding. This would make fast forward a lot faster and slow computers would benefit from this. Also computers running on battery would benefit from this as less battery power is needed to fast forward say a year[...]

threading the graphics drawing routine is a great idea... [...]. help prevent networking desyncs, [...]

Nonesense.
Slow drawing is not in any way related to desynchronisation.
Desyonchronisation happens when the client and server do different things, which is always the result of a programming error.
Please do not spread disinformation.

interesting, I sense a disturbance in the development force

The funniest thing is, they are both partly right. It WILL help against slower clients in a networkgame, but not against desyncs. It does help against timeouts from those clients.
Now when a client slips behind, it stays behind, if it is not able to recover from it, if it can't speed up enough to get back at the same frame the server is. Only, the error given on the client isn't a desync error, but a simple timeout. Desyncs are, as Tron stated pretty clear, always a programming error, on which level what so ever, or, the other possibility, different NewGRF loads on client/server and/or modifications on either the server or client. Short, it is a problem in different handling of information (and the order of doing that), never of slowness of the system.

Now about threading the graphics, it will not really help against timeouts, because the drawing isn't consuming that much CPU. Pathfinding on the other hand is. That is why you see that many connection drops with 300+ trains maps.

I hope that clears the thing up around desyncs and timeouts (and now lets hope I remembed the network code correctly, which I should :s)

[DmitryKo]

Sorry for bringing out an old post, but there were some interesting ideas, and I'd like to hear more feedback on them.

There are some valid points that it's not feasible to start any kind of major alteration - such as modular structure, multithreading, general speed optimisations, C++ style conversions, OpenGL rendering, whatever - until OpenTTD is feature complete (completeness is a moving target though - to me, OpenTTD 0.4.5 is pretty feature complete because it's everything that TTD was and even more )

I guess the current intentions are to get rid of TTD legacy almost entirely, so both the code and art are "clean" for licensing purposes. So maybe the team would set some major milestone (0.5.0 seems to be a good candidate) after which feature freeze is declared, so the developers could dedicate themself to making whatever code conversions will be deemed appropriate to simplify further development...


Now back to the original post:

1. Make a message system, which has the ability to queue messages. Move code to its appropriate location (no map code in vehicle code, no vehicle code in ui code, no ui code in sound code, etc.)
   The message queue should be simple enough to make, but there might be a need to skip some messages temporarily until they can be processed. The messages should contain as little information as possible and only contain relevant information. This to ensure both performance and simplicity. Some strange modifications might become needed for this.
2. Build wrappers, to allow for a painless transition.
3. Build message handlers in the appropriate places.
4. convert wrappers to message system.

Well, messages typically wouldn't contain ANY complex data, not just "as little as possible", or they are soon indistinguishable from objects and conversion to object-oriented code is imminent. The only real purpose of events would be to signal the engine to start some operations, but the current engine does everyting all at once by simply looping all the game entities, and it works fine for now.

Yes, multithreading would require some syncronisation measures, but it basically doesn't mean the entire engine has to be split in parts that can only communicate with simple messages (although the network code does essentially this ) - you just set the shared memory and restrict acces to the critical sections with mutexes, semaphores and other OS-specific stuff.


What needs to be done in the first place is replaceing direct accesses to the tile array with inline wrapper functions (that could possibly be converted into member functions at a later stage), in orcer to hide actual implementation details, and I guess it's currently being implemented. Only then you could start moving the code to appropriate locations and change the data structures.

5. Now start puting things in threads... I suggest the following

Currently there's no real need for threads because the current engine is not computation-limited, although that could change in the future as parts of the AI get rewritten and get more complex. And there's no easy way to directly communicate with a child thread, so basically game structures should be altered so to be as much independent as possible (which is not currently the case).

As for separate modules, firstly implementation details should be hidden entirely and direct access to game entities is prohibitedm and only then you could actually start rearranging internal structures so they better match different tasks of the engine. It just makes no sense to break the engine in parts without considering actual data structures and access patterns. And even then any performance issues could be tuned just by adjusting the ticks for any particular part of the engine.

1. User Interface (includes console) + viewport + OS interface (just needs to keep going with as little lag as possible).
2. Network Interface + game ticks: would this help fight desyncs?
3. Sound engine / mixer (just to be sure sound works, no matter what happens to the other parts of the game).
4. AI players: unknown how much time a given AI player consumes.
5. Pathfinder: keep game lag to a minimum.
6. Vehicle database.
7. Map engine.
8. Message system

I'll comment on that later.

[Edit] Never write anything at a late night Done some rewording to make more sense.

[bobingabout]

something else i recently read. someone wants suport for multiple CPUs, if the graphics were threaded, then, since the graphics can take a lot of juice, like NPF, threadding the graphics would allow 1 CPU to handle graphics, while the other handles the rest.

[DmitryKo]

[quote="Expresso"][list=a]
[*]User Interface (includes console) + viewport + OS interface (just needs to keep going with as little lag as possible).
[*]Network Interface + game ticks: would this help fight desyncs?
[*]Sound engine / mixer (just to be sure sound works, no matter what happens to the other parts of the game).
[*]AI players: unknown how much time a given AI player consumes.
[*]Pathfinder: keep game lag to a minimum.
[*]Vehicle database.
[*]Map engine.
[*]Message system[/list][/quote]
Sorry, but I think you miss some critical points and confuse threads with code modules. Even though the engine can be highly modular - i.e. have well-defined functional interfaces so the whole parts can be replaced entirely by linking with a different code module or loading a different DLL without breaking other parts - it doesn't necessarily mean all these parts need to run in different threads! There should be some clear goals that can be achieved, i.e. improving responsiveness or performance scaling on multiprocessor machines.


Take your "graphics, user interface and OS interface". First, there are already at least some modularization, because some OS-specific things are handled by different modules (and multithreading is OS-specific in the first place, because it's not supported on UNIX). Then, while user interface is closely related to graphics, it's actually a separate entity from the rendering engine.

Consider having several different rendering engines for different platforms - for example, an OpenGL-accelerated sprite renderer, a PocketPC software renderer, maybe a hypothetical 3D renderer. They can all use the same current user interface concept - i.e. mouse-clickable vehicles each with their own window, vehicle and town lists, top button row layout, window buttons laouyt, function key combinations, etc.
OR, a different user interface could be implemented for each engine, considering the capabilities of the target platform and its renderer - say, a Pocket PC interface that doesn't rely on keyboard, has different button layout etc, or maybe some crazy stuff with 3D vehicle views etc.
And either interface or rendering engine would still be driven by the same game logic.

So the options are either
1) rendering and the user interface could be separated in two different code entities (function sets, modules etc.) for easier expandability AND some critical parts could be multithreaded for increased performance or responsiveness, OR
2) some parts of the existing rendering and UI code could be multithreaded, given that some internal data structures are rearranged to better handle interprocess syncronisation

I'm not saying anything of that is required or should even be considered as a possible direction, I just want to make it clear that the decision to break the code in modules needs to be based on some solid grounds and should not be confused with multithreading the existing code.


"Network protocl and sync, sounds and music": while these parts are not entirely independent (they basically rely on game logic and don't have a lot of work to do on their own), they deal with different hardware devices so I think an multithreading attempt could be made.


AI players - well, there no such thing as AI players, at least from the coding point of view OK, maybe I'm a little bit overemphasizing, but there's no easy way gain any benefits by dividing the game logic into different execution threads. There are lot of shared data structures with dependent data access patterns, so they need to be would be heavily mutexed and multiple threads would just end waiting for each other, add nothing but syncronization overhead.
And the game engine is already threaded, because it is and should continue to be the main thread in the program

to be continued

[DmitryKo]

Pathfinder - again, there are lots of dependencies on the tile map array and other game data. I really doubt it would be practical to separate it.

But I recall that sector-based game engines like Doom, Quake and Duke3D have their game levels partitioned into binary trees of sectors (BSP). This mainly helps avoid screen drawing overhead but also simplifies the game logic, because game actors never have to do anything in any sectors besides the current one, and every action is heavily scripted.

I guess NPF pathfinder already uses some clever tricks, but maybe it should go farther completely avoid direct polling of the map tile array. The paths would be precompiled into a graph at the load time and then just updated thoughout the game - that is when a station/dock/airport/depot is created or altered, when a road/rail/water is set/removed etc. This would reduce the CPU load in extreme cases and provide for some neat features like as auto-counting the buoys and road signs as path nodes, train schedules, air traffic control etc. Only then maybe there would be less syncronization to perform, so some pathfinding tasks could be multithreaded in an efficient way.


Vehicle database - well, ideally there should be no such thing from the engine point of view, because different parts of the game engine need some different vehicle data. That is, the renderer doesn't have to know anything about the vehicle name, capacities, running costs, current orders etc., the game logic shouldn't even care about what sprites or polygons/textures the vehicle model use, the name strings etc., pathfinder would only need to know vehicle position etc., and the user interface doesn't need to keep track of all the vehicles in the game as well.


Map engine - you all know what I'm going to say now Terrain handling is actually just a part of the game engine and I guess it consumes very low fraction of CPU resources anyway.

There are some issues associated with the current implementation. Ideally, the terrain map as the array of tiles should only be accessed by the renderer and user interface. The problem is that the original game design just assumed it would be natural to store much of the game AI data right in the tile map array and then allow to access it directly, instead of maintaining different datasets for different tasks. I can't really blame the original designer for this decision, considering the memory requirements and CPU speed of a typical gamer's PC in the year 1995 and the single-tasking OS (Pentium 75 with 8 MBytes of RAM anyone? Today's handhelds can be an order of magnitude as powerful). This was an established way of writing the early generation platform and scrolling games.

However, now this decision has hammered back, because it's not easy to hide realization details so to add new features in an efficient way. I mean, the terrain shouldn't really care or dictate what's built on it or beneath it, although the tiles could still be an essential part of the game logic (at least for compatility

[Tron]

(and multithreading [...], because it's not supported on UNIX)

Any more bullsh^Winsights?

to be continued

please not