Allow variable-cost cells in pathfinding

[alexjurkiewicz]

I noticed that A* pathfinding implementation calls its passability callback to determine if the sourceX,sourceY cell is passable. In my game this is a problem, since monsters block movement and the monster I'm pathfinding for therefore blocks its own movement! I work around this by creating the callback dynamically, and ignoring the source monster:

(typescript)

  /**
   * Build a function that checks if a point is passable, ignoring a given
   * entity. We need this so entities do not block themselves while pathfinding!
   * @param e Entity to ignore.
   */
  private passableCallbackFactory(e: Entity): (x: number, y: number) => boolean {
    return (x, y) => {
      if (!inRange(x, 0, this.MAX_X) || !inRange(y, 0, this.MAX_Y)) {
        return false;
      }
      const entities = entitiesAt(x, y);
      // Don't let entities block themselves
      if (entities === [e]) { return true; }
      // Otherwise, the tile is passable if there are no entities
      return entities.length === 0;
    };

Could the pathfinding algorithm be changed to assume the starting position is passable?

--- Want to back this issue? **[Post a bounty on it!](https://www.bountysource.com/issues/44095305-allow-variable-cost-cells-in-pathfinding?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github).

[ondras]

This is more tricky than it looks. Partly because I would like to maintain consistency between the AStar and Dijkstra pathfinders.

The Dijkstra algorithm works by computing distances from every source cell to a particular target. That is why the [toX, toY] coords are fixed by passing them to ROT.Path.Dijkstra constructor, while [fromX, fromY] can be modified by calling .compute() with different arguments.

This means that the actual underlying computation is totally unrelated to the starting position. The topology used (i.e. what neighbors a particular cell has) is expected to by consistent and immutable for every single .compute() call. But your request (a very reasonable one!) implies that you want different topologies for different .compute() calls.

I am really not sure how to implement the requested behavior, given the current state of the API/implementation of the ROT.Path.Dijkstra pathfinder. On the other hand, I see no problem with your approach to the issue -- that is why the passableCallback exists; to provide enough flexibility for all situations.

[alexjurkiewicz]

Fair enough! While we're on the subject I have another feature request which I don't think I can implement myself: different cell traversal costs. Maybe mud tiles cost 2x to move through, or similar. Would this be possible?!

On Thu., 13 Apr. 2017, 6:29 pm Ondřej Žára, notifications@github.com wrote:

This is more tricky than it looks. Partly because I would like to maintain consistency between the AStar and Dijkstra pathfinders.

The Dijkstra algorithm works by computing distances from every source cell to a particular target. That is why the [toX, toY] coords are fixed by passing them to ROT.Path.Dijkstra constructor, while [fromX, fromY] can be modified by calling .compute() with different arguments.

This means that the actual underlying computation is totally unrelated to the starting position. The topology used (i.e. what neighbors a particular cell has) is expected to by consistent and immutable for every single .compute() call. But your request (a very reasonable one!) implies that you want different topologies for different .compute() calls.

I am really not sure how to implement the requested behavior, given the current state of the API/implementation of the ROT.Path.Dijkstra pathfinder. On the other hand, I see no problem with your approach to the issue -- that is why the passableCallback exists; to provide enough flexibility for all situations.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/ondras/rot.js/issues/115#issuecomment-293826366, or mute the thread https://github.com/notifications/unsubscribe-auth/AAXKda3IbuRoQn5byS6phi9cAswepUIWks5rvdzUgaJpZM4M8Qm3 .

[ondras]

I have another feature request which I don't think I can implement myself: different cell traversal costs. Maybe mud tiles cost 2x to move through, or similar. Would this be possible?!

Yes, and I think that we can even re-use the current API for that. The passableCallback can return a numeric value, representing a relative traversal cost. This behavior might be implemented for both AStar and Dijkstra pathfinders.

I am out of time to do this properly now, but feel free to open an Issue for this feature. Someone else might be interested in implementing it or I might find some time in the future.