Latest Posts

Topic: New pathfinding

einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1021
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-11-15, 13:49

Hi!

I want to open old problem once again.

Problem: on huge maps with very complex road system and thousands of wares there, there is a problem of low FPS due to computing wares transportation.

Solution: currently unknown. Probably modifying current A* (A-star) algorithm will help, but it should be smarter than years of invention face-smile.png

Goal: prepare good Launchpad bug report with proper solution, as easy as possible to implement with current state. Target: Build 21 face-smile.png .

So I ask: if anybody wants to investigate the problem, it is the perfect place.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1021
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-11-15, 13:56

And in second message, I post 3 good videos that probably will show the problem from "human" position:

So my idea (previously mentioned) is to simplify road system by creating some "sections", so the ware pathfinder will look much faster, because there will be much less nodes. As far as I know, currently every flag is another node. But many times we have long road-flag only roads, which can be treated as one node-road-node. It can be expanded even better, but I don't have proper attempt yet.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
EgyLynx
Joined: 2010-08-22, 08:51
Posts: 39
Ranking
Pry about Widelands
Posted at: 2018-11-16, 15:32

einstein13 wrote:

And in second message, I post 3 good videos that probably will show the problem from "human" position:

So my idea (previously mentioned) is to simplify road system by creating some "sections", so the ware pathfinder will look much faster, because there will be much less nodes. As far as I know, currently every flag is another node. But many times we have long road-flag only roads, which can be treated as one node-road-node. It can be expanded even better, but I don't have proper attempt yet.


Looked already these at them two... good videos...

that down one not yet...


Top Quote
kaputtnik
Avatar
Joined: 2013-02-18, 20:48
Posts: 1523
Ranking
One Elder of Players
Location: Germany
Posted at: 2018-11-18, 02:04

einstein13 wrote:

Problem: on huge maps with very complex road system and thousands of wares there, there is a problem of low FPS due to computing wares transportation.

Is this also a problem for release builds? As far i encountered this as a problem only for debug builds. Maybe i am wrong face-smile.png


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 2626
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2018-11-18, 10:34

I have no idea what the current code looks like, but one thing that could certainly help is to remember some calculations and then invalidate them on significant changes to the road network.

Precalculating would certainly make seafaring pathfinding more efficient, because we'd only need to invalidate the paths on a terrain change.


Busy indexing nil values

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1021
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-11-18, 17:43

@kaputtnik: the problem was significant in the last tournament. On The Nile map I have found playing Widelands almost impossible after some time. FPS around 10 or less is very hard to play with.

@GunChleoc: pathfinding for ships can be at least partly precalculated. For sure distances are constant except terrain change (which is very rare situation). But general path can be given as one from several equal distance.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
WorldSavior
Avatar
Joined: 2016-10-15, 04:10
Posts: 795
Ranking
One Elder of Players
Location: GER
Posted at: 2018-11-19, 00:03

I would like to share an interesting observation: Once I've opened a savegame from the eco tournament in build19, there were many roads and so on, the game runned really slow. But later I opened the same savegame with trunk and there it runned really smooth as if there wouldn't be many roads at all. Unfortunately I don't know anymore if that was before or after the new road algorithm.

Einstein, did you have the problems with build19 or trunk?


“It's a threat to our planet to believe that someone else will save it.” - Robert Swan

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1021
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-11-19, 09:10

I have spot the problem on trunk, the version from time of the tournament.

I know that there were minor changes introduced by ypopezios, which erased some congestion problems, but except that I don't know if anything else changed.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
Tino
Joined: 2009-02-20, 17:05
Posts: 246
Ranking
Widelands-Forum-Junkie
Location: Somewhere in Germany...
Posted at: 2018-11-19, 09:18

Just to throw something into the discussion: I think it would be worth to look into parallelizing things. With current CPUs Widelands would benefit from putting AI and pathfinding calculations into seperate Threads...


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1021
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-11-19, 13:50

I was thinking about parallelizing pathfinding, but it can be a bit problematic: the path result should be instant, while pathfinder will give the values after some time. So main widelands thread should have at least some heuristic algorithm included.

But ypopezios suggested that we can see if there are two wares going opposite directions, then we can swap their paths and make the transport faster. That can be done in almost any timing.

So: +1 for this idea! face-smile.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote