This stand-alone script pack has the ability to drastically alter your game, hopefully for the better! Your ships will no longer fly through Enemy sectors, as long as there is a decent alternative!
Quick, someone tell me what is the default path from Bad Debt to Hativah's Faith? If you said through the Paranid sectors, then through Pirate sectors you'd be correct. This isn't a very safe path, and even worse if the Paranid's hate you!
The AStar path from Bad Debt to Hatikvah's Faith goes through the Boron and Argon sectors. It's much safer, and a mere 30k (7%) longer!
This script pack overrides the default commands Dock At and Move To Sector - and replaces them with my AStar commands.
Even better, you control how things work! (see FAQ)
What is AStar?
It is a fast pathfinder that is guaranteed to find the 'best' path. Best here is subjective, because by defualt I've made it a blend of length and safety. The default Egosoft paths are only length and no safety.
What do you mean by 'decent' alternative?
If there is a safe path that is 3 times longer than the unsafe path, this is not decent. The ratio is 1.55 times longer.
I want to edit the variables, what should I do?
Open up your script editor, and open the file ADB.AStar.GetPlayerCosts. You may edit the 4 numbers at the top, but it is recommended you only edit the FOE number. YOU MAY NOT EDIT ANY OTHER SCRIPT!
I want to have different costs for different races of the same type, because Xenon and Khaak are more dangerous than Pirate, what should I do?
V1.1 has added this ability. Simply edit the races one by one in the middle of the script inbetween where it says to edit. Follow the example and you should be fine, but there is a backup included.
What if I've killed the Argon and Boron so they are hostile to me, but the Paranids are neutral?
In the example, the path would be different. Paths are calculated based on your current relations with races.
Will this slow down my computer?
A very tiny bit. I highly doubt it would be noticable, even under heavy load.
I want my transports to avoid enemy sectors, and my combat ships to enter enemy sectors, can I do this?
Unfortunately no. Enabling this would make things just too complex.
In what other ways will this affect my game?
Your ships will use the AStar paths even when not issued the order. This can happen when using other scripts, for example any that use the command START Ship Command_Dock_At Station....
Can the NPC ships use this?
By default no. Each path takes cpu cycles to calculate, and it isn't necessary for the NPC races to basically 'waste' that. However, you can enable this by editing the setup script and replacing the TRUE with FALSE.
Can I edit other files?
Only if you know what you're doing, or don't know and want to learn. Pathfinding is a touchy subject and minor editing can break it.
I'm a scripter, can I include this in one of my scripts?
Yes, just say the pathfinding was written by me. You can look at a custom implementation in the Station Manager by Burianek and myself.
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!
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)