Created
February 17, 2022 07:03
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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