Recursive array searching optimisation

programming flash
1

I’m working on a grid based game where a user selects a tile and all the tiles with the same colour that are beside it disappear. Up until now I’ve been using this very rudimentary method to find the neighbouring tiles with the same colour (see below) but now that the game has gotten more complex and larger grids are involved performance is starting to lag so I would like to ask some help optimizing the code.

I have a Tile class like this:

package {
	
	public class Tile {
		
		public var xi:int;
		public var yi:int;
		public var value:int;
		
		public var searched:Boolean = false;
		
		public function Tile (xi:int, yi:int, value:int) {
			this.xi = xi;
			this.yi = yi;
			this.value = value;
		}
	}
}

Which is used to populate a grid. This is the code I’m using right now to search round a tile to find all its neighbours:

package {
	import flash.display.Sprite;
	
	public class RecursiveTest extends Sprite {
		
		private var arr:Array = [];
		private var rows:int = 10;
		private var cols:int = 10;
		
		public function RecursiveTest () {
			
			// Create grid and populate it with Tiles
			for (var xi:int = 0; xi < rows; xi++) {
				arr [xi] = [];
				
				for (var yi:int = 0; yi < cols; yi++) {
					
					// Give each Tile a random value between 0 and 4
					arr [xi][yi] = new Tile (xi, yi, int (Math.random () * 5));
				}
			}
			
			trace (findRelatedNeighbours (arr [3][6]));
		}
		
		private function findRelatedNeighbours (tile:Tile) : Array {
			var value:int = tile.value;
			var neighbours:Array = [];
			
			// Stops a tile being searched twice
			tile.searched = true;
			
			// Add tile to array
			neighbours.push (tile);
			
			// Check neighbouring tiles (if tile is not on an edge) to see if the value is the same and if so
			// Continue to search that tile
			
			// Check tile directly above
			if (tile.xi != 0 && !arr [tile.xi - 1][tile.yi].searched && arr [tile.xi - 1][tile.yi].value == value)
				neighbours = neighbours.concat (findRelatedNeighbours (arr [tile.xi - 1][tile.yi]));
			
			// Check tile directly below
			if (tile.xi != cols - 1 && !arr [tile.xi + 1][tile.yi].searched && arr [tile.xi + 1][tile.yi].value == value)
				neighbours = neighbours.concat (findRelatedNeighbours (arr [tile.xi + 1][tile.yi]));
				
			// Check tile to the left
			if (tile.yi != 0 && !arr [tile.xi][tile.yi - 1].searched && arr [tile.xi][tile.yi - 1].value == value)
				neighbours = neighbours.concat (findRelatedNeighbours (arr [tile.xi][tile.yi - 1]));
				
			// Check tile to the right
			if (tile.yi != rows - 1 && !arr [tile.xi][tile.yi + 1].searched && arr [tile.xi][tile.yi + 1].value == value)
				neighbours = neighbours.concat (findRelatedNeighbours (arr [tile.xi][tile.yi + 1]));
				
			return neighbours;
		}
	}
}

One approach I tried was at the initialization of the grid every tile is given a property with an array referencing all its similarly coloured neighbours so when a search needs to be done I can simply recurse through them. It is much faster but if possible I would like to avoid coupling a tile with anything else.

Thanks.

Edit: I managed to to speed it up by optimizing other parts of the game so its not that important anymore. If anyone still has suggestions though I’d love to hear them :smiley: