Ich stimme den anderen zu. Dies war eine überraschend schwierige Herausforderung. Teilweise aufgrund des Erfordernisses, benachbart verbundene Pixel desselben Regionstyps zu haben, aber auch aufgrund der ästhetischen Herausforderung, die Regionen wie eine Karte von Ländern aussehen zu lassen.
Hier ist mein Versuch ... es ist schrecklich ineffizient, scheint aber vernünftige Ergebnisse zu liefern. Fortsetzung des Trends, gemeinsame Eingaben zu Vergleichszwecken zu verwenden:
Parameter: 380 260 233 420 1300 3511 4772 5089 9507 22107 25117 26744
Parameter: 380 260 8 5 6 7 8 4 5 6 7 9 4 6 9 5 8 7 5
Dunkles Zeitalter von Camelot 213 307 1 1 1
Mein größeres Beispiel: (640 480 6 1 7 2 9 3 4 5 6 1 9 8 7 44 3 1 9 4 5 6 7 2 3 4 9 3 4 5 9 8 7 5 6 1 2 1 2 2 6 7 8 9 63 3)
Ein Beispiel mit mehr Ländern: 640 480 6 1 7 2 9 3 4 5 6 1 9 8 7 44 3 1 9 4 5 6 7 2 3 4 9 3 4 5 9 8 7 5 6 1 2 1 2 1 2 6 7 8 9 63 5 33 11 88 2 7 9 5 6 2 5 7
package GenerateRealisticMaps;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import javax.imageio.ImageIO;
public class GenerateRealisticMaps
{
private static final Random rand = new Random(3);
private static final Color[] paletteizedColours = new Color[100];
// create colour palette
static
{
paletteizedColours[0] = new Color(0xFF000000);
for (int i = 1; i < paletteizedColours.length; i++)
{
paletteizedColours[i] = Color.getHSBColor(rand.nextFloat(), rand.nextFloat(), 0.5f + rand.nextFloat() * 0.4f);
}
}
/**
* Represents a pixel that is the boundary of a region
* @author default
*
*/
public static class BoundaryPixel
{
public BoundaryPixel(int x, int y, int otherRegionId)
{
super();
this.x = x;
this.y = y;
this.otherRegionId = otherRegionId;
}
int x;
int y;
int otherRegionId;
}
/**
* Group of adjacent pixels that represent a region (i.e. a country in the map)
* @author default
*
*/
public static class Region
{
static private int masterId = 0;
Region(int desiredSize)
{
this.desiredSize = desiredSize;
id = ++masterId;
}
int desiredSize;
int size = 0;
int id;
List<BoundaryPixel> boundary = new ArrayList<GenerateRealisticMaps.BoundaryPixel>();
}
/**
* Container of regions
* @author default
*
*/
public static class Regions
{
List<Region> regionList = new ArrayList<GenerateRealisticMaps.Region>();
Map<Integer, Region> regionMap = new HashMap<Integer, GenerateRealisticMaps.Region>();
}
public static void main(String[] args) throws IOException
{
int width = Integer.parseInt(args[0]);
int height = Integer.parseInt(args[1]);
int[] s = new int[args.length - 2];
// read in the region weights
int sum = 0;
for (int i = 0; i < args.length - 2; i++)
{
sum += s[i] = Integer.parseInt(args[i + 2]);
}
int totalPixels = width * height;
double multiplier = ((double) totalPixels) / sum;
// convert region weights to pixel counts
int runningCount = 0;
for (int i = 0; i < s.length - 1; i++)
{
runningCount += s[i] = (int) (multiplier * s[i]);
}
s[s.length - 1] = totalPixels - runningCount;
Regions regions = new Regions();
int[][] map = new int[width][height];
// initialise region starting pixels
for (int v : s)
{
Region region = new Region(v);
regions.regionList.add(region);
regions.regionMap.put(region.id, region);
int x;
int y;
do
{
x = rand.nextInt(width);
y = rand.nextInt(height);
} while (map[x][y] != 0);
map[x][y] = region.id;
region.size++;
}
// initialise a "height" map that provides cost to claim a unclaimed region. This allows for more natural shaped countries
int[][] heightMap = new int[width][height];
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
heightMap[i][j] = rand.nextInt(50);
}
}
boolean equal = false;
// main loop
do
{
growRegions(map, heightMap, width, height, regions);
// determine whether regions have reached their desired size
equal = true;
for (Region region : regions.regionList)
{
equal = equal && region.size == region.desiredSize;
}
if (equal)
{
HashMap<Integer, Set<Integer>> commonIsolatedRegions = new HashMap<Integer, Set<Integer>>();
int isolatedRegionId = 0;
int[][] isolatedRegions = new int[width][height];
List<Integer> isolatedRegionSize = new ArrayList<Integer>();
isolatedRegionSize.add(-1); // add dummy entry at index 0 since region ids start at 1
// go though each pixel and attempt to identify an isolated region from that point if it as not
// yet been identified... i.e. an enclosed area.
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if (isolatedRegions[i][j] == 0)
{
isolatedRegionId++;
Point point = new Point(i, j);
int size = identifyEnclosedArea(map, isolatedRegions, width, height, point, isolatedRegionId);
// add this isolated region id to the group of isolated regions associated with the region at this pixel
Set<Integer> isolatedRegionSet = commonIsolatedRegions.get(map[i][j]);
if (isolatedRegionSet == null)
{
isolatedRegionSet = new HashSet<Integer>();
commonIsolatedRegions.put(map[i][j], isolatedRegionSet);
}
isolatedRegionSet.add(isolatedRegionId);
isolatedRegionSize.add(size);
}
}
}
// only keep the largest isolated region in each group. Mark the other members in the group areas as unclaimed.
for (Region region : regions.regionList)
{
Set<Integer> isolatedRegionSet = commonIsolatedRegions.get(region.id);
// find the largest isolatedRegion mapped to this region
int largestIsolatedRegionId = -1;
int largestIsolatedRegionSize = -1;
for (Integer isolatedRegionIdentifier : isolatedRegionSet)
{
if (isolatedRegionSize.get(isolatedRegionIdentifier) > largestIsolatedRegionSize)
{
largestIsolatedRegionSize = isolatedRegionSize.get(isolatedRegionIdentifier);
largestIsolatedRegionId = isolatedRegionIdentifier;
}
}
// remove the largest isolated region (i.e. retain those pixels)
isolatedRegionSet.remove(largestIsolatedRegionId);
if (isolatedRegionSet.size() > 0)
{
equal = false;
// for all remaining isolated regions mapped to this region, convert to unclaimed areas.
for (Integer isolatedRegionIdentifier : isolatedRegionSet)
{
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if (isolatedRegions[i][j] == isolatedRegionIdentifier)
map[i][j] = 0;
}
}
}
}
}
}
} while (!equal);
saveOutputImage("out.final.png", map);
}
/**
* Renders and saves the output image
*
* @param filename
* @param map
* @throws IOException
*/
public static void saveOutputImage(String filename, int[][] map) throws IOException
{
final int scale = 1;
final int width = map.length;
final int height = map[0].length;
BufferedImage image = new BufferedImage(width * scale, height * scale, BufferedImage.TYPE_INT_RGB);
Graphics2D g = (Graphics2D) image.getGraphics();
for (int j = 0; j < height; j++)
{
for (int i = 0; i < width; i++)
{
g.setColor(paletteizedColours[map[i][j]]);
g.fillRect(i * scale, j * scale, scale, scale);
}
}
ImageIO.write(image, "png", new File(filename));
}
/**
* Grows the regions of the world. Firstly by unclaimed cells and then by distributing cells amongst the regions.
*
* @param map
* cell to region map
* @param heightMap
* the "height" cost of unclaimed cells. Used to give more natural shapes.
* @param width
* @param height
* @param regions
*/
public static void growRegions(int[][] map, int[][] heightMap, int width, int height, Regions regions)
{
// reset region sizes
for (Region region : regions.regionList)
{
region.size = 0;
region.boundary.clear();
}
// populate corners with adjacent pixel region id... these pixels cannot ever be "grown" into.
map[0][0] = map[1][0];
map[width - 1][0] = map[width - 1][5];
map[width - 1][height - 1] = map[width - 2][height - 1];
map[0][height - 1] = map[1][height - 1];
int i, x, y, dx = 0, dy = 0, currHeight, currentId = -1, pixelRegionId;
Region currRegion = null;
;
// calculate initial region sizes
for (y = 0; y < height; y++)
{
for (x = 0; x < width; x++)
{
if (map[x][y] > 0)
regions.regionMap.get(map[x][y]).size++;
}
}
// expand regions into surrounding unclaimed pixels.
// construct a list of region boundary pixels in the process.
for (y = 1; y < height - 1; y++)
{
for (x = 1; x < width - 1; x++)
{
int cellId = map[x][y];
if (cellId > 0)
{
if (cellId != currentId)
{
currRegion = regions.regionMap.get(map[x][y]);
currentId = currRegion.id;
}
currHeight = heightMap[x][y]++;
for (i = 0; i < 4; i++)
{
switch (i)
{
case 0:
dx = x - 1;
dy = y;
break;
case 1:
dx = x + 1;
dy = y;
break;
case 2:
dx = x;
dy = y - 1;
break;
case 3:
dx = x;
dy = y + 1;
break;
}
pixelRegionId = map[dx][dy];
switch (pixelRegionId)
{
// unclaimed cell...
case 0:
if (heightMap[dx][dy] < currHeight)
{
map[dx][dy] = currRegion.id;
currRegion.size++;
}
break;
// claimed cell...
default:
if (pixelRegionId != currRegion.id)
{
currRegion.boundary.add(new BoundaryPixel(dx, dy, pixelRegionId));
}
break;
}
}
}
}
}
HashMap<Integer, List<BoundaryPixel>> neighbourBorders = new HashMap<Integer, List<BoundaryPixel>>();
// for all regions...
for (Region region : regions.regionList)
{
// that are less than the desired size...
if (region.size < region.desiredSize)
{
neighbourBorders.clear();
// identify the boundary segment per neighbour of the region
for (BoundaryPixel boundaryPixel : region.boundary)
{
List<BoundaryPixel> neighbourBorderSegment = neighbourBorders.get(boundaryPixel.otherRegionId);
if (neighbourBorderSegment == null)
{
neighbourBorderSegment = new ArrayList<GenerateRealisticMaps.BoundaryPixel>();
neighbourBorders.put(boundaryPixel.otherRegionId, neighbourBorderSegment);
}
neighbourBorderSegment.add(boundaryPixel);
}
out:
// for each neighbour...
for (int id : neighbourBorders.keySet())
{
Region neighbourRegion = regions.regionMap.get(id);
int surplusPixelCount = neighbourRegion.size - neighbourRegion.desiredSize;
// that has surplus pixels...
if (surplusPixelCount > 0)
{
// and convert the border segment pixels to the current region...
List<BoundaryPixel> neighbourBorderSegment = neighbourBorders.get(id);
int index = 0;
while (surplusPixelCount-- > 0 && index < neighbourBorderSegment.size())
{
BoundaryPixel boundaryPixel = neighbourBorderSegment.get(index++);
map[boundaryPixel.x][boundaryPixel.y] = region.id;
region.size++;
regions.regionMap.get(boundaryPixel.otherRegionId).size--;
// until we reach the desired size...
if (region.size == region.desiredSize)
break out;
}
}
}
}
// if region contains more pixels than desired...
else if (region.size > region.desiredSize)
{
// and the region has neighbours
if (region.boundary.size() > 0)
{
// choose a neighbour to off load extra pixels to
Region neighbour = regions.regionMap.get(region.boundary.remove(rand.nextInt(region.boundary.size())).otherRegionId);
ArrayList<BoundaryPixel> adjustedBoundary = new ArrayList<>();
// iterate over the boundary neighbour's boundary pixels...
for (BoundaryPixel boundaryPixel : neighbour.boundary)
{
// and then for those pixels which are of the current region, convert to the neighbour region
if (boundaryPixel.otherRegionId == region.id)
{
map[boundaryPixel.x][boundaryPixel.y] = neighbour.id;
neighbour.size++;
region.size--;
// stop when we reach the region's desired size.
if (region.size == region.desiredSize)
break;
}
else
{
adjustedBoundary.add(boundaryPixel);
}
}
neighbour.boundary = adjustedBoundary;
}
}
}
}
/**
* identifies the area, starting at the given point, in which adjacent pixels are of the same region id.
*
* @param map
* @param isolatedRegionMap
* cells identifying which area that the corresponding map cell belongs
* @param width
* @param height
* @param point
* the starting point of the area to be identified
* @param isolatedRegionId
* the id of the region to assign cells with
* @return the size of the identified area
*/
private static int identifyEnclosedArea(int[][] map, int[][] isolatedRegionMap, int width, int height, Point point, final int isolatedRegionId)
{
ArrayList<Point> stack = new ArrayList<Point>();
final int EXPECTED_REGION_ID = map[point.x][point.y];
stack.add(point);
int size = 0;
while (stack.size() > 0)
{
Point p = stack.remove(stack.size() - 1);
int x = p.x;
int y = p.y;
if (y < 0 || y > height - 1 || x < 0 || x > width - 1 || isolatedRegionMap[x][y] > 0)
continue;
int val = map[x][y];
if (val == EXPECTED_REGION_ID)
{
isolatedRegionMap[x][y] = isolatedRegionId;
size++;
stack.add(new Point(x + 1, y));
stack.add(new Point(x - 1, y));
stack.add(new Point(x, y + 1));
stack.add(new Point(x, y - 1));
}
}
return size;
}
}
Erklärung (aus Kommentaren)
Der Algorithmus ist ziemlich einfach: Initialisieren Sie zunächst die Karte mit zufälligen Gewichten, und wählen Sie zufällige Ausgangspixel für jede der Länderregionen aus. Zweitens "wachsen" Sie jeden Bereich, indem Sie versuchen, nicht beanspruchte benachbarte Pixel zu beanspruchen. Dies tritt auf, wenn das Gewicht des aktuellen Pixels das nicht beanspruchte Gewicht überschreitet.
Jedes Pixel in einer Region erhöht bei jedem Wachstumszyklus sein Gewicht. Wenn eine Region Nachbarn hat und die aktuell betrachtete Region weniger Pixel als gewünscht hat, stiehlt sie außerdem Pixel von ihrem Nachbarn, wenn der Nachbar mehr Pixel als gewünscht hat. Wenn der aktuelle Bereich mehr Pixel als sein Nachbar hat, wählt er zufällig einen Nachbarn aus und gibt diesem Nachbarn alle überzähligen Pixel. Wenn alle Regionen die richtige Größe haben, werden in der dritten Phase alle Regionen identifiziert und konvertiert, die aufgeteilt wurden und nicht mehr kontinuierlich sind.
Es wird nur die größte Aufteilung der Region beibehalten, und die anderen Aufteilungen werden in nicht beanspruchte Pixel umgewandelt, und die zweite Phase beginnt erneut. Dies wiederholt sich, bis alle Pixel in einer Region benachbart sind und alle Regionen die richtige Größe haben.
Diese Herausforderung ist überraschend schwierig. Ich habe mit Pygame einen Kartengenerator in Python geschrieben. Das Programm vergrößert den Farbbereich zu freiem Speicherplatz und erstellt ein Bild, das möglicherweise wie eine Karte aussieht (wenn Sie blinzeln).
Mein Algorithmus vervollständigt nicht immer die Länder, da der verbleibende Bereich möglicherweise nicht genügend Speicherplatz hat, aber ich dachte, dass dies zu einem interessanten Effekt geführt hat, und ich werde keine Zeit mehr darauf verwenden. Die verbliebenen blauen Flecken können als große Seen betrachtet werden, und die blau gesprenkelten Merkmale zwischen den Ländern sind die Flüsse, die die Grenze markieren (es ist ein Merkmal, kein Käfer!).
Um mit dem Super Chafouin zu vergleichen, habe ich deren Parameterbeispiele verwendet.
Parameter: 380 260 233 420 1300 3511 4772 5089 9507 22107 25117 26744
Parameter: 380 260 8 5 6 7 8 4 5 6 7 9 4 6 9 5 8 7 5
Dunkles Zeitalter von Camelot (213 307 1 1 1)
Mein größeres Beispiel: (640 480 6 1 7 2 9 3 4 5 6 1 9 8 7 44 3 1 9 4 5 6 7 2 3 4 9 3 4 5 9 8 7 5 6 1 2 1 2 2 6 7 8 9 63 3)
Dieses Beispiel sieht ein bisschen aus wie Osteuropa?
Ein Beispiel mit mehr Ländern: 640 480 6 1 7 2 9 3 4 5 6 1 9 8 7 44 3 1 9 4 5 6 7 2 3 4 9 3 4 5 9 8 7 5 6 1 2 1 2 1 2 6 7 8 9 63 5 33 11 88 2 7 9 5 6 2 5 7
Mit diesem Beispiel habe ich den Farbgenerator geändert
colors = [(80+ri(100), 80+ri(100), 80+ri(100)) for c in counts], um einen weicheren (und kartenähnlichen) Bereich zu erhalten.Python-Code:
quelle
"any pixel in the region can be reached from any other by staying within the region and only moving orthogonally". Ich sehe isolierte Pixel?Lassen Sie uns faul sein und meine Antwort von dieser Frage anpassen !
Der Algorithmus berechnet ausgehend von der oberen linken Ecke einen "Schlangenpfad", der das gesamte Rechteck ausfüllt. Die Schlange kann nur hoch, runter, links, rechts gehen.
Der Schlangenpfad wird verfolgt und mit der ersten Farbe, dann der zweiten Farbe usw. gefüllt, wobei die Farbprozentsätze berücksichtigt werden
Dieser Algorithmus erzeugt viele gerade Linien. um es zu verbessern, erkenne ich sie und ersetze sie durch "Wellen", die die gleiche Anzahl von Pixeln behalten.
Parameter: 380 260 233 420 1300 3511 4772 5089 9507 22107 25117 26744
Parameter: 380 260 8 5 6 7 8 4 5 6 7 9 4 6 9 5 8 7 5
Dunkles Zeitalter von Camelot (213 307 1 1 1)
Der Code:
quelle