Alpha Centauri 2

Sid Meier's Alpha Centauri & Alien Crossfire => Modding => Topic started by: Alpha Centauri Bear on February 24, 2023, 10:07:24 PM

Title: SMACX better pathfinding algorithm
Post by: Alpha Centauri Bear on February 24, 2023, 10:07:24 PM

Vanilla pathfinding algorithm is satisfactory good and quick. I guess its ignores ZOC a price to pay for speed.
However, now when I am improving AI I need to use it more and more as travel time computation is a backbone in decision making. That is already add up to 1-5 seconds thinking time. Of course, it is not big of a deal as the whole turn of merely pushing pieces takes about 10 seconds to few minutes in late game. Could be also I have an outdated computer. Still I would like to use something more optimal if possible to not worry about it.

The problem is that game map is not uniform cost movement. There are a lot of blazingly fast algorithms for clean field with obstacles type of map but this game movement hex cost is more complex. I was trying to use A* algorithm for approximate computation but it didn't impress me with its speed or maybe I didn't implement it good enough.

So here is the request to the community.
Anyone knows or can direct me to good, fast (could be approximate) path finding or travel time finding algorithm for non-uniform movement cost grid map?
I need specific algorithm description or ready implementation. I don't need research papers on that as I won't have time to understand them.
Thank you.

Title: Re: SMACX better pathfinding algorithm
Post by: DrazharLn on February 25, 2023, 02:31:48 AM

If A* is too slow then you must be searching for a huge number of paths or your algorithm is buggy. If you're looking for a huge number of paths then pay attention to where you can save work. E.g. if you're searching repeatedly for the same unit (or a unit on the same tile with identical movement stats) then you can save your intermediate calculations for the distance from the starting tile (tho you may need to recalculate the heuristic value when the searched-for destination changes).

If you give some more details about what you're trying to do then I might be able to point you to some other stuff.

Title: Re: SMACX better pathfinding algorithm
Post by: DrazharLn on February 26, 2023, 03:54:42 PM

If you're confident that your algorithms are good but you can't get the performance high enough then check out this video for practical advice on using less memory to get much higher performance: