Well I am working on a project I dubbed Random RPG. It is basically a retro style(I use the NES color pallete and 25 color limit) RPG that is visually very much like the original Dragon Warrior games on the NES. Now I created a random continent generator(tile based) I am very proud of. My problem is trying to come up with solutions for how to place the towns and dungeons. The problem comes down to not just finding the best locations but also how to space them correctly.

For example, imagine my generator created a moutain range that surrounded plains tiles. My generator does this quite often and if it is not by mountains, it is by a combination of mountains and water. Like this.

MMMMM

MMMPMMM

MMPPPM

MMPPPMM

MMMMM

Now it would be in my best interest to figure out the easiest way of checking for where these locations are so I can place a high tier dungeon or town that would only be accessible later in the game, when the player acquires a flying form of transportation. Each type of tile is represented by a number and the entire continent is really one big array of integers. I have a seperate array with the tile information(tile world location, tile type etc.) in another array the same size which gathers all the integer arrray information once the world is generated. So if my continent is a map 256x256 I add 256 to an index in the integer array to check the tile directly north, - 1 for the one directly left and so on. From what I explained could anyone help me come up with some ideas for how i can tackle this probem?

Hi ILoveJesus,

I am currently working on 3D world generation (but it also applies for 2D i guess). I personaly only want to generate cities but not the less. What I do is is the following:

1) Generate the world itself (just a simple world with some mountains)

2) Randomly select locations I would like to place a city (random numbers basically).

3) Verify if there location I selected isn't 2 rough (checking 'x' locations around my selected location)

4) Generate a city layout

5) Encase the border of the city with mountains (with another bit of random generation magic)

6) Override world data for that part of the map

7) Generate accesspaths

You could do the same with 2d generation just generate a location for the dungeon surround the location with mountains and if it is a low level dungeon generate access paths if it's a high level dungeon don't generate.

Hope this helps, With kind regards,

StaticCube

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.

its 2d view right so on the x-y you know where generally coordinates will be in that world. You can then specify specific dungeans etc to be specific places on the map regions, for your main dungeons, the one's you don't want to be randomly placed every time the game starts, which are central to story.

As for random, just use a function to randomize the x-y coords of placement. The numbers you specify can put things into very specific locations or boxes.

Like

place castle( rand(10000, 12000, rand(1000,500) )

so the x and y placement is randomized. But you randomized it within a box, and you know where that box falls within the gameworld.

You can widen your net or box of placement as you see fit. Create an array and loop through it for as many castles as you want.

I really am a simpleton, I am sure someone will come along with a nice algorithm you don't understand :)

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.