Handmade Hero»Forums»Code
17 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
Edited by nikki on
Hiya,

I've been using the Memory Arena stuff in a project of my own, now I ran into something which I am not sure how to solve the 'proper' way:

Same as Casey i am using a scratch arena and a persistent arena,
I've been building some pathfinding code that uses the scratch arena during its run and then returns a linked list of Nodes

In my Game State / persistent arena i have an array of Actors that each possibly have a Path to follow.
I am not completely sure how to fix this, off course I can copy the linked list of Nodes (that lived in Scratch) into some new structure (because that scratch arena will be cleared much earlier then the path will be done with), but i don't really know of a way to have some memory in use for as long as i need it and then return it to the arena.

Both the persistent arena and the scratch are not really suited for that. what i am doing now is just give all the Path structs for the Actors a fixed size with quite some margin so short paths but also very long ones will fit, but this feels very wasteful (as in 100Mb vs 3Mb kind of wasteful), its by far the biggest chunk of memory at the moment. And most of the time all that memory is not used (many paths are like 4 nodes long, but i still reserve 512 nodes for it :))

Is this being tackled somewhere in the stream? If not what would your advice be?
511 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
free list doesn't work?

For freeing a linked list you'll want to have a tail pointer (either in the path or in the free list) so you can just drop the freed path in as is.
Dumitru Frunza
24 posts
Apprentice github.com/dfrunza/hoc
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
Maybe create a new sub-arena dedicated to path nodes?
17 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
@ratchetfreak @dfrunza, thanks guys, I didnt think of the freelist at all, a combination of a dedicated arena for pathnodes and the freelist is exactly what I need, thanks!
17 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
Edited by nikki on
I was thinking some more about this, I eventually intend to have more lists of nodes that ought to be usable for some time, (like an action queue for example)
I guess some more general way of doing this (So I don't end up needing an Arena for each nodetype) would be some dedicated Arena with a FreeList in it and on that Freelist the nodes arent structs like

{
int somedata, moredata, andmore;
Node* Next;
Node* Prev;
} Node;

but instead have a void* Value.

In this case one could use 1 Arena for all kinds of data that can be used for all kinds of durations, at the cost of casting that void* to read the data for each node.
Is this logic correct?
511 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
nikki
I was thinking some more about this, I eventually intend to have more lists of nodes that ought to be usable for some time, (like an action queue for example)
I guess some more general way of doing this (So I don't end up needing an Arena for each nodetype) would be some dedicated Arena with a FreeList in it and on that Freelist the nodes arent structs like

{
int somedata, moredata, andmore;
Node* Next;
Node* Prev;
} Node;

but instead have a void* Value.

In this case one could use 1 Arena for all kinds of data that can be used for all kinds of durations, at the cost of casting that void* to read the data for each node.
Is this logic correct?


That basically moves the allocation and freeing complexity to whatever the void* is pointing to.

if instead you have specific pools and freelists for certain types of actions (grouped by the size of the required additional data) then you shouldn't need to split out the node and the data.
17 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
Maybe i was a bit unclear, or i dont fully understand your answer ;).

But i meant: I have an array of Actors, they live on the permanent state.
Now I want to have a PathList for each Actor, my original problem was how to get some memory that remains intact for some unknown duration.
For that the combination of a dedicated Arena and Freelist will work I can imagine.

But then I thought some more about it, and wondered if that would mean if all sorts of Lists that i would end up wanting would need their own Arena & Freelist.

39 posts / 1 project
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
Edited by graeme on
That would work, but giving each type its own arena has advantages, for example you can instantly find out the memory usage for a given subsystem (path finding, action queues, etc) by looking at how much of the arena has been used. It also promotes cache locality, which for linked lists may not be a huge concern, but outside HMH you see arenas most often in cases where it is important.

I don't know if you're caught up on HMH but in the next few episodes Casey is going to address this exact problem, but for memory for particle systems rather than pathfinding nodes

edit: I believe ratchetfreak is suggesting something like

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct FooNode
{
    i32 data[4];
};

struct BarNode
{
    f32 data[4];
};

struct BazNode
{
    i32 data[8];
};

struct Node_16
{
    union 
    {
        FooNode foo;
        BarNode bar;
        u8 reserved[16];
    };
    Node_16 *next, *prev;
};
static_assert(sizeof(Node_16) == sizeof(Node_16*)*2 + 16);

struct Node_32
{
    union
    {
        BazNode baz;
        u8 reserved[32];
    };
    Node_32 *next, *prev;
};
static_assert(sizeof(Node_32) == sizeof(Node_32*)*2 + 32);

And any node type that fits in Node_16 can go in a Node_16 arena, and for larger nodes, a Node_32 arena, and so on. I didn't add a type field to make it a tagged union because the calling code would know, presumably.
17 posts
Using the Memory Arena for pathfinding ran into an issue, how to keep memory around?
Ah thanks for that!

It clears it up, got it know