Region Growing Algorithm is one of pathfinding solutions and it is simple to implement. For example, in a game you have a map of two-dimensional-array and you want to move a character from start point to end point. The advantages if you use Region Growing are you don’t have to check every tiles and effective if your map is not perfect maze.
Here’s the preudocode :
1. Create a list of the four adjacent cells (right left up down), with a counter variable of the current element’s counter variable + 1
2. Check all cells in each list for the following two conditions:
– If the cell is a wall, remove it from the list
– If there is an element in the main list with the same coordinate and an equal or lower counter, remove it from the list
3. Add all remaining cells in the list to the end of the main list
4. Go to the next item in the list
5. Stop if :
– You find the goal
– All adjacent cells are invalid and you still can’t find the goal (impossible)
6. If you found the goal, track solution path in reversed way.
Here’s the example, a character (start) and a goal. the obstacles are trees (we will ignore them). In images below, we need 5 iterations before we find the goal, and once the goal is found, we’ll built the solution in reversed way ( starting from 5 to 0; 5-4-3-2-1-0 )