Optimize Searching Using Value Types
December 6, 2011 Leave a comment
As mentioned in my blog post here, I need to write a searching algorithm of hexes adjacent to the active unit to display movable/visible/attackable hexes. The original code was a bit of a beast across 3 functions:
1 public List<Hex> GetTotalAdjacentHexes(Hex currentHex, Int32 maxDistance) 2 { 3 List<Hex> hexes = new List<Hex>(); 4 List<Hex> tempList = GetAdjacentHexes(currentHex); 5 foreach (Hex hex in tempList) 6 { 7 if (!InHexList(hexes,hex)) 8 GetAdjacentHexes(currentHex, hexes, hex, tempList, 0, maxDistance); 9 } 10 return hexes; 11 } 12 13 public void GetAdjacentHexes(Hex currentHex, List<Hex> hexes, Hex hex, List<Hex> currentList, int distanceCounter, int maxDistance) 14 { 15 distanceCounter++; 16 { 17 foreach (Hex tempHex in currentList) 18 { 19 hexes.Add(tempHex); 20 if (distanceCounter < maxDistance) 21 { 22 List<Hex> tempList = GetAdjacentHexes(tempHex); 23 GetAdjacentHexes(currentHex, hexes, hex, tempList, distanceCounter, maxDistance); 24 } 25 } 26 } 27 } 28 29 public List<Hex> GetAdjacentHexes(Hex currentHex) 30 { 31 32 List<Hex> adjacentHexes = new List<Hex>(); 33 Hex targetHex = null; 34 //Above 35 int targetColumnNumber = currentHex.ColumnNumber; 36 int targetRowNumber = currentHex.RowNumber - 1; 37 targetHex = GetHex(targetColumnNumber, targetRowNumber); 38 if (targetHex != null) 39 adjacentHexes.Add(targetHex); 40 //Top Left 41 targetColumnNumber = currentHex.ColumnNumber - 1; 42 if (currentHex.ColumnNumber % 2 == 0) 43 targetRowNumber = currentHex.RowNumber - 1; 44 else 45 targetRowNumber = currentHex.RowNumber; 46 targetHex = GetHex(targetColumnNumber, targetRowNumber); 47 if (targetHex != null) 48 adjacentHexes.Add(targetHex); 49 //Bottom Left 50 targetColumnNumber = currentHex.ColumnNumber - 1; 51 if (currentHex.ColumnNumber % 2 == 0) 52 targetRowNumber = currentHex.RowNumber; 53 else 54 targetRowNumber = currentHex.RowNumber + 1; 55 targetHex = GetHex(targetColumnNumber, targetRowNumber); 56 if (targetHex != null) 57 adjacentHexes.Add(targetHex); 58 //Below 59 targetColumnNumber = currentHex.ColumnNumber; 60 targetRowNumber = currentHex.RowNumber + 1; 61 targetHex = GetHex(targetColumnNumber, targetRowNumber); 62 if (targetHex != null) 63 adjacentHexes.Add(targetHex); 64 //Bottom Right 65 targetColumnNumber = currentHex.ColumnNumber + 1; 66 if (currentHex.ColumnNumber % 2 == 0) 67 targetRowNumber = currentHex.RowNumber; 68 else 69 targetRowNumber = currentHex.RowNumber + 1; 70 targetHex = GetHex(targetColumnNumber, targetRowNumber); 71 if (targetHex != null) 72 adjacentHexes.Add(targetHex); 73 //Top Right 74 targetColumnNumber = currentHex.ColumnNumber + 1; 75 if (currentHex.ColumnNumber % 2 == 0) 76 targetRowNumber = currentHex.RowNumber - 1; 77 else 78 targetRowNumber = currentHex.RowNumber; 79 targetHex = GetHex(targetColumnNumber, targetRowNumber); 80 if (targetHex != null) 81 adjacentHexes.Add(targetHex); 82 83 return adjacentHexes; 84 }
I recently had a duh moment when I tried to optimize the code for speed (replacing hexes with tiles) – each hex has an unique row/column value that I could use to calculate distance. In addition, instead of looping and collecting heavy reference types, I am using 2 integers in 1 loop, so the performance is dramatically improved. Finally, since I drop from 84 lines of code to 54, I am making my code more maintainable.
1 public List<Tile> GetTotalAdjacentTiles(Tile startTile, Int32 maxDistance) 2 { 3 List<Tile> tiles = new List<Tile>(); 4 int startingColumn = startTile.ColumnNumber - maxDistance; 5 if(startingColumn < 0) 6 { 7 startingColumn = 0; 8 } 9 int endingColumn = startTile.ColumnNumber + maxDistance; 10 if (endingColumn > Game.CurrentBoard.NumberOfColumns) 11 { 12 endingColumn = Game.CurrentBoard.NumberOfColumns; 13 } 14 15 int startingRow = startTile.RowNumber - maxDistance; 16 if (startingRow < 0) 17 { 18 startingRow = 0; 19 } 20 int endingRow = startTile.RowNumber + maxDistance; 21 if (endingRow > Game.CurrentBoard.NumberOfRows) 22 { 23 endingRow = Game.CurrentBoard.NumberOfRows; 24 } 25 26 Tile tile = null; 27 int combinedDistance = 0; 28 for (int i = startingColumn; i <= endingColumn; i++) 29 { 30 for (int j = startingRow; j <= endingRow; j++) 31 { 32 tile = GetTile(i, j); 33 if (!tiles.Contains(tile)) 34 { 35 combinedDistance = GetDistanceBetweenTwoTiles(startTile,tile); 36 if (combinedDistance <= maxDistance) 37 { 38 tiles.Add(tile); 39 } 40 } 41 } 42 } 43 44 //Remove Starting Tile 45 tiles.Remove(startTile); 46 47 return tiles; 48 } 49 50 public List<Tile> GetAdjacentTiles(Tile currentTile) 51 { 52 return GetTotalAdjacentTiles(currentTile, 1); 53 }
Jamie Dixon's Home 