AStar Pathfinding: List all plots in direct path between two plots

[Akilla]

The problem I am trying to come to grips with is this: I have two CvPlots and need to check all the plots that are in direct line between these plots for certain conditions. Since I have only recently begun to mod the SDK, I am unsure which would be the best code in the DLL to base my function on.

To explain better what I am trying to do, let me explain how I would proceed if I had to start from scratch. I would make a loop that starts on the FromPlot, gets all adjacent plots, picks the plot that is closest to the Destination Plot, and then increases a counter if the conditions that I want to check are met. The Loop would then re-run with the same Destination Plot, setting the FromPlot to the plot that was closest to it among the adjacent plots of the previous loop, until the FromPlot is equal to the Destination Plot. Does that make sense?

Now I cannot imagine that there is no such function yet in the DLL. I haven't found there what I need yet, although I really do not understand the A* Pathfinding engine. Could the generatePath Function be used for my purposes? Note that I would want to treat unpassable terrain equal to all other plots. What matters is the actual distance, plot or step. Yet I do not need the actual distance as an integer, but a list of all the CvPlots that jointly make up the shortest path between two plots in terms of distance.

It would be great if you could give me some hints that can make my life easier, before I try implementing the function described above from scratch.

 

[Asaf]

I can't give you a full answer, but maybe this will help:
If you look at CvMap::setup() you'll see the initialization of a few path finders. Each of them is initialized with a few callback functions (for example - the cost function pathCost() )that can influence the path finding process.

In CvPlot::updateIrrigated() there is an example for using the path finding function for irrigation path, which requires different parameters.

I guess you can write your own cost function for your needs, and use a custom path finder.

I didn't use this information so I can't tell you anything else without more research, but I hope this helps...

 

[davidlallen]

Do you want the shortest path as if the terrain (including water and peaks) was not there? I am not sure how this would be useful, except maybe to an air unit, and those only operate from bases anyway. If this is what you want, then the solution is obviously a straight line, and you can use a standard 2D graphics algorithm. I have not googled for this, I learned it from textbooks in the 1980s, but you should be able to find this. It does not require any searching.

Basically, first establish whether you are further away in X or in Y by subtraction. The shortest path will have a number of plots equal to the larger distance. Suppose you need to travel 8 plots in Y and 3 plots in X. Then the Y coordinates of the shortest path are clear. For each step, your "dx" value is 0.375 ( = 3/8). Use a float to increment this, and the X position is the truncated version of the float.

If that isn't what you want, please describe in a little more detail.

 

[Akilla]

@Asaf:
Thank you for the information about the place where the pathfinders are initialised. Did not know that before. I still cannot make much sense of how to use them, so if anyone has some useful links for that, they would be much appreciated! Preferably some links that relate to Civ-Modding, not to understanding the Astar system as such... BTW, Asaf, thank you very much for your VS2008 Compiling Tutorial!! Indeed, having one place to start, with all the files made readily available, lowered my reluctance to get into DLL-Modding considerably. Even completely novice-programmers like me are getting their hands dirty now, so be prepared for some more questions...

@davidallen
Ahm, uhm, well... You just revealed the fact that I haven't seen a math text-book for about a decade, since I left school to get into a language career. At least to me, the insight that the number of plots in the shortest path is always equal to the greater coordinate delta is not trivial at all. So THANK YOU VERY MUCH for the useful information!! You understood perfectly well what I am trying to do. Your comments allowed me to save a lot of computing power as compared to the "Get nearest among adjacent"-approach described above which I would have otherwise implemented. I have now written a function along the lines of what you described, which I shall post shortly after some more testing. Thank you both for your assistance!!

 

[Asaf]

No problem. I guess you don't need more information.
Glad to hear my tutorial helped
And also that davidlallen's advice worked for you

 

[Red Key]

After some searching this thread seems to be the most similar to what I'm trying to do.

How would I check if a certain plot is part of a path? i.e. I have a certain plot (plot A) I want to check. I generate a path between two other plots (plots B & C). How do I check if plot A is part of the path between B and C?