Limit breadth-first search in confined space

Questions & Answers
1

Hello everyone,

I’m trying to find a way to limit a breadth search, but have run into some problems due to the search overrunning the confines of it’s search area. To illustrate, this is an example of the search working normally, and here is what happens when it’s search range is outside the border of it’s search area.

I know that this is because I’m only breaking the search loop when the current position is greater than the origin + range, but I can’t think of any other ways to do this. I have considered also checking if the position is less than the origin - range, however that won’t help, due to the variable size of the search area (it would be possible for both top and bottom positions to overlap the area).

If it helps, the code I’m using to search is bellow (with the range-check at line 27), and the full source is linked, after that.

    private Tile FindNearest ( Tile origin, int range, String environmentName )
	{

		List<Int2D> visitedTiles = new List<Int2D> ();
		
		Queue<Tile> queue = new Queue<Tile> ();
		queue.Enqueue ( origin );
		
		while ( queue.Count > 0 )
		{
			
			Tile current = queue.Dequeue ();
			if ( current == null || visitedTiles.Contains ( current.position ))
			{
				
				continue;
			}
			
			if ( current.environment.name == environmentName )
			{
				
				return current;
			}
			
			if ( current.globalPosition.z > origin.globalPosition.z + range )
			{

				break;
			}
			
			visitedTiles.Add ( current.position );

			queue.Enqueue ( current.Top );
			queue.Enqueue ( current.Left );
			queue.Enqueue ( current.Right );
			queue.Enqueue ( current.Bottom );
		}
		
		return null;
	}

Full Source (above code starts at 280)

TL;DR:

How do I limit the range of a breadth-first search, without using it’s position?

Thanks for taking the time to consider my question!
Michael

2

For anyone with the same question,

I eventually figured out that some basic geometry was in order. Simply finding the area of a rhombus ( A = p*q/2 ) gives the correct area of a completed BFS, which I use to check the it’s range.

This isn’t completely flawless yet; even though it subtracts from total tiles when it encounters a space outside of it’s scope, it doesn’t run the exact number of times when it’s on an edge. However it no longer runs endlessly when it encounters a border, and as that was the subject of my question, I’m posting this solution as an answer.

    private Tile FindNearest ( Tile tile, int range, String environmentName )
	{
		
		List<Int2D> visitedTiles = new List<Int2D> ();
		
		Queue<Tile> queue = new Queue<Tile> ();
		queue.Enqueue ( tile );
		
		int tilesToVisit = Mathf.CeilToInt ( Mathf.Pow (( range*2 )+1, 2 )/2 );
		while ( queue.Count > 0 )
		{
			
			Tile current = queue.Dequeue ();
			if ( current == null )
			{
				
				tilesToVisit -= 1;
				continue;
			}
			
			if ( visitedTiles.Contains ( current.position ))
			{
				
				continue;
			}
			
			if ( current.environment.name == environmentName )
			{
				
				return current;
			}
			
			visitedTiles.Add ( current.position );
			if ( visitedTiles.Count () >= tilesToVisit )
			{

				break;
			}

			queue.Enqueue ( current.Top );
			queue.Enqueue ( current.Left );
			queue.Enqueue ( current.Right );
			queue.Enqueue ( current.Bottom );
		}
		
		return null;
	}

I hope this helps!

Michael