Skip to content

Instantly share code, notes, and snippets.

@notnullnotvoid
Created February 17, 2022 07:03
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save notnullnotvoid/e84e5d41069e522f6d267b213b916c3c to your computer and use it in GitHub Desktop.
Save notnullnotvoid/e84e5d41069e522f6d267b213b916c3c to your computer and use it in GitHub Desktop.
the box2d cloning code from sir happenlance, just for reference for those who might find it useful - it relies heavily on the block allocator strategy used by box2d so the strategy here wouldn't work if you replace the allocator with someting radically different
#include "b2deepclone.hpp"
#include "level.hpp"
#include "box2d.h"
#include "trace.hpp"
//definitions copied from b2_block_allocator.cpp
static const int32 b2_chunkSize = 16 * 1024;
struct b2Chunk {
int32 blockSize;
b2Block* blocks;
};
struct b2Block {
b2Block* next;
};
//PERF TODO: make this an O(1) hashmap
struct ChunkMap {
struct Chunk { size_t src, dst, size; };
List<Chunk> chunks;
void finalize() { chunks.finalize(); };
void add(void * src, void * dst, size_t size) {
//TODO: assert we haven't already added this somehow?
chunks.add({ (size_t) src, (size_t) dst, size });
}
void * optional_get(void * src) {
assert(src);
for (Chunk & chunk : chunks) {
if ((size_t) src >= chunk.dst && (size_t) src < chunk.dst + chunk.size) {
assert(!"pointer has already been remapped"); //should we just allow this?
}
if ((size_t) src >= chunk.src && (size_t) src < chunk.src + chunk.size) {
size_t offset = (size_t) src - chunk.src;
size_t dst = chunk.dst + offset;
return (void *) dst;
}
}
return nullptr;
}
void * get(void * src) {
void * dst = optional_get(src);
assert(dst);
return dst;
}
};
static ChunkMap chunkMap = {};
#define MAP(ptr) do { *((void **) &(ptr)) = chunkMap.get(ptr); } while (false)
//NOTE: can't have OPT_MAP call chunkMap.optional_get(ptr) because that would silently return null
// for non-null pointers if they aren't mappable, and we want to assert in that situation
#define OPT_MAP(ptr) do { if (ptr) { MAP(ptr); } } while (false)
struct b2DeepCloner {
static void map(b2BlockAllocator * dst) { TimeFunc
//copy chunks list
b2Chunk * srcChunks = dst->m_chunks;
dst->m_chunks = (b2Chunk *) b2Alloc(dst->m_chunkSpace * sizeof(b2Chunk));
//NOTE: I don't know whether we need to memcpy the whole capacity or just the count, so let's be safe
memcpy(dst->m_chunks, srcChunks, dst->m_chunkSpace * sizeof(b2Chunk));
//copy chunks and add them to the chunk map
for (int i = 0; i < dst->m_chunkCount; ++i) {
b2Block * srcBlocks = dst->m_chunks[i].blocks;
dst->m_chunks[i].blocks = (b2Block *) b2Alloc(b2_chunkSize);
memcpy(dst->m_chunks[i].blocks, srcBlocks, b2_chunkSize);
chunkMap.add(srcBlocks, dst->m_chunks[i].blocks, b2_chunkSize);
}
//patch the free lists which are woven through the chunks
for (int i = 0; i < b2_blockSizeCount; ++i) {
b2Block * block = (b2Block *) &dst->m_freeLists[i];
while (block->next) {
MAP(block->next);
block = block->next;
}
}
}
static void map(b2TreeNode * dst) {
if (dst->height != -1) { //NOTE: -1 means free node, which means this node should be ignored
//NOTE: stored as void*, but actually b2FixtureProxy* that points in to the fixtures' proxy lists
OPT_MAP(dst->userData); //can be null, apparently
}
}
static void map(b2DynamicTree * dst) {
b2TreeNode * srcNodes = dst->m_nodes;
dst->m_nodes = (b2TreeNode *) b2Alloc(dst->m_nodeCapacity * sizeof(b2TreeNode));
//NOTE: I don't know whether we need to memcpy the whole capacity or just the count, so let's be safe
memcpy(dst->m_nodes, srcNodes, dst->m_nodeCapacity * sizeof(b2TreeNode));
//NOTE: `m_nodeCount` is not what you'd expect, because this is NOT a straightforward growable array list.
// It contains a free list, so we MUST iterate the whole capacity and map non-free nodes.
for (int i = 0; i < dst->m_nodeCapacity; ++i) {
map(&dst->m_nodes[i]);
}
}
static void map(b2BroadPhase * dst) {
map(&dst->m_tree);
int32 * srcMoveBuffer = dst->m_moveBuffer;
dst->m_moveBuffer = (int32 *) b2Alloc(dst->m_moveCapacity * sizeof(int32));
//NOTE: I don't know whether we need to memcpy the whole capacity or just the count, so let's be safe
memcpy(dst->m_moveBuffer, srcMoveBuffer, dst->m_moveCapacity * sizeof(int32));
b2Pair * srcPairBuffer = dst->m_pairBuffer;
dst->m_pairBuffer = (b2Pair *) b2Alloc(dst->m_pairCapacity * sizeof(b2Pair));
//NOTE: I don't know whether we need to memcpy the whole capacity or just the count, so let's be safe
memcpy(dst->m_pairBuffer, srcPairBuffer, dst->m_pairCapacity * sizeof(b2Pair));
}
static void map(b2ContactEdge * dst) {
MAP(dst->other);
MAP(dst->contact);
OPT_MAP(dst->prev);
OPT_MAP(dst->next);
}
static void map(b2Contact * dst) {
OPT_MAP(dst->m_prev);
OPT_MAP(dst->m_next);
map(&dst->m_nodeA);
map(&dst->m_nodeB);
MAP(dst->m_fixtureA);
MAP(dst->m_fixtureB);
}
static void map(b2ContactManager * dst, b2BlockAllocator * allocator) {
map(&dst->m_broadPhase);
OPT_MAP(dst->m_contactList);
b2Contact * contact = dst->m_contactList;
while (contact) {
map(contact);
contact = contact->m_next;
}
//this lives in our malloc'd b2World, not in a mapped block, so we have to pass it in and assign it normally
dst->m_allocator = allocator;
}
static void map(b2ChainShape * dst) {
b2Vec2 * srcVertices = dst->m_vertices;
dst->m_vertices = (b2Vec2 *) b2Alloc(dst->m_count * sizeof(b2Vec2));
memcpy(dst->m_vertices, srcVertices, dst->m_count * sizeof(b2Vec2));
}
static void map(b2Shape * dst) {
if (dst->m_type == b2Shape::e_chain) { //the only shape type with dynamically allocated data
map((b2ChainShape *) dst);
}
}
static void map(b2FixtureProxy * dst) {
MAP(dst->fixture);
}
static void map(b2Fixture * dst) {
OPT_MAP(dst->m_next);
MAP(dst->m_body);
MAP(dst->m_shape);
map(dst->m_shape);
//remap the proxies list
//NOTE: m_proxies is allocated through the block allocator, but it can be larger than the largest block size,
// so it sometimes ends up on the heap, in which case we have to copy it instead of mapping the pointer
//NOTE: m_proxyCount should always be at least 1, so we should not have to null-check m_proxies here
b2FixtureProxy * proxies = (b2FixtureProxy *) chunkMap.optional_get(dst->m_proxies);
if (proxies) {
dst->m_proxies = proxies;
} else {
b2FixtureProxy * srcProxies = dst->m_proxies;
dst->m_proxies = (b2FixtureProxy *) b2Alloc(dst->m_proxyCount * sizeof(b2FixtureProxy));
memcpy(dst->m_proxies, srcProxies, dst->m_proxyCount * sizeof(b2FixtureProxy));
//NOTE: because `b2TreeNode`s store pointers into these lists, they need their own mapping table entries
chunkMap.add(srcProxies, dst->m_proxies, dst->m_proxyCount * sizeof(b2FixtureProxy));
}
//remap the proxies themselves
for (int i = 0; i < dst->m_proxyCount; ++i) {
map(&dst->m_proxies[i]);
}
}
static void map(b2Body * dst, b2World * world) {
//this lives in our malloc'd b2World, not in a mapped block, so we have to pass it in and assign it normally
dst->m_world = world;
OPT_MAP(dst->m_prev);
OPT_MAP(dst->m_next);
OPT_MAP(dst->m_fixtureList); //optional because the ground body will not have any fixtures in an empty level
b2Fixture * fixture = dst->m_fixtureList;
while (fixture) {
map(fixture);
fixture = fixture->m_next;
}
OPT_MAP(dst->m_jointList); //contents will be mapped later while mapping world's joint list
OPT_MAP(dst->m_contactList); //contents were already mapped while mapping contact manager's contact list
}
static void map(b2JointEdge * dst) {
MAP(dst->other);
MAP(dst->joint);
OPT_MAP(dst->prev);
OPT_MAP(dst->next);
}
//NOTE: none of the subclasses of b2Joint hold any pointers, so we don't need to care about them, only the superclass
static void map(b2Joint * dst) {
OPT_MAP(dst->m_prev);
OPT_MAP(dst->m_next);
map(&dst->m_edgeA);
map(&dst->m_edgeB);
MAP(dst->m_bodyA);
MAP(dst->m_bodyB);
}
static b2World * clone(b2World * src, b2World * dst) { TimeFunc
*dst = *src;
map(&dst->m_blockAllocator);
//NOTE: stack allocator is surprisingly a pure value-type so the copy assignment takes care of it
MAP(dst->m_bodyList); //need not be optional, because we will always have at least one body: the ground body
b2Body * body = dst->m_bodyList;
while (body) {
map(body, dst);
body = body->m_next;
}
//NOTE: the broad phase (via contact manager) must be mapped AFTER the fixtures (via bodies) are mapped,
// because the broad phase tree nodes point into fixture proxies lists stored in the fixtures,
// and if those lists are large they will live outside the block allocator's chunks,
// so they need to have their own mapping intries in the ChunkMap table before pointers into them can be mapped
map(&dst->m_contactManager, &dst->m_blockAllocator);
OPT_MAP(dst->m_jointList);
b2Joint * joint = dst->m_jointList;
while (joint) {
map(joint);
joint = joint->m_next;
}
return dst;
}
};
b2World * box2d_deep_clone(b2World * src, SimState * sim) { TimeFunc
b2World * dst = (b2World *) malloc(sizeof(b2World));
b2DeepCloner::clone(src, dst);
//map pointers in sim objects
for (SimObject & o : sim->objects) {
OPT_MAP(o.b2body);
//maybe we should be setting these pointers to null when not in use anyway, but I don't want to do that right now
//so I'm just living with it and checking if they are alive
if (o.type == ENT_LANCER) {
if (!o.lancer.dead) MAP(o.lancer.sensorFixture);
} else if (o.type == ENT_PLAYER) {
if (!o.player.dead && o.player.active) {
MAP(o.player.groundFixture);
MAP(o.player.sensorFixture);
}
} else if (o.type == ENT_LANCE) {
SimObject * owner = sim->get_object(o.lance.owner);
assert(owner && (owner->type == ENT_PLAYER || owner->type == ENT_LANCER));
if (owner->type == ENT_LANCER || (owner->type == ENT_PLAYER && owner->player.active)) {
MAP(o.lance.tip);
if (!owner->actor.dead) MAP(o.lance.joint);
}
} else if (o.type == ENT_LANCE_IMPALEMENT_SLOT) {
OPT_MAP(o.lanceImpalementSlot.joint);
}
}
// print_log("%d chunks\n", chunkMap.chunks.len);
chunkMap.finalize();
return dst;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment