Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualILoveJesus

Posted 07 January 2013 - 10:01 PM

You could use a flood fill sort of algorithm to see what areas on your map are connected. I did something like this as an experimental project (that I haven't tried to make into a game yet so take my advice with a grain of salt) and although it wasn't very elegant it seemed to work. The flood fill routine that I used worked with a list of points to process rather than recursion to avoid potential stack overflow and I think also to control the flow direction of the flood.

 

Say your array (or a temporary one) is filled with 1s where you can walk and 0s where you can't. Iterate through your entire map array to find the first point where there's a location with a 1. Perform a flood fill that turns all accessible locations to a 2. Also (optionally) track how many spaces are changed to a 2. Continue on to the next location you find that still has a 1 and start a flood that turns all accessible locations now to a 3. Continue until you've gone through the entire map. You should then have the ability to determine how many isolated areas you have as well as their sizes. You could also then experiment with ways to open up areas to each other and then run the routine again to verify that they are indeed connected.

 That is exactly what I am looking for. Thank you. I guess I should also maybe make an array of int arrays. With each int array containing a seperate flood. Then I can use the sizes of each array to determine the area sizes and put the high tier towns and dungeons in the smallest arrays. That is perfect. Thank you.


#1ILoveJesus

Posted 07 January 2013 - 10:00 PM

You could use a flood fill sort of algorithm to see what areas on your map are connected. I did something like this as an experimental project (that I haven't tried to make into a game yet so take my advice with a grain of salt) and although it wasn't very elegant it seemed to work. The flood fill routine that I used worked with a list of points to process rather than recursion to avoid potential stack overflow and I think also to control the flow direction of the flood.

 

Say your array (or a temporary one) is filled with 1s where you can walk and 0s where you can't. Iterate through your entire map array to find the first point where there's a location with a 1. Perform a flood fill that turns all accessible locations to a 2. Also (optionally) track how many spaces are changed to a 2. Continue on to the next location you find that still has a 1 and start a flood that turns all accessible locations now to a 3. Continue until you've gone through the entire map. You should then have the ability to determine how many isolated areas you have as well as their sizes. You could also then experiment with ways to open up areas to each other and then run the routine again to verify that they are indeed connected.

 That is exactly what I am looking for. Thank you. I guess I should also maybe make an array of int arrays. With each int array containing a seperate flood. Then I can use the sizes of each array to determine the area sizes and put the high tier towns and dungeons in the smallest vectors. That is perfect. Thank you.


PARTNERS