001/*
002The MIT License(MIT)
003Copyright(c) mxgmn 2016.
004
005Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
006
007The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
008
009The software is provided "as is", without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the software.
010*/
011package squidpony.squidgrid;
012
013import squidpony.squidmath.*;
014
015import java.util.Arrays;
016
017/**
018 * Similar to MimicFill, this class can be used to imitate the style of an existing piece of data, but this works on
019 * more than just booleans; it can produce similar styles of texture (its original use in SynTex), of map, of item
020 * placement, and so on by specifying a different technique for differentiating two int values.
021 * <br>
022 * Two options are now available; the process() method allows the slow analyze() step to be computed once,
023 * before the rest of processing is potentially done many times, but the new neoProcess() method produces
024 * comparable or better results and is drastically faster even without needing analysis. This means
025 * neoProcess(), based on P.F. Harrison's algorithm in SynTex, is strongly recommended now.
026 * <br>
027 * Example results of neoProcess(), with a procedural dungeon first and the mimic versions after it:
028 * https://gist.github.com/tommyettinger/405336fb0fc74838d806c021aabe77da (you may need to click Raw and zoom
029 * out somewhat for it to render well).
030 * <br>
031 * Ported from https://github.com/mxgmn/SynTex by Tommy Ettinger on 6/9/2016.
032 */
033public class DetailedMimic {
034
035    /**
036     * Constructor that uses an unseeded RNG and, without any instruction otherwise, assumes the ints this is asked to
037     * compare are colors in RGBA8888 format. You can specify your own implementation of the AestheticDifference
038     * interface (one function) and pass it to other constructors, as well.
039     */
040    public DetailedMimic()
041    {
042        this(AestheticDifference.rgba8888);
043    }
044
045    /**
046     * Constructor that uses an unseeded RNG (effectively a random seed) and the given AestheticDifference. An example
047     * piece of code that implements an AestheticDifference is available in the docs for
048     * {@link AestheticDifference#difference(int, int)}; it is also considered a functional interface if you use Java 8
049     * or newer. You can also use the ready-made implementation {@link AestheticDifference#rgba8888} if you have int
050     * data that represents RGBA8888 colors, which can be obtained from libGDX Colors or SColors in the display module.
051     * @param diff an implementation of the AestheticDifference interface, such as {@link AestheticDifference#rgba8888};
052     *             may be null, but that forces all calls to processing methods to treat discrete as true
053     */
054    public DetailedMimic(AestheticDifference diff)
055    {
056        this(diff, new GWTRNG());
057    }
058
059    /**
060     * Constructor that uses the given RNG and the given AestheticDifference. An example
061     * piece of code that implements an AestheticDifference is available in the docs for
062     * {@link AestheticDifference#difference(int, int)}; it is also considered a functional interface if you use Java 8
063     * or newer. You can also use the ready-made implementation {@link AestheticDifference#rgba8888} if you have int
064     * data that represents RGBA8888 colors, which can be obtained from libGDX Colors or SColors in the display module.
065     * @param diff an implementation of the AestheticDifference interface, such as {@link AestheticDifference#rgba8888};
066     *             may be null, but that forces all calls to processing methods to treat discrete as true
067     * @param rng an IRNG, such as an RNG, to generate random factors; may be seeded to produce reliable output
068     */
069    public DetailedMimic(AestheticDifference diff, IRNG rng)
070    {
071        random = rng;
072        difference = diff;
073        analyzed = null;
074    }
075
076    /**
077     * DISCOURAGED; use {@link #neoProcess(int[], int, int, int, int, int, int, boolean)} instead, which doesn't need a
078     * separate analysis step.
079     * Analyzes a sample as a 1D int array and stores the needed info to call
080     * {@link #process(int[], int, int, int, int, int, int, double, boolean)} any number of times later on without
081     * recalculating some heavy-weight information.
082     * @param sample a 1D array of ints that can be compared by the AestheticDifference this uses (or any ints if
083     *               discrete is true)
084     * @param width the width of the area in sample this should use (sample can be interpreted as different shapes)
085     * @param height the height of the area in sample this should use (sample can be interpreted as different shapes)
086     * @param detailLevel how much detail to try for; if 0 or less this does nothing, 2 works well in general
087     * @param proximity how far away to consider cells as affecting another; 3 works well
088     * @param discrete false if this can produce ints other than those in the input; true if it uses a fixed set
089     */
090    public void analyze(int[] sample, int width, int height, int detailLevel, int proximity, boolean discrete)
091    {
092        discrete |= (difference == null);
093        if(detailLevel > 0)
094            analysis(sample, width, height, detailLevel, proximity, discrete);
095    }
096    /**
097     * DISCOURAGED; use {@link #neoProcess(int[], int, int, int, int, int, int, boolean)} instead, which doesn't need a
098     * separate analysis step.
099     * Processes a sample as a 1D int array and returns a different 1D int array that mimics the input. If the last time
100     * this was called used the same sample, sampleWidth, and sampleHeight parameters, or if
101     * {@link #analyze(int[], int, int, int, int, boolean)} was called with its width equal to sampleWidth and its
102     * height equal to sampleHeight, then this doesn't need to perform as many expensive calculations.
103     * @param sample a 1D array of ints that can be compared by the AestheticDifference this uses (or any ints if
104     *               discrete is true)
105     * @param sampleWidth the width of the area in sample this should use (sample can be interpreted as different shapes)
106     * @param sampleHeight the height of the area in sample this should use (sample can be interpreted as different shapes)
107     * @param targetWidth the desired width of the output
108     * @param targetHeight the desired height of the output
109     * @param detailLevel how much detail to try for; if 0 or less this doesn't perform analysis and has somewhat lower
110     *                    quality, but 2 works well in general
111     * @param proximity how far away to consider cells as affecting another; 3 works well
112     * @param temperature a level of unpredictability in the output relative to the input; must be greater than 0
113     * @param discrete false if this can produce ints other than those in the input; true if it uses a fixed set
114     * @return a new 1D int array that can be interpreted as having targetWidth and targetHeight, and mimics sample
115     */
116    public int[] process(int[] sample, int sampleWidth, int sampleHeight, int targetWidth, int targetHeight,
117                         int detailLevel, int proximity, double temperature, boolean discrete)
118    {
119        discrete |= (difference == null);
120        if(detailLevel > 0)
121        {
122            if(analyzed == null || analyzed.length != sampleWidth || analyzed.length == 0 ||
123                    analyzed[0].length != sampleHeight)
124                analyze(sample, sampleWidth, sampleHeight, detailLevel, proximity, discrete);
125            return coherentSynthesis(sample, sampleWidth, sampleHeight, analyzed, proximity,
126                    targetWidth, targetHeight, temperature, discrete);
127        }
128        else {
129            return fullSynthesis(sample, sampleWidth, sampleHeight, proximity,
130                    targetWidth, targetHeight, temperature, discrete);
131        }
132    }
133
134    /**
135     * Processes a 1D int array representing 2D storage of values that can be compared by this object's
136     * AestheticDifference (or any values if that is null or discrete is true), and returns a 1D array representing data
137     * with potentially different dimensions but similar appearance to sample.
138     * @param sample a 1D array of ints that can be compared by the AestheticDifference this uses (or any ints if
139     *               discrete is true)
140     * @param sampleWidth the width of the area in sample this should use (sample can be interpreted as different shapes)
141     * @param sampleHeight the height of the area in sample this should use (sample can be interpreted as different shapes)
142     * @param targetWidth the desired width of the output
143     * @param targetHeight the desired height of the output
144     * @param detailLevel how much detail to try for; here this will always be treated as at least 1
145     * @param proximity how far away to consider cells as affecting another; 3 works well
146     * @param discrete false if this can produce ints other than those in the input; true if it uses a fixed set
147     * @return a new 1D int array that can be interpreted as having targetWidth and targetHeight, and mimics sample
148     */
149    public int[] neoProcess(int[] sample, int sampleWidth, int sampleHeight, int targetWidth, int targetHeight,
150                         int detailLevel, int proximity, boolean discrete)
151    {
152            return reSynthesis(sample, sampleWidth, sampleHeight, proximity, 20,
153                    Math.max(1, detailLevel), discrete || (difference == null), targetWidth, targetHeight);
154    }
155
156    public IRNG random;
157    public AestheticDifference difference;
158    private int[][] analyzed;
159
160    private void analysis(int[] bitmap, int width, int height, int K, int N, boolean indexed)
161    {
162        int area = width * height;
163        analyzed = new int[area][];
164        OrderedSet<Integer> points = new OrderedSet<>(area);
165        for (int i = 0; i < area; i++) points.add(i);
166
167        double[] similarities = new double[area * area];
168        for (int i = 0; i < area; i++) for (int j = 0; j < area; j++)
169            similarities[i * area + j] = similarities[j * area + i] != 0 ? similarities[j * area + i] :
170                    similarity(i, bitmap, width, height, j, bitmap, width, height, N, null, indexed);
171
172        for (int i = 0; i < area; i++)
173        {
174            analyzed[i] = new int[K];
175            OrderedSet<Integer> copy = new OrderedSet<>(points);
176
177            analyzed[i][0] = i;
178            copy.remove(i);
179
180            for (int k = 1; k < K; k++)
181            {
182                double max = -10000;
183                int argmax = -1;
184
185                for(Integer p : copy)
186                {
187                    double s = similarities[i * area + p];
188                    if (s > max)
189                    {
190                        max = s;
191                        argmax = p;
192                    }
193                }
194
195                analyzed[i][k] = argmax;
196                copy.remove(argmax);
197            }
198        }
199    }
200
201    private int[] coherentSynthesis(int[] sample, int SW, int SH, int[][] sets, int N, int OW, int OH, double t, boolean indexed)
202    {
203        int[] result = new int[OW * OH];
204        Integer[] origins = new Integer[OW * OH];
205        GreasedRegion mask = new GreasedRegion(SW, SH);
206
207        for (int i = 0; i < OW * OH; i++)
208        {
209            int x = i % OW, y = i / OW;
210            IntDoubleOrderedMap candidates = new IntDoubleOrderedMap();
211            mask.clear();
212
213            for (int dy = -1; dy <= 1; dy++){
214                for (int dx = -1; dx <= 1; dx++)
215                {
216                    int sx = (x + dx + OW) % OW, sy = (y + dy + OH) % OH;
217                    Integer origin = origins[sy * OW + sx];
218                    if ((dx != 0 || dy != 0) && origin != null)
219                    {
220                        for (int pi = 0, p; pi < sets[origin].length; pi++)
221                        {
222                            p = sets[origin][pi];
223                            int ox = (p % SW - dx + SW) % SW, oy = (p / SW - dy + SH) % SH;
224                            double s = similarity(oy * SW + ox, sample, SW, SH, i, result, OW, OH, N, origins, indexed);
225
226                            if (!mask.contains(ox, oy)) candidates.put(ox + oy * SW, Math.pow(100, s / t));
227                            mask.insert(ox, oy);
228                        }
229                    }
230                }
231            }
232
233            int shifted = candidates.isEmpty() ? random.nextInt(SW) + random.nextInt(SH) * SW : weightedRandom(candidates, random.nextDouble());
234            origins[i] = shifted;
235            result[i] = sample[shifted];
236        }
237
238        return result;
239    }
240
241    private int[] fullSynthesis(int[] sample, int SW, int SH, int N, int OW, int OH, double t, boolean indexed)
242    {
243        int[] result = new int[OW * OH];
244        Integer[] origins = new Integer[OW * OH];
245
246        if (!indexed) for (int y = 0; y < OH; y++) {
247            for (int x = 0; x < OW; x++){
248                if (y + N >= OH)
249                {
250                    result[x + y * OW] = sample[random.nextInt(SW * SH)];
251                    origins[x + y * OW] = -1;
252                }
253            }
254        }
255
256        for (int i = 0; i < OW * OH; i++)
257        {
258            double[] candidates = new double[SW * SH];
259            double max = -10000;
260            int argmax = -1;
261
262            for (int j = 0; j < SW * SH; j++)
263            {
264                double s = similarity(j, sample, SW, SH, i, result, OW, OH, N, origins, indexed);
265                if (s > max)
266                {
267                    max = s;
268                    argmax = j;
269                }
270
271                if (indexed) candidates[j] = Math.pow(100.0, s / t);
272            }
273
274            if (indexed) argmax = weightedRandom(candidates, random.nextDouble());
275            result[i] = sample[argmax];
276            origins[i] = -1;
277        }
278
279        return result;
280    }
281
282
283    private int[] reSynthesis(int[] sample, int SW, int SH, int N, int M, int polish, boolean indexed, int OW, int OH)
284    {
285        IntVLA colors = new IntVLA();
286        int[] indexedSample = new int[Math.min(SW * SH, sample.length)];
287        for (int j = 0; j < indexedSample.length; j++)
288        {
289            int color = sample[j];
290
291            int i = 0;
292            for (int cn = 0; cn < colors.size; cn++)
293            {
294                if(colors.get(cn) == color) break;
295                i++;
296            }
297
298            if (i == colors.size) colors.add(color);
299            indexedSample[j] = i;
300        }
301
302        int colorsNumber = colors.size;
303
304        double[][] colorMetric = null;
305        if (!indexed && colorsNumber <= 1024)
306        {
307            colorMetric = new double[colorsNumber][colorsNumber];
308            for (int x = 0; x < colorsNumber; x++)
309            {
310                for (int y = 0; y < colorsNumber; y++)
311                {
312                    int cx = colors.get(x), cy = colors.get(y);
313                    colorMetric[x][y] = difference.difference(cx, cy);
314                }
315            }
316        }
317
318        int[] origins = new int[OW * OH];
319        Arrays.fill(origins, -1);
320
321        int[] shuffle = new int[OW * OH];
322        for (int i = 0; i < shuffle.length; i++)
323        {
324            int j = random.nextInt(i + 1);
325            if (j != i) shuffle[i] = shuffle[j];
326            shuffle[j] = i;
327        }
328
329        for (int round = 0; round <= polish; round++) for (int counter = 0; counter < shuffle.length; counter++)
330        {
331            int f = shuffle[counter];
332            int fx = f % OW, fy = f / OW;
333            int neighborsNumber = round > 0 ? 8 : Math.min(8, counter);
334            int neighborsFound = 0;
335
336            int[] candidates = new int[neighborsNumber + M];
337
338            if (neighborsNumber > 0)
339            {
340                int[] neighbors = new int[neighborsNumber];
341                int[] x = new int[4], y = new int[4];
342
343                for (int radius = 1; neighborsFound < neighborsNumber; radius++)
344                {
345                    x[0] = fx - radius;
346                    y[0] = fy - radius;
347                    x[1] = fx - radius;
348                    y[1] = fy + radius;
349                    x[2] = fx + radius;
350                    y[2] = fy + radius;
351                    x[3] = fx + radius;
352                    y[3] = fy - radius;
353
354                    for (int k = 0; k < 2 * radius; k++)
355                    {
356                        for (int d = 0; d < 4; d++)
357                        {
358                            x[d] = (x[d] + 10 * OW) % OW;
359                            y[d] = (y[d] + 10 * OH) % OH;
360
361                            if (neighborsFound >= neighborsNumber) continue;
362                            int point = x[d] + y[d] * OW;
363                            if (origins[point] != -1)
364                            {
365                                neighbors[neighborsFound] = point;
366                                neighborsFound++;
367                            }
368                        }
369
370                        y[0]++;
371                        x[1]++;
372                        y[2]--;
373                        x[3]--;
374                    }
375                }
376
377
378                for (int n = 0; n < neighborsNumber; n++)
379                {
380                    int cx = (origins[neighbors[n]] + (f - neighbors[n]) % OW + 100 * SW) % SW;
381                    int cy = (origins[neighbors[n]] / SW + f / OW - neighbors[n] / OW + 100 * SH) % SH;
382                    candidates[n] = cx + cy * SW;
383                }
384            }
385
386            for (int m = 0; m < M; m++) candidates[neighborsNumber + m] = random.nextInt(SW * SH);
387
388            double max = -1E+10;
389            int argmax = -1;
390
391            for (int c = 0; c < candidates.length; c++)
392            {
393                double sum = random.nextDouble(0.000001);
394                int ix = candidates[c] % SW, iy = candidates[c] / SW, jx = f % OW, jy = f / OW;
395                int SX, SY, FX, FY, S, F;
396                int origin;
397
398                for (int dy = -N; dy <= N; dy++)
399                {
400                    for (int dx = -N; dx <= N; dx++)
401                    {
402                        if (dx != 0 || dy != 0)
403                        {
404                            SX = ix + dx;
405                            if (SX < 0) SX += SW;
406                            else if (SX >= SW) SX -= SW;
407
408                            SY = iy + dy;
409                            if (SY < 0) SY += SH;
410                            else if (SY >= SH) SY -= SH;
411
412                            FX = jx + dx;
413                            if (FX < 0) FX += OW;
414                            else if (FX >= OW) FX -= OW;
415
416                            FY = jy + dy;
417                            if (FY < 0) FY += OH;
418                            else if (FY >= OH) FY -= OH;
419
420                            S = SX + SY * SW;
421                            F = FX + FY * OW;
422
423                            origin = origins[F];
424                            if (origin != -1)
425                            {
426                                if (indexed) sum += sample[origin] == sample[S] ? 1 : -1;
427                                else if (colorMetric != null) sum += colorMetric[indexedSample[origin]][indexedSample[S]];
428                                else sum += difference.difference(sample[origin], sample[S]);
429                            }
430                        }
431                    }
432                }
433
434                if (sum >= max)
435                {
436                    max = sum;
437                    argmax = candidates[c];
438                }
439            }
440
441            origins[f] = argmax;
442        }
443
444        int[] result = new int[OW * OH];
445        for (int i = 0; i < result.length; i++) result[i] = sample[origins[i]];
446        return result;
447    }
448
449    private double similarity(int i1, int[] b1, int w1, int h1, int i2, int[] b2, int w2, int h2, int N, Integer[] origins, boolean indexed)
450    {
451        double sum = 0;
452        int x1 = i1 % w1, y1 = i1 / w1, x2 = i2 % w2, y2 = i2 / w2;
453
454        for (int dy = -N; dy <= 0; dy++) for (int dx = -N; (dy < 0 && dx <= N) || (dy == 0 && dx < 0); dx++)
455        {
456            int sx1 = (x1 + dx + w1) % w1, sy1 = (y1 + dy + h1) % h1;
457            int sx2 = (x2 + dx + w2) % w2, sy2 = (y2 + dy + h2) % h2;
458
459            int c1 = b1[sx1 + sy1 * w1];
460            int c2 = b2[sx2 + sy2 * w2];
461
462            if (origins == null || origins[sy2 * w2 + sx2] != null)
463            {
464                if (indexed)
465                    sum += c1 == c2 ? 1 : -1;
466                else
467                    sum -= difference.difference(c1, c2);
468                    /*
469                    Color C1 = Color.FromArgb(c1), C2 = Color.FromArgb(c2);
470                    sum -= (double)((C1.R - C2.R) * (C1.R - C2.R) + (C1.G - C2.G) * (C1.G - C2.G) + (C1.B - C2.B) * (C1.B - C2.B)) / 65536.0;
471                    */
472            }
473        }
474
475        return sum;
476    }
477
478    static int weightedRandom(double[] array, double r)
479    {
480        double sum = 0;
481        for (int j = 0; j < array.length; j++)
482            sum += Math.max(1.0, array[j]);
483
484        for (int j = 0; j < array.length; j++)
485            array[j] /= sum;
486
487        int i = 0;
488        double x = 0;
489
490        while (i < array.length)
491        {
492            x += array[i];
493            if (r <= x) return i;
494            i++;
495        }
496
497        return 0;
498    }
499
500    static int weightedRandom(IntDoubleOrderedMap dic, double r) {
501//        int[] ints = dic.keySet().toIntArray();
502//        double[] doubles =  dic.values().toDoubleArray();
503        double sum = 0;
504        final int sz = dic.size();
505        for (int j = 0; j < sz; j++)
506            sum += Math.max(1.0, dic.getAt(j));
507
508        int i = 0;
509        double x = 0;
510
511        while (i < sz)
512        {
513            x += dic.getAt(i) / sz;
514            if (r <= x) return dic.keyAt(i);
515            i++;
516        }
517        return dic.firstKey();
518    }
519
520    /**
521     * Utility method to produce 1D int arrays this can process when discrete is true or difference is null.
522     * @param map a 2D char array
523     * @return an int array that can be used as a sample
524     */
525    public static int[] convertCharToInt(char[][] map)
526    {
527        int w = map.length, h = map[0].length;
528        int[] result = new int[w * h];
529        for (int x = 0; x < w; x++) {
530            for (int y = 0; y < h; y++) {
531                result[x * h + y] = map[x][y];
532            }
533        }
534        return result;
535    }
536
537    /**
538     * Utility method that takes a 1D int array that represents chars (such as a sample produced by
539     * {@link #convertCharToInt(char[][])} or, more likely, the result of processing such a sample with this class) and
540     * returns a 2D char array with the requested width and height (which should match the targetWidth and targetHeight
541     * given during processing).
542     * @param arr a 1D int array that represents char values
543     * @param w the width that arr can be interpreted as; should probably match the targetWidth given in processing
544     * @param h the height that arr can be interpreted as; should probably match the targetHeight given in processing
545     * @return a 2D char array with the given width and height, probably filled with the data from arr
546     */
547    public static char[][] convertIntToChar(int[] arr, int w, int h)
548    {
549        char[][] result = new char[w][h];
550        if(arr == null)
551            return result;
552        for (int x = 0; x < w; x++) {
553            for (int y = 0; y < h; y++) {
554                if(x * h + y >= arr.length)
555                    return result;
556                result[x][y] = (char) arr[x * h + y];
557            }
558        }
559        return result;
560    }
561}