Finding a path to nearest walkable tile, of a nonwalkable tile

[Mads]

I have my AStar pathfinding set up, and it works great! However, I can only find paths to tiles I define.
If theres not a path to this location, it will return null.

The scenario is this: I want to go to a tree at x3 y6, but I can’t feed those coordinates to the pathfinder, because I cant walk on the tree.
I also just can’t grab the coordinate next to it, because it might not be the nearest to the tree. That’s all the functionality it needs, so it’s not quite as wide as the title may suggest.

How would you go about this?

[loom_weaver]

One possibility is to make all tiles walkable but some just have a really high weight.

As a result, you’ll get a path and your character will try to walk it but will be blocked once they reach the obstacle.

[Mads]

@loom_weaver

One possibility is to make all tiles walkable but some just have a really high weight.

As a result, you’ll get a path and your character will try to walk it but will be blocked once they reach the obstacle.

That does seem a little hacky, and it’ll still walk there if there is not other choice

[UprightPath]

Closest tile of a non-walkable tile?

Have you tried doing a BFS from the nonwalkable tile, selecting the closest one(s). Then performing your A* to those and picking from there? This will render the closest tile.

If you want to find the closest-walking distance walkable tile, it takes a bit of finesse. You’d have two different pathfinders.

The Non-walkable one’s hueristic would add in the distance from the walkable tile to the non-walkable goal. Then you’d keep expanding nodes like a regular A* until the current-cost-to-node > (best-cost-to-node + distance to hueristic tile).

[gbeebe]

Examine the tiles in the closed list, calculate the distance to the destination and pick the one that has the least.

[Mads]

@UprightPath

Closest tile of a non-walkable tile?

Have you tried doing a BFS from the nonwalkable tile, selecting the closest one(s). Then performing your A* to those and picking from there? This will render the closest tile.

If you want to find the closest-walking distance walkable tile, it takes a bit of finesse. You’d have two different pathfinders.

The Non-walkable one’s hueristic would add in the distance from the walkable tile to the non-walkable goal. Then you’d keep expanding nodes like a regular A* until the current-cost-to-node > (best-cost-to-node + distance to hueristic tile).

Can you elaborate on what a BFS is? I didn’t quite get the rest of your post
EDIT: I just did some more research, and I found out not only what a BFS is, but also that it could solve my problem.
I suppose I can use the same heuristic as the pathfinder to determine the tile?

@gbeebe

Examine the tiles in the closed list, calculate the distance to the destination and pick the one that has the least.

The tile I want could be in the open-list though. If I could make a path to the tree (the tile I want to end next to), it would be the next-last one in the entire path. However, I can’t make a paths goal a walkable tile.

Did I mention my movers can’t travel diagonals?

[Damocles]

You should make 2 searches then.

One from the target position to a closeby “A* Node” to check if its valid.
(You can also test several nodes, and pick the shortest as Targetnode)

Then when the mover reaches the End A* Node, make a local search to the target.

So you have 2 “resolutions” in your pathfinding.

[gbeebe]

If you can’t reach the tree, it shouldn’t be in your open list.

[UprightPath]

Hmm, when I stated the second half I had an idea. However, now I don’t know for sure if it’d work or not. I’d have to work on it a bit before I actually repeat it.

[gbeebe]

Here’s how I would do it, in somewhat pseudo code:

A Node has an x, y, cost, and parentNode. parentNode is the Node that got you to this Node.
Create a 2d array Node nodeMap[][]; equal to the width and height of the map (in tiles).
Create an ArrayList openList = new ArrayList();
Create another ArrayList path = new ArrayList();
Add your starting tile to the nodeMap in the X and Y coordinate, set the x and y, cost = 0 and parentNode = null;
Add it to the openList, openList.add(nodeMap[ x ][ y ]);
Now your loop while(!openList.isEmpty()){
for(int n = 0; n < openList.size(); n++){
examine the possible reachable neighbors of openList.get(n)
if this node already has data (check the parent value), see if your cost is better and update it.
add them to the nodeMap and fill in the values
Then add that entry to the openList.
remove the current tile from the openList, openList.remove(n);
}
}
When you’ve gotten to this point you’ve mapped out all reachable tiles.
If the nodeMap[destinationX][destinationY].parent is null, you can’t reach the tile
so scan through your nodeMap and find the tile that is closest to the destination and assign it as the destination.
Otherwise we’ll start at the destination.
Work your way back, from destination parent (in nodeMap) to parent to parent until you’ve reached the start node.
Using 0 as the index will ensure it gets placed at the beginning of the list, path.add(0, thisNode.parent);
Now you have an arraylist that is traceable from start to the destination (or close as you can get to the destination).

[loom_weaver]

@Mads

@loom_weaver

One possibility is to make all tiles walkable but some just have a really high weight.

As a result, you’ll get a path and your character will try to walk it but will be blocked once they reach the obstacle.

That does seem a little hacky, and it’ll still walk there if there is not other choice

It won’t walk through the tile because it can’t. I made an error in typing my original advice. What I actually meant to say is give non-walkable tiles a high value from the cost function when calculated during A*. I.e. to your game logic the tile is still unwalkable but to A* it is.

[DrZoidberg]

Why don’t you use Dijkstra’s algorithm? It’s very similar to A* exept it uses only one list and it doesn’t need you to give it a destination. Just give it the start node and it finds the distance of every node to the start node. So after running that algorithm you just have to look at all the tiles near your tree and check which one has the lowest distance. You could also use something in between the two algorithms. By adding a second list to Dijkstra’s algorithm you can get something that’s basically an A* without the heuristics and may run faster then Dijkstra.

Dijkstra's algorithm

[Mads]

@gbeebe

Here’s how I would do it, in somewhat pseudo code:

A Node has an x, y, cost, and parentNode. parentNode is the Node that got you to this Node.
Create a 2d array Node nodeMap[][]; equal to the width and height of the map (in tiles).
Create an ArrayList openList = new ArrayList();
Create another ArrayList path = new ArrayList();
Add your starting tile to the nodeMap in the X and Y coordinate, set the x and y, cost = 0 and parentNode = null;
Add it to the openList, openList.add(nodeMap[ x ][ y ]);
Now your loop while(!openList.isEmpty()){
for(int n = 0; n < openList.size(); n++){
examine the possible reachable neighbors of openList.get(n)
if this node already has data (check the parent value), see if your cost is better and update it.
add them to the nodeMap and fill in the values
Then add that entry to the openList.
remove the current tile from the openList, openList.remove(n);
}
}
When you’ve gotten to this point you’ve mapped out all reachable tiles.
If the nodeMap[destinationX][destinationY].parent is null, you can’t reach the tile
so scan through your nodeMap and find the tile that is closest to the destination and assign it as the destination.
Otherwise we’ll start at the destination.
Work your way back, from destination parent (in nodeMap) to parent to parent until you’ve reached the start node.
Using 0 as the index will ensure it gets placed at the beginning of the list, path.add(0, thisNode.parent);
Now you have an arraylist that is traceable from start to the destination (or close as you can get to the destination).

I have A* and pathfinding, but I can’t make the destination the tile I want to end standing next to, because it’s unreachable.
This seems like A* from the bottom up.

@DrZoidberg

Why don’t you use Dijkstra’s algorithm? It’s very similar to A* exept it uses only one list and it doesn’t need you to give it a destination. Just give it the start node and it finds the distance of every node to the start node. So after running that algorithm you just have to look at all the tiles near your tree and check which one has the lowest distance. You could also use something in between the two algorithms. By adding a second list to Dijkstra’s algorithm you can get something that’s basically an A* without the heuristics and may run faster then Dijkstra.
http://en.wikipedia.org/wiki/Dijkstra’s_algorithm

I really don’t want to search the entire map, because it’s not nessecary, and it doesn’t solve the problem.
What I’m looking for, is a Path that leads to anything neighboring x4, y7 for instance.

[gbeebe]

After the A* calculations are done you have a closed list. This is the list of all the tiles that you can reach. cycle through those and find the one that is closest to the destination (aka: your tree). You can use a simple calculation to figure out how close it is to the destination like Math.abs(nX - dX) + Math.abs(nY - dY);

[loom_weaver]

Mads,

I would encourage you to take another look at my solution. It’s not “hacky” in any way and you won’t be walking on tiles that are impassible.

In a roguelike or basically any kind of tile game you will have many tiles that will be permanently unwalkable or temporarily unwalkable. A tree is a good example of the former and simply having a mobile occupy a tile would be an example of the latter.

Take your initial problem that you posed:

.....
.a.T.
.....

a = the starting point and T is a tree.

The most elegant way to determine what path ‘a’ should take is to do A* from the start ‘a’ to the destination ‘T’ even though the tree is unwalkable.

The way to do this is to make it appear to A* that all paths are possible but tiles with obstacles just have a very high cost function. For example walking on the grass (.) costs 1 pt and the tree is 999. If you have a monster occupying a tile it would still have a high cost e.g. 25 but not as high as the permanently unwalkable tiles. The reasoning is that if the mobile encounters a log-jam of other mobiles it should walk up to it and wait until it clears rather than giving up because there is no empty path “right now”.

With this approach A* will give you a solution and you only need to execute the algorithm once. You make your mobile follow the given path as long as its possible and it will do so until it gets to the tree where it will be blocked because in reality, the tree is unwalkable.

[Mads]

@loom_weaver

Mads,

I would encourage you to take another look at my solution. It’s not “hacky” in any way and you won’t be walking on tiles that are impassible.

In a roguelike or basically any kind of tile game you will have many tiles that will be permanently unwalkable or temporarily unwalkable. A tree is a good example of the former and simply having a mobile occupy a tile would be an example of the latter.

Take your initial problem that you posed:

.....
.a.T.
.....

a = the starting point and T is a tree.

The most elegant way to determine what path ‘a’ should take is to do A* from the start ‘a’ to the destination ‘T’ even though the tree is unwalkable.

The way to do this is to make it appear to A* that all paths are possible but tiles with obstacles just have a very high cost function. For example walking on the grass (.) costs 1 pt and the tree is 999. If you have a monster occupying a tile it would still have a high cost e.g. 25 but not as high as the permanently unwalkable tiles. The reasoning is that if the mobile encounters a log-jam of other mobiles it should walk up to it and wait until it clears rather than giving up because there is no empty path “right now”.

With this approach A* will give you a solution and you only need to execute the algorithm once. You make your mobile follow the given path as long as its possible and it will do so until it gets to the tree where it will be blocked because in reality, the tree is unwalkable.

Very good point! This would be much faster (potentially four a*-findPath calls) than the thing I finally did (see below).
However, what would happen in this situation:

..TTT
.a.TG
..TTT

If the user selects the G, the pathfinder will be forced to return a path that is expensive, but it will return it as being possible.

What I finally implemented looks like this. I hope it’ll get better, because there is potentially four findPath calls on each of these.
I’m also kind of unhappy with the MAX_VALUE - I think it could’ve been done nicer. Does anyone have suggestions or comments?

public Path nearestNeighbor(Mover mover, int sx, int sy, int tx, int ty) {	
		
		Path closest = null;
		int stepAmount = Integer.MAX_VALUE;
		
		for (int x=-1;x<2;x++) {
			for (int y=-1;y<2;y++) {
				if ((x == 0) && (y == 0)) { // it's not a neighbour
					continue;
				}

				if ((x != 0) && (y != 0)) { // no diagonal movement
						continue;
				}	
				
				// determine the location of the neighbor and evaluate it
				int xp = x + tx;
				int yp = y + ty;
				if (isValidLocation(mover, sx, sy, xp, yp)) {
					Path path = findPath(mover, sx, sy, xp, yp);
					if (path != null) { // If there was not a path, continue on, adventurer!
						int steps = path.getLength();
						if (steps < stepAmount) { // If it has less steps there than anything before
							closest = findPath(mover, sx, sy, xp, yp);
							stepAmount = steps;
						}
					}
				}	
			}
		}
		// We've run out of search folks!
		if (closest != null) { // Something was found!
			return closest;
		} else { // Nothing was found!
			return null;
		}
	}

[loom_weaver]

@Mads

If the user selects the G, the pathfinder will be forced to return a path that is expensive, but it will return it as being possible.

Yes, A* will return a path that will take you into the pocket surrounded by the trees 2 tiles away from G. That is the tile you’re seeking right?

If you’re merely trying to determine if any path exists I would use a different algorithm such as flood-fill.

[Mads]

@loom_weaver

@Mads

If the user selects the G, the pathfinder will be forced to return a path that is expensive, but it will return it as being possible.

Yes, A* will return a path that will take you into the pocket surrounded by the trees 2 tiles away from G. That is the tile you’re seeking right?

How does this work? I thought a* avoids the ones with high costs but if there is no other route, it’ll take the ones with high cost.
To word it differently, because I did a bad job: I thought the high cost ones was low priority, but not completely out of question.

[loom_weaver]

@Mads

@loom_weaver

@Mads

If the user selects the G, the pathfinder will be forced to return a path that is expensive, but it will return it as being possible.

Yes, A* will return a path that will take you into the pocket surrounded by the trees 2 tiles away from G. That is the tile you’re seeking right?

How does this work? I thought a* avoids the ones with high costs but if there is no other route, it’ll take the ones with high cost.
To word it differently, because I did a bad job: I thought the high cost ones was low priority, but not completely out of question.

A* doesn’t completely avoid the high cost paths. It just evaluates the cheaper ones first.

I.e., it will avoid the tiles with high cost because it’s cheaper to start exploring the grass in the opposite direction than you’re trying to reach.

Imagine you’re hiking and want to get to the other side of a body of water. Depending on the terrain, at some point in time it’s cheaper to swim than to walk X number of miles to go around.

In the same manner A* will reach a point where biting the bullet and evaluating the path through the “impassible” trees is the cheapest path there is (note that the trees aren’t impassible to A*, they’re just really expensive to go through). In your example, the cost of going directly east through the ‘.’ and ‘T’ to the ‘G’ would be 1 + 999 + 1 = 1001. That’s the cheapest path and is what will be returned by A*.

[edit] Now given this path, you move your mobile along it until it can’t go any farther (because of the trees). Your mobile will move into the grass tile surrounded on three sides by trees which is where you wanted it to go all along.

[UprightPath]

A* is a modified Best-First search. Where the best is the node that has the lowest (traveled-to + remaining) cost. This means that for the most part expensive nodes will not be exploded, the same with paths that go backwards from your goal.

However, the amount of exploration depends on your heuristic. That is the basis of what makes it good. If your Heuristic isn’t goo, then you will explore more nodes than necessary. A lot more than necessary or a lot less.

This gets into the idea of Admissibility and Optimal.

If your heuristic does indeed render a cost that is <= the best path, it’s admissible. This means that it’s likely to only explore nodes that will lead it to the goal, instead of nodes that won’t. If it’s over, it will explore more of the more expensive nodes. Further, the closer it is to being the exact value, the more likely you are to find the optimal path. If it’s lower, you’re likely to find a path, but not always the best path. If it’s above you’re always going to find the best path.

Heuristic- Result

Actual Best path, not Optimal
= Actual Best path, and Optimal
< Actual A Path (Can’t figure the Optimality, however it’ll be faster than the > Actual).

So A* isn’t magical. It will not always find the best path, will often find a good path in a good amount of time.

Part of the issue that I have with the ‘High’ cost for impassable objects is that it if you make them cost too much, they will be the only part of path that matters in deciding your end point. If you make them cost too little, then your pathfinder will often kick out a path that will go through them.