Pathfinding

[NeonSturm]

Afaik, the game is using A-Star as pathfinding algorithmus currently.

I don't know if this is a good idea for ships.



In space instead, you should take the direct route to your target and if anything is inbetween, calculate a tangential route along the box edge and connect both end points to your start/end or next tangential point.



In 3D space, you have the choice of either calculating only the paths below/above/2xAside and object or implement the algoritm using min-max x dependent on min-max y etc.

First is easier, last would be more abstract and find a better path faster.



For flat terrain, this could also speed up the pathfinding, because you create a possible path left and a possible path right around an obstracle - shortest ways, instead of processing all tiles along the edge.

1. Direct path (x)
2. Line in a right angle to it. Starting from the center of obstruction.
3. Another right-angle line (x2) from the center of every non-obstruction to check if something is left/right of it.
4. Diagonal line between center of obstructions from the lines of 2. and 3, to check if there is no passage.
5. Right-angle line partially within the obstruction to get the (x) length along a box edge on round objects.
6. move the line from 5 to out of the obstruction, using line 2.
7. connect points from line 5/6 to start/end

Although it is a lot more complex to code, it can save a lot of tiles to process for large-scale 2D and 3D objects.



EDIT:

Fix for 3.: Calculating the lenght of non-obstructions is stupid, my fault. Instead it should take an offset into the non-obstructing space/terrain based on the distance of blocks at the obstracle-exit point.

Every hole smaller than ship.x * ship.z counts as obstruction too.



And for all peoples which got tired of above math:

• ****, still 2'406 bytes. I should have made it smaller or use another compression method XD

 

[MossyStone48]

From experience this is what I can figure about the way the game handles non-players. I could be wrong. Currently pathfinding system applies to NPCs more than simulation controlled Ships. Or at least i suspect they do. They seem to be handled differently. The NPCs pathfinding allows them to move and even return to a given position. (IE follow the leader) The current simulation that runs Bobby AIs, Trader and Pirate factioned craft appears to be earlier work and does not have the ability to do anything besides select a target and fly towards it while another simulation fires on it if hostile. A new target can be designated afterward and the entity despawned (as traders do when delivering to shops) but they are not , infact, returning to any particular point.