How to test for adjacency?

Question

I need to come up with a better way to test for adjacency in a grid environment. Imagine that the blue is water, the green is land, and the red dot is a character. What I need to do is efficiently return a list of Vector positions of all grid tiles for the "island" that the character is on.

I have attempted to do this with raycasts using the following procedure.

-raycast at all of the immediately adjacent nodes surrounding the player.

-if (hit == land) then add hit to adjacent list.

-raycast at all immediately adjacent grid cells around each of the previous hits on land. (if they have not already been tested)

-if (hit == land) add to the adjacent list.

-loop until no more hits on land.

this seems to work okay, but is not very fast. If possible I need to maintain the raycasting because the levels are randomly generated at run time.

Answer 1

It's called a flood fill, and it's what you see in paint programs. It's very fast. Pseudocode:

declare visited list //the results you want
declare unvisited list

add current element (where red dot is) to unvisited list

while unvisited list not empty
   get current element from unvisited list
   add current element to visited list
   for all (8) neighbours of current element
       if neighbour is green
          if neighbour is not in visited list //be sure not to process same ones again!
              add neighbour to unvisited list
   remove current element from unvisited list

The way I'd do this is using a set (or hashtable if set not available); as these structures don't allow duplicates, you don't have to do the if neighbour is not in visited list in your own code.

Answer 2

so let me understand, you have a grid based datastructure and you use raycasting to analyse the data in it?

If so, what you should use is simple a recursive search. IF you make iterative will be even faster.

Simply start from the tile where your character is and then test the adjacent ones using indices. If they are island, repeat the operation until you don't find any.

Look for Breadth Search on Grids for further information. It's more or less like you described, but you don't really need the raycast.

Answer 3

If your land is fixed and predetermined when your game starts, you could store all information on adjacent tiles for each tile in a vector (or better a vector of vector, such as in C++, std::vector<std::vector <int> > during the game initialization stage and before your actual gameplay starts. The elements in the list contains information on all adjacent land tiles (e.g. for your 46th tile, the adjacent are 45, 47 etc.) Hence, you don't have to check the same thing over and over again in your gameloop.

Secondly, store the size of each vector too in a vector for each tile during your initialization. Thus don't have to check how many there are adjacent tiles for each tile (e.g. by size()) within your gameloop when you iterate over your adjacent tiles, for example if you want to show where your characters can move to.