Elegantes Autotiling

Ich suche nach Informationen darüber, wie Leute Autotiling in ihren kachelbasierten Spielen implementieren. Bisher habe ich es immer mit einer Reihe von hartcodierten "if ... else ..." - Aussagen improvisiert, und jetzt habe ich beschlossen, dass es Zeit ist, eine elegantere Lösung zu finden. Ich habe im Internet nach Beispielen für Autotiling-Implementierungen und Diskussionen zu diesem Thema gesucht, aber nur drei Artikel gefunden:

• http://www.codeproject.com/Articles/106884/Implementing-Auto-tiling-Functionality-in-a-Tile-M
• http://blog.rpgmakerweb.com/tutorials/anatomy-of-an-autotile
• http://web.archive.org/web/20130927193449/http://www.squidi.net/mapmaker/musings/m091016.php

(Besonders der letzte ist umfassend und sehr hilfreich.)

Ich habe mir auch verschiedene Implementierungen und Dokumentationen von Bibliotheken angesehen, die diese implementieren, zum Beispiel flixel: http://www.flixel.org/features.html#tilemaps

Leider sind alle Lösungen, die ich finden konnte, genauso improvisiert und willkürlich wie das, womit ich angefangen habe, und decken fast nie alle möglichen Fälle ab.

Ich suche nach einem eleganten Beispiel für die Implementierung von Autotiling, von dem ich lernen kann.

Ich habe eine bitweise Methode zum Anwenden von Tilemaps verwendet und festgestellt, dass dies eine sehr elegante Lösung ist. Der Artikel enthält ein konkretes Beispiel und erläutert, wie der Algorithmus auf mehrere Geländetypen erweitert werden kann.

Ich bin hierher gekommen, indem ich dieses Problem selbst gegoogelt, die verlinkten Artikel gelesen und eine relativ kompakte Lösung erstellt habe, die den gemeinsamen Satz von 47 Kacheln generiert. Für das automatisch gekachelte Material ist ein 2x3-Kachelsatz erforderlich:

Mit einer Einzelkachelvariante oben links, inneren Ecken oben rechts und vier äußeren Eckkacheln unten (Sie können diese Anordnung von RPG Maker erkennen).

Der Trick besteht darin, jede "logische" Kartenkachel zum Rendern in 4 Halbkacheln zu unterteilen. Darüber hinaus kann sich eine halbe Kachel im Kachelsatz nur in dieser Position in einer generierten Kachel befinden, sodass eine obere linke halbe Kachel nur in einer Position oben links verwendet werden kann.

Diese Einschränkungen bedeuten, dass Sie nur 3 Vollkachelnachbarn pro Halbkachel anstelle aller 8 benachbarten Kacheln überprüfen müssen.

Ich habe diese Idee schnell umgesetzt, um sie zu testen. Hier ist der Proof-of-Concept-Code (TypeScript):

//const dirs = { N: 1, E: 2, S: 4, W:8, NE: 16, SE: 32, SW: 64, NW: 128 };
const edges = { A: 1+8+128, B: 1+2+16, C: 4+8+64, D: 4+2+32 };
const mapA = { 0:8, 128:8, 1:16, 8:10, 9:2, 137:18, 136:10, 129:16 };
const mapB = { 0:11, 16:11, 1:19, 2:9, 3:3, 19:17, 18:9, 17:19 };
const mapC = { 0:20, 64:20, 4:12, 8:22, 12:6, 76:14, 72:22, 68:12 };
const mapD = { 0:23, 32:23, 4:15, 2:21, 6:7, 38:13, 34:21, 36:15 };

export function GenerateAutotileMap(_map: number[][], _tile: integer): number[][]
{
    var result = [];
    for (var y=0; y < _map.length; y++) {
        const row = _map[y];
        const Y = y*2;
        // half-tiles
        result[Y] = [];
        result[Y+1] = [];
        // each row
        for (var x=0; x < row.length; x++) {
            // get the tile
            const t = row[x];
            const X = x*2;
            if (t != _tile) continue;
            // Check nearby tile materials.
            const neighbors = (North(_map, x, y) == t? 1:0)
                + (East(_map, x, y) == t? 2:0)
                + (South(_map, x, y) == t? 4:0)
                + (West(_map, x, y) == t? 8:0)
                + (NorthEast(_map, x, y) == t? 16:0)
                + (SouthEast(_map, x, y) == t? 32:0)
                + (SouthWest(_map, x, y) == t? 64:0)
                + (NorthWest(_map, x, y) == t? 128:0);
            // Isolated tile
            if (neighbors == 0) {
                result[Y][X] = 0;
                result[Y][X+1] = 1;
                result[Y+1][X] = 4;
                result[Y+1][X+1] = 5;
                continue;
            }
            // Find half-tiles.
            result[Y][X] = mapA[neighbors & edges.A];
            result[Y][X+1] = mapB[neighbors & edges.B];
            result[Y+1][X] = mapC[neighbors & edges.C];
            result[Y+1][X+1] = mapD[neighbors & edges.D];
        }
    }
    return result;
}    

Erläuterung:

• Aist der obere linke Teil der Kachel, Bist der obere rechte Teil, Cist der untere linke Teil, Dist der untere rechte Teil.
• edges enthält Bitmasken für jede dieser Informationen, sodass wir nur die relevanten Nachbarinformationen abrufen können.
• map* sind Wörterbücher, die Nachbarzustände grafischen Indizes im Kachelsatzbild (0..24) zuordnen.
  • Da jede halbe Kachel 3 Nachbarn prüft, hat jede 2 ^ 3 = 8 Zustände.
• _tile ist die Kachel, die für das Autotiling bestimmt ist.
• Da unsere logischen Kacheln doppelt so groß sind wie unsere Rendering-Kacheln, müssen alle Autotile-Koordinaten (x, y) in der Rendering-Map verdoppelt werden.

Wie auch immer, hier sind die Ergebnisse (jedenfalls mit nur einer Kachel):

Ich habe die meisten Links gelesen und einige Zeit damit verbracht, eine andere Lösung zu finden. Ich weiß nicht, ob es gut ist oder nicht, aber um das automatische Kachelverhalten von RPG Maker VX Ace (47 Kacheln) zu simulieren, habe ich Folgendes begonnen:

(links 0 oder 1) + (rechts 0 oder 1) + (oben 0 oder 1) + (unten 0 oder 1) Jetzt habe ich 5 Fälle.

wenn 4 = Plättchen 46 wird platziert

wenn 3 Boarder =

wenn 2 4 Fälle + 2 Fälle nicht sicher über Algorithmus, aber nicht viele Verzweigungen zu machen.

wenn 1 = daran arbeiten, aber jede Richtung kann in 4 Fällen enden

Wenn 0 = Ich kann den in den Links mit 1, 2, 4, 8 gezeigten Zahlenalgorithmus verwenden und die ID von 1 bis 15 erhalten. Ich kann ihn direkt verwenden.

Ich bin kein Programmierer und nicht der Beste mit mathematischen Algorithmen und der 1, 2, 4, 8, 16, 32, 64, 128-Lösung, die mir auch nicht besonders gut gefallen hat.

Vielleicht ist mein Ansatz zumindest besser.