Print

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

[Nekudotayim]

Single threaded application... boo.   

Getting a game sim of any complexity to run across multiple cores is almost impossible.  Folks can generally dream up some fake game world situation where it would work - but for most games, no.  Something like DF where he is going to have an order of event applies and resolutions is impossible.

You could spend time going through the sim and looking for iterative loops where previous results don't affect others and split that operation up.  But its going to take a lot of time for probably not much reward.

Nah. For example: The path finding algorithm could be done by another thread implementing message queues for request and response. That way, everything stays synchronized but is still able to get calculated by multiple cpus, increasing the speed in total if you got 2 cores for this example. It's a general concept of server applications just to name it.

[Kogut]

In my naive approach I think that there are possibilities
- simulating outside world (weather, diplomacy)
- pathfinding - but maybe not for military
- ?

[ninja'd]

[Hateweaver]

Single threaded application... boo.   

Getting a game sim of any complexity to run across multiple cores is almost impossible.  Folks can generally dream up some fake game world situation where it would work - but for most games, no.  Something like DF where he is going to have an order of event applies and resolutions is impossible.

You could spend time going through the sim and looking for iterative loops where previous results don't affect others and split that operation up.  But its going to take a lot of time for probably not much reward.

Nah. For example: The path finding algorithm could be done by another thread implementing message queues for request and response. That way, everything stays synchronized but is still able to get calculated by multiple cpus, increasing the speed in total if you got 2 cores for this example. It's a general concept of server applications just to name it.

That would work except that your sim update is going to change your path-ablity.  So a path request updating at the begining of the sim update is going to have different data than one at the end of the sim update.  I'm used to working on sims which are determanistic so that they are more debug-able.  Adding randomness to the pathing resolution would drive me nuts.

Also you are going to have to make all data that the pather needs thread safe - that trade-off of locks is going to slow down the sim update which is the primary pinch point for the processing.

[Kogut]

So DF would have limit for pathfinding lag (n frames of main game) - and after it pathfinding would be started in main thread. Yeah - random crash almost impossible to debug.

[Hateweaver]

So DF would have limit for pathfinding lag (n frames of main game) - and after it pathfinding would be started in main thread. Yeah - random crash almost impossible to debug.

It really is going to depend on how the sim update applies the events and the time of resolution for each one. If he first applies all events which could changing pathing (cave-ins, switches to doors, things melting, etc, etc), and then does everything else (making things, dwarves eating, miasma, etc, etc) - then you could thread off the pathing.  There would be some contraints in that pathing decisions could only react to other pathing movers from the previous frame.  IE: If Urist McOutSideTheFort is running away from a gobo chasing him - he would be reacting to the position of the chasing gobo from the previous frame.

Also,  I don't know if DF has limits to the number of units in 1 tile - if it does (ie: No more than 3 units trying to get through a door-way), then this solution won't work.

[Nekudotayim]

Single threaded application... boo.   

Getting a game sim of any complexity to run across multiple cores is almost impossible.  Folks can generally dream up some fake game world situation where it would work - but for most games, no.  Something like DF where he is going to have an order of event applies and resolutions is impossible.

You could spend time going through the sim and looking for iterative loops where previous results don't affect others and split that operation up.  But its going to take a lot of time for probably not much reward.

Nah. For example: The path finding algorithm could be done by another thread implementing message queues for request and response. That way, everything stays synchronized but is still able to get calculated by multiple cpus, increasing the speed in total if you got 2 cores for this example. It's a general concept of server applications just to name it.

That would work except that your sim update is going to change your path-ablity.  So a path request updating at the begining of the sim update is going to have different data than one at the end of the sim update.  I'm used to working on sims which are determanistic so that they are more debug-able.  Adding randomness to the pathing resolution would drive me nuts.

Also you are going to have to make all data that the pather needs thread safe - that trade-off of locks is going to slow down the sim update which is the primary pinch point for the processing.

I do not really get your point here. All the input for the path finder would be read-only for it, since the outcome is some new data: the current path.

So DF would have limit for pathfinding lag (n frames of main game) - and after it pathfinding would be started in main thread. Yeah - random crash almost impossible to debug.

Err... what?

[Hateweaver]

"I do not really get your point here. All the input for the path finder would be read-only for it, since the outcome is some new data: the current path"

Even though it is read-only, it has to be thread safe. So you are going to have to either use reader/writer locks - or you are going to have to make a read-only full copy of ALL the data the pather needs at the start of the frame.

On the other - if you have any sim event whose resolution is going to depend on WHEN the thread it is in is executed - then you are introducing randomness.  Trying to debug a crash with a crash-dump is going to be impossible.

[Nekudotayim]

"I do not really get your point here. All the input for the path finder would be read-only for it, since the outcome is some new data: the current path"

Even though it is read-only, it has to be thread safe. So you are going to have to either use reader/writer locks - or you are going to have to make a read-only full copy of ALL the data the pather needs at the start of the frame.

Well, I agree but that depends on how smart you want it to become. If you - for example - want to implement the path finder being able to avoid dangerous areas depending on the current position of an enemy at this time, then you need to do, what you are pointing at. Transactions could help here.

On the other - if you have any sim event whose resolution is going to depend on WHEN the thread it is in is executed - then you are introducing randomness.  Trying to debug a crash with a crash-dump is going to be impossible.

Yes of course you are introducing randomness but it is not impossible to find the error. Logfiles could be helpful. It's not like we are reinventing the wheel here.

[Hateweaver]

"Well, I agree but that depends on how smart you want it to become"
It is not just reacting to other movers - but reacting to the path data from the sim itself (doors closing, paths being destroyed, etc).

Logfiles do help - but trying to sync logs from different threads so you can interlace then to figure out wtf happened is a big pain in the ass.

Also- all of this is based on the assumption (probalby true) that pathing in DF takes a lot of time. If that is true - then even just adding a long range/short range pather to the single threaded sim might help it alot.

[Nekudotayim]

It is not just reacting to other movers - but reacting to the path data from the sim itself (doors closing, paths being destroyed, etc).

Once the initial path has been calculated you know your way to go, if something on this path changes, you can request a new one.

Logfiles do help - but trying to sync logs from different threads so you can interlace then to figure out wtf happened is a big pain in the ass.

I have never seen any business application I have been working on since the last 7 years trying so sync the logs. And we always have been able to find the errors. It's more difficult, I admit.

Also- all of this is based on the assumption (probalby true) that pathing in DF takes a lot of time. If that is true - then even just adding a long range/short range pather to the single threaded sim might help it alot.

I like the idea of using a long range/short range pather.

Btw. the pathfinder was just an example.

[Hateweaver]

The long range/short range idea I've used before is kinda similar to what you suggested above.  Each frame the short range one is really just quick logic to keep you on a path layed out by A* from the long range pather.  If it cannot get you where it needs to, it tries to get you close, if it can't do that it figures out if the original long range path it has is still viable - if not it requests a new one next frame.   In that next frame the long range pather has a list of requests which is can prioritize and gate based on how much time it has to opperate.

On the logs - the problem I frequently have is that each thread writes into its own log file (otherwise you have the issue of write contention on the log file which creates bottlenecks that you are trying to avoid in the first place).  So you end up with 3 different files that you are trying to interlace together on the same timeline so you can figure out what happened.

[darkrider2]

Ah, another thread successfully invaded by the multi-core debate. If IIRC, a lot of these things end with people saying they run DF in one core and just go do other stuff while it's running, or on the flip side, end with people trying to speak for toady.

Either way I find it rather arbitrary as I seriously doubt there is a large number of individuals on the forum who actually understand multicore coding (the two in this thread seem competent though), and there are even less who know the details into DF's code.

If you want my advice, the forumites are rather intuitive and have invented incredible ways to get around the games many inconveniences. There's a magma pump stack built specifically to stop the game from recalculating temperature (which is what makes usual magma pumps cause so much fps drop). You can even drop a chunk of land on the magma sea and cause magma to be displaced to the top.

[Nekudotayim]

On the logs - the problem I frequently have is that each thread writes into its own log file (otherwise you have the issue of write contention on the log file which creates bottlenecks that you are trying to avoid in the first place).  So you end up with 3 different files that you are trying to interlace together on the same timeline so you can figure out what happened.

Ah, now I get your point here. Well, the API does that for me, so I never thought about it.

I guess we officially undwarvened this thread. :-) Yes, see post above.

[Marthnn]

There would be some contraints in that pathing decisions could only react to other pathing movers from the previous frame.  IE: If Urist McOutSideTheFort is running away from a gobo chasing him - he would be reacting to the position of the chasing gobo from the previous frame.

Of course! If it wasn't so, pathing decision would be dependent on the order of the pathing. Say you are the 1st creature on the map to path, then you will have priority over everyone, and others will be able to anticipate your move 1 frame in advance. In that case, it wouldn't be timeframes but stateframes : each frame is a change of state, and time only advances once a full cycle has been done.

The use of timeframes lets you calculate the next frame using data from the current frame and nothing else. I don't see where's the problem, this computation has a known input and can be separated into several threads, such as "pathing of Urist McWoodcutter" and "pathing of Goblin EliteAmbusher". Once all movements are done, you can get to the next part: "Goblin EliteAmbusher decapitates Urist McWoodcutter".

Note that my knowledge of multi-threading requirements is very limited...

Either way I find it rather arbitrary as I seriously doubt there is a large number of individuals on the forum who actually understand multicore coding (the two in this thread seem competent though), and there are even less who know the details into DF's code.

Ah. I know numerical modeling, up to a certain point. I'm probably way out of my league about multicore coding AND DF code details.

I'll stop. now.

[Nekudotayim]

Just one last word about this topic from my side. If you really do not like to implement a multi-theading application and make your thoughts about all the complications that come along with it, use Erlang.