Allow node to path "up to" a blocking tile

[charlie-s]

First, thank you so much for writing and releasing this, I found it quite easy to get it implemented in my SpriteKit app.

In my game, I want the sprite to be able to walk up to a boundary and stop if the user so decides it. For example, if there's a blocking wall that the user commands the sprite to walk beyond, the sprite should walk all the way to the wall and stop.

In HUMAStarPathfinder.m on line 115, we've got:

// check to make sure we can actually get a path to the target node
if (![self canWalkToNodeAtTileLocation:targetTileLocation]) {
    return nil;
}

Is this really necessary? Because the subsequent code will stop the sprite from reaching an unreachable tile anyway.

Aside from this, even if I direct my sprite to move past a blocking wall (as opposed to onto the actual block as described above) they do not move at all as shortestPath always turns up empty. I think this may be happening because of the logic in findAdjacentNodesForNode but can't really discern it yet. Can you shed any light on how I might achieve this?

[colinhumber]

Hey Charlie, glad you've found some use out of this! It's been awhile since I've looked at this, but I'll have a look at send you some thoughts/ideas when I've refreshed my memory!

On Apr 24, 2014, at 8:10 AM, Charlie Schliesser notifications@github.com wrote:

First, thank you so much for writing and releasing this, I found it quite easy to get it implemented in my SpriteKit app.

In my game, I want the sprite to be able to walk up to a boundary and stop if the user so decides it. For example, if there's a blocking wall that the user commands the sprite to walk beyond, the sprite should walk all the way to the wall and stop.

In HUMAStarPathfinder.m on line 115, we've got:

// check to make sure we can actually get a path to the target node if (![self canWalkToNodeAtTileLocation:targetTileLocation]) { return nil; } Is this really necessary? Because the subsequent code will stop the sprite from reaching an unreachable tile anyway.

Aside from this, even if I direct my sprite to move past a blocking wall (as opposed to onto the actual block as described above) they do not move at all as shortestPath always turns up empty. I think this may be happening because of the logic in findAdjacentNodesForNode but can't really discern it yet. Can you shed any light on how I might achieve this?

— Reply to this email directly or view it on GitHub.

[charlie-s]

Thanks Colin.

[colinhumber]

Hey @csdco just got around to having a look. I'm a little confused what the issue is. So, at line 116-118 I do the initial check to see if we can even walk to the target tile. If that check wasn't there no path would be returned eventually after the pathing algorithm completed, but it would be calculating it unnecessarily.

Are you trying to make it so that if you select a tile beyond a blocking wall the player will move all the way up to the wall and then stop? Basically, the pathing algorithm works where it will try and find a valid path from the start tile to the end tile. If it makes it to the end tile, then it performs a reverse path from the target to the source tile. If it never makes it to the end tile the path is determined invalid and will not complete.

A good example of this is http://qiao.github.io/PathFinding.js/visual/. Notice the path is only completed if it makes it to the end.

[charlie-s]

Yes, that's basically what I'm looking for. Finding the most valid path, regardless of the ending destination. That is, if I command the green square to move to the red square in that last screenshot it would get as close as it can, i.e. up to that center wall.

[colinhumber]

The A* algorithm works by working it's way towards the target node, inspecting a number of neighbor nodes to determine the shortest path. Once it hits the target node it works backwards checking the "value" on the nodes it's inspected to determine the shortest path. If it never makes it to the target node it's determined that there is no valid path.

I'd have to do some additional work to see if it's possible without mangling how A* typically works.

[charlie-s]

Good point. I'm basically looking at implementing this style as it existed in older point-and-click adventure games, but I can think of newer gameplay styles where an object is commanded to move to point X and has to go as far as they possibly can, for example an RTS game.

It is probably a good exercise for me to take your A* and work on this myself – do you think it's better to start fresh or start with yours, considering how yours implements it?