egosoft.com

AalaarDB wrote:For AStar's first debut it has gone through some minor changes.
AStar now includes a Request Path function, making it easier to use the algorithm. Please call Request Path instead of the algorithm. There is also the Get Default Race Costs so you can ..... The returned path no longer includes gates. There is a Fly to Station command that uses AStar, but no Fly to Sector - I got lazy. I removed the caching part; I didn't like it. It was too complex and didn't save enough cpu cycles. You can still calculate a path in 1/20 of a second, and even long paths are computed smoothly.

*Distance Calculator is now included in the AStar zip.*
The distance calculator takes 2 objects or 1 object and a sector and finds the distance between them in meters, even across sectors!

AStar Pathfinder:
Sometimes the pathfinding can be annoying. True it is fast, but that's because it's precalculated. The game only shows the shortest route, and all too often this is through some enemy sector where your unarmed traders have no chance. The A* algorithm, however, is different. It is guarenteed to find the "best" path. Please note that best is subjective. It could be the shortest, or the safest, or somewhere inbetween. But the beauty is that that is controlled by you, the script writer. If you are writing a script for a universal trader, then you can set it up to avoid Xenon sectors. Or a pirate script might be willing to take some chances for increased profit.

How A* works is beyond explaining inside of a readme. Visit here: http://www.gamedev.net/reference/articl ... le2003.asp for a beginner's tutorial. You don't have to read this to use the script, although it helps.

I've done my best to make it easy for you, so you don't have to know how it works. But the script won't run as is. To run, it needs customization from you; actually there are only 2 scripts you need to customize, which are GetSectorCost and CalcH. But then to distribute these and not have one A* customization clash with another you must rename these customizations - and every script that calls them.

After you've read the above link maybe you're still confused, and that's ok. It's really simple. All you have to do is determine how much it costs to move inside of a certain type of sector and pack this into an array. Don't forget to pack into the array what race the ship is so that you can tell which sectors are friendly, and any other variable you need! For example, it costs 1 unit to move 1 km through a friendly sector, and 5 units to move 1 km through an enemy sector. The smaller the number, the better this sector is. Then, alter the GetSectorCost script to your data. When you do this, you are setting the "G" value(s). You also need to set a cost for sectors whose type you don't know in advance. This will be the "H" value, although it is called the DEFAULTCOST in the script. Go ahead and make your own and delete that one. The H value should be near the minimum cost of a sector. For example, if we are using the above G values, then H should be the cost to travel through the shortest, most friendliest sector. For tips on setting the "H" value see: http://theory.stanford.edu/%7Eamitp/Gam ... stics.html

Experiment with different values until you understand it and get the best results. The A* algorithm is one of the fastest "best path" pathfinders, and the fast binary heap should help, but since it's a script it's still slow. Don't run this too often, and try to cache results. It's probably not as slow as I make it out to be, but still.

Binary Heap Sort (already included)