Minikaart

Sissejuhatus

Vaatame, kuidas luua lihtsa 2D-mängu jaoks minikaarti, mis näitab mängijale teed sihtmärgini. Mängija juhib ruudukujulist tegelast, kes saab liikuda ainult ruudustikus. Eesmärk on jõuda kaardil kindlasse punkti, kasutades selleks minikaarti ja sellele joonistatud trajektoori. Kogu projekti koodiga saab tutvuda siin.

Mida teha?

Kõigepealt loome mängija. Selle klassi salvestame ainult x ja y koordinaadid. NB! Need määravad asukoha mängusisesel kaardil, mitte ekraanil, seega võivad need olla täisarvu tüüpi - int.

public class Player {
    public int x, y;
    private ShapeRenderer shape = new ShapeRenderer();

    public Player(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void render(SpriteBatch batch) {
        shape.setProjectionMatrix(batch.getProjectionMatrix());
        shape.begin(ShapeRenderer.ShapeType.Filled);
        shape.setColor(Color.BLUE);
        shape.rect(x * 32, y * 32, 32, 32);
        shape.end();
    }

    public Vector2 getPosition() {
        return new Vector2(x, y);
    }

    public void dispose() {
        shape.dispose();
    }
}

Nüüd loome MapRenderer klassi, kus meie kaart salvestatakse ja renderdatakse. Kaart salvestatakse kahemõõtmelisse massiivi, kus kõigepealt tuleb X-koordinaat ja seejärel Y-koordinaat map[x][y]. Ja väärtus saab olema int arv. Number tähistab lahtri tüüpi. Alustuseks on meil ainult kahte tüüpi lahtrid: 0 - millel saab seista ja 1 - mis on takistus. Kaart genereeritakse juhuslikult.

public class MapRenderer {
    public static final int MAP_WIDTH = 20;
    public static final int MAP_HEIGHT = 15;
    public static final int TILE_SIZE = 32;
    public int[][] map = new int[MAP_WIDTH][MAP_HEIGHT];

    public MapRenderer() {
        generateRandomObstacles();
    }

    private void generateRandomObstacles() {
        for (int x = 0; x < MAP_WIDTH; x++) {
            for (int y = 0; y < MAP_HEIGHT; y++) {
                map[x][y] = Math.random() < 0.2 ? 1 : 0;
            }
        }
    }
}

Nüüd on vaja ainult joonistada kaart. Iga lahter on sama suur kui mängija - 32, ka vabad lahtrid on märgitud helehalliks ja takistused tumehalliks. Lisame abimeetodi - isWalkable(int x, int y), mis ütleb, kas mängija saab koordinaatidel kõndida.

...
private ShapeRenderer shape = new ShapeRenderer();

public boolean isWalkable(int x, int y) {
    return x >= 0 && y >= 0 && x < MAP_WIDTH && y < MAP_HEIGHT && map[x][y] == 0;
}

public void render(SpriteBatch batch) {
    shape.setProjectionMatrix(batch.getProjectionMatrix());
    shape.begin(ShapeRenderer.ShapeType.Filled);
    for (int x = 0; x < MAP_WIDTH; x++) {
        for (int y = 0; y < MAP_HEIGHT; y++) {
            shape.setColor(map[x][y] == 0 ? Color.LIGHT_GRAY : Color.DARK_GRAY);
            shape.rect(x * TILE_SIZE, y * TILE_SIZE, TILE_SIZE, TILE_SIZE);
        }
    }
    shape.end();
}

public void dispose() {
    shape.dispose();
}
...

Lisame mängijale liikumise.

..
public void update(MapRenderer map) {
    if (Gdx.input.isKeyJustPressed(Input.Keys.LEFT) && map.isWalkable(x - 1, y)) x--;
    if (Gdx.input.isKeyJustPressed(Input.Keys.RIGHT) && map.isWalkable(x + 1, y)) x++;
    if (Gdx.input.isKeyJustPressed(Input.Keys.UP) && map.isWalkable(x, y + 1)) y++;
    if (Gdx.input.isKeyJustPressed(Input.Keys.DOWN) && map.isWalkable(x, y - 1)) y--;
}
..

Nüüd lisame MiniMapRendereri. See klass kordab kaardi renderdamist, erinedes ainult selle poolest, et lahtrite suurus on väiksem ja kaart joonistatakse nurka.

public class MiniMapRenderer {
    private MapRenderer map;
    private Player player;
    private ShapeRenderer shape = new ShapeRenderer();

    public MiniMapRenderer(MapRenderer map, Player player) {
        this.map = map;
        this.player = player;
    }

    public void render(SpriteBatch batch) {

        shape.setProjectionMatrix(batch.getProjectionMatrix());
        shape.begin(ShapeRenderer.ShapeType.Filled);

        for (int x = 0; x < map.MAP_WIDTH; x++) {
            for (int y = 0; y < map.MAP_HEIGHT; y++) {
                shape.setColor(map.map[x][y] == 0 ? Color.LIGHT_GRAY : Color.DARK_GRAY);
                shape.rect(x * 4 + 600, y * 4 + 400, 4, 4);
            }
        }
        // render player position
        shape.setColor(Color.BLUE);
        shape.rect(player.x * 4 + 600, player.y * 4 + 400, 4, 4);

        shape.end();
    }

    public void dispose() {
        shape.dispose();
    }
}

A*

Oleme nüüdseks rakendanud kõik kolm mängu jaoks vajalikku komponenti. Nüüd saame neid kasutada teeotsingu algoritmi rakendamiseks. Meie mängus kasutame A* algoritmi.

Algoritm on järgmine - loome prioriteetidega järjekorra (PriorityQueue), kuhu lisame lahtrid, mida saame läbida, ja kahemõõtmelise massiivi visited, mis X ja Y järgi näitab, milliseid lahtreid oleme juba külastanud.

public class PathFinder {
    public static List<Vector2> findPath(MapRenderer map, int startX, int startY, int goalX, int goalY) {
        PriorityQueue<Node> open = new PriorityQueue<>();
        boolean[][] visited = new boolean[MapRenderer.MAP_WIDTH][MapRenderer.MAP_HEIGHT];
    }

    private static double dist(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
}

Loome ka abiklassi Node, kuhu salvestame lahtri koordinaadid, kust me sellesse lahtrisse jõudsime, samuti numbrilised väärtused - g, h, f.

public class Node {
    public int x, y;
    public Node parent;
    public double g, h, f;

    public Node(int x, int y, Node parent, double g, double h) {
        this.x = x;
        this.y = y;
        this.parent = parent;
        this.g = g;
        this.h = h;
        this.f = g + h;
    }
}

Kõik algab koordinaatidelt 0, 0. Mõtleme, kus teha meie esimene samm - selleks arvestame kõiki kõrvalolevaid ruute, mida saab läbida ja mida algoritm pole veel külastanud (ei ole massiivis visited). Nüüd tekib aga küsimus, millisest ligipääsetavast ruudust alustada? Kui me rakendaksime Dijkstra algoritmi, läheksime kõigepealt sellesse lahtrisse, mille teekulu on väiksem, st kui näiteks ühe naabri läbimiseks kulub 1 minut ja teise naabri läbimiseks 3 minutit, alustaksime esimesest naabrist. Aga mis siis, kui ruut, kuhu jõudmiseks kulub 1 minut, asub eesmärgist täpselt vastupidises suunas? Siinkohal tuleb A* algoritm appi! Selle asemel, et võtta arvesse ainult kaugust praegusest asukohast, võtame arvesse ka seda, kui lähedal see ruut on sihtmärgile! Sageli kasutatakse heuristikana Manhattani kaugust. Iga lahtri jaoks arvutame kulu järgmise valemi abil: f = g + n, kus g on kaal ja n on heuristika |startX - goalX| + |startY - goalY|. Nüüd lisame koordinaadid meie prioriteetide järjekorda ja määrame, kuidas PriorityQueue peaks lahtreid võrdlema.

    ...
    PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));

    Node start = new Node(startX, startY, null, 0, dist(startX, startY, goalX, goalY));
    open.add(start);

    while (!open.isEmpty()) {
        Node current = open.poll();

        visited[current.x][current.y] = true;

        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if ((dx == 0 && dy == 0) || (Math.abs(dx) + Math.abs(dy) != 1)) continue;
                int nx = current.x + dx;
                int ny = current.y + dy;
                if (!map.isWalkable(nx, ny) || visited[nx][ny]) continue;

                double g = current.g + 1;
                double h = dist(nx, ny, goalX, goalY);
                open.add(new Node(nx, ny, current, g, h));
            }
        }
    }
}

private static double dist(int x1, int y1, int x2, int y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

Nüüd lisame uue kontrolli - kui praeguse sõlme koordinaadid langevad kokku eesmärkide koordinaatidega, tagastame leitud tee. Selleks peame minema kogu tee tagasi, sihtpunktist alguspunktini, teeme seda Node'i parent-välja abil.

...
while (!open.isEmpty()) {
    Node current = open.poll();

    if (current.x == goalX && current.y == goalY) {
        List<Vector2> path = new ArrayList<>();
        while (!(current.x == startX && current.y == startY)) {
            path.add(0, new Vector2(current.x, current.y));
            current = current.parent;
        }
        return path;
    }
...

Nüüd on vaja vaid lisada teekonna trajektoor minikartile. Kõigepealt lisame MiniMapRendererile meetodi update(), millega uuendame teekonda sihtmärgini.

Olulised punktid, esiteks, ressursside säästmiseks arvutame raja ainult siis, kui mängija on eelmisest kohast liikunud. Selleks salvestame kasutaja viimased koordinaadid.

Teiseks arvutame tee uuesti ainult siis, kui mängija on arvutatud teelt lahkunud. See aitab vabaneda ka „tõmblemisest“, sest isegi kui mängija järgiks rada, arvutaks algoritm raja uuesti ja see võib erineda algsest. Selleks salvestame raja ja mängija liikumise korral kontrollime, kas mängija on liikunud mööda antud teed, ja kui mitte, siis arvutame raja uuesti.

public MiniMapRenderer(MapRenderer map, Player player) {
    this.map = map;
    this.player = player;
    lastPlayerPosition = player.getPosition();
    path = PathFinder.findPath(map, (int) lastPlayerPosition.x, (int) lastPlayerPosition.y, (int) goal.x, (int) goal.y);
}

public void update() {
    Vector2 currentPosition = player.getPosition();
    if (!currentPosition.equals(lastPlayerPosition)) {
        if (!path.isEmpty()) {
            Vector2 nextStep = path.removeFirst();
            if (!currentPosition.equals(nextStep)) {
                path = PathFinder.findPath(map, (int) currentPosition.x, (int) currentPosition.y, (int) goal.x, (int) goal.y);
            }
        }
        lastPlayerPosition = currentPosition;
    }
}

Nüüd tuleb vaid panna rada minikaardile peale ja nautida tulemust!

public void render(SpriteBatch batch) {
    shape.setProjectionMatrix(batch.getProjectionMatrix());
    shape.begin(ShapeRenderer.ShapeType.Filled);

    for (int x = 0; x < map.MAP_WIDTH; x++) {
        for (int y = 0; y < map.MAP_HEIGHT; y++) {
            shape.setColor(map.map[x][y] == 0 ? Color.LIGHT_GRAY : Color.DARK_GRAY);
            shape.rect(x * 4 + 600, y * 4 + 400, 4, 4);
        }
    }
    // render path to the goal
    for (Vector2 point : path) {
        shape.setColor(Color.YELLOW);
        shape.rect(point.x * 4 + 600, point.y * 4 + 400, 4, 4);
    }
    // render goal position
    shape.setColor(Color.GREEN);
    shape.rect(goal.x * 4 + 600, goal.y * 4 + 400, 4, 4);

    // render player position
    shape.setColor(Color.BLUE);
    shape.rect(player.x * 4 + 600, player.y * 4 + 400, 4, 4);

    shape.end();
}