物理游戏的内存高效AI对象 [英] Memory efficient AI objects for physics game

问题描述

我正在使用box2d在java中创建一个物理游戏。

I am creating a physics game in java using box2d.

我正在编写一个AI类，并希望确保我的数据尽可能高效地存储，考虑到内存对齐。

I am writing an AI class and want to make sure my data is being stored as efficiently as possible, taking into consideration memory alignment.

最微小的增加可能会产生巨大的差异，因为我真的在运行'尽可能多的AI对象'，直到系统变慢。该程序已经在碰撞检测中使用了大量内存，因为我希望能够尽可能多地支持代理。

The tiniest increase will likely make a huge difference because I am literally running 'as many AI objects as I can' until the system slows down.The program is already using a lot of memory on the collision detection, because once again, I want to be able to support as many agents as possible.

我理解的是到目前为止，最小的Java类型是8字节，并且该对象被填充为8的倍数。我已经在布尔数组中构建了我的AI控件，表示移动：x +/- 1，y +/- 1和顺时针/ CCW旋转某些灯具。

What I understand so far, is that the smallest Java type is 8bytes, and that objects are padded into multiples of 8. I have structured my AI controls in boolean arrays, representing movement: x+/-1, y+/-1, and clockwise/CCW rotations for certain fixtures.

由于Java没有布尔值的空值设置，因此我使用bool值on_off和pos_neg嵌套了命令对象中的控件。通过移动和旋转，我每个'默认'动作处理大约7个命令对象（例如向右移动）。所以我为每个动作创建了Command数组。

Since Java doesn't have null settings for Booleans, I nested the controls in command objects with the bool values on_off, and pos_neg. With the movements and rotations, I'm dealing with about 7 command objects per one 'default' action, (such as move right). So I create Command arrays for each action.

我的问题是：我这样做有效吗？

My question is: Am I doing this efficiently?

我还没有最终确定设计，所以我不确定每个阵列的大小。但是，考虑到内存对齐要求，我猜我至少会有一些填充，这最终会浪费内存。我正在考虑做一些像切割对象大小以适应填充限制和然后将剩余数据从多个对象推送到溢出对象......或类似的东西。

I haven't finalized the design, so I'm not certain about the size of each array. But, given memory-alignment requirements, I'm guessing I will have at least some padding, which is ultimately wasted memory.I'm considering doing something like cutting the object size to fit the padding limit and then pushing the remaining data from multiple objects into an 'overflow' object... or something like that.

这会加快速度吗？为什么或为什么不呢？

Will this speed things up? Why or why not?

我也在考虑使用bitset，虽然我认为我的命令对象可能已经取得了类似的结果，但我被告知有点位移很慢。

I'm also considering using bitsets, though I think my command objects may have achieved a similar result, and I've been told bit-shifting is slow.

public class Command {

        boolean on_off  = false;
        boolean pos_neg = false;
}

public class DefaultMoves {

    //Note: these arrays are 2d in the event multiples are necessary
    //to complete a single action, I may change this later.
    Command[][] mvRight =    
        { 
              {     new Command(false, false), //
                    new Command(false, false), //
                    new Command(false, false), //
                    new Command(false, false), //
                    new Command(false, false), //
                    new Command(true, true), //moveX
                    new Command(false, false)  //   
              },   
        };
    Command[][] mvLeft =    
        { 
              {     new Command(false, false), //
                    new Command(false, false), //
                    new Command(false, false), //
                    new Command(false, false), //
                    new Command(false, false), //
                    new Command(true, false), //moveX
                    new Command(false, false)  //   
              },   
        };
}

推荐答案

这将只是评论，但有点冗长，我不想写它作为3条评论。

This was going to be just a comment, but got a bit lengthy, and I didn't feel like writing it as 3 comments.

由于这是另一个问题的后续问题，我将从不要担心填充开始。担心如何存储您的数据。

Since this is a follow-up question of another, I would start with "Stop worrying about padding". Worry about how you store YOUR data.

而且，如果您要担心物品占用多少空间，请分配7个对象而不是7个单独对象的数组。我确信Java在每个分配中都有开销。在典型的C或C ++实现中，每个 new 或 malloc 的分配占用16-32个字节，超出分配的实际数据的大小，并将大小舍入为16或32个字节。在java中有一个建议这里一个对象的内存开销是8字节 - 这可能不是适用于所有Java VM和实现。

And, if you are going to worry about how much space your things take, allocate an array of 7 objects instead of 7 individual objects. I'm sure Java has overhead in each allocation. In a typical C or C++ implementation, each allocation with new or malloc takes up 16-32 bytes above and beyond the size of the actual data allocated, and the size is rounded to 16 or 32 bytes. In java there is a suggestion here that the memory overhead of an object is 8 bytes - this may not be true for ALL Java VMs and implementations.

此外，所有空间和时间优化都是空间和时间之间的折衷[几乎总是至少]，因此以更紧凑的形式存储数据将花费时间节省空间。例如，我可以认为将 on_off 和 pos_neg 配对为较大整数结构中的两位。所以你的7个命令将存储在一个整数中。但是，现在您必须进行轮班和屏蔽才能获得正确的数据。同样，如果要存储某些东西，也可以进行移动和定位。 （我把它写成C，因为我不太了解Java）。

Further, all space&time optimisation is a compromise between space and time [nearly always at least], so storing your data in a more compact form will cost in time for the saving in space. I can for example think that having pairs of on_off and pos_neg as two bits in a larger integer structuer. So your 7 commands would be stored in one integer. However, now you have to do shifts and masking to get the right data out. Likewise, shifting and oring if you are going to store something. (I'm writing this as C, since I don't know Java well enough).

/* This is big enough for 16 pairs of on_off and pos_neg */
/* In a pair of bits, bit 0 = on_off, bit 1 = pos_neg */
uint32_t cmdData;

/* Get values of on_off and pos_neg for element number n */
void getData(int n, bool& on_off, bool& pos_neg)
{
    uint32_t shifted = cmdData >> (2 * n);
    on_off = (shifted & 1) != 0;
    pos_neg = (shifted & 2) != 0;
}

/* Store values for element n */
void setData(int n, bool on_off, bool pos_neg)
{
    uint32_t bits = (int)on_off + (2 * (int)pos_neg); 
    uint32_t mask = 3 << (n * 2);
    cmdData &= ~mask; /* Clear bits */
    cmdData |= bits << (n * 2);
}

如您所见，这可以更有效地存储数据，因为我们可以存储16对 {on_off，pos_neg} ，4个字节，而不是每个（可能）占用一个字节。但要获得每个，你必须每次做一些额外的操作（并且代码变得更加混乱）。这是值得拥有还是不高度取决于具体情况，您访问这些内容的频率与系统内存有多低（假设THESE对象的内存使用率是造成问题的原因 - 如果您有100个命令结构和使用命令的40000000个对象，那么命令不会成为问题）。

As you can see, this stores the data more efficiently, as we can store 16 pairs of {on_off, pos_neg} in 4 bytes, rather than each (probably) taking up a byte each. But to get to each, you have to do a few extra operations each time (and the code gets messier). Whether this is "worth having" or not highly depends on the situation, how often you access these versus how low on memory the system is (assuming the memory usage for THESE objects is what is causing the problem - if you have 100 command structures and 40000000 objects that USE the commands, then the commands aren't going to be the issue).

我存储方向/移动命令的方式可能是两个整数值（ int8_t [<$如果空间紧张，c $ c> byte in java），持有 +1 ，例如向右或向下移动，<$ c $向左或向上移动c> -1 。这不是最紧凑的形式，但它可以轻松访问并轻松计算新的位置。

The way I would store the commands for direction/movement is probably as two integer values (int8_t [byte in java] if space is tight), holding a +1 for moving for example right or down, -1 for moving left or up. This is not the most compact form, but it makes for easy access and easy calculation of a new position.

然后可以使用此对描述所有可能的方向：

This pair can then be used to describe all possible directions:

struct direction
{
     int x, y;
};

direction directions[] =
{
     { 0, 0 },    // Don't move.
     { 0, 1 },    // Right.
     { 0, -1 },   // Left.
     { 1, 0 },    // Down.
     { -1, 0 },    // Up.
 };

如果你想对角移动，你还需要添加另外四对组合 {1,1}，{-1,1} 等。

If you want to move diagonally too, you'll have to add another four pairs with the combinations of { 1, 1 }, {-1, 1}, etc.

同样适用于可以移动的对象，作为一对 xDir，yDir 值。

The same can be applied to an object that can move, as a pair of xDir, yDir values.

但这里的关键是你想要的首先想出一个更重要的东西：空间或计算。从中，找出占据大部分空间的对象（具有最高计数的对象）。摆弄一些或几十个物体的大小不会产生任何大的不同，你有数百万的意愿。如果空间不是问题（并且公平地说，编写能够在具有千兆字节RAM的系统中有效使用足够大量数据的代码真的很难 - 在内存耗尽之前，通常CPU会耗尽速度为每个框架的每个对象做一些事情。）

But the key here is that you want to first of all come up with a good understanding of what is more important: space or computation. From that, find out what objects are taking up most of the space (what has the highest count). Fiddling with the size of objects that you have one or a few dozen of won't make any big different, something you have millions of will). If space is not an issue (and to be fair, it's really hard to write code that efficiently uses large enough amounts of data in a system with gigabytes of RAM - it is usually the CPU that runs out of speed before memory is exhausted if you do something to each object for every frame).

手提箱类比：

想象一下，你有一个手提箱，它可以容纳4个小盒子的宽度[以及长度上的任何数字 - 这是一个奇怪的行李箱！]，你有更大的盒子，分别是1,2,3或4个小盒子。盒子用魔术贴制成，所以它们粘在一起，可以随意拆分，但你必须跟踪哪些属于一起，每次你拆分或重新组合单位时，需要额外的时间。

Imagine that you have a suitcase that can hold exactly 4 little boxes in it's width [and any number at the length - it's a weird suitcase!], and you have larger boxes that are 1, 2, 3 or 4 units of little boxes. The boxes are made with "velcro", so they stick together and can be split as you like, but you have to keep track of which belong together, and each time you "split" or "put back together" the units, it takes extra time.

如果你想变得懒惰并且简单易行，你只需将三盒装的东西放在行李箱中，每个行李箱旁边都有一个空的空间。

If you want to be lazy and make it simple, you just stick your three-box ones into the suitcase with one empty space next to each.

 1 2 3 4
 a a a x
 b b b x
 c c c x
 d d d x 

依此类推。

如果你想紧紧包装，你拿一个3个单位的盒子，然后切下一个单位的一个单位，然后把它贴在第一个单位旁边，然后在下一个空间的剩余两个单元，然后从下一个单元切下两个单元，并将其粘在包2旁边，依此类推。

If you want to pack it tightly, you take one 3 unit box, and then cut one unit of the next one, and stick it next to the first one, then the remnant two units on the next space, then cut a two unit piece from the next one, and stick it next to packet 2, and so on.

1 2 3 4
a a a b
b b c c
c d d d 

现在，你已经减少了25％的空间来存储它们，但你花了一些时间来分割它们，你必须花时间再把它们拿出来当你以后需要使用这些数据时，以三个为单位。

Now, you have used 25% less space to store them, but you spent time split them, and you have to spend time again to fetch them out into units of three when you later need to use the data.

现在，想象一下，如果你把东西放进行李箱就得到了报酬，你按照你放的项目得到报酬你选择哪种方法？

Now, imagine that you get paid to put things into the suitcase, and you get paid per item you put, which method do you choose?

然后考虑到您不必为每件物品付款，您必须支付行李箱空间（因为您是公司的所有者）。现在你想尽可能多地挤进空间。但这需要额外的时间，对吗？如果手提箱很贵，那么它可能是值得的。如果它不是那么昂贵，你可能更喜欢节省空间时间。这是一个妥协。

Then consider that you instead of being paid per item, you have to pay for suitcase space (because you are the owner of the company). Now you want to squeeze as much into the space as possible. But it takes extra time, right? If suitcase is expensive, then it may be worth it. If it's not so expensive, you may prefer to save time over space. It's a compromise.

[我们可以用8,32或64更现实的单位做同样的事情，但我认为这会让它更难以阅读和绝对让你更难打字]

[We could do the same thing in more realistic units of 8, 32 or 64, but I think that would just make it harder to read and definitely make it harder to type]

这篇关于物理游戏的内存高效AI对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！