Pathfinding based on ending callback instead of position

[crotron]

Looking at the documentation, the Dijkstra routine for rot.js seems to accept a starting position and an ending position (among other things) and tells you the path between the two. I think this could potentially be made a bit more flexible through an alternate set of input parameters. The Dijkstra algorithm (unlike A*) is capable of handling multiple possible ending positions by basically just stopping at the first ending position you find. So rather than providing a single ending position, could we instead pass in a callback that takes in an x,y position and returns a boolean telling you whether or not it found one of the ending points? This would be of use in, for example, implementing an auto-explore system. In order to find the nearest unexplored tile to walk to, just have your ending callback return 1 if the tile at x,y is unexplored and 0 if it is not.

As a side note, it should also be possible to have multiple possible starting positions for Dijkstra as well, although I can't really think of any great use cases for that off the top of my head.

[ondras]

Well, this is hard API-wise. All pathfinder objects in rot.js have their constructor signature based on (targetX, targetY, ...), so swapping those coordinates with a callback will be quite messy.

This is also complicated by the historical fact that the logic is kind of inverted: you first specify the target and than (re-)use the instance for individual source positions. I am not sure why I made this decision: perhaps because the very first use case for pathfinding was "one player, many monsters tracking its position at once".

So the implementation literally starts iterating from the target set of coordinates, spreading away and checking "whether the source has been reached". This is wildly incompatible with the idea of a target callback.

[ChristianKienle]

First of all thank you very much for your library. I am using parts of it in a game I am developing. I also tried to use your path finding implementation and also found it not flexible enough. Before I continue: I am not writing this in order to make you feel bad or anything. As I said: rotjs is fantastic. I am writing this because of two reasons:

1. To give you (additional) feedback.
2. To offer help :)

So my problems with the path finding in rotjs:

The documentation states:

If no such path exists, outputCallback will never be called.

To me this was not good enough because I wanted to know whether or not a path actually exists. If the callback is never called I cannot "try the next" set of coordinates that I have in mind.

When I wanted to implement the rails/train-scheduling part of my game I found that I need more than just 4/8 directions that need to be checked (for curves, crossings in the rail system).

Also I think it is not possible to use your implementation to compute a route via a certain location. It is trivial if you create two instances of the path finder but impossible if you do not AND you want to re-use the same instance for other path computations.

Because of all those things I took the code of your A*-algorithm as a basis for my own A-* path finder.

• I removed the output callback (the path is now returned synchronously or undefined)
• You can set a new source/destination coordinate
• You can pass in an additional callback the returns custom adjacent coordinates
• You can mutate the internal state of the path finder and reset it
• You can easily "reverse" paths by calling reversed(): Path.

If you compare my code with yours you will find a lot of similarities because I basically just modified your code in an incompatible way. If you want I can clean it up and share it with you or even create a PR. How do you want to handle incompatible changes? A new class?

Again: Thanks a lot for your library and hard work.

[ondras]

If no such path exists, outputCallback will never be called.

To me this was not good enough because I wanted to know whether or not a path actually exists. If the callback is never called I cannot "try the next" set of coordinates that I have in mind.

Well, so you call compute and if your callback does not get executed, you can try the next set. Am I missing something here?

(The callback would only set a bool value to true, to be checked after the compute() ends. It is all synchronous; the presence of a callback does not imply non-blocking execution.)

When I wanted to implement the rails/train-scheduling part of my game I found that I need more than just 4/8 directions that need to be checked (for curves, crossings in the rail system).

Also I think it is not possible to use your implementation to compute a route via a certain location. It

Yeah, one can never be flexible enough to cover all potential use cases 🤷

If you want I can clean it up and share it with you or even create a PR.

Yes, please. I believe that the pathfinding part of rot.js can benefit from additional improvements.

How do you want to handle incompatible changes? A new class?

The original pathfinding intent was to declare a common interface for pathfinders and provide many compatible implementations. Turns out this was way too ambitious (we only have A* and dijkstra, one being a subset of another) as well as limiting (fixing the interface). So I would suggest you add your pathfinder as a new class/object, not constrained with the current API. If it happens to be customizable enough (so one can configure the A* cost in order to become Dijkstra), I would be happy to offer it as a full-blown alternative to the current ROT.Path namespace.

[ChristianKienle]

Thanks for your response!

Well, so you call compute and if your callback does not get executed, you can try the next set. Am I missing something here?

Yeah sure. I tried this initially and it worked but it was a head scratcher for me. The fact that the callback function is called synchronously was not clear from the documentation alone. So I had to read the source code to make sure that it really is synchronous. I thought "hmmm maybe he will use promises internally in some future update so I will not rely on the callback function being called synchronously for now.". Maybe I was just afraid because I am not so experienced.

But when I have an API that is doing it's stuff synchronously I personally avoid callbacks and just return the result. This way it is also clear for the consumers of such an API. But this is probably also just personal preference.

Yeah, one can never be flexible enough to cover all potential use cases 🤷

Sometimes (most of the times?) flexibility is also a curse.

The original pathfinding intent was to declare a common interface for pathfinders and provide many compatible implementations. Turns out this was way too ambitious (we only have A* and dijkstra, one being a subset of another) as well as limiting (fixing the interface). So I would suggest you add your pathfinder as a new class/object, not constrained with the current API. If it happens to be customizable enough (so one can configure the A* cost in order to become Dijkstra), I would be happy to offer it as a full-blown alternative to the current ROT.Path namespace.

<3 I will do my best some reserve some time for this.

[ondras]

But when I have an API that is doing it's stuff synchronously I personally avoid callbacks and just return the result. This way it is also clear for the consumers of such an API. But this is probably also just personal preference.

True. I agree that this design decision is a bit controversial. My main point was to not force a particular (complex) data structure. With callbacks, you receive all relevant values as individual (scalar) arguments and are free to store them according to your preference.