Search code examples
c++algorithmgame-enginegame-physics

Cluster terrain map disjoint by river through map/matrix?

I have simple matrix (matrix, which represents terrain map in 2d game, contains ASCII characters for example 'm' for mountain, 'v' for valley, 'r' for river) and on map there maybe one or none river. River can flow from any position from matrix to any ( and always separate map on two distinct parts => no source of river on map possible, always enter at one end and exists on another). How to separate matrix/terrain map on two clusters if there is river present ?

example terrain 

v v v v v v v v r v v v v v 
v v v v v m m m r m m m m m
v v v v v m m r r m m m m m
m m v m m m m r r m m m v v 
v v v v v v r r v v v v v v

here I should get left cluster and right cluster of coordinates which are not river.

Solution

  • You should try looking up the Fill algorithm. http://en.wikipedia.org/wiki/Flood_fill

    Basically you want to pick a point that it's not in a river, start the flood fill algorithm which will give you a set of points connected to the starting point. This way now you have one part and finding the one is pretty easy from now on.