java - 在 Android 中使用 Hashmap 存储伪无限游戏世界时内存不足

Question

继续 a previous question regarding infinite game worlds and coordinate data structures我决定使用 HashMap 。然而，由于我是在 Android 上尝试这个，所以我很快就遇到了问题。

这里是要求的回顾:

• 伪无限 2D 瓷砖世界。世界将生成为 探索所有 4 个方向 (2D) 所以我们需要一些东西去 负指标。
• 相邻图 block 需要随机访问 等
• 需要能够从特定坐标检索图 block ，例如 得到(x，y)

所以，这是我用来创建 600 * 600 个图 block 的 HashMap 的代码 fragment 。

每个 map 图 block 的类:

public class MapTile {
    public int type;

    public MapTile(int type) {
        this.type = type;
    }

    public boolean is(int type) {
        return (type==this.type);
    }
}

生成大 map 的测试代码:

long startTime;
long lastTime;    
map = new HashMap<Point, MapTile>();
int x;
int y;
int tile;
startTime = System.currentTimeMillis();
lastTime = startTime;
for (x=-300;x<=300;x++) {
    for (y=-300;y<=300;y++) {
        tile = (x+y)%2; //Just so I differentiate the tiles
        this.map.put(new Point(x,y), new MapTile(tile));

    }
    // Logging each row
    Log.d(this.getClass().toString(), "Generated x:" + x + " Time in ms:"+(System.currentTimeMillis() - lastTime));
    lastTime = System.currentTimeMillis();

}

因此，当我在 Java 中运行类似代码时。它成功完成(虽然吃了大量内存)。没问题。

但是，当我尝试在高端设备上的 Android 中执行此操作时，它实际上在达到 x = 190 标记(通常)之前就停止了。垃圾收集器开始运行，随后出现无限循环:

** snip **
05-26 15:52:19.565  10758-10758/com.ayk.test04        D/class com.ayk.test04.WorldMap2D: Generated x:187 Time in ms:2
05-26 15:52:19.570  10758-10758/com.ayk.test04        D/class com.ayk.test04.WorldMap2D: Generated x:188 Time in ms:6
05-26 15:52:19.575  10758-10758/com.ayk.test04        D/class com.ayk.test04.WorldMap2D: Generated x:189 Time in ms:2
05-26 15:52:19.995  10758-10760/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 66.002MB to 64.000MB
05-26 15:52:19.995  10758-10760/com.ayk.test04        D/dalvikvm: GC_CONCURRENT freed 3K, 2% free 64797K/65543K, paused 4ms+30ms, total 429ms
05-26 15:52:19.995  10758-10758/com.ayk.test04        D/dalvikvm: WAIT_FOR_CONCURRENT_GC blocked 421ms
05-26 15:52:20.335  10758-10758/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 66.002MB to 64.000MB
05-26 15:52:20.335  10758-10758/com.ayk.test04        D/dalvikvm: GC_FOR_ALLOC freed 0K, 2% free 64797K/65543K, paused 341ms, total 341ms
05-26 15:52:20.335  10758-10758/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 64.002MB to 64.000MB
05-26 15:52:20.335  10758-10758/com.ayk.test04        I/dalvikvm-heap: Grow heap (frag case) to 64.000MB for 16-byte allocation
05-26 15:52:20.695  10758-10760/com.ayk.test04        I/dalvikvm-heap: Clamp target GC heap from 66.002MB to 64.000MB
05-26 15:52:20.695  10758-10760/com.ayk.test04        D/dalvikvm: GC_CONCURRENT freed 0K, 2% free 64797K/65543K, paused 12ms+2ms, total 358ms
05-26 15:52:20.695  10758-10758/com.ayk.test04        D/dalvikvm: WAIT_FOR_CONCURRENT_GC blocked 332ms
** thousands of these... snip **

所以，差不多，我被困在这里了。
我的瓷砖现在只包含一个 int 变量。这是准系统。所以我明白了，创建一个包含 50.000 个左右对象的 HashMap 在技术上是不可能的？这对我来说似乎有点小。

我想尝试的是:

• 仅将 map 的 Activity 区域保留在内存中，同时将其余部分卸载到存储中。虽然这可能会解决内存问题，但恐怕在访问 Activity 区域之外的图 block 时可能会导致性能问题。
• 有人建议使用 block (ala Minecraft)。所以我保留了一个 HashMap 的 HashMap ？行得通吗？如果可以，我该怎么做？
• 我是否完全偏离了目标并且以错误的方式看待它？

感谢您提供的任何帮助。

更新

你好。在您的帮助下，我决定继续使用数据库。它的工作效率更高，到目前为止，我还没有遇到任何问题。对于后代，这是它的工作原理:

数据库

在 Android 中工作，我已经设置了一个 SQLite 数据库和表来存储每个图 block 。起初，我决定在每次生成图 block 时运行插入查询。这很快就变成了另一个性能瓶颈，因为每个 INSERT 都需要 2 毫秒多一点的时间才能完成，即使是最小的 300x300 切片生成过程也会遇到麻烦。我不得不使用多个 INSERT 查询，该查询采用多个图 block 并使用单个查询存储它们。因此，我创建了一个“图 block 缓冲区”，其中每个图 block 都存储了它们的坐标:

//A linked list of integers is good enough. 
//The first 2 are X and Y coordinates, the third one is the tile type. 
//I can add more fields if needed.
this.tileDBbuffer = new LinkedList<Integer[]>();

缓冲区的填充方式如下:

void addTileBuffer(int x,int y, MapTile map_tile) {
    int maxsize = 10000;
    Integer[] tile_data;
    tile_data = new Integer[3];
    tile_data[0] = x;
    tile_data[1] = y;
    tile_data[2] = map_tile.type;
    if (this.tileDBbuffer.size()>= maxsize) {
        Log.d(this.getClass().toString(), "Buffer filled up... Saving");
        savemapbuffer();
    }
    this.tileDBbuffer.add(tile_data);
}

一旦缓冲区达到一定大小(或瓦片生成结束)，“savemapbuffer()”函数就会运行，基本上首先调用此函数，然后清除缓冲区:

public void addTileBulk(LinkedList<Integer[]> map_tiles) {
    Integer[] tile_data = new Integer[3];

    if (db == null) db = this.getWritableDatabase();

    String sql = "INSERT INTO "+TABLE_NAME_MAP+" ("+COLUMN_NAME_MAP_X+", "+COLUMN_NAME_MAP_Y+", "+COLUMN_NAME_MAP_TILE_TYPE+") VALUES (?,?,?)";
    db.beginTransaction();
    SQLiteStatement stmt = db.compileStatement(sql);
    try {
        while (!map_tiles.isEmpty()) {
            tile_data = map_tiles.pop();
            stmt.bindLong(1,tile_data[0]);
            stmt.bindLong(2,tile_data[1]);
            stmt.bindLong(3,tile_data[2]);
            stmt.execute();
        }
        db.setTransactionSuccessful();
    } finally {
        db.endTransaction();

    }

    map_tiles.clear();
}

正在使用 HashMap

此后不久，绘制 map 时出现问题。绘图是在另一个线程中完成的，因此在生成新图 block 的同时迭代它会引发许多奇怪的错误。在使用“ map 是否繁忙” boolean 值进行了一些测试后，我最终使用了 ConcurrentHashmap 而不是常规的 Hashmap。它奏效了。

block

在那之后，我最终还是需要使用“ block ”。管理 map 的离散部分比根据玩家距离估计加载哪些图 block 更容易。所以现在，每个 HashMap 元素都是一个固定的二维整数数组，包含瓦片。我称它们为细胞

map = new ConcurrentHashMap<Point, MapCell>();

一个单元格是这样的:

public class MapCell {
    public int x,y;
    private static int cell_size = 32;
    public MapTile[][] tiles = new MapTile[cell_size][cell_size];
}

现在。我要去 Perlin 噪声和 map 生成冒险:) 下次见。

Answer 1

您可能不得不选择将子集保留在内存中的第一个选项，尤其是当您的游戏世界变得更大时。为了尽量减少性能损失，您可以考虑创建 30x30 子图 block 之类的东西。在任何时候，保持当前子图加载，同时在后台加载 8 个相邻的 30x30 子图。当玩家角色在 subtile 之间转换时，它会加载得很快，因为它已经加载了，然后当他正在探索新的 subtile 时，您可以将下一个加载到内存中，等等。

如果您遵循 subtiles 策略(subtile 边界对齐到 30 的倍数)，则不必经常检查，但只有在您越过 subtile 边界时才检查。此外，通过一次加载 30x30，您可以最大限度地减少数据库或文件访问。您也不需要使用 HashMap:将每个子图 block 表示为 30x30 数组，并存储当前中心子图 block 的左上角坐标。然后，如果需要，您应该能够进行一些数学运算以检索 90x90 附近的相关图 block 。