Important Dates

Latest Posts

Topic: Low FPS

einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1107
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-07, 08:46

@GunChleoc, will it be compatible with current savegame? I would like to test it, but I don't have much time to build another empire.

One way to achieve that is by performing the routing per flag, instead of per ware. Then each ware decides its next destination reading solely its current flag's info.

I was rather considering placing artificial route points, which define total route, but not the specific way. So the ware could go to route point A, then B, then C, then to warehouse/ workplace. Pathfinding would be much smaller then.

Algorithm has to find ware that is closest to requestor. It checks wares in warehouses and at flags/roads (referred to as providers).

So maybe a heuristic algorithm here? There are two cases: one when you have insufficient ware number (demand is greater than supply), second when you have more wares than needed (and you have 150 logs waiting in a traffic jam).

But sticking to the topic:

Do you know how can I finish my game for the tournament? Have you got any idea/ solution for that?


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
Tibor
Joined: 2009-03-23, 23:24
Posts: 1317
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2018-05-07, 08:53

The branch I linked should be fully compatible with trunk = the changes in algorithm does not affect savegame.

BTW - artificial route points looks like great idea. F.e skip flags on long stretches of roads


Top Quote
Tino
Joined: 2009-02-20, 17:05
Posts: 252
Ranking
Tribe Member
Location: Somewhere in Germany...
Posted at: 2018-05-07, 10:37

GunChleoc wrote:

I have created a bug for the .dll issue, hopefully our Windows packager can fix this. https://bugs.launchpad.net/widelands/+bug/1769426

Pathfinder is definitely a good guess, and with seafaring, it gets even more to do.

Debug builds generally run a lot slower than release builds, because the compiler can't do a lot of optimization.

As far as i understand einstein, the missing DLL problem does not occure with more recent builds? The problem is, that the appveyor builds are dynamically linked and the dlls are manually added by the ISS script. So if Appveyor updates/changes their environment, sometimes the ISS script has to be adapted. I've no idea how to automate this.

The problems should not occur with my builds on https://widelands.8-schuss.de/ , because i am linking everything statically. Perhaps i find a someday a solution for cmake to port this to appveyor, but for now i cannot get Cmake to link statically if libraries are available dynamically. On my personal system i can compile every library and forcing only static builds, but that is not possible on appveyor...


Top Quote
Tino
Joined: 2009-02-20, 17:05
Posts: 252
Ranking
Tribe Member
Location: Somewhere in Germany...
Posted at: 2018-05-07, 10:46

But sticking to the topic:

Do you know how can I finish my game for the tournament? Have you got any idea/ solution for that?

If you can run windows 64bit builds, i can compile a certain buildnumber/ branch for you. But i am not sure which version would be able to load your savegame and includes the bugfix...


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1107
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-07, 12:33

Thank you Tino for this. I will try to compile on a vritual machine. If it fails, I will ask you directly. face-smile.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 3156
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2018-05-07, 12:38

einstein13 wrote:

@GunChleoc, will it be compatible with current savegame?

Yes

One way to achieve that is by performing the routing per flag, instead of per ware. Then each ware decides its next destination reading solely its current flag's info.

I was rather considering placing artificial route points, which define total route, but not the specific way. So the ware could go to route point A, then B, then C, then to warehouse/ workplace. Pathfinding would be much smaller then.

Sound like splitting into short-range and long-range pathfinder. That would be a good idea especially for seafaring as well. Routes between ports could be pre-calculated and then small local adjustments made as needed.

Speedup branch is here: https://code.launchpad.net/~widelands-dev/widelands/ware_routing_speedup


Busy indexing nil values

Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-07, 14:29

einstein13 wrote:

I was rather considering placing artificial route points, which define total route, but not the specific way.

and

Tibor wrote:

artificial route points looks like great idea. F.e skip flags on long stretches of roads

and

GunChleoc wrote:

Sound like splitting into short-range and long-range pathfinder. That would be a good idea especially for seafaring as well.

That is focusing on the problem instead of the solution, trying to patch the system instead of fixing it. That is ok to meet deadlines, but in the long run we need a better approach.

Tibor wrote:

If there are 5 providers - no problem. If there is 150 of them (like traffic jam full of logs or water) - this kills the performance.

That is typical bad scaling. Such problems are solvable, but they need serious changes.

GunChleoc wrote:

Routes between ports could be pre-calculated and then small local adjustments made as needed.

That is the proper direction for the solution. But it has to be applied at the flag/node level in an efficient way. More specifically, routing should be decoupled from serving. Matching sources with destinations should take place at a higher level than routing, and matching producers with consumers should take place higher than both. Of course information will still flow between those levels, but only the absolutely necessary one. Calculations should be performed only once per route and updated only when roads get added/removed. Traffic information can also be considered, but this is again a separate problem, as it changes dynamically. In a well designed system, an economy left in auto-pilot should be light to the processor. But I don't want to highjack this thread with the details. If you are willing for serious improvement after version 20, be assured that such improvement is totally feasible.

Edited: 2018-05-07, 14:30

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1107
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-07, 16:58

@GunChleoc, @Tibor

Thanks for advicing for compiling myself the branch. It was easier than I expected. Unfortunately it didn't help. The game is still lagging. But fortunately it printed lots of lines like this:

destination disappeared or economy mismatch -> fail
destination appears to have become split from current location -> fail

Can somebody tell what is going on? It is based on release mode. I can run debug one, if needed.

Also I have noticed one bug: when you open a window (f.e. build new building) your cursor is moved to that window. But when you move the mouse, the cursor jump again to previous location. It should move back when you close the window.

@Tino

If you want, you can compile, but it is not necessary any more here. Thank you for your will of help here!

@ypopezios

The main problem of routing in Widelands is that we have both dynamic and static situation. For 99% of economy the situation is rather static and the rest (1%) is completely dynamic. Most of my clicks in the game is about placing roads. When I build a building -> place a road. See a traffic jam -> place a road. Rebuilding roads -> delete and place roads. Expanding -> place a road. So the whole economy is dynamic. But most of the economy is rather static with a flow of wares. The solution for pathfinder should be based on static data (less CPU), but include also dynamic response to the changes.

My idea of marking some points (or areas) around was about decreasing CPU usage in the simplest way by reducing length of paths to find. The problem increase with square of length. If we reduce length 2 times, we have 4 times less CPU neeed. But we have to double the calculations, so we have total of 2 times less CPU usage. Plus of this idea is that CPU can be used in two different moments. It reduce even more CPU usage when finding the path.

The main problem is that finding good spots for routepoints is not an easy problem. If you make a small mistake, your route point will be somewhere on the Moon (or on the other side of the ocean) and it will not be used any time.

But sticking to the topic:
low FPS is not based on routing now (or the bug wasn't solved?). I can't see that the game was going smoothly on branch test.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
Tibor
Joined: 2009-03-23, 23:24
Posts: 1317
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2018-05-07, 17:19

@einstein13

Those printouts are quite common, so I dont think they do necessarily indicate a problem. But it is pity that it did not help.... I remember we had performance problems also when an attack was in progress...

What I am afraid about caching of pre-calculates routed is huge number of combinations that would need to be cached. Take economy with 400 flags and 40 productionsites with inputs or constructionsites - well I dont even know how to get number of all possible routes, moreover considering frequent changes to roads that would invalidate the cache.....


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-07, 17:21

einstein13 wrote:

For 99% of economy the situation is rather static and the rest (1%) is completely dynamic.

That's exactly the point. In a mostly static economy we need a static solution (i.e. routing per flag), enhanced by dynamic elements on top of it (i.e. wallet-based adjustments).


Top Quote