Pathfinding API

[Earendel]

I would like the ability to make use of factorio's internal pathfinding api. Currently I am spawning an invisible unit and using it's trail to follow a path but there are a number of issues with that approach that I won't go in to.

Factorio already has a powerful pathfinder so it would be nice to expose it's functionality. Below are some thoughts on a possible way to do that but whatever fits best with the current system should be fine providing it's not specifically tied to unit entities. Part of the idea behind this is that you could use it to find paths for vehicles, characters, routes for transport belt, etc.

LuaSurface or LuaForce both seem like suitable places to expose the pathfinder.

The Pathfinder should make use of the existing path caching systems so any data passed in to the request should match that format. I don't know what that format is, but I it looks like it does recognise the differences between unit size and unit collision masks, so I'd imagine the function would wither required a collision_box and collision_mask, or would require a prototype name instead?

So something like:
surface.pathfinder_request_path{force=LuaForce, collision_box={{-0.49,-0.49},{0.49,0.49}}, collision_mask={"water-tile", "object-layer"}, start_position={x=0,y=0}, target_position={x=100,y=100}}
or
force.pathfinder_request_path{surface=LuaSurface, name="big-biter", start_position={x=0,y=0}, target_position={x=100,y=100}}

Expected responses would be
{ request={the data that made the request including the tick the request was made}, complete = bool(has the process finished), path={list of tiles from start to finish or nil}, valid=bool(only true if a path was found), failed=(nil if pending, string with either "timeout" or "impossible" if failed), pathfinding_started_tick=int(the tick the path was started or nil), pathfinding_ended_tick=int(the tick the path was found or failed or nil)}

The assumption would be that when you first make the request you get a response back with complete=false and maybe pathfinding_started_tick=nil so the pathfinder is busy and has not started yet. If you make the same request a few ticks later then if the pathfinder has found a path for that request it would return a response with the path. An alternative could be to have an on_path_found event instead?

For performance might also be necessary to have a required accuracy in the system to allow or disallow paths from nearby areas to use the same path cache.

[Earendel]

Any feedback on whether it's likely that pathfinder functionality might ever be exposed?

[Adil]

Pathfinder would be useful indeed.

[primedead]

I want this!

[Earendel]

@Rseding91 are you able to feed back on the chances of this ever happening?

[Rseding91]

The current path finder was built around biters and running over multiple ticks. I have no idea if it could be re-purposed to support one-off immediate calls and even if it could, I don't know how the result path would be fed back to Lua.

[Earendel]

Maybe if a path request was made and it fired an event when it finished?

[AntiBlueQuirk]

Yeah, I definitely think the pathfinding needs an API. I have an idea for a mod involving cars that desperately needs access to the pathfinding API. An asynchronous API would be totally fine. If the biters can put up with it, I think most mod authors would be able to. The way I think would work best is that you call a function like pathfinder_request_path, and then one of the following happens:

• Polling - The request function returns a request id, which can be passed to another function to get the current results of the pathfinder, if any.
• Events - You also register a callback with a "pathfinder_result" event. The request function returns a request id, which will match the request id later when the "pathfinder_result" event is triggered.
• Callbacks - You simply pass a callback along with your request. The callback is called when the results of the pathfinder are available.

Some thoughts about this:

• The polling method could cause memory leak issues, if mods request paths and then never follow up on the request. It would also require more bookkeeping in mods, which could cause errors.
• The events method would work well, and you wouldn't need the request id if you could pass arbitrary user data through to the events.
• The callback method seems the most elegant to me, since it would enable you to capture state through closures. Code to handle the finished path could also be close to the code that requested the path.
• I think the event/callback based methods would work better with the asynchronous nature of the pathfinder.
• Partial path data would be useful, since it would allow you to "get started" on the path early, even if you have to change your mind later, though it could increase complexity, and the current pathfinder may not support it.
• I'm a bit curious how the game keeps pathfinding synchronized between computers and demos, since it's handled in a separate thread. It would have to be handled similarly here.

[Earendel]

I think events would be a lot better than callbacks given that it would be asynchronous and a save-load could mean a code change between the request and the completion.

[Patashu]

Maybe if a path request was made and it fired an event when it finished?

This is how it works in Game Maker and Construct 2, IIRC.

[AntiBlueQuirk]

I think events would be a lot better than callbacks given that it would be asynchronous and a save-load could mean a code change between the request and the completion.

I meant for the callbacks to be asynchronous too, but now that you bring it up, saving the closure state might be difficult. Though it does raise some more questions. Are pathfinding calls saved now? If we had Lua access, should we expect our pathfinding calls to be saved anyway? Or would it just be part of the API that you have to resubmit pathfinding calls after reloads?

[Earendel]

Some further thoughts on a proposed specification:

LuaSurface.request_path{
collision_radius :: double : The collision box to use for pathfinding is created from this.
collsion_mask :: CollisionMask : The collision mask to use for pathfinding is created from this.
start_position :: Position : The position to start the pathfinding task.
end_position :: Position : The position to end the pathfinding task.
ignore_entities :: {LuaEntity} : A list of entities to ignore during the pathfinding task. Expected use is that pathfinding starts at the position of an entity, but that entity would block the starting position, so ignore that entity.
identifier:: string (optional) : A string that is passed to the path response event, can help identify a requested path.
}

on_path_result
Called when a pathfinding process has finished.
Contains
collision_radius :: double : The largest extend of the collision box used for pathfinding. eg: 0.4 for a Big Biter
collsion_mask :: CollisionMask : The collision mask to used for pathfinding.
start_position :: Position : The start position.
end_position :: Position : The end position.
identifier :: string (optional) : eg: "base big-biter".
tick_requested :: uint : The tick the path request was made.
path :: {Position} (optional) : Nil if the result is that no path was found. If a path is found then it would be a list of positions along the path including the start and end positions.