Pixel distribution algorithm

Question

Pixel distribution algorithm

Navigation

#1 by (7 votes)
#2 by (6 votes)

5

Well, lately I've been thinking about algorithms for creating random maps / maps and I've got a question that I'll post here for you to elucidate.

Suppose I have green and yellow pixels. I'm not working with array, but rather a one-dimensional vector on account of the project.

Could anyone quote me an algorithm sketch or where to begin to distribute the pixels grouped each time I run the program, but what is not always the same result, that creates shapes with those green and yellow pixels? / p>

c++ imagem jogos

asked by anonymous 04.11.2016 / 17:03

2 answers

7

As I have already commented, there are a multitude of suggestions that can be made. But unfortunately you have not given feedback on your problem, so there is no way to suggest something more appropriate. Patience.

Your current answer (which you have already accepted, incidentally) has a possible suggestion that works well. But, as you yourself noted in the comments, working with data as a single one-dimensional vector also has its difficulties. So I suggested that you work with the image in the traditional (ie, two-dimensional) format and only then transform the data into the one-dimensional format you need (you know why, since you do not describe it). This approach will give you the edge to work with a variety of different algorithms and, most importantly, reuse ready code out there.

Finally, here is a simple implementation of the suggestion using the region growth algorithm I commented earlier. The explanation is documented in the code.

#include <cstdlib>
#include <iostream>
#include <ctime>
#include <algorithm>
#include "image.h"

// ------------------------------
// Remova se não usar OpenCV
// ------------------------------
#include <opencv2\opencv.hpp>
using namespace cv;
// ------------------------------

/**
 * Função de geração de um número inteiro aleatório entre um intervalo dado.
 * @param min Inteiro com o mímimo número esperado.
 * @param max Inteiro com o máximo número esperado.
 * @return Inteiro com o valor sorteado.
 */
int random(int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while(x >= RAND_MAX - remainder);
    return min + x % n;
}

/**
 * Gera um mapa de regiões aleatórias.
 * @param colors Vetor de Pixels com as cores possívels
 * para as regiões.
 * @param width Inteiro positivo com o largura da imagem gerada.
 * @param width Inteiro positivo com o altura da imagem gerada.
 * @param iterations Inteiro positivo com o número de interações para
 * o agrupamento de pixels sob a imagem inicialmente aleatória. O default
 * é 100 mil. Se esse valor for 0, nenhuma permutação é realizada e a imagem
 * do mapa resultante contém apenas ruído.
 * @param window Inteiro positivo com o tamanho da janela de comparação para
 * o agrupamento. Essa janela tem que ser um número cuja raíz quadrada resulta
 * em um inteiro ímpar (9, 25, 49, 81, etc) de valor mínimo 9.
 * @return Objeto Image com a imagem gerada.
 */
Image genMap(vector<Pixel> colors, uint width, uint height, uint iterations = 100000, uint window = 9)
{
    // Checa os parâmetros de entrada
    double windowRoot = std::sqrt(window);
    if(windowRoot < 3 || (windowRoot - int(windowRoot)) != 0 || int(windowRoot) % 2 == 0)
        throw std::invalid_argument("tamanho de janela invalido");

    // Usa o horário atual como semente para o gerador de números aleatórios
    std::srand((uint)std::time(0));

    // ++++++++++++++++++++++++++++++++++++++
    // 1 - Cria o mapa totalmente em preto
    // ++++++++++++++++++++++++++++++++++++++
    Image map(width, height);

    // ++++++++++++++++++++++++++++++++++++++
    // 2 - Sorteia aleatoriamente os pixels nas cores recebidas
    // ++++++++++++++++++++++++++++++++++++++
    for(uint x = 0; x < width; x++)
    {
        for(uint y = 0; y < height; y++)
        {
            uint c = random(0, colors.size()-1);
            map.pixel(x, y) = colors[c];
        }
    }

    // ++++++++++++++++++++++++++++++++++++++
    // 3 - Agrupa os pixels aleatoriamente, para formar as regiões  
    // ++++++++++++++++++++++++++++++++++++++
    uint offset = int(std::ceil(windowRoot) / 2);
    for(uint i = 0; i < iterations; i++)
    {
        // Sorteia um pixel qualquer na imagem
        int xCenter = random(0, width-1);
        int yCenter = random(0, height-1);
        Pixel color = map.pixel(xCenter, yCenter);

        // Conta quantos são os pixels vizinhos que são iguais
        // ao pixel "central" sorteado
        int count = 0;
        for(uint x = xCenter - offset; x <= xCenter + offset; x++)
        {
            for(uint y = yCenter - offset; y <= yCenter + offset; y++)
            {
                // Desconsidera pixels fora da área da imagem
                if(x < 0 || x >= width || y < 0 || y >= height)
                    continue;

                // Incrementa se for a mesma cor
                if(map.pixel(x, y) == color)
                    count++;
            }
        }

        // Se mais da metade da janela é da mesma cor do pixel central,
        // transforma todos os vizinhos na cor do pixel central
        if(count > int(window / 2))
        {
            for(uint x = xCenter - offset; x <= xCenter + offset; x++)
            {
                for(uint y = yCenter - offset; y <= yCenter + offset; y++)
                {
                    // Desconsidera pixels fora da área da imagem
                    if(x < 0 || x >= width || y < 0 || y >= height)
                        continue;

                    // Define a cor
                    map.pixel(x, y) = color;
                }
            }
        }
    }

    // ++++++++++++++++++++++++++++++++++++++
    // Pronto! Só devolve a imagem gerada. :)
    // ++++++++++++++++++++++++++++++++++++++
    return map;
}

// ------------------------------
// Remova se não usar OpenCV
// ------------------------------
void showImage(char *title, Mat image)
{
    namedWindow(title, cv::WINDOW_AUTOSIZE);
    imshow(title, image);
}
// ------------------------------

/**
 * Converte a imagem (bidimensional) para um longo vetor de
 * valores (unidimensional).
 * @return Vetor de com todos os valores dos pixels (na ordem
 * R, G, B) agrupados linha após linha.
 */
vector<uchar> imageToVector(const Image &image)
{
    vector<uchar> ret;
    for(uint y = 0; y < image.height(); y++)
    {
        for(uint x = 0; x < image.width(); x++)
        {
            Pixel p = image.pixel(x, y);
            ret.push_back(p.red);
            ret.push_back(p.green);
            ret.push_back(p.blue);
        }
    }
    return ret;
}

/**
 * Converte um longo vetor de valores (unidimensional) para uma
 * imagem (bidimensional).
 * @param data Vetor com todos os valores dos pixels (na ordem
 * R, G, B) agrupados linha após linha.
 * @param width Inteiro positivo com a largura da imagem.
 * @param height Inteiro positivo com a altura da imagem.
 */
Image vectorToImage(vector<uchar> data, uint width, uint height)
{
    if(data.size() != (width * height * 3))
        throw std::invalid_argument("os dados e as dimensoes recebidos não são condizentes com uma imagem em 3 canais");

    Image ret(width, height);
    for(uint i = 0; i < data.size(); i += 3)
    {
        int x = (i / 3) % width;
        int y = (i / 3) / width;
        ret.pixel(x, y) = Pixel(data[i], data[i + 1], data[i + 2]);
    }

    return ret;
}

/**
 * Função principal.
 */
int main()
{
    Pixel amarelo(255, 255, 0);
    Pixel verde(0, 255, 0);

    Image t1 = genMap({ amarelo, verde }, 400, 300, 0);
    Image t2 = genMap({ amarelo, verde }, 400, 300, 100000);
    Image t3 = genMap({ amarelo, verde }, 400, 300, 100000, 25);
    Image t4 = genMap({ amarelo, verde }, 400, 300, 500000, 25);

    cout << "Teste 1: " << endl;
    cout << t1 << endl << endl;

    cout << "Teste 2: " << endl;
    cout << t2 << endl << endl;

    cout << "Teste 3: " << endl;
    cout << t3 << endl << endl;

    cout << "Teste 4: " << endl;
    cout << t4 << endl << endl;

    // ------------------------------
    // Remova se não usar OpenCV
    // ------------------------------
    showImage("Teste 1 - Aleatoria", t1.toMat());
    showImage("Teste 2 - Janela: 9 e Iteracoes: 100 mil", t2.toMat());
    showImage("Teste 3 - Janela: 25 e Iteracoes: 100 mil", t3.toMat());
    showImage("Teste 4 - Janela: 25 e Iteracoes: 500 mil", t4.toMat());
    waitKey(0);
    // ------------------------------

    cout << endl << "Teste de Conversao" << endl;
    Image t = genMap({ amarelo, verde }, 4, 10, 0);

    cout << "Imagem bidimensional original: " << endl;
    cout << t << endl << endl; 

    cout << "Convertida para vetor unidimensional: " << endl;
    vector<uchar> v = imageToVector(t);
    for(uint i = 0; i < v.size(); i++)
        cout << int(v[i]) << " ";
    cout << endl << endl;

    cout << "Convetida de volta para imagem bidimensional: " << endl;
    cout << vectorToImage(v, 4, 10) << endl;

    return 0;
}

It generates the following text output:

Teste 1:
Largura: 400 Altura: 300
Pixels:
[(255,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(255,255,0),(255,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(255,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(0,255,0),(0,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(0,255,0),(255,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0),(255,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
mais 290 linhas...


Teste 2:
Largura: 400 Altura: 300
Pixels:
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(0,255,0),(0,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
mais 290 linhas...


Teste 3:
Largura: 400 Altura: 300
Pixels:
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0),(255,255,0), mais 390 colunas...]
mais 290 linhas...


Teste 4:
Largura: 400 Altura: 300
Pixels:
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
[(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0),(0,255,0), mais 390 colunas...]
mais 290 linhas...



Teste de Conversao
Imagem bidimensional original:
Largura: 4 Altura: 10
Pixels:
[(0,255,0),(0,255,0),(255,255,0),(255,255,0)]
[(255,255,0),(0,255,0),(0,255,0),(0,255,0)]
[(255,255,0),(255,255,0),(0,255,0),(0,255,0)]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0)]
[(255,255,0),(0,255,0),(0,255,0),(255,255,0)]
[(0,255,0),(255,255,0),(0,255,0),(0,255,0)]
[(0,255,0),(255,255,0),(0,255,0),(255,255,0)]
[(0,255,0),(255,255,0),(255,255,0),(255,255,0)]
[(0,255,0),(255,255,0),(0,255,0),(255,255,0)]
[(255,255,0),(255,255,0),(255,255,0),(0,255,0)]


Convertida para vetor unidimensional:
0 255 0 0 255 0 255 255 0 255 255 0 255 255 0 0 255 0 0 255 0 0 255 0 255 255 0 255 255 0 0 255 0 0 255 0 255 255 0 255 255 0 255 255 0 255 255 0 255 255 0 0 255 0 0 255 0 255 255 0 0 255 0 255 255 0 0 255 0 0 255 0 0 255 0 255 255 0 0 255 0 255 255 0 0 255 0 255 255 0 255 255 0 255 255 0 0 255 0 255 255 0 0 255 0 255 255 0 255 255 0 255 255 0 255 255 0 0 255 0

Convetida de volta para imagem bidimensional:
Largura: 4 Altura: 10
Pixels:
[(0,255,0),(0,255,0),(255,255,0),(255,255,0)]
[(255,255,0),(0,255,0),(0,255,0),(0,255,0)]
[(255,255,0),(255,255,0),(0,255,0),(0,255,0)]
[(255,255,0),(255,255,0),(255,255,0),(255,255,0)]
[(255,255,0),(0,255,0),(0,255,0),(255,255,0)]
[(0,255,0),(255,255,0),(0,255,0),(0,255,0)]
[(0,255,0),(255,255,0),(0,255,0),(255,255,0)]
[(0,255,0),(255,255,0),(255,255,0),(255,255,0)]
[(0,255,0),(255,255,0),(0,255,0),(255,255,0)]
[(255,255,0),(255,255,0),(255,255,0),(0,255,0)]

And it also generates the following graphic output (dependent on OpenCV - do not use if you have not installed it):

Quickly,howthiscodeworks:

Itcreatesanimage(atwo-dimensionalvectorofpixels,with3channelssinceyouspeakofcolors-couldbeachannelonlyforgrayscaleimages)andsetsthepixelsrandomlyaccordingtothegivencolors(testimage1).

Then,itgroupsthepixelsintoasortofiterativeregiongrowth:itdrawsapixelandchecksthecolorsoftheneighborhood(accordingtoapredefinedwindow);iftheneighborshaveenoughofthecolorofthedrawnpixel,italtersthe

neighborhood

neighborhoodforthatcolor,

Repeatstep2foranewinteraction.

Thus,itshouldbepossibletoseethatthenumberofinteractionsandthesizeofthewindowinfluencetheresult.However,manyinteractionsmakeprocessingnaturallytakelonger.Itisimportanttofindanappropriatebalanceforyourneeds.

IhaveimplementedtwohelperclassescalledImageandPixeltoallowyoutorunthiscodegenerically(withoutOpenCV,whichIonlyusetodisplaytheimagesbecausetheyarecool!).Butthisimplementationisrathercrudeandsimple.Ifyoucan,useanotherframeworkdirectly(suchas%OpenCV%,whichalreadyimplementsaseriesofalgorithmsthatyoucouldusetomanipulateandgeneratemoreinterestingstructures).

Ifyouhavethedataoriginallyinaone-dimensionalvector,convertittoatwo-dimensionalstructure,usethatalgorithmandthenconvertitbacktoone-dimensional.

Finally,twoadditionalinformation:

Ifyourneedinvolvescontentgeneration(aterrainforagame,perhaps?),therearemanyotherapproachesthatmaybeuseful.  Inthiscase,I'dalsoliketotakealookatthis my other answer   about Procedural Content Generation .



If the real need behind the idea of the one-dimensional vector is something related to image serialization, there are better ways of   do that. In many cases native to even the implementation of   library you are going to use. In OpenCV, for example, you have   direct access to attribute Mat of class data if you need, in addition to   that there are various suggestions out of how to do it.

The full code (including helper classes Mat and Image ) is in Github .

EDIT : I had also commented on other possibilities, including use of Automata Celulares . To see a good functional example cool that can be useful in map generation, I suggest playing com this implementation in JavaScript of the famous cellular automaton called Game of Life .

18.11.2016 / 19:24

XML serialization - NFC e-element [closed] Question and answer with if and else in Java

score 6 · Accepted Answer

Do you want something like the one below? Click the blue button to run.

function agrupar(antes) {
    var depois = "";
    for (var i = 0; i < antes.length; i++) {
        var a = i === 0 ? "A" : antes.charAt(i - 1);
        var b = antes.charAt(i);
        var c = i === antes.length - 1 ? "A" : antes.charAt(i + 1);
        var m = (a === "V" ? 1 : 0) + (b === "V" ? 1 : 0) + (c === "V" ? 1 : 0);
        depois += m >= 2 ? "V" : "A";
    }
    return depois;
}

var cores = "VA";

var resultado = "";
for (var i = 0; i < 50; i++) {
    resultado += cores.charAt(Math.floor(Math.random() * cores.length));
}

$("#antes").html(resultado);
resultado = agrupar(resultado);
$("#depois1").html(resultado);
resultado = agrupar(resultado);
$("#depois2").html(resultado);
resultado = agrupar(resultado);
$("#depois3").html(resultado);

#antes, #depois1, #depois2, #depois3 {
  font-family: monospace;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table>
    <tr><td>Original ranômico:</td><td id='antes'></td></tr>
    <tr><td>Agrupando 1:</td><td id='depois1'></td></tr>
    <tr><td>Agrupando 2:</td><td id='depois2'></td></tr>
    <tr><td>Agrupando 3:</td><td id='depois3'></td></tr>
</table>