Come rilevare gli sprite in un SpriteSheet?

Dopo un po 'di navigazione, ho creato la mia soluzione alcuni mesi prima, ma non l'ho pubblicata qui nell'interesse di qualcuno che vorrebbe fare lo stesso. Pertanto, descriverò rapidamente il metodo prima di mostrare il codice. È in Kotlin, ma se hai familiarità con Java e / o AS3 dovresti essere in grado di capire la sintassi.

Il metodo

1. Scansiona l'intera immagine e memorizza ogni colore in una tabella.
2. Determina quale colore si presenta più spesso- questo è il colore di sfondo
3. Inizia in alto a sinistra e scansiona ogni riga.
4. Se un pixel non non corrisponde al colore di sfondo, allora è uno sprite.
5. Utilizza un algoritmo di backtracking per "compilare" l'intero sprite.
6. Crea un rettangolo fuori da questo grafico.
7. Memorizzalo e taglia lo sprite fuori dall'immagine.
8. Ripeti 4-7 fino al termine.

Il codice

L'origine è disponibile su github , ed ecco il codice senza documentazione o importazioni.

 fun unpack(spriteSheet: Path): List<Image> {
    Preconditions.checkArgument(Files.exists(spriteSheet),
                                "The file ${spriteSheet.getFileName()} does not exist")

    logger.debug("Loading sprite sheet.")
    // TODO: Convert to png so we have an alpha layer to work with
    val spriteSheetImage = readImage(spriteSheet).toBufferedImage()

    logger.debug("Determining most probable background color.")
    val backgroundColor  = determineProbableBackgroundColor(spriteSheetImage)
    logger.debug("The most probable background color is $backgroundColor")

    return findSprites(spriteSheetImage, backgroundColor) map(::copySubImage.bindFirst(spriteSheetImage))
}

private fun findSprites(image: BufferedImage,
                        backgroundColor: Color): List<Rectangle> {
    val workingImage = copy(image)

    val spriteRectangles = ArrayList<Rectangle>()
    for (pixel in workingImage) {
        val (point, color) = pixel

        if (color != backgroundColor) {
            logger.debug("Found a sprite starting at (${point.x}, ${point.y})")
            val spritePlot = findContiguous(workingImage, point) { it != backgroundColor }
            val spriteRectangle = Rectangle(spritePlot, image)

            logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}")

            spriteRectangles.add(spriteRectangle)
            eraseSprite(workingImage, backgroundColor, spritePlot)
        }
    }

    logger.info("Found ${spriteRectangles.size()} sprites.")
    return spriteRectangles
}

private fun findContiguous(image: BufferedImage, point: Point, predicate: (Color) -> Boolean): List<Point> {
    val unvisited = LinkedList<Point>()
    val visited   = HashSet<Point>()

    unvisited.addAll(neighbors(point, image) filter { predicate(Color(image.getRGB(it.x, it.y))) })

    while (unvisited.isNotEmpty()) {
        val currentPoint = unvisited.pop()
        val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y))

        if (predicate(currentColor)) {
            unvisited.addAll(neighbors(currentPoint, image) filter {
                !visited.contains(it) && !unvisited.contains(it) &&
                predicate(Color(image.getRGB(it.x, it.y)))
            })

            visited.add(currentPoint)
        }
    }

    return visited.toList()
}

private fun neighbors(point: Point, image: Image): List<Point> {
    val points = ArrayList<Point>()

    if (point.x > 0)
        points.add(Point(point.x - 1, point.y))
     if (point.x < image.getWidth(null) - 1)
     points.add(Point(point.x + 1, point.y))

     if (point.y > 0)
     points.add(Point(point.x, point.y - 1))
     if (point.y < image.getHeight(null) - 1)
     points.add(Point(point.x, point.y + 1))

     return points
 }

Tuttavia, il codice non è ancora completo - la confezione e la creazione del metafile sono mancanti - ed è rimasta languida nel mio Github da marzo, ma spero di completarla un giorno.

Ho implementato un algoritmo di rilevamento sprite molto veloce e decente ma diverso da sopra e ... superiore in velocità e precisione (10 secondi su I7 vs ~ istante su una bitmap 2048 * 2048).

a causa del modo in cui funzionava la struttura del rettangolo VB standard, dovevo eseguire il rollover. la ragione è la loro destra = sinistra + larghezza. Ne avevo bisogno in modo che Left potesse essere uguale a Right. Nel mio caso per un singolo pixel a (0, 0) {Sinistra = 0, Destra = 0, Superiore = 0, Inferiore = 0, Larghezza = 1, Altezza = 1}. Tuttavia per quello standard questo avrebbe ritenuto il rettangolo "vuoto".

Innanzitutto se estrai un JPG, lo sfondo ha un po 'di rumore, quindi devi usare un algoritmo di tolleranza del colore per determinare se un pixel è di sfondo o altro.

Questo algoritmo presuppone che gli sprite siano casualmente sopra il foglio e abbiano uno sfondo attorno ad essi in modo tale che un rettangolo possa racchiudere singoli sprite senza sovrapposizioni di altri sprite. Tuttavia, NON FUNZIONERÀ ad esempio se il foglio ha sprite che sono 32 * 32 e sono imballati 32 * 32 senza spazi vuoti.

1) Permetti all'utente di fare clic su un pixel ritenuto lo sfondo (In fase di test ho appena ipotizzato che pixel a (0, 0) fosse lo sfondo). I fogli di sprite ben confezionati possono avere meno pixel di sfondo rispetto ad altri colori e anche in questo caso il rumore JPG si distorcerà se si cerca il colore più frequente come indicato sopra.

2) Una volta deciso il colore di sfondo e scelta una tolleranza (per esempio 32), prendere un clone del foglio sprite e scorrere su ogni pixel UNA VOLTA. Imposta i valori dei pixel su 0 se rispettano la tolleranza del colore di sfondo altrimenti ... 1. Ora finisci con un clone con 0 e 1 che sarà MOLTO più facile (e più veloce) da trattare di seguito.

3) Ora iterate su ciascun pixel del clone modificato una volta. Dall'alto al basso, da sinistra a destra, l'ordine non è molto importante ora.

4) Quando colpisci un pixel non di sfondo (es. 1) usa un algoritmo di riempimento a pieno per cancellare i pixel a 0. Ho usato uno personalizzato che è stato molto veloce e mi ha offerto un controllo esatto. Anche il riempimento personalizzato (importante) mi ha permesso di restituire il rettangolo di delimitazione dell'operazione di riempimento.

5) Il rettangolo di delimitazione di ogni riempimento è aggiunto a un elenco di rettangoli.

6) Alla fine della scansione di ogni pixel si dovrebbe avere un elenco di rettangoli. Su un file .PNG di prova con 63 sprite l'algoritmo originale aveva > 10.000 rettangoli che poi dovevano essere uniti. Il fill-flood aveva ... "drum roll" 88.

7) L'elenco dei rettangoli sarà vicino ma potrebbe avere "orfani". Analizza tutto come un algoritmo di ordinamento in modo da confrontare ogni elemento con tutti gli altri. Se intersecano, si uniscono (unione) in modo che 2 rettangoli diventino 1. (per unire prendo il rettangolo in basso nell'elenco e lo metto al posto del 2 ° che ho confrontato. Il primo è modificato e il conteggio delle liste è decrementato di 1 Ora ... se toccano, vengono nuovamente uniti SOLO se soddisfano la condizione di area massima.

1) La tolleranza del colore 2) Il rettangolo unisce le dimensioni massime. Quando 2 rettangoli si intersecano, vengono sempre uniti (unione), tuttavia quando 2 rettangoli sono uno accanto all'altro senza spazi vuoti di pixel, vengono uniti solo se la loro area interna è < qualche taglio. In questo modo i piccoli orfani vengono uniti a rettangoli più grandi ma i rettangoli più grandi non vengono uniti. 3) Riempimento, ha un'opzione. Quando itera alla ricerca del prossimo pixel, guarda in alto, a destra, in basso, a sinistra. Tuttavia, se lo si desidera, può anche guardare le diagonali.

NOTA ... Per verificare se 2 rettangoli sono uno accanto all'altro usa il codice sottostante con expand = 1.

Public Function IntersectsWith(rectb As strRect, expand As Integer) As Boolean
    If isEmpty Or rectb.isEmpty Then Return False

    If Not (m_top - expand <= rectb.m_bottom + expand) Then Return False

    If Not (m_bottom + expand >= rectb.m_top - expand) Then Return False

    If Not (m_left - expand <= rectb.m_right + expand) Then Return False

    If Not (m_right + expand >= rectb.m_left - expand) Then Return False

    Return True
End Function 

Bit di codice che imposta i pixel cloni su 1 o 0: -

    m_bmp = DirectCast(p_bmp.Clone(), Bitmap)

    Dim lock As BitmapData = BMPLock(m_bmp)

    Dim dword_bgcolor As Integer = bgcolor.ToArgb

    ' first smash the copied bitmap into either BG or non bg so can search exact

    For i As Integer = 0 To lock.Width * lock.Height - 1
        If BMPColorsAreSimilar(BMPGetPixelFastDWORD(lock, i), dword_bgcolor, tol) > 0 Then  ' bg
            BMPSetPixelFast(lock, i, 0)
        Else
            BMPSetPixelFast(lock, i, 1)
        End If
    Next

Ciclo principale che trova i pixel da riempire: -

    Dim rect As strRect
    Dim temp_stack As New Stack ' fill algo uses this... passing it means not allocated every call

    For y As Integer = 0 To lock.Height - 1
        For x As Integer = 0 To lock.Width - 1
            If BMPGetPixelFastDWORD(lock, x, y) = 1 Then ' hit a sprite so erase it with flood fill to get the bounds
                BMPFloodFill(lock, temp_stack, filldiag, x, y, 0)
                rect.SetBounds(BMPFloodFillLastMinX(), BMPFloodFillLastMaxX(), BMPFloodFillLastMinY, BMPFloodFillLastMaxY)
                m_bounds.Add(rect) ' add to our list of rectangles
            End If
        Next
    Next

Spero che questo aiuti chiunque. Algoritmo molto divertente.

Il mio codice per il riempimento flood è sotto ... È in C ++ gestito e chiamato tramite VB.NET. Usa una pila di coordinate per tornare indietro quando cerchi nuovi percorsi di pixel piuttosto che essere ricorsivi. Non ho idea se altre persone compiano riempimenti di inondazioni come questo ... ma è veloce e preciso e, a differenza di quelli in scatola, funziona su una superficie bloccata a 32 bit e offre il controllo completo.

int fill_dx[] = { 0, -1, 0, 1, -1, -1, 1, 1 };
int fill_dy[] = { -1, 0, 1, 0, -1, 1, -1, 1 };

int fill_minx;
int fill_miny;
int fill_maxx;
int fill_maxy;

BYTE *fill_track = 0;
DWORD fill_track_size = 0;

Int32  MCUMakerSupport::MCUBitmap::BMPFloodFill(BitmapData ^%bmp_lock,  Stack ^%mCods, Int32 diag, Int32 x, Int32 y, Int32 col)
{
    diag = diag ? 8 : 4;

    if (!bmp_lock)
    {
        return 0;
    }

    int w = bmp_lock->Width;
    int h = bmp_lock->Height;

    if (x < 0 || x >= w || y < 0 || y >= h) return 0;

refill:

    if (!fill_track)
    {
        fill_track = (BYTE *)malloc(w * h);
        fill_track_size = w * h;
    }
    else
    {
        if (fill_track_size < w * h)
        {
            free(fill_track);
            fill_track = 0;
            fill_track_size = 0;
            goto refill;
        }

    }

    if (!fill_track)
    {
        fill_track_size = 0;
        return 0;
    }

    memset(fill_track, 0, w * h);

    //BitmapData ^bmp_lock = bmp->LockBits(Rectangle(0, 0, w, h), ImageLockMode::ReadWrite, bmp->PixelFormat);


    DWORD *fill_addr = (DWORD *)bmp_lock->Scan0.ToPointer();

    DWORD fill_color = col;
    DWORD target_color = fill_addr[y * w + x];

    //Stack ^mCods = gcnew Stack();

    Point pt;

    pt.X = x;
    pt.Y = y;

    mCods->Clear();

    int filled = 1;

    fill_minx = fill_maxx = x;
    fill_miny = fill_maxy = y;

    fill_addr[pt.Y * w + pt.X] = fill_color;
    fill_track[pt.Y * w + pt.X] = 255;
    mCods->Push(pt);

    while (mCods->Count > 0)
    {
    recheck:

        for (int i = 0; i < diag; i++)
        {
            int cx = pt.X + fill_dx[i];

            if (cx < 0 || cx >= w) continue;

            int cy = pt.Y + fill_dy[i];

            if (cy < 0 || cy >= h) continue;

            bool res = false;

            if (!fill_track[cy * w + cx])
            {
                fill_track[cy * w + cx]++;

                DWORD c = fill_addr[cy * w + cx];

                if (c == target_color)
                {
                    res = true;
                    fill_addr[cx + cy * w] = fill_color;

                    if (cx < fill_minx) { fill_minx = cx; }
                    if (cy < fill_miny) { fill_miny = cy; }

                    if (cx > fill_maxx) { fill_maxx = cx; }
                    if (cy > fill_maxy) { fill_maxy = cy; }
                }
            }

            if (res) // fill?
            {
                mCods->Push(pt);
                filled++;
                pt.Y = cy;
                pt.X = cx;
                goto recheck;
            }
        }

        pt.X = ((Point ^)mCods->Peek())->X;
        pt.Y = ((Point ^)mCods->Peek())->Y;
        mCods->Pop();
    }

    mCods->Clear();

    return filled;    // number of pixels filled
}