[Bugzy]

In my plugin, I need to detect when a player touches a trigger_multiple and then uniquely identify the entity touched using a mapping that looks like:

entity_index -> ID

Where the ID is simply an unsigned integer.

Assume, that all data structures are built once and only once, never to be have entries inserted/deleted post-initialization. In your opinion, which of the following ways is the best for data retrieval?

Edit: Assume further that the data retrieval happens the instant OnTouch event fires, and that a client can touch multiple trigger_multiple entities at a time.

1. Use a hard-coded constant and large global static array

#define MAXENTITIES 2048 
new g_iMyIDs[MAXENTITIES];

public OnTouch(const String:output[], caller, activator, Float:delay)
{
    if (caller < MAXENTITIES)
        PrintToChatAll("Entity id is %d", g_iMyIDs[caller]);
}

Advantages:

• Super-quick, constant-time retrieval.

Disadvantages:

• Wastes a small amount of memory. Array will be sparse.
• You can't, on initialization, store more entities than the MAXENTITIES constant allows. The program must be recompiled with a new larger constant.

2. Use a global dynamic array

new Handle:g_hMyIDs = CreateArray(2);

public OnTouch(const String:output[], caller, activator, Float:delay)
{
    new ref = EntIndexToEntRef(caller);
    for (new i = 0; i < GetArraySize(g_hMyIDs); i++)
    {
        if (GetArrayCell(g_hMyIDs, i, 0) == ref)
        {
            PrintToChatAll("Entity id is %d", GetArrayCell(g_hMyIDs, i, 1));
            break;
        }
    }
}

Advantages:

• No memory is wasted.
• No need to set arbitrary constants pre-compilation, the array will automatically grow larger to accomodate the entities.

Disadvantages:

• Dynamic arrays are slower than static arrays. It takes linear time to find the entity, and assuming GetArrayCell() also takes linear(?) time, it would, at worst, take exponential time.

3. Modify the m_iName ent prop data at initialization to include the ID

public OnTouch(const String:output[], caller, activator, Float:delay)
{
    decl String:sTargetName[256];
    GetEntPropString(caller, Prop_Data, "m_iName", sTargetName, sizeof(sTargetName));
    PrintToChatAll("Entity id is %d", StringToInt(sTargetName));
}

Advantages:

• No space is wasted.
• Constant-time retrieval.

Disadvantages:

• This will break communication if one entity hooked receives output from another entity.

[Powerlord]

Can a player ever be touching more than on trigger_multiple at a time?

If not, you could do something like this...

new giMyPlayersTouch[MAXPLAYERS+1];

// in code somewhere
    for (new i = 1; i <= MaxClients; i++)
    {
        if (IsClientInGame(i) && giMyPlayersTouch[i] == myId)
        {
            // Do something because they're touching the ID thing
        }
    }

That is assuming you're hooking OnStartTouch, OnEndTouch, and using ClientDisconnect to keep track of the ID the client is touching (keeping in mind that ClientDisconnect also fires for each client on map change).

[Bugzy]

Originally Posted by Powerlord Can a player ever be touching more than on trigger_multiple at a time? If not, you could do something like this... new giMyPlayersTouch[MAXPLAYERS+1]; // in code somewhere for (new i = 1; i <= MaxClients; i++) { if (IsClientInGame(i) && giMyPlayersTouch[i] == myId) { // Do something because they're touching the ID thing } } That is assuming you're hooking OnStartTouch, OnEndTouch, and using ClientDisconnect to keep track of the ID the client is touching (keeping in mind that ClientDisconnect also fires for each client on map change).

Thanks for your feedback and I appreciate your lateral thinking. Sorry for not being more clear but yes, it's allowed for a client to touch multiple triggers at the same time. Not only this, but it's also important that the plugin detects what trigger was touched the instant it occurred (as oppose to retroactively detecting it at some later event). This is because I'm developing a special timer plugin unlike the ones that exist so far.

[friagram]

I have a mod that uses zones.

I store the zones in a dynamic array, but most overhead occurs only in external native calls (infrequently).
Since on/off touch fires very infrequently, its fine to use dynamic arrays.
Almost everything can be done by getting one cell from a dynamic array on/off touch, I just use an integer to store flags. You could store this informstion in a netprop also, (like m_inname or possibly some unused int) but this would have overhead also. Again, you can store the flags count for each client, so you know how many zones of that type they are in, and overlaps are accounted for.

The dynamic arrays are not *that* slow. And unless you are doing several thousands of operations a second, you're not going to notice anything. I assume the problem with the dynamic arrays is that it is not contiguous, so it takes longer to calculate the memory location... The more fragmented, the slower, as it had to iterate over an index of memory ranges to find where the data is. I really have no idea. I don't think you can multiply indexes in arrays to calculate multidimensional cells like you can in c. Either that, or it is contiguously allocating the arrays like malloc/calloc, but then using realloc each time the array is resized. If this is the case, there is even less overhead overall (as add/remove is done less frequently than simple retrieval). This would probably be the better solution, but again I don't know and am a shit c programmer.

When you allocate something contiguously, you can find it simply by multiplying the start address by the size of each cell.

[Bugzy]

Originally Posted by friagram I have a mod that uses zones. I store the zones in a dynamic array, but most overhead occurs only in external native calls (infrequently). Since on/off touch fires very infrequently, its fine to use dynamic arrays. Almost everything can be done by getting one cell from a dynamic array on/off touch, I just use an integer to store flags. You could store this informstion in a netprop also, (like m_inname or possibly some unused int) but this would have overhead also. Again, you can store the flags count for each client, so you know how many zones of that type they are in, and overlaps are accounted for. The dynamic arrays are not *that* slow. And unless you are doing several thousands of operations a second, you're not going to notice anything. I assume the problem with the dynamic arrays is that it is not contiguous, so it takes longer to calculate the memory location... The more fragmented, the slower, as it had to iterate over an index of memory ranges to find where the data is. I really have no idea. I don't think you can multiply indexes in arrays to calculate multidimensional cells like you can in c. Either that, or it is contiguously allocating the arrays like malloc/calloc, but then using realloc each time the array is resized. If this is the case, there is even less overhead overall (as add/remove is done less frequently than simple retrieval). This would probably be the better solution, but again I don't know and am a shit c programmer. When you allocate something contiguously, you can find it simply by multiplying the start address by the size of each cell.

Thanks so much for helping out again! I admit linear time for indexing a dynamic array was a gross estimation but I couldn't find info on how it's implemented, so I began to worry that maybe a linked list was used. Your explanation of why dynamic arrays are considered slow is because they probably use realloc in the background does make sense. Hence, from a more optimistic standpoint, I think it would be worthwhile, post-initialization to use SortADTArrayCustom and thereafter use binary search to index the array. This will whittle indexing time right down to O(2 * log_2(n - 1)). With respect to the fact that the game engine can only store a maximum of 2048 edicts, the maximum number of comparison will be 22, which might as well be constant time.