Improve pathfinding algorithm

[AlexFolland]

My Settlers unit in this screenshot started in London and I used GoTo to send it to the tile where the cursor is pointing, but the GoTo ended where the Settlers unit is currently standing.

[SWY1985]

Path finding for GoTo is not properly implemented at the moment. If the unit gets stuck, it will cancel the GoTo action. That's similar to what the original game does. The original has better path finding though...

[AlexFolland]

I've changed the name of this ticket to better reflect the nature of the issue then. Please mark it as an enhancement.

[AlexFolland]

Alternatively, if reverse-engineering and copying the Civilization pathfinding algorithm is planned, it can be marked as a bug.

I say these things about reverse-engineering because of this project by Deadcode with 100% accuracy in porting the entire DOS game, Snipes with only access to the binary, and adding features to it. https://www.vogons.org/viewtopic.php?f=7&t=49073

Someone with a similar level of reverse-engineering skill could do similar with Civilization, or parts of it. It is reasonable to guess that someone could find the pathfinding algorithm inside CIV.EXE and port it to C# for use in CivOne.

[SWY1985]

On the Civfanatics forums, Darkpanda and Gowron have picked apart a lot of the inner workings of the games. A lot of this project wouldn't have been possible without that work.
The rest is done with observation, and thankfully I'm getting very useful feedback here on GitHub.
I believe the path finding algorithm is explained somewhere on the Civfanatics forums. If not, I guess I'm going to have to learn how to reverse engineer some of the inner workings of the game myself.

I'm going to improve the GoTo algorithm in the next version...

[axx0]

would using algorithms such as A* be useful?

[SWY1985]

I am not familiar with A*, what is it?
I will try to get the original algorithm to work first...

[AlexFolland]

A* is a common node traversal algorithm. Wikipedia has more information about it. https://en.wikipedia.org/wiki/A*_search_algorithm

[SWY1985]

Thank you, I'll read it.

[AlexFolland]

It would be ideal to use a superior algorithm to the one employed by Civilization, as Civilization's does not fully utilize the railroad system to minimize movement points spent for traversing the path. A* with priorities per node type (tile type) would always create an optimal path, which is what the user hopes for when they use GoTo.

Using A* has that advantage, plus it is very well-documented.

[axx0]

A* is used in many games (e.g. Rimworld). However if Civfanatics explains the original algorithm you might as well use it. In any case I think Goto wasn't much used in Civ1, but perhaps this is rash judgment based on my own experiences.

[AlexFolland]

For the record, I use GoTo often in Civilization with obvious direct routes before railroad to minimize manual and potentially distracting movements.

[EnockNitti]

As an old Civ1 fanatic I was always frustrated with the goto function in Civ1.
I am also a retired C/C++ programmer who would like to make a try to implement
the A-Star algorithm into CivOne.
I have had a look at https://github.com/justinhj/astar-algorithm-cpp.
I played around with it, and it seems not too much work to implement it into CivOne.
There is also a C# port from the cpp-code which helps.
Whatdoyouthink, Do you want me to have a shot at it ?

[AlexFolland]

Cool! Would you have priorities per node type (tile type) to take advantage of roads and railroads?

[EnockNitti]

Sure, that is the main reason why I would like to implement AStar in CivOne. It is very frustrating when units "derail" from a road/railroad when using "goto".

[SWY1985]

Hey, thank you for your proposal. I would love it to have a better pathfinding algorithm implemented in CivOne, but when doing so, can you make the algorithm optional (via a Patch setting). I want to keep vanilla gameplay (including its flaws) available for those who want it.

[EnockNitti]

About use of AStar algorithm in the "goto" command: Have a pending pull request on that. If someone has a really large continent saved, please check it out
The implementation is a bit slow since the algorithm is run for every step.
It can easily be improved to be only run once for every turn if it is too slow as now.