Contiguous Polymorphic Memory Storage

[helios]

The Tile struct should contain information that pertains exclusively to a single instance of a tile. A Tile represents a part of the game world.
For example, the tile type PatchOfGrass may have an animation where the grass rustles; this does not mean that every instance of that tile needs a copy of that animation, or even a pointer to a single copy. Only the render_PatchOfGrass() function needs to know that patches of grass are animated. If necessary, each Tile could contain an integer that the PatchOfGrass tile type could use to store the current animation frame index. That would allow you to animate each tile individually, rather than all of them in unison.

What I would do is write a code generation program where I specify the members each tile type needs and the program automatically figures out the data layout. For example:

CodeGenerator code_generator;
{
    TileType patch_of_grass("PatchOfGrass");
    patch_of_grass.add_member(DataType::Int, "animation_frame");
    patch_of_grass.add_member(DataType::Bool, "is_destroyed");
    code_generator.add(patch_of_grass);
}
{
    TileType road_surface("RoadSurface");
    road_surface.add_member(DataType::Int, "damage");
    road_surface.add_member(DataType::Bool, "is_illuminated");
    code_generator.add(road_surface);
}
{
    TileType teleporter("Teleporter");
    teleporter.add_member(DataType::Int, "destination_x");
    teleporter.add_member(DataType::Int, "destination_y");
    code_generator.add(teleporter);
}
std::cout << code_generator.generate();

And this generated something like:

struct Tile{
    TileType type;
    std::uint32_t booleans;
    int integer1;
    int integer2;
};

struct PatchOfGrassTile{
    TileType type;
    std::uint32_t booleans;
    int animation_frame;
    int unused;
};

struct RoadSurfaceTile{
    TileType type;
    std::uint32_t booleans;
    int damage;
    int unused;
};

struct TeleporterTile{
    TileType type;
    std::uint32_t unused;
    int destination_x;
    int destination_y;
};

inline is_destroyed(const PatchOfGrass &tile){
    return tile.booleans & 1;
}

inline is_illuminated(const RoadSurfaceTile &tile){
    return tile.booleans & 1;
}

Of course, you can also add empty members if you want to accommodate plugins or something.

EDIT: Or just use a union, I guess... ._.

[lordseanington]

Thanks for the feedback, you have been a great help. I will work something out, thanks to everyone who gave me responses, I really appreciate it.

I probably will end up using a system similar to the one where each uses a generic update function and passes data with it, this data will be defined in a tile instance but the function identifier will be defined in a tile instance. I will work something with that.

Edit: now that I think of it a Union might be the best way to handle data. Thanks

[jonnin]

Don't destroy the memory (2 posts back). Put a used flag on it, and when an object dies, mark it deleted and re-use it. This keeps the memory in one solid block and saves the allocation and de-allocation costs. Actually given the nature of your code the used flag might not work, you may just have to have a vector<bool> of the same size as your construct to store which locations are used or not.

[lordseanington]

I know. My chunk size remains constant as long as ay least a single chunk is loaded. Thus meaning I can always use pointer arithmatic to get a desired block, and stoor a list of booleans for it (so I don't just read garbage if there's nothing there)

[jonnin]

Yes, this should work. Side notes .. did you multi-thread the inner loop? If you do that, be sure to iterate each thread over a piece of it, sequentially. Also it might be worth a once-over on the objects to see if there is any wasted space, might be able to reduce the footprints.

Its probably possible and safe to add say a c-string to your union, and set it to some sentinel value for deleted blocks, instead of the bools on the side. I dunno... vector bool is ultra efficient, but its extra space and cache interruption. If you can keep it in the memory block, checking the block won't cost you to move out to hit the other memory (vector of bool). Think about it. Youll want to try to iterate over this thing without touching any other big memory blocks if possible.

[dhayden]

If you have 80,000 tiles and each contains 10k of data, that's 800MB: well within the range of a modern PC. If each tile contains 1k of data, which seems more reasonable to me, then you're looking at 80MB, which isn't big at all. Are you sure you have caching problem?

Do you have to update all 80,000 tiles in real time? Just as an example, the appearance of a tile doesn't have to be updated unless it's actually being viewed by someone. Do all 80,000 tiles change every 8ms? Maybe your event system could update a smaller number.

[lordseanington]

I could probably have a new block that's created cache a future event regarding that block to update it when the event triggers. My event system is expensive. Also about the viewable part, the whole issue is I'm supporting a larger number of players. 80,000 is an example number as well. And it isn't necessarily the apearence that needs to be updated either. My designer wants to add a wiring system that will run as long as the chunk is loaded.

I could probably have the event handler take care of that aswell to be honest.A given block that sends a signal sends an event stepped up by a tick (so it won't run until the next frame), and it foes down the line of wires with each forwarding to the next.

Either way I think I have enough to to off of, I'll tinker around with it.

[lordseanington]

I found a way to do this with relative ease. I made a union to handle data and keeping the memory aligned properly by keeping the max size standard. At that point I made a pool alocator for the given chunk and it gave me great results on optimization. I went from roughly 8-9 ms for 80,000 blocks to 6-7 ms for 80,000 blocks.

[helios]

Instead of allocating each tile separately, if possible keep it in a vector.

[lordseanington]

What I ended up doing was creating a pool of Block objects by allocating a pool the size of the malp(sized*sizey*sizes). Since the union kept data the same size (as it is equal to the largest possible type), and since the malloc is already properly aligned to it (again, because size is the same), it was a matter of placement new and pointer arithmaric to get the data. This turned out to be extremely ram cache friendly.

[helios]

It sounds like you're doing manually what std::vector or even a simple array could do for you.

[lordseanington]

I pretty much am, but I am using the preallocated pool memory and using placement new to comstruft new block object types. A vector would not be effective as I can't do a placement new with a vector, and I also am now treating the assigned data as an array of block objects.

The layout of my map is in a psuedo multidimensional array, so I am just using a normal array but pooled and placement newed.