Pathfinding Using Region Growing Algorithm

Posted: April 8, 2011 in Algorithm, Game Programming, Programming
Tags: , ,

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 )

Comments
  1. Matt Jeers says:

    Nice post! This was a good introduction to pathfinding algorithms, something I would have no idea how to write before this. I’m getting heavy Minesweeper vibes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s