I'm posting this so taht people can understand what was, and what it's changing to. It's mainly for the people that are looking at what features may/may not fit into future releases, so that they can understand a bit of the mecahnics, and why some things aren't as diffucult as they might seem.
The 'old' way of finding your way from point a to point b was to try to go in a straight line, then look for a different line, etc. Then do special processing for roads, etc. It was extremely slow, but worked well enough on small maps.
The 'new' way is something called A*. It works differently.
A* works by figuring the distnace from the source to the destination, and then starting at the source, calculates the cost to move into the 6 hexes around it. It marks these as 'open' and the starting hex as 'closed'. It them looks through the map and finds the hex where the cost to move into that hex + the remaining distance is the lowest. Once it's foind that hex, it looks at the 6 hexes that are adjacent to that hex, and figures the cost to move into each of those hexes.. If the cost is less, it sets that hex to 'open'. If it's more (like the starting hex would be) it leaves the hex alone.
By doing this, A* will snake a path towards the ending hex. If there's a path to the target, A* is very fast, The only problem with A* is that it will potentially look at every possible hex trying to find a solution if there isn't one. Even on a 300x300 size map, that hasn't been a major problem so far, but if we go to 700x700, it's going to be about 5 times as many hexes.
There are ways to fix this problem by prepopulating a grid, and numbering each hex with a number 1 through N that represents a contiguous region of land or sea. I'll wait and see if I need to do that. That would at least cut down on the search space for 'impassible' paths
It's also possbile to make this allow for trains, planes and ships for Elmer's use, but I haven't tried using these yet. It's probably going to break some scenarios, so it has to wait. Once the program is modified to allow for pathfinding through multiple transportation means, that should help Emler, especially in places like the Pacific.
One very interesting feature about A* is that it's possible to modify it to be useful when you have more tha one source/destination. For example, when retreating, you could use that same algorithm, and stop once you'd reached a command or HQ unit. It would be a little better than what currently works, but probalby not noticeably different in most situations.
Another interesting applicaiton would be for things like supply. It's possible to 'seed' the map with all the supply points, and then to move outward from all of them at the same time , filling in the supply map. This is a LOT faster than the current method, it's also a lot more flexible. The old method made 4 passes through the map. Once for Rail, Roads, etc. The new methid doesn't need to hard code those levels, and can be a lot more flexible, and easier to modify. If we want to allow for supply to travel through friendly owned ports, that's possible, if we want to attentuate by distance instead of doing 4 levels, that's possible. Heck, if we wanted to allow for supply points to provide different levels of supply, that may be possible too.
It's also going to (eventually) provide some perfomance boosts for Elmer. Most of the Elmer code still uses a brute force method of determing his next target. We can do faster/better than that.
I probalby did a poor job of explaing how A* works. There are a lot of tutorials about it on the Net now. The important thing to remember is that is kind of flows out like water, looking for the low spots, and is very fast for a lot of things, and is very improtant for this game going forwards. The fact that is handles multiple sources/destinations makes it very useful for a lot of things.