5
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ What kind of information do you need regarding the adjacency? Just the x,y coordinate of the grid item? So if the player is at 6,6 you want to know that (6,5), (7,5), (5,6), (7,6), (5,7), (6,7) are solid? \$\endgroup\$ – Steven Oct 20 '15 at 0:23
  • 3
    \$\begingroup\$ I dont think you can come up with better algorithm than flooding you described. If there are n tiles of island and e water tiles around, you cannot find all of them with less than n + e tests(assuming you are not testing already tested ones). The raycasting is the slow part, I would try to find a way how to avoid it e.g. if(grid[x,y] == land) if you generated the grid at runtime you know if there is land on specific tile. \$\endgroup\$ – wondra Oct 20 '15 at 0:23
  • \$\begingroup\$ Is the landmass changing or fixed? \$\endgroup\$ – Majte Oct 20 '15 at 11:53
  • \$\begingroup\$ Can't you do preprocessing? \$\endgroup\$ – Adrian Krupa Oct 20 '15 at 11:59
  • \$\begingroup\$ @Steven Yes, I just need the coordinate pairs. My picture may be a little misleading because the islands can be a lot larger, and I would need to return all of the tiles for that island. In other words, the land positions adjacent to the player and the land positions adjacent to the adjacent positions until the entire island is covered. \$\endgroup\$ – GeoJohn Oct 20 '15 at 14:13
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This sounds great. The hashtable! Good idea. Probably eliminates some unnecessary processing time! This sounds like the way to go if I end up sticking with the raycasting method. \$\endgroup\$ – GeoJohn Oct 20 '15 at 14:19
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, this sounds like the best way to do it dynamically at run time without indexing the entire map when it is created. \$\endgroup\$ – GeoJohn Oct 20 '15 at 14:21
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.