Dijkstra's algorithm for path computation

Can you help improve your favourite game? Hardcore C mages, talented artists, and players with any level of experience are welcome!
LobsterNinja
Posts: 1
Joined: Fri Dec 09, 2016 8:29 am

Dijkstra's algorithm for path computation

Postby LobsterNinja » Fri Dec 09, 2016 8:54 am

Often, when moving my units, FreeCiv computes very bad paths. Even when a very short path exists, FreeCiv sometimes generates a roundabout path that will take several times longer, sometimes all the way around a continent! I'm sure everyone experiences this from time to time.

Efficient movement is crucial. I believe fixing this will make a huge difference in the game play experience.

Fortunately, there is a good solution. Please take a look at Dijkstra's algorithm. This will yield the correct answer to all such situations reasonably quickly. If you are already using Dijkstra's algorithm, your implementation is apparently buggy. If you are not using Dijkstra's algorithm, you should be.

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

If I get an enthusiastic response, and someone points me in the right direction in the code base (which I haven't looked at yet), I might consider doing the work to implement it.

cazfi
Elite
Posts: 1320
Joined: Tue Jan 29, 2013 6:54 pm

Re: Dijkstra's algorithm for path computation

Postby cazfi » Fri Dec 09, 2016 12:11 pm

In the core of pathfinding is Dijkstra. If you have a savegame with which to demonstrate case where pathfinding selects wrong route, please share. Oftentimes pathfinding finds better routes than human would, as humans tend to select direct route not noticing how bit of a roundabout would result in faster movement.

bard
Veteran
Posts: 87
Joined: Fri Jun 14, 2013 2:00 pm

Re: Dijkstra's algorithm for path computation

Postby bard » Fri Mar 24, 2017 2:06 pm

I think what LobsterNinja notices could be caused by zones of control. When a unit can not move to a tile due to zones of control of enemy units, the autopath tries to find an alternative path that avoid those tiles, and looks like not optimal.

However, I think this is one of the main weaknesses of the AI, because AI does not seem to take into account that blocked paths could be freed when the enemy unit is killed (or moved), or by using igZOC units. (At least AI in v2.5, I have to test later AIs yet).

GriffonSpade
Elite
Posts: 450
Joined: Mon Apr 29, 2013 4:41 pm

Re: Dijkstra's algorithm for path computation

Postby GriffonSpade » Fri Mar 24, 2017 5:45 pm

bard wrote:I think what LobsterNinja notices could be caused by zones of control. When a unit can not move to a tile due to zones of control of enemy units, the autopath tries to find an alternative path that avoid those tiles, and looks like not optimal.

However, I think this is one of the main weaknesses of the AI, because AI does not seem to take into account that blocked paths could be freed when the enemy unit is killed (or moved), or by using igZOC units. (At least AI in v2.5, I have to test later AIs yet).


It also seems to use mathematically optimal movement, disregarding intuitive paths. So, while it might take the same number of turns it takes a 'wonky', zig-zag path rather than the straight one a human would prefer.

Bedawyn
Posts: 7
Joined: Sat Jun 06, 2015 10:59 pm

Re: Dijkstra's algorithm for path computation

Postby Bedawyn » Fri Jun 09, 2017 7:54 pm

I run into this frequently. On land, it's usually because some civilian unit is temporarily blocking the path, so it plots a course that's five times longer than it needs to be. A smarter AI would recognize that the blockage is just a unit that's liable to move, ignore it, then when my unit gets to the blockage point -- if it's still blocked, which it usually won't be -- then it can recalculate its course if necessary. Alternatively, perhaps units involved in multi-turn Go's should automatically pause whenever they reach a city and recalculate their remaining path; that what's we do in real life, after all. But a lot of this type of problem could be avoided by refining the ZOC rules.

On water, I have the opposite problem. The pathfinding doesn't recognize borders that it can't cross until it actually gets to them, so it happily plots a course that it can't complete. By the time it tells me it's stuck, it's lost in the middle of foreign territory far from home, somewhere where I can't see the ship and any recognizable landmarks on the same map, and I have to spend ages trying to figure out where it actually is and manually get it past other ships back to somewhere useful.