# When to terminate search for path in an infinite grid

I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in a certain scope/range. However when expanding this to an infinite 2D grid, I don't understand when (say using BFS as an example) to conclude that a path simple doesn't exist without having the algorithm run infinitely since I can't use grid size as a boundary condition. Is there some kind of formula that can be used in these cases? Also, take into account that there could be obstacles along the path too so the path distance can vary from different origins to destinations.

I've considered trying to take the absolute value of the difference between the coordinate points and raising it to some power as a way of setting an upper limit of steps taken before considering that a path must not exist, but this approach is obviously lacking and incorrect to say it bluntly since it doesn't work for many cases.

I apologize if my question is confusing. I'll restate it here: basically, how do I know when to assume a path from an origin to a destination doesn't exist in an infinite 2D grid?

• How is the infinite 2D grid given? If there is a finite number of obstacles, sure you can only consider the finite part of the board, which is their (plus start point and end point) bounding rectangle, expanded a little. If the number of obstacles is infinite, there's no general-case recipe, but it may still be possible to deduce the existence of the path from the obstacles' structure. – Gassa Jun 18 '18 at 21:40
• The start and end point are known but the grid itself isn't given, so I've decided to pursue a bfs approach to find a path. Assuming there are a finite number of obstacles, I'm confused on how to calculate the bounding rectangle and how much extra space to allow to make certain a path either exists or doesn't. – TheDifficultyOfAlgortihms Jun 18 '18 at 22:00
• What properties does the grid have? Does each cell have a (possibly different) cost associated with moving through it? If not, one cell of extra space will be sufficient. – Gassa Jun 18 '18 at 22:12