2
\$\begingroup\$

Bukkit/CraftBukkit/Spigot are Minecraft server extenders that allow for creating and using plugins. A particular type of plugin is a generator, which creates the game world. Generators operate chunk-by-chunk, where a chunk is a 16x16x256 area of blocks. First, the generator creates the terrain of the chunk. Then, the generator populates the chunk with extra "stuff." A generator can have any number of populators.

The "problem" with populators is that they may attempt to populate outside of the bounds of the current chunk, so in another chunk. If the other chunk does not yet exist, the generator will then attempt to generate and populate that chunk, and so on until the server crashes from locked threads waiting for all of the neighboring chunks.

My solution is to create a "SafeBlockPopulator" that doesn't attempt population until it is certain that all neighboring chunks exist. It uses a SQLite database to keep track of all of the chunks it has seen, and only actually attempts to populate a given chunk until all neighboring chunks within a given radius exist in the database.

package com.michaelbmorris.generator;

import java.io.File;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

import org.bukkit.Chunk;
import org.bukkit.World;
import org.bukkit.generator.BlockPopulator;

/**
 * Populates a chunk once all surrounding chunks within a radius are generated.
 */
public abstract class SafeBlockPopulator extends BlockPopulator {
    private static final HashSet<String> DatabaseUrls = new HashSet<String>();
    private static final int DEFAULT_RADIUS = 1;

    /*
     * Statuses
     */

    private static final int STATUS_GENERATED = 0;
    private static final int STATUS_POPULATED = 1;

    /*
     * SQL
     */

    private static final String CREATE_TABLE = "CREATE TABLE IF NOT EXISTS chunkCoordinate (x INTEGER NOT NULL, z INTEGER NOT NULL, status INTEGER NOT NULL, PRIMARY KEY (x, z));";
    private static final String DELETE_GENERATED_CHUNKS = "DELETE FROM chunkCoordinate WHERE status = " + STATUS_GENERATED + ";";
    private static final String GET_CHUNK = "SELECT * FROM chunkCoordinate WHERE x = ? AND z = ?;";
    private static final String GET_GENERATED_CHUNKS = "SELECT * FROM chunkCoordinate WHERE status = " + STATUS_GENERATED + ";";
    private static final String INSERT_CHUNK = "INSERT INTO chunkCoordinate (x, z, status) VALUES (?, ?, 0);";
    private static final String RESET_CHUNK = "UPDATE chunkCoordinate SET status = " + STATUS_GENERATED + " WHERE x = ? AND z = ?;";
    private static final String SET_CHUNK_POPULATED = "UPDATE chunkCoordinate SET status = " + STATUS_POPULATED + " WHERE x = ? AND z = ?;";

    private static ResultSet getGeneratedChunks(Connection connection) throws SQLException {
        PreparedStatement getGeneratedChunks = connection.prepareStatement(GET_GENERATED_CHUNKS);
        return getGeneratedChunks.executeQuery();
    }

    private static void insertOrResetChunk(int x, int z, Connection connection) throws SQLException {
        PreparedStatement getChunk = connection.prepareStatement(GET_CHUNK);
        getChunk.setInt(1, x);
        getChunk.setInt(2, z);
        ResultSet chunk = getChunk.executeQuery();

        if (!chunk.next()) {
            PreparedStatement insertChunk = connection.prepareStatement(INSERT_CHUNK);
            insertChunk.setInt(1, x);
            insertChunk.setInt(2, z);
            insertChunk.executeUpdate();
        } else {
            PreparedStatement resetChunk = connection.prepareStatement(RESET_CHUNK);
            resetChunk.setInt(1, x);
            resetChunk.setInt(2, z);
            resetChunk.executeUpdate();
        }
    }

    private final HashMap<String, Chunk> chunks;
    private final int radius;
    private final String databaseUrl;

    /**
     * Creates a SafeBlockPopulator with the default radius of 1.
     */
    protected SafeBlockPopulator(String databaseUrl, boolean isNew) {
        this(databaseUrl, isNew, DEFAULT_RADIUS);
    }

    /**
     * Creates a SafeBlockPopulator with a specified radius.
     */
    protected SafeBlockPopulator(String databaseUrl, boolean isNew, int radius) {
        if (databaseUrl == null || databaseUrl.isEmpty()) {
            throw new IllegalArgumentException("Inheriting block populator must supply a URL for the SQLite database.");
        }

        if (DatabaseUrls.contains(databaseUrl)) {
            throw new IllegalArgumentException("Each populator must have a unique database URL.");
        }

        if (radius < 1) {
            throw new IllegalArgumentException("The radius must be at least 1.");
        }

        DatabaseUrls.add(databaseUrl);
        this.radius = radius;
        this.databaseUrl = "jdbc:sqlite:" + databaseUrl;


        if (isNew) {
            File database = new File(databaseUrl);
            database.delete();
        }

        try (Connection connection = DriverManager.getConnection(this.databaseUrl)) {
            Statement statement = connection.createStatement();
            statement.execute(CREATE_TABLE);
            statement.executeUpdate(DELETE_GENERATED_CHUNKS);
        } catch (SQLException e) {
            System.out.println(e.getMessage());
        }

        chunks = new HashMap<String, Chunk>();
    }

    @Override
    public final void populate(World world, Random random, Chunk chunk) {
        int x = chunk.getX();
        int z = chunk.getZ();
        chunks.put(x + " " + z, chunk);

        try (Connection connection = DriverManager.getConnection(databaseUrl)) {
            insertOrResetChunk(x, z, connection);
            attemptPopulate(world, random, connection);
        } catch (SQLException e) {
            System.out.println(e.getMessage());
        }
    }

    private void attemptPopulate(World world, Random random, Connection connection) throws SQLException {
        ResultSet unpopulatedChunks = getGeneratedChunks(connection);
        PreparedStatement setChunkPopulated = connection.prepareStatement(SET_CHUNK_POPULATED);

        while (unpopulatedChunks.next()) {
            if (unpopulatedChunks.getInt("status") == STATUS_GENERATED) {
                int chunkX = unpopulatedChunks.getInt("x");
                int chunkZ = unpopulatedChunks.getInt("z");

                if (hasSurrounding(connection, chunkX, chunkZ)) {
                    Chunk chunk;
                    String key = chunkX + " " + chunkZ;

                    if (chunks.containsKey(key)) {
                        chunk = chunks.get(key);
                        chunks.remove(key);
                    } else {
                        chunk = world.getChunkAt(chunkX, chunkZ);
                    }

                    actuallyPopulate(world, random, chunk);
                    setChunkPopulated.setInt(1, unpopulatedChunks.getInt("x"));
                    setChunkPopulated.setInt(2, unpopulatedChunks.getInt("z"));
                    setChunkPopulated.executeUpdate();
                }
            }
        }
    }

    private boolean hasSurrounding(Connection connection, int x, int z) throws SQLException {
        PreparedStatement getChunk = connection.prepareStatement(GET_CHUNK);
        ResultSet resultSet;

        for (int i = 0 - radius; i <= radius; i++) {
            for (int j = 0 - radius; j <= radius; j++) {
                getChunk.setInt(1, x + i);
                getChunk.setInt(2, z + j);
                resultSet = getChunk.executeQuery();

                if (!resultSet.next()) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * Actually populates this chunk once all surrounding chunks within the radius
     * are generated.
     */
    protected abstract void actuallyPopulate(World world, Random random, Chunk chunk);
}

This obviously causes somewhat reduced performance. The database interactions are costly compared to keeping track of the data in memory, but persistence is required for when the server restarts. Theoretically, it would be nice to load all the data from the database on startup and save it all back on shutdown, but there's no guarantee that the server will be shutdown correctly. I do have to keep the chunks themselves in memory because there's another bug in the server that causes chunks to be "forgotten" if they are generated but not populated for a while. That's why I delete all generated but not populated chunks from the database on startup; the server consistently sends all of them through again.

Larger radii decrease performance as well, but it's up to the author of the inheriting class to determine how much room their populator implementation needs.

Is there any way to optimize/reduce my database calls while still ensuring that all data is persisted immediately? In particular, I'm looking at the hasSurrounding() method that makes (2 * radius + 1)^2 amount of database calls. Are there any other improvements I could make?

\$\endgroup\$
1
\$\begingroup\$

Your algorithm by example: In your method hasSurrounding(), you are executing a query for each point. If for example you have current x=100 and current z=1000 and surrounding=10, you are examining every point between x=90 to 109 and z=990 to 1009. That makes 10*10 = 100 queries. If one of these points do not exists, you immediately return false.

You can do that in one query, given example values above:

SELECT * FROM chunkCoordinate WHERE x >= 90 AND x < 110 AND z >= 990 and z < 1009

But because you do not need to know which point(s) does not exist, you can just count the number of points. If one is missing, you would receive 99 instead of 100 results. That leads to high performance since the database does not need to fetch the data for the point, but just needs to check if it exists, by using its buffered index tables (primary keys).

Changed code:

private boolean hasSurrounding(Connection connection, int x, int z) throws SQLException {
    String CHECK_SURROUNDING = "SELECT COUNT(*) FROM chunkCoordinate WHERE x >= ? AND x < ? AND z >= ? and z < ?;";
    PreparedStatement getChunkCount = connection.prepareStatement(CHECK_SURROUNDING);
    getChunkCount.setInt(1, x - radius);
    getChunkCount.setInt(2, x + radius);
    getChunkCount.setInt(3, z - radius);
    getChunkCount.setInt(4, z + radius);

    ResultSet resultSet = getChunkCount.executeQuery();     
    if (! resultSet.next()) {
        throw new IllegalStateException("Could not get the record count to check surrounding. Check if table 'chunkCoordinate' exists.");
    }

    int numberOfRows = rs.getInt(1);
    return (numberOfRows == radius * radius);
}

Another method is to use a cache: read the whole table into an arraylist and only operate on that. You will need a flag (or version number) to know when the table is modified and needs to be read again. There are java libraries out there that already do that for you.

Remarks:

  • Some databases have a BETWEEN operator. Try if it is faster.
  • regarding real-time checks: If you execute 100 queries for checking the surrounding one after the other, it will take some time. It may happen that one point got deleted during this time that was there some milliseconds before you checked or vice versa, leading to wrong results. With a single query like above this cannot happen. But if in your code you have no choice than executing many queries, you should accumulate the results in an intermediate table and return that. In other words: using subqueries withing your single query.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.