How can I better place cities around procedurally generated terrain?

Question

I'm making a terrain/map generator. The terrain generation works fine, but a problem arises when placing cities around the terrain. I place cities on given terrain depending on the terrain's moisture, temperature, soil quality, and underground mineral prevalence. Naturally, the optimal terrain will have the next-to-optimal terrain very nearby, so my cities appear in clusters, like so (cities are red dots):

The solution I'm leaning towards is identifying if two cities are within a certain defined distance of each other, and if they are, move one of the cities to a location clear of other cities. My questions are:

1. Is that the best approach for spreading out cities?
2. If so, what technique can I use to determine how close two cities are (I read about nearest neighbor searches and it looked very promising, maybe that)?

Answer 1

I would lower the constrains for possible city-locations. Calculate a probability for each position for a city.

Than set a city by random according to the probabilities of all locations not yet occupied by cities.

Than lower the probabilities around the new set city (within a certain radius, Near the city lower the probabilities a lot (or even set them ti 0) and only lower then less with increasing distance.

This way the cities should be spread around your terrain quite naturally.

Example (very little one) How to take the next location:
You have 3 possible locations with probabilities 0.9, 0,2 and 0.4 Now sum up the probabilities 0.9 + 0.2 + 0.4 = 1.5
now take a random number between 0 and 1.5.

0   .. 0.9 take the first location  
0.9 .. 1.1 take the second location  
1.1 .. 1.5 take the third location

Answer 2

Two approaches:

If you have only few cities, whenever you are considering adding a new one, just calculate the distance from the new site to the existing cities, and do not add the city if the distance is lower than a threshold you set.

If you have lots of cities, allocate a mask of the same size as the original map grid, and whenever you add a city, mark all points near that city as "occupied" meaning that you can't add a new city to those. Basically, you set the suitability of a terrain point near existing city to zero by marking that in the mask. Create a disk shaped mask for best results. If you want, you can use a floodfill starting from the city then to fill the disk mask only through land routes, so that the influence of a city stops to one side of a river, say. (Think of Buda and Pest).