Heh, yeah that’s what I meant. Like I said I might be using the word Dijkstra too much these days 
Yeah, I certainly learned a bunch, and replacing everything with Dijkstra and seeing the blueprint shrink to half the size and run three times as fast was almost worth it in itself 
(But seriously, avoid A* unless you really need it)
Thanks, I will keep it in mind when I get to that point.
Right now I am trying to work out the theory behind the weather system. Probably going to take into account the Easterly tropical winds and the Westerly temperate winds. I am leaning towards a system where I check tiles East/West and increase precipitation the more water tiles are passed over, and decrease it as you pass over land. Throw in some randomness related to the player set precipitation setting which could hopefully create desert where normally there would be rain and vice versa. Not totally convinced that would handle all cases well enough so I have to think about ways to compensate where needed.
I think the speed difference may depend on how it’s implemented, I actually went the other way, A* to an off map destination devolves into Dijkstra. No need for two separate algorithms.
Ah I understand your reasons for wanting to set the destination or select it from a list of candidates.
Isn’t A* Dijkstra but using a user defined heuristic to assign priority to nodes to expand next? That gives more control than Dijkstra then. You could use that to find suboptimal paths before optimal paths and maybe even snaking.
I think in the context of rivers, A* might produce rivers that are too winding. Generally on a continental scale rivers tend to head in one general direction apart from circumventing elevation. What I am probably going to need is a way to vary the river on a small scale on it’s way to it’s destination. Perhaps this could be done by setting a mini-objective which once reached would then path back to the original destination. Kind of like the anomaly that the Arkansas river pulls in Kansas on it’s way to the Mississippi. I will have to play around with that when I get the rest working.
Also, I think in just about every case I am going to want to path find the entire continent looking for river exits. I can then sort all the options and choose randomly from a list of the best options.
I also think I will upgrade my river array from true/false to a byte so I can essentially cost all the tiles around the river. The tiles on the river itself would be say 5, and each tile further away is reduced by one. Then when a river is choosing an outlet it could use that as a kind of buffer check when choosing destinations. That is probably something that will basically apply to other systems such as AI city expansion. Additionally, I could count the number of tiles in the continent that are river, and see if they make up a proper % of the tiles in the continent. If not, generate new river until over the threshold. Makes room for a setting that allows players to choose more jungles but less rivers, or even more desert and more rivers.
I believe Dijkstra will always be slightly faster than A* with an off map destination, since there are fewer steps involved in doing the calculations. This will of course only matter where every millisecond of speed increase is important, but I believe that’s the case for Zeus’ and my own blueprint. I even used a binary heap for sorting my open list when I used A*, and I still had speed improve significantly when I moved to Dijkstra.
Yeah, that’s basically what A* is, though I think we are moving beyond the standard definitions here since Zeus isn’t interested in the optimal path. I agree that some sort of modified Dijkstra would be the best solution, probably by using heuristics or some form of randomization to get less predictable results, probably through a sorting algorithm in the open list.
Did you ever run a visualization on the tiles that were checked when A* was doing it’s business? From what I understand, A* should be checking less tiles than Dijkstra in most cases. I think that is the part that should make up for any extra iterations in A*, maybe apart from some special cases such as when I want to find multiple destinations in multiple directions.
I just noticed that Amit posted an updated introduction to A* post about 6 months ago that I think I missed. It has some better visualizations: Introduction to the A* Algorithm Here is the old one: Introduction to A*
I did visualization every step of the way, and I have read through all of Amit’s newer stuff. He’s much the reason why I went for A* in the first place. The A* visualizations of Amit and other are very neat, and you can’t avoid being impressed by A*s seeming superiority to all other methods. And it is certainly the best method in a lot of cases, but not all.
The amount of time lost sorting the open list and re-checking paths compared to Dijkstra is not insignificant, so in my opinion you should only use A* if the distance to the end point is significant and you know the end point beforehand. Whether or not this is a special case does depend on your game, of course, but in my own game this is nearly any case, as on the players turn I want to display all possible paths to the player, and on the AIs turn I want the AI to decide multiple targets in range. I think this will be the case for many path checks in a Civ-like game too, and I think any paths benefitting from A* might actually be the rarer cases.
If you use A* for your river you must have an algorithm to choose the end point beforehand, and the combined time used for this algorithm and the A* pathfinding will have to be quicker than a single Dijkstra search. For rivers of the length you will be generating, I’m quite certain that Dijkstra will be faster. And, like Nisshou said, A* is just Dijkstra with a heuristic for choosing the next tile in the open list. I would recommend that you start with Dijkstra, see how it runs, and then modify it to A* later on and see if you get any improvement. I’m sure there are many cases in your game where A* is superior, but this should be decided by testing it out.
Ok, so you were searching all directions to show the possibilities prior to just sending him on his way using one of those pre-calculated paths.
I think A* is used when you have 1 destination and need a single path to it, so yeah not what I need if I reuse the results from Dijkstra. There will probably be plenty of cases where A* will be used by the AI as it moves around, though I am wondering how many of those paths could also be stored for later use. Amit has a lot of good ideas for simplifying the grid to what you really need which I can hopefully make sense of when the time comes. 
Yes, that’s how I do it.
Dijkstra for relatively short paths and precalculated paths for longer paths could make things run really fast. The terrain won’t change much in your game, so precalculation should work well. With my current system I’m able to calculate the optimal path to every node in a 10 000 tile grid in about half a second. If you run some of these at startup from nodes spread evenly on the map (maybe spread at a distance equal to the maximum search distance of your Dijkstra search) you could have pawns instantly find paths spanning the entire map. These would be like highways, and then you calculate smaller side roads at the start and end using Dijkstra or A*, or detours using Dijkstra if you hit a dynamic obstacle along the way to find the way back to the “highway”. Such a system should run very fast indeed. The biggest hurdle would be finding the best algorithms for precalculation.
I think if I can pre-calculate any kind of “highway” system I should be pretty well off. I think that Civ games in general wouldn’t be so slow in the end game if they had optimized pathfinding & AI systems. Lot of useless workers wandering around, dozens of units with no strategic direction probably calling for pathfinding every turn, etc. On top of all that, the pathfinding has to wait to the end of turn to start calculating because the units move every player’s turn, instead of all at once at the very end, which spoils any pathfinding that could have been performed while the human gives orders.
I expect many headaches are in my future with those systems. 
It will be quite the undertaking for sure, but I’m getting more and more confident that it’s doable. Hopefully I can be of some help since I’ve been tackling a lot of the same problems, the same way as I’m going to look to you when I move on to procedural generation
I am sure we can help each other out.
Here is the first working version of the new weather system:
Blue = Wet
Green = Moderate
Yellow = Semi-Arid
Red = Arid
Arctic and Tropical/Sub-Tropical winds travel East to West. Temperate/Tundra winds travel West to East.
Right now, for every tile on the Y(latitude), I hit all the tiles to the East or to the West until I have wrapped the world twice(for the wrap). As it moves along, water increases precipitation level, and land decreases it. Each tile gets set to the current precipitation level. So, coming off the ocean the precipitation level is high, and as it crosses a continent it falls off. If the wind coming off the water hits a mountain range you have a spike in precipitation with a falloff behind it. Also, I smoothed the precipitation levels so you don’t have wet and arid directly neighboring each other.
Generally the deserts are set to only form in the arctic and Sub-Tropics, but in the image I have a huge desert in the temperate zone, so that will have to be fixed.
Another thing I need to do is properly implement seeds since right now there is no variation. A seed is put on a tile according to it’s precipitation type. This will change to allow much more variance as well as scaling to the player setting. When I space the seeds out more, you will see much better shaped biomes from the Voronoi cells.
I also need to tweak the depth at which precipitation penetrates continents and properly scale it to the map size.
Lastly, I need to figure out a way to spin precipitation vertically from the tropics as you would see in the western Pacific and Atlantic. This is what makes the east coasts of Asia and North America wetter than they would be with simple horizontal wind flow. It will likely be a separate process that occurs after the horizontal wind steps.
Here is what I am basing the wind model on:
Progress:
Getting a pretty good rain shadow effect with the mountain ranges.
I am going to make a few precipitation settings:
I still need to work on the vertical weather fronts/jet streams. Not sure how I am going to aim them, since they could pretty easily just head out to the middle of the ocean. Though, they will probably be pretty wide. Maybe 5-10% of the map width. That could be enough for most maps, and if they miss land completely then I guess that is just how that planet’s weather ends up. Earth basically has 2 of these in the Northern hemisphere and ~1.5 in the Southern, which are pretty much where all of the hurricanes happen.
Also, I have it set so that the precipitation is always at least moderate in the Tropics(on Earth-like settings). Earth only has a couple very small Semi-Arid zones in the tropics, which makes me want to bias the entire band to always be at least partially wet, but I don’t think that is the right way to do it. Problem is, if I let it drop down to Semi-Arid there will be perhaps too much of it, especially depending on which side of a continent it’s mountain range is on(Imagine the Andes on the other side of South America… could have been the Amazonian Desert I guess). You could end up with a situation where the tropics are completely dry. I suppose that could happen anyway if you had a giant Pangaea at the tropics… If I don’t think of something I may just allow it to be semi-arid but put an additional bias on how deep the weather penetrates landmasses in the tropics.
Precipitation now scales to the landmass and penetrates according to the Precipitation Setting, which for the below images is set to ~60%:
Again, it is 100% seeded, so that is why some areas look too straight and unnatural. When the seed count is lowered it will look better. This basically just shows the depth scaling at work.
I also added a bias for certain latitudes. For instance, in the Sub-Tropical latitude, the depth was decreased by about 30% which makes for more prominent deserts. I will probably bias the Tropical latitude for more precipitation and then get rid of the precipitation minimum which is keeping Arid/Semi-Arid out of the tropics. When I do that I will probably implement a method to gradually drop the precipitation off since the current depth method is pretty black and white at the transition. At some point the Precipitation Biases will be made into a Setting.
When this is all worked out I need to work on the water side of the equation since passing over 1-2 water tiles currently builds the precipitation up enough to cross large continents. A depth checking system similar to the land system will probably be used, but I need to implement some kind of mechanic scaled to map size and weighted to the number of water tiles crossed.
Also need to work out a good way to bias the depth for small islands on large maps without swamping small islands on small maps(continents).
Put in a filter so that small islands play by different precipitation rules. “Small Island” is scaled to map size. This also generally applies to thin strips of land as well.
Also started work on precipitation uptake over open water. Before it was set up so that moving over open water increased precipitation, but now I am seeing how it looks with lower rates of uptake.
Been pretty busy lately, so I have not had much time to put work into the generator. Also, I have been contemplating a better way to handle precipitation. The precipitation depth system I worked out is ok, but its limitations keep nagging at me.
Here is the system I have in mind to replace it:
The precipitation level will exist on a weighted 0-1000 system. As it moves over water and land, the level will rise and fall. The type of seed dropped on any given tile will depend on the precipitation level: 0-249 Arid, 250-499 Semi-Arid, 500-749 Moderate, and 750-1000 Wet.
The increases and decreases to the precipitation level will scale to Map Size. So on size 10, it might decrease by 50, whereas on size 100 it might decrease by 5(or whatever numbers I work out).
There will be a few settings which will drive the precipitation level changes:
These 2 settings would have default values set to “Earth-like”. Increasing or decreasing the setting could make the world wetter/drier, but would still follow the general rules of the system.
Precipitation Uptake - The rate at which precipitation builds when moving over open water. Tropical waters get a bonus, Sub-Tropical get a negative, and Temperate/Tundra are neutral.
Precipitation Dropoff - The rate at which precipitation depletes over landmasses. Tropical depletes slower, Sub-Tropical faster, and Temperate/Tundra are neutral.
These 2 settings will “break” the system and are designed to give the player more control over total map precipitation.
Precipitation Multiplier - This will be used to create unreasonably wet or dry conditions. This will probably affect minimum and maximum precipitation conditions which are generally locked to the climate band they are in(Tropical, Temperate, etc).
Precipitation Penetration - The rate at which precipitation makes it through mountain ranges intact. Earth-like will be 0-10%. I have to have this option since a map with lots of mountains would be extremely dry even if every other precipitation setting were set to extremely wet.
I will also have to take into account maps with no oceans whatsoever, such as a Highlands map and other similar generations. There may be a setting that seeds precipitation separately from the normal system for these cases. Perhaps available only on those map types.
In addition to the East/West winds, there will be 4 East-slanted(45 degree inclination) “jet streams” that will originate from the equator to soak whatever is in their path(think east coast of North America and Asia). Should generally follow the above settings. I probably won’t be able to guarantee these jetstreams hit enough water to gather precipitation, or even that they touch any land on their way north/south. The jet streams in the southern hemisphere generally dump their rain on open water, so that could be common in the generations as well.
Ok, here is the first run with the new system. No biases or settings yet implemented, but I think it already shows a significant improvement. Also, still 100% seeded, and no mountains cutting things short:
I had wanted to implement something like this when I first started revamping precipitation, but my weighted system didn’t have enough room to maneuver and was extremely clunky. So, I tried a couple different approaches before coming back to it with the 0-1000 range which is pretty much all I needed.
Uptake and Dropoff settings are just about complete. Had some other issues in the river generator that popped up when I tweaked some settings that I had to check out. That will be fixed when I overhaul the rivers following this climate system.
Here are a couple images of the precipitation uptake occurring in the oceans:
You can see how the level of precipitation picks up out over the ocean and depletes over land. Landmasses that are well situated in regards to oceans, other landmasses, and the winds receive lots of rain, while others receive less.
Once I finish tweaking these settings as well as the rain shadow setting, I will implement the jet streams. The way that will most likely work is from ~2 points at the equator, rain will move Northwest in a 45 degree angle until reaching the temperate zone, at which point the angle will change to 45 degrees to the Northeast and will stop at the arctic. This generally fits the way Easterly tropic winds push storms away from the equator until the hit the Westerly temperate winds that push the storms in the other directions. Think of the Hurricanes that come up from the mid-Atlantic, Northwest towards the US Gulf Coast, and are often pushed back Northeast, sometimes making landfall all the way in Europe. They normally lose steam by the time they get up there, but this is largely responsible for Europe being warmer and wetter than it otherwise would be. A similar system brings cyclones through the Philippines towards China, while that weather eventually makes it’s way to the Northwest coast of North America. It will be mirrored in the Southern hemisphere.
I must say that following progress on this blueprint is educative in more ways than one You’ll probably never look at a map the same way after this. Are you planning to include natural disasters that occur during the game using this system? It would be awesome if the player could take this into account when settling.