Path-finding: Clicking somewhere that they can't walk paths until they are blocked?

[goldfire]

Is this behavior possible? For example, if I've got an entity that is occupying a tile, and I want the player to click on it and walk up to it. Currently, the player will just do nothing. However, it would be nice if they could click on it and it would path them up to the adjacent tile.

Another example would be where a player is on the other side of a wall and click on the side they can't get to. In some cases, I'd like the player to walk up to the wall when they do this, instead of just not moving.

I realize this isn't a behavior that would always be desirable, but I'm seeing use-cases where it would be as an option.

[Irrelon]

Agreed, I'll see what I can do...

[brockfanning]

I wrote some hacky code to attempt this a while back. It worked with the assumption that users would usually click 1 tile away from where they can actually walk to. I think the engine has change a lot since I wrote it, so I won't paste any code, but essentially the logic was:

• Before generating a path, check the "path class" of the end point, to see if it is valid (ie, make sure it's not a wall, ocean, or whatever)
• If so, temporarily make it valid (change the path class of that tile)
• Generate the path as usual
• Revert the end point's path class to whatever it was before
• When the entity is walking the path, if the end point was invalid, ignore the last step in the path

[Irrelon]

@brockfanning Thanks for that! That works well for use cases where only the destination tile is an invalid class but what about if the surrounding tiles are also invalid?

The way to do it I think, would be to:

1) Generate a path without ANY invalid tiles which would effectively end up being an almost straight-line to the destination. 2) Walk backwards along the path from the destination and check each tile until a "valid" tile is found. That becomes your "real" destination. 3) Generate a path using valid tiles to the new destination.

It is double the path generating cost in the worst case. Best case would be that it might be very quick to generate the first "all valid" path and then walk it to a valid tile (steps 1 and 2).

Can anyone see a flaw in the logic above? I haven't tested the idea at all, just had it stewing in my brain for a bit.

[brockfanning]

You're right, my solution was just for 1-tile-off clicking. I was thinking that that would cover the most common use case. (ie, clicking on a target, or accidentally clicking on an obstacle) If the surrounding tiles were also invalid, then no path would be generated, and the user would not move. I suppose you could make it as "fuzzy" as you want, but eventually there would be some hard-coded limit of number of tiles.

The only issue I can think of with your straight line solution is that if the straight line contains invalid tiles just before the destination, the behavior could be odd in some cases. For example if the target is standing right behind an obstacle, then the user's path would stop on the other side of the obstacle, instead of walking around the obstacle to get to the target.

[Irrelon]

This has now been implemented. The final solution wasn't either of the above-mentioned techniques but still works very well. Here are the new aStar() method arguments:

/**
 * Uses the A* algorithm to generate path data between two points.
 * @param {IgeCollisionMap2d} tileMap The tile map to use when generating the path.
 * @param {IgePoint} startPoint The point on the map to start path-finding from.
 * @param {IgePoint} endPoint The point on the map to try to path-find to.
 * @param {Function} comparisonCallback The callback function that will decide if each tile that is being considered for use in the path is allowed or not based on the tile map's data stored for that tile which is passed to this method as the first parameter. Must return a boolean value.
 * @param {Boolean} allowSquare Whether to allow neighboring tiles along a square axis. Defaults to true if undefined.
 * @param {Boolean} allowDiagonal Whether to allow neighboring tiles along a diagonal axis. Defaults to false if undefined.
 * @return {Array} An array of objects each containing an x, y co-ordinate that describes the path from the starting point to the end point in order.
 * @param {Boolean=} allowInvalidDestination If the path finder cannot path to the destination tile, if this is true the closest path will be returned instead.
 */
aStar: function (tileMap, startPoint, endPoint, comparisonCallback, allowSquare, allowDiagonal, allowInvalidDestination) {

The new "allowInvalidDestination boolean enables the behaviour of finding the nearest path.

[goldfire]

Thank you, seems to work great. Much improved gameplay experience :)