[SDK] Path search for units: Does a modded A*-Star-Algo already exists?

[Ramkhamhaeng]

Hello,

does anybody know if other modders already implemented an own A*-Star algorithm for the unit path search?
This fundamental part is not implemented in the DLL source code, just parts, see
FAStarNode.h, CvGameCoreUtils.cpp

I know that Caveman2Cosmos successfully extended the game by its own path search, but the code basis of this mod is so complex that it is extremely hard to pick one single feature. They changed almost everything…

Some more thoughts about the problem:

Spoiler :

• It is no easy problem because the we just had access to a few function handlers, which will be called during the path search, hidden in the Civ4 binary.
• I've already learned that it not possible to define new path finders similar to the existing ones. The EXE contains some hard coded calls to 'GeneratePath(...)' with a fixed pointer (GC.getPathFinder()). It is not possible to made getPathFinder() non-constant.
(from CvMap.cpp)

        gDLL->getFAStarIFace()->Initialize(&GC.getPathFinder(), getGridWidthINLINE(), getGridHeightINLINE(), isWrapXINLINE(), isWrapYINLINE(), pathDestValid, pathHeuristic, pathCost, pathValid, pathAdd, NULL, NULL);
        gDLL->getFAStarIFace()->Initialize(&GC.getInterfacePathFinder(), getGridWidthINLINE(), getGridHeightINLINE(), isWrapXINLINE(), isWrapYINLINE(), pathDestValid, pathHeuristic, pathCost, pathValid, pathAdd, NULL, NULL);
// adding new finders here...

=> So, the new code had to be hooked into the existing unit path finder(s).

• My targeting search algorithm needs a search from the target plot to the unit plot.
This is inverse to Civ4's search order!
I was able to swap both plots during the search
(By writing setter-function for the existing 'GetDestX(FAStar*)', etc functions)

This approached failed because CvDLLFAStarIFaceBase.GeneratePath(...) then runs the A*-Star search, but the result (chain of nodes/plots) is unuseable because it just contain the ending plot (I can not flip the generated path back.)

 

[f1rpo]

Under which assumptions do you need to compute those inverse paths? Well, maybe it doesn't really matter. I think it should be possible to get what you want out of the BtS pathfinder by using the BBAI mod as a guide. BBAI computes paths for "generic" units (no CvUnit or CvSelectionGroup object needed) by passing its teamStepValid function to CvDLLFAStarIFaceBase::Initialize and the parameters (to be taken into account at every step) to CvDLLFAStarIFaceBase::SetData. BBAI passes the BtS stepCost function to Initialize for a uniform movement cost, but a more complex cost function could be passed instead.

Hello,does anybody know if other modders already implemented an own A*-Star algorithm for the unit path search?

karadoc has done that. His pathfinder only computes paths starting at the current tile of an existing selection group, but it could of course be generalized. In fact, I've already done that by deriving a "TeamPathFinder" (with capabilities similar to the BBAI code mentioned above, but with much better performance) from karadoc's class and by moving the group-specific code into another derived class:
KmodPathFinder <-- GroupPathFinder

^--- TeamPathFinder​

Global functions shared with the BtS pathfinders (also the case in K-Mod, which keeps them in CvGameCoreUtils):
FAStarFunc.h/cpp
and as a kind of glue
FAStarNode.h

For merging any version of karadoc's pathfinder, these Git commits by @devolution should be helpful, specifically this one, at least for getting an overview of the affected files.

Oh, and here's my latest version of the BBAI code (getting deleted because TeamPathFinder makes it obsolete). It might be better not to rely on the original BBAI code because part of it was unused and erroneous.

Edit: Merging my TeamPathFinder into another mod (if that's a consideration at all) would be a big task because I've refactored much of the pathfinding code to make use of various helper functions and macros available in my mod.

 

[Ramkhamhaeng]

Under which assumptions do you need to compute those inverse paths? Well, maybe it doesn't really matter. I think it should be possible to get what you want out of the BtS pathfinder by using the BBAI mod as a guide.

Thanks for for this detailed reply and code references!

I need the computation of those inverse paths under following assumptions:
• A ship placed at an edge of a plot (pPlot, iEdge)=P_S,e_S) .
• We want use a plot based path search, without any virtual extra nodes for edges.
This is useful to re-use the given 'can enter plot'-logic from Civ4.

The open question:
Search the shortest path to an other plot P_T . It does not matter which edge on the target plot will be used or if the ship is just placed inside of the plot (cities/water tiles) , you just want the shortest path.

Note that a path search under this conditions requires paths which enters a plot twice, e.g. because
a river is at the north and south edge of a plot. This problem was solved by me by 'shifting the used plot' at two of the four edges to the neighbor plot. Lets call this two plots P_T' and P_T'' in my example.

Problematic for my search are the end points of the path. If you search from P_S to P_T you also need the information if movements on the edges of P_T' or P_T'' are feasible and cheaper.
Not a trivial question. Maybe the shortest path to P_T'/P_T'' can not be connected to P_T, but the a longer path could!

If you search from P_T to P_S you could simply set the moving costs from P_T to P_T' P_T'' to zero.
On P_S the problem disappears because the edge is already fixed.


P.S. Maybe you thinks my algorithmic idea does not work. I've working on this a few years and I've already developed a program in Python to test the path search on many random maps. Inaccurate phrases are mostly based on my lack of English skills.

 

[f1rpo]

The K-Mod pathfinder is not used for the waypoints shown on the main map e.g. in Go-To mode. I assume that the paths shown as waypoints are handled entirely by the EXE and that the DLL can affect them only through the existing global step and cost functions. This seems like a problem to me because I assume that you'll want to show waypoints (and the number of turns to reach the destination) when a human player moves a ship along a river. Maybe that's what you had already concluded:

The EXE contains some hard coded calls to 'GeneratePath(...)' with a fixed pointer (GC.getPathFinder()). It is not possible to made getPathFinder() non-constant.

Note that a path search under this conditions requires paths which enters a plot twice, e.g. because
a river is at the north and south edge of a plot. This problem was solved by me by 'shifting the used plot' at two of the four edges to the neighbor plot. Lets call this two plots P_T' and P_T'' in my example.

Problematic for my search are the end points of the path. If you search from P_S to P_T you also need the information if movements on the edges of P_T' or P_T'' are feasible and cheaper.
Not a trivial question. Maybe the shortest path to P_T'/P_T'' can not be connected to P_T, but the a longer path could!

It's not clear to me that such problems are inevitable. It seems to depend on how specifically rivers get associated with plots. But I'm not sure if it makes sense for you to spell out those details when you've already analyzed the problem thoroughly.

Let me, in any case, offer an example for illustration. This is supposed to be an excerpt of the map's tile grid, the curly lines representing river segments. W is the great blue sea (water).

 -- -- -- -- --
|  |  |  |  |  |W
 -- ~~ -- -- --
|  {  {  |  |  |W
 ~~ -- ~~ ~~ ~~
|  |  |  |  |  |W
 -- -- -- -- --

Now let me give a name to each land tile (capital letters), assume that a ship (pathfinding source s) is located south of F and that the destination d is on tile O.

 -- -- -- -- --
|A |B |C |D |E |W
 -- ~~ -- -- --
|F {G {H |I |J |W
 ~s -- ~~ ~~ ~~
|K |L |M |N |Od|W
 -- -- -- -- --

I don't suppose there is a problem with searching forward in this example?

Edit: spelling

 

[Ramkhamhaeng]

I don't suppose there is a problem with searching forward in this example?

Edit: spelling

A problematic example would be:

▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█████████████████▒▒▒▒▒▒▒▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒▒▒▒▒██████████▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒
▒ W W  ▒▒      █▒      █▒      █▒      ▒
▒  S   ▒▒      █▒  T'  █▒  T   █▒      ▒
▒ W W  ▒▒      █▒      █▒      █▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒

I hope this is displayed correctly
The white edges are marking edges with rivers. To mark the associated plot of an edge I made the edges two characters wide.
'W' is a water plot and our start. T is our target plot.
The moving costs are '1' for each used edge.

My wished path from S to T (over river edge of T') looks like that:

▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█████████████████▒▒▒▒▒▒▒▒
▒      ▒▒      █▒  3   █▒      █▒      ▒
▒      ▒▒     2█▒     4█▒      █▒      ▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒▒▒▒▒██████████▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒
▒ W W  ▒▒  1   █▒      █▒      █▒      ▒
▒  S   ▒▒      █▒  T'  █▒5 T   █▒      ▒
▒ W W  ▒▒      █▒      █▒      █▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒

This path is shorter than the way over the (east) river edge of T.
Moreover, the required partial path to T' is not the shortest path to T':

Shortest Path to T' (over other river)

▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█████████████████▒▒▒▒▒▒▒▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒      ▒▒      █▒      █▒      █▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒
▒▒▒▒▒▒██████████▒▒▒▒▒▒▒█▒▒▒▒▒▒▒█▒▒▒▒▒▒▒▒
▒ W W  ▒▒  1   █▒      █▒      █▒      ▒
▒  S   ▒▒      █▒2 T'  █▒  T   █▒      ▒
▒ W W  ▒▒      █▒      █▒      █▒      ▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒
▒      ▒▒      ▒▒      ▒▒      ▒▒      ▒

An A*-Algo would save the wrong path from T' back to S.

 

[Ramkhamhaeng]

The K-Mod pathfinder is not used for the waypoints shown on the main map e.g. in Go-To mode. I assume that the paths shown as waypoints are handled entirely by the EXE and that the DLL can affect them only through the existing global step and cost functions. This seems like a problem to me because I assume that you'll want to show waypoints (and the number of turns to reach the destination) when a human player moves a ship along a river. Maybe that's what you had already concluded:

Yes, the handling of path evaluations after pressing 'g'- is the most problematic case for me.

 

[Ramkhamhaeng]

I attach as reference my path search. It could print out the A*-Algo costs etc for some random maps by

python3 main.py
or
python3 main2.py

If your terminal does not support color output it can be disabled in CvMap.py.
Warning: Messy code and just written for my tests.

Legend:
C, M, W: City, Mountain, Water,
C [num] evaluated costs
I [num] marks used plots of path
arrows: marks path

┌▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼┐
▒ M  M ▒ W  W ▒ W  W ▒ W  W ▒      █      █      █
▒      ▒      ▒      ▒      ▒      █      █      █
▒ M  M ▒ C 2.0▒ C 2.0▒ C 2.0▒ C 3.0█ C 4.0█ C 6.0█
┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┾██████╋██████╃▒▒▒▒▒▒╀
▒ W  W ▒ C  C ▒ W  W ▒      ▒      █      ▒ W  W ▒
▒      ▒      ▒      ▒      ▒      █      ▒      ▒
▒ W  W ▒ C 1.0▒ C 1.0▒      ▒ C 4.0█      ▒ C 5.0▒
┼▒▒▒▒▒▒┾██████┽▒▒▒▒▒▒┼▒▒▒▒▒▒╁▒▒▒▒▒▒╂▒▒▒▒▒▒┼▒▒▒▒▒▒┼
▒ W  W ▒      ▒ W  W ▒ M  M █ M  M █ M  M ▒      ▒
▒      ▒      ▒ Start▒      █      █      ▒      ▒
▒ C 2.0▒ C 1.0▒ I 0  ▒ C 1.0█ M  M █ M  M ▒      ▒
┼▒▒▒▒▒▒┾██████╅▒▒▒▒▒▒╆██████╋██████╋██████╈██████╅
▒      ▒ M  M █      █      █ M  M █ M  M █ M  M █
▒      ▒      █   1  ↑      █      █      █      █
▒      ▒ C 1.0█ I 1  █      █ M  M █ M  M █ M  M █
┼▒▒▒▒▒▒┼▒▒▒▒▒▒╄██████╉▒▒▒▒▒▒╄██████╃▒▒▒▒▒▒╄██████╃
▒      ▒      ▒      █ M  M ▒      ▒      ▒ M  M ▒
▒      ▒      ▒   2  ↑      ▒      ▒      ▒      ▒
▒      ▒      ▒ I 2  █ C 3.0▒      ▒      ▒ M  M ▒
┼▒▒▒▒▒▒┾██████┽▒▒▒▒▒▒╄██←███╈██████┽▒▒▒▒▒▒┼▒▒▒▒▒▒┼
▒ W  W ▒ M  M ▒ M  M ▒      █ M  M ▒ W  W ▒      ▒
▒      ▒      ▒      ▒ End n█      ▒      ▒      ▒
▒ W  W ▒ M  M ▒ M  M ▒ I 3  █ M  M ▒ W  W ▒      ▒
┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒╀▒▒▒▒▒▒┼▒▒▒▒▒▒┾██████┽
▒      ▒      ▒ C  C ▒      ▒      ▒      ▒      ▒
▒      ▒      ▒      ▒      ▒      ▒      ▒      ▒
▒      ▒      ▒ C  C ▒      ▒      ▒      ▒      ▒
┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼▒▒▒▒▒▒┼

 

[f1rpo]

Yes, the handling of path evaluations after pressing 'g'- is the most problematic case for me.

I've taken a look at the memory layout of the FAStar class; screenshot attached. Re-reading your opening post, it seems that you've already gone there:

I was able to swap both plots during the search
(By writing setter-function for the existing 'GetDestX(FAStar*)', etc functions)

I hope that one of the FAStarNode pointers is indeed what gets returned by CvDLLFAStarIFaceBase::GetLastNode. If so, then it should be possible to replace that node pointer with a pointer to an FAStarNode computed by a different pathfinder – if we can find an EXE-to-DLL call that happens before the waypoints get displayed and after the path computation has been completed. Maybe you've actually already tested this.

So this sounds like a workable approach – and a lot of work.

Thanks for sharing your script. (I haven't yet tried it out though.)

I hope this is displayed correctly

To say that this puts my ASCII art to shame would be an understatement. Also illustrates the problem well:

Problematic for my search are the end points of the path. If you search from P_S to P_T you also need the information if movements on the edges of P_T' or P_T'' are feasible and cheaper.
Not a trivial question. Maybe the shortest path to P_T'/P_T'' can not be connected to P_T, but the a longer path could!

Just to make sure: A river being associated with only one tile is just an implementation detail – as far as the game rules are concerned, a ship is located on a river edge, and there is no distinction between the two adjacent tiles?

Would it help to allow (I guess in EdgeAStar.neighbors in your Python code) moves like the one from T' to T in the special case when T is the target tile?
Well, probably there is no such easy solution, and I don't want to end up wasting your time, so please don't feel obliged to answer this.

Edit (13 Feb): A more plausible guess at the data members of FAStar (though not substantiated through further tests):

Spoiler :

struct FAStarData
{
   // The function pointers that were passed to CvDLLFAStarIFaceBase::Initialize
   void* m_pPathFuncs[5];
   /*   I've only seen 0 here. Easy enough to verify that these bytes get set
       by setData, but I haven't done so. */
   void const* m_pData;
   /*   I've seen e.g. 214452064 and similarly high numbers. Could've been
       group movement flags I guess, but I haven't verified that. */
   int m_iInfo;
   int m_iMapWidth;
   int m_iMapHeight;
   // Start, Dest: likely ...
   int m_iStartX;
   int m_iStartY;
   int m_iDestX;
   int m_iDestY;
   int m_iUnknown1; // I've seen 8
   int m_iUnknown2; // I've seen 1 (bool?)
   /*   I really don't know how the nodes are arranged. Probably there is an
       array of all nodes, and probably the end node is stored separately.
       In my (very few) tests, pLastNode and pNodes were pointing to the
       node returned by CvDLLFAStarIFaceBase::GetLastNode. */
   FAStarNode* m_pSomeNode; // ?
   FAStarNode* m_pLastNode;
   FAStarNode* m_pNodes;
};