[Script] AStar Pathfinder v1.3 (Mar 3)

The place to discuss scripting and game modifications for X³: Reunion.

Moderators: Scripting / Modding Moderators, Moderators for English X Forum

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

[Script] AStar Pathfinder v1.3 (Mar 3)

Post by AalaarDB » Tue, 22. Nov 05, 02:32

AStar Sector Pathfinder Commands
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)

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.


Old Post:
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)
Last edited by AalaarDB on Sat, 4. Mar 06, 07:55, edited 27 times in total.

User avatar
Sandalpocalypse
Posts: 4447
Joined: Tue, 2. Dec 03, 22:28
x4

Post by Sandalpocalypse » Mon, 28. Nov 05, 10:21

Was looking for some other stuff, thought this might be worth a bump!

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

Post by AalaarDB » Mon, 28. Nov 05, 10:37

Yeah, only 3 people have downloaded this, maybe it's too early...

Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)
Posts: 22197
Joined: Sun, 14. Nov 04, 23:26
x4

Post by Cycrow » Mon, 28. Nov 05, 11:36

u'll just have to wait until ppl start making scripts that will actaully utilise this

i sugguest you put a link in the tutorials section or something, coz it will definatly be handy in the future

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

Post by AalaarDB » Thu, 19. Jan 06, 10:00

Bump for release.

User avatar
Dgn Master
Posts: 1311
Joined: Fri, 27. Feb 04, 10:36
x3tc

Post by Dgn Master » Thu, 19. Jan 06, 13:07

Well i'll be the 4th then :) .. always interested in seeing what can be done to increase the life expectancy of freighters that i order from the split. I'll let you know in a few days how it's working out for me.
Could the parents of the little Argon girl, Suzie, please claim her sealed jar of remains?
She didn't mind the gap and ended up vapourized!

Sutore
Posts: 186
Joined: Wed, 2. Nov 05, 00:46
x3

Post by Sutore » Tue, 24. Jan 06, 15:08

Just one small bug - since installing the scripts, I can no longer dock at stations (yep, including friendly ones . . . )

Now in process of reinstalling X3 :(
Always keep an open mind - there are things far more wondrous than you can dream of.

User avatar
arcana75
Posts: 2165
Joined: Tue, 2. Dec 03, 09:28
x3tc

Post by arcana75 » Tue, 24. Jan 06, 15:43

Am I correct to say the script auto-checks your current race relations (and maybe FF settings) and calculates the "best" path?

If so, maybe it would be a good idea to add a command like
"Safely Dock At ...",
"Safely Move to Sector ...",
etc... maybe replace "Safely" with "AStar", like "AStar: Dock At ..."

That way players would install this script and be able to choose between the default ones and the new AStar ones. I'm not sure a battle fleet needs to avoid a hostile sector :D

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

Post by AalaarDB » Wed, 25. Jan 06, 00:19

Bump for update.
Fixed not able to dock at stations in the same sector (stations in different sectors ok)
Changed to use XScript Installer

Fachtna
Posts: 722
Joined: Mon, 2. Feb 04, 23:25
x3

Post by Fachtna » Wed, 25. Jan 06, 20:28

i am scared to download this :)

I have a few scripts installed, a coupel of LV's and all Cycrows. They work seamlessly together (as far as i can see) and dont wanna chance upsetting it.

i remember the torture i had in x2 with people using duplicate entries in the wares list etc, and really cannae be bothered going through that again.

If your scripts will integrate seamlessly, I am all for it

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

Post by AalaarDB » Wed, 25. Jan 06, 23:52

Seamlessly

User avatar
Malakie
Posts: 1059
Joined: Tue, 13. Apr 04, 23:08
x4

;)

Post by Malakie » Thu, 26. Jan 06, 01:25

FIrst time I have seen this.. adding it to me list! Now maybe I will not loose so many ships...

Malakie

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

Post by AalaarDB » Fri, 27. Jan 06, 02:47

Bump for v1.1
It converts to use the XScript Installer.
Fixed a problem with docking at stations.
You now have greater control over editing the costs for each race.

User avatar
Stevio
Posts: 2271
Joined: Sat, 4. Jun 05, 10:36
x3tc

Post by Stevio » Fri, 27. Jan 06, 13:50

[ external image ]
this is what gets extracted after download???

What kind of file is this meant to be. is this correct???

xeon_1
Posts: 3535
Joined: Thu, 4. Dec 03, 17:16
x4

Post by xeon_1 » Fri, 27. Jan 06, 13:58

it say in the file name wath you need to do just remame it with this at the end .zip

User avatar
arcana75
Posts: 2165
Joined: Tue, 2. Dec 03, 09:28
x3tc

Post by arcana75 » Fri, 27. Jan 06, 13:59

Just rename the file to .zip, eg astar.zip.

User avatar
Stevio
Posts: 2271
Joined: Sat, 4. Jun 05, 10:36
x3tc

Post by Stevio » Fri, 27. Jan 06, 14:07

Why upload a file as "Renameto.zip"

why not keep it as .zip

or upload it as a normal Cycrow script installer file .pck

User avatar
arcana75
Posts: 2165
Joined: Tue, 2. Dec 03, 09:28
x3tc

Post by arcana75 » Fri, 27. Jan 06, 14:30

The host used prolly doesn't allow zips to be uploaded... some hosts I know only allow gifs, jpgs and htm.

User avatar
Stevio
Posts: 2271
Joined: Sat, 4. Jun 05, 10:36
x3tc

Post by Stevio » Fri, 27. Jan 06, 14:41

savefile.com pretty much allows all file types

thats what i use anway

oh and i use photobucket for pics
but i think most people use photobucket

AalaarDB
Posts: 2282
Joined: Thu, 29. Jan 04, 08:19
x3tc

Post by AalaarDB » Fri, 27. Jan 06, 23:48

At first the host did support zips. Then they changed something and it broke. But by that time I was firmly entrenched. Spk doesn't work either.

Post Reply

Return to “X³: Reunion - Scripts and Modding”