Factorio Forums

I had some freetime this weekend, so I spent it with some proof-of-concept modding.
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 The most important function is calcPath() it needs the start-/currentposition, the targetposition and (optional) a mode-parameter which defines what obstacles should be took into consideration.

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.

Mind if I .. "steal" your code for my mod ?
I want to implement some sort of vehicle that'll automatically go to destination, and your algo seems perfect for that

Meh, that is why I posted it here Feel free use it everywhere you might think it fits.

I also expanded the OP a bit.

Nirahiel wrote:Mind if I .. "steal" your code for my mod ?
I want to implement some sort of vehicle that'll automatically go to destination, and your algo seems perfect for that

In your place I would rather request developers to give access to ingame pahtfinding algorithm as it already has some optimizations done based on games needs.
Also drs9999 algorithm doesn't seem to work corectly. it would seem that it only supports only horizontal and vertical movments.
Or is one of those "optimized" A* algorithmy which only keep limited amont of already scanned node information in it as a way to lower memory imprint. But this could unfortunately lead to pathfinding algorithm of making much larger routes in certain conditions.

@drs9999
If you want I can make you a few test cases for testing of your lagorithm. I use theese mysel since I'm reimplementing Heuristic A* pathfinding algorithm in Object Pascal to be used with one of my future games.

drs9999 wrote:Also drs9999 algorithm doesn't seem to work corectly. it would seem that it only supports only horizontal and vertical movments.

Nope, it works correctly, because I implemented it that way
Anyway, it is simple to modify. You just have to expand the findNeighbours - function that it will check the "diagonal" nodes as well.

And no I am not using an "optimized" algorithm, as far as I know (just basic wikipedia knowledge), the modified ones only lower the needed memory, but also decrease the performance. And the speed/ amount of time to find the solution is already the bottleneck here.

Test-cases are appreciated
What I did so far was to create a sand-box game ( this one with god-controller) save it and calculate the exact path every time while tweaking some values/ functions.

Well this took longer for me to understand than it should have
The main issue (and this might be minor, I've never done any pathfinding) is to actually incorporate the 'size' of the rails. For instance, in the image you have you'd never be able to get a track from a to b along the path calculated. The easiest solution (I think) would likely be to calculate straight paths (high weight to any direction changes), and at direction changes move backwards by seven (I think, since for a right turn you need 2 curved rails with 2 straight rails inbetween, also check if possible to place these, otherwise straight continue until you can?) and start new path with the start position being the ending position of the second curved track needed for turning....not entirely sure if that would work and it wouldn't be the most optimal but...
It should be noted that after clicking 'build bridge' and then 'cancel' you can press 'build bridge' again even though the markers are destroyed. Which leads to an entity target is zero crash, that is for some reason unclickable (have to close factorio window)...
Also, scenario, I placed the ending marker near a tree (imagine train stop though), infinite search initiated when using 'avoid entities and water'. (btw, changing mode and reclicking build path seems to have no effect, I didn't check the code for that yet though).
Could also have a way to avoid resources (though that's easy enough).

I'll play with this more when I have time, though not sure what else I'd use it for right now it's definitely interesting (to me)

Yes you are absolutly right. Anyway it took me a whole afternoon to create a function that creates a rail from point A to B without searching for obstacles or water. Just a horizontal, a vertical and a curve. So I discarded that aproach and started with the simplest implementation of the algorithm.

But sure that would be the next step. But like I said, I am afraid that I will not have the time, bachelor-thesis, other university projects, important exams, yalla yalla

And yes I was aware that the other stuff will not work well. Nevertheless it is more a proof of concept than a "real" mod. So I would say it is sufficient

I think this Railnetwork.zip is close to this thread. So I just drop in here before I make a proper mod, if I make.
I guess you could call it semi-automatic since you need player to steer it, but rail building is automatic.

Usage:

• Place locomotive on straight rail and jump in.

• Code: Select all

  remote.call("railnetwork", "start")

• Start driving

If you make a loop, try the remote call again.

edit: I forgot to you are free to use it or parts of it for the A*. I imagine that aiming towards certain coord might be challenging though.

I tested it and there is one thing that really bothers me...

It is so awesome that it does not deserve to be buried here, so PLEASE continue and make it a proper mod

Would love to test this mod, but I am getting an error I cant really make heads or tails of.

when attempting to run the scenario "base/sandbox" (and any other scenario) with base 9.8 and v 0.1.0 of this mod, I get the error
-"Error while running the oninit: ...\mods\UtilityMarker|control.lua:35; attempt to index global 'hf' (a boolean value)"

Given Im not proficient in lua any help would be greatly appreciated!

Eclipse wrote:Would love to test this mod

It's really not a mod and if you want to work with it you're going to want/need to learn some Lua fairly well...but, here's a self-contained (does not require the blueprint mod), loadable version for 0.9.8: UtilityMarker.zip

mind if I ask you why you stopped your idea of automatic rail placement ?
from what I saw in your code, you put some work into it !

would you mind me using your idea to try to make a whole mod (I've got some ideas of how to do it !)?

well, actually, I just read the FARL thread,
my idea is preety much already done so ...