I finally programmed a pathfinding-module.
The basic idea was/ is to make placing rails much more comfortable.
Anyway I am quite sure that a lot of work needs to be done until this target is reached and I will not have the time for it in the near future. So I thought it would be a good idea to upload it here, so everyone who might try it has a basic-foundation.
The uploaded file includes an example mod to try the pathfinding-module.
All functions that are related to the algorithm can be found in the a-star.lua file
- a_star.png (746.49 KiB) Viewed 16630 times
The function will return the currentNode (which can be passed as startposition in the next iteration) while the path is calculated. If there is no possible path to the target e.g. target is on an island the function returns nil.
If a path was found it returns a list of positions that leads to the target.
As a note: It is relative simple to modify the function to calculate the complete path in a single shot ( using a while-loop instead "if #openlist > 0") but at least on my pc the algorithm is a big performance sink , so the game will freeze completly until the calculation is done then, that is why I "split" the calculation over time.
Also you might want to look at the H-value-calculation ( calcH()). The H-value is used to estimate the distance between the currentPosition and the target. Like it is now, it calculate the Manhatten-Distance and multiplies it with an arbitrary value, which I call "weight". From my observation this "weight" has a huge impact on the performance, a higher value speeds up the whole process a lot, as a downside the algorithm might not return the shortest path between start and targetposition.
Just to show how big the impact is, I tested it with an "weight"- value of 1 and 10. With 1 the whole calculation needs 2:30 mins whereas the other calculation just needs 15 sec.
Feel free to ask if anything is unclear or you have any suggestions.
Feel free use it everywhere you might think it fits.
