Efficient Vehicle Looping
#1

Let say I have scripted it so when you press KEY_WALK (LALT), the boot of a vehicle you are standing near opens.

To do this, I need to loop through all vehicles, get their position, get the offset for the boot, get the player’s position, then get the distance between the two and check if they are in range.

I’d like to discuss the most efficient method to do this. The way I see it, there are two options:

Option 1:
Loop through every vehicle and check if it is in range.

Option 2:
When a vehicle streams in for a player (OnVehicleStreamIn), add the vehicle ID to an iterator, then use that in the loop instead.

Option 2 would obviously make it more efficient when the button is pressed, but I want to look at the whole picture.

Is it more efficient to have frequent 2000-iteration loops, or to have constant iterator adding/removing as vehicles are streamed in and out? Think about if there were 100 players on the server; there would be constant vehicles streaming in and out – probably hundreds every few seconds.

I personally think option 2 (Iterator) is more efficient, as even if it is called frequently, it won’t stop the PAWN thread like the raw loop will.

Thoughts?
Reply
#2

I used a streamer for that..attached an area to each vehicle then instead of the vehicle you need to check each
...area..oww wait..lol then youll still have to loop through every area nvm XD

anyway thats how i did it.

Edit: option 2 works only once i guess..what happens if you already streamed in and want to do something with the vehicle again ?
Reply
#3

http://forum.sa-mp.com/showpost.php?...7&postcount=16
Reply
#4

https://sampwiki.blast.hk/wiki/IsVehicleStreamedIn

I use this and its other variants.


Also, if you don't have 2k vehicles at your server, just decrease your MAX_VEHICLES definition.
Reply
#5

Quote:
Originally Posted by Tamer
Посмотреть сообщение
https://sampwiki.blast.hk/wiki/IsVehicleStreamedIn

I use this and its other variants.
Would that be more efficient than a distance check? I assume so. But still, is a 2000 loop of that more or less efficient than the Iterator?

Quote:
Originally Posted by Tamer
Посмотреть сообщение
Also, if you don't have 2k vehicles at your server, just decrease your MAX_VEHICLES definition.
It's likely that I will have 2000. I may even need a vehicle streamer.
Reply
#6

Quote:
Originally Posted by MP2
Посмотреть сообщение
Would that be more efficient than a distance check? I assume so. But still, is a 2000 loop of that more or less efficient than the Iterator?


It's likely that I will have 2000. I may even need a vehicle streamer.
If you will make that streamer as a plugin then I am sure you can loop through the vehicles much more easier, by saving data related to the vehicle to the memory, so in a way using an iterator would be useful if done in a plugin. For example, mark where a vehicle is, dividing the map to sections and saving at which area is a vehicle at etc.

A position check would take much longer than checking stream status and then checking positions, because isn't stream status taken from the client / server pool?

You should do some benchmarking.
Reply
#7

It's standard memory vs performance. For iterators you'd need MAX_PLAYERS * MAX_VEHICLES memory cells (as multiple people can see shared vehicles), so for example if you need 2000 vehicles for 50 players, you already take up 10000 cells. Not to mention adding and removing them from your collections. I doubt everybody will press that button all the time, so I'd say computing it on the fly would be more performant. Also IsVehicleStreamedIn is a native function, so it shouldn't be much overhead. BUT, if you are still worried about performance, you might split your map into areas, and keep track of which vehicle is in which area. Then, just check current player area + neighbouring areas + IsVehicleStreamedIn for maximum performance. I'm not certain, but maybe your particular vehicle streamer contains some function like GetVehiclesStreamedForPlayer?
Reply
#8

Loop through the streamed vehicle IDs of the player and check if player is staying behind it or not. If the player is, store the vehicle ID and remove if not. Option 2 was what I thought at first, but this might help you with performance and will cost only a few memory.
Reply
#9

I think I will just keep the loop with IsVehicleStreamedIn for now. That button won't be pressed much. I also have a time limit of 3 seconds on it, as you shouldn't need to press it that fast. I will also use GetVehiclePoolSize, although eventually the 2000 limit will be hit and it won't really be needed.

I've also made it so it checks the last vehicle you entered first, and the last known closest vehicle (from previous presses).
Reply
#10

Adding the vehicles are streamed for a player to an iterator would be probably the way I'd do it instead of looping 2k times.
Though that function seems to be nice: https://sampwiki.blast.hk/wiki/GetPlayerCameraTargetVehicle since you get the vehicle ID the player is looking at and it (most likely) will chose the closest one.
Reply
#11

Quote:
Originally Posted by Konstantinos
Посмотреть сообщение
Adding the vehicles are streamed for a player to an iterator would be probably the way I'd do it instead of looping 2k times.
Though that function seems to be nice: https://sampwiki.blast.hk/wiki/GetPlayerCameraTargetVehicle since you get the vehicle ID the player is looking at and it (most likely) will chose the closest one.
Ah, never thought of that, thanks. I will make it check that vehicle FIRST, but not ONLY that vehicle as they may not be looking at it.
Reply
#12

Honestly I just scanned through the front page.

There are 2 efficient ways to do this.

1. GetPlayerCameraTargetVehicle but this forces the player to look at the vehicle (which it should be anyway) so this function is perfect..

2. Track all streamed in vehicles for each player using StreamIn and StreamOut callbacks, (I suggested this with some filterscript iPleomax made awhile ago) it's really efficient compared to looping through 2000 vehicles on a normal server.
Reply
#13

2,000 iterations isn't that much. Just saying.

pawn Код:
new
    tick = GetTickCount();

for (new i = 0; i < 50; i ++)
{
    for (new j = 0; j < 2000; j ++)  {  }
}

printf("%d ms", GetTickCount() - tick);
This code runs a loop with 2,000 iterations 50 times, which comes out to 100,000 iterations in total. This only takes 1-2 ms.

Now depending on the code you'll have in there, you'll probably dealing with less than 50 milliseconds of code execution time.

In my experience, this is the best way:

pawn Код:
for (new i = 0, j = GetVehiclePoolSize(); i <= j; i ++)
{
    if (!IsValidVehicle(i) || !IsVehicleStreamedIn(i, playerid))
        continue;

    // Check if a player is near a trunk, show a dialog, etc.
}
Reply
#14

Quote:
Originally Posted by Tamer
Посмотреть сообщение
Also, if you don't have 2k vehicles at your server, just decrease your MAX_VEHICLES definition.
Have you heard of the new GetVehiclePoolSize? That function beats this recommendation by a mile. I recommend using just GetPlayerCameraTargetVehicle. It's quite realistic too considering the player MUST be looking at the vehicle. In all reality, do you stand backwards when you are opening your car's trunk? I think not! Either way, like Emmet said, 2000 is not a lot, it would take nanoseconds without any code in the loop (it's definitely not going to take much with the code, depending on the code of course).
Reply
#15

I actually am going to just use the camera target, because it works even if you aren't looking directly at the vehicle. Even if you look sideways or backwards, it still detects that vehicle as being the target.

Thanks everyone for your opinions and advice.
Reply
#16

Hey! Interesting question.

Quote:
Originally Posted by Emmet_
Посмотреть сообщение
In my experience, this is the best way:

pawn Код:
for (new i = 0, j = GetVehiclePoolSize(); i <= j; i ++)
{
    if (!IsValidVehicle(i) || !IsVehicleStreamedIn(i, playerid))
        continue;

    // Check if a player is near a trunk, show a dialog, etc.
}
This is indeed a very good way, but can be improved to use maximally ONE function call to determine whether a vehicle is valid and streamed in for the player. Since if a vehicle is streamed in for someone, it is definitely valid, the IsValidVehicle check can be omitted as it is done internally anyways (this was not the case in SA-MP 0.1 with some natives and the PAWN programmer had to implement some extra sanity checks, though).
pawn Код:
for(new i = 0, j = GetVehiclePoolSize(); i != j; i++)
{
    if(!IsVehicleStreamedIn(i, playerid)) {
        continue;
    }

    // code
}
This is a situation similar to:
pawn Код:
if(IsPlayerInAnyVehicle(playerid))
{
    new vID = GetPlayerVehicleID(playerid);
    // code
}
which can be simplified to
pawn Код:
new vID;
if((vID = GetPlayerVehicleID(playerid)) != 0) {
    // code
}
------

Coming back to the original problem, the OP has already found a viable solution by running the code infrequently, so the algorithm won't be a problem even if it is slow.

If you desire to make the 3-second interval smaller and allow the player to quickly open-close the trunk, you could, for example, keep information about vehicles close to them somewhere and recalculate that data after some interval.
If you were to do it in PAWN, it would indeed be an array of MxN (M - number of players, N - number of vehicles) cells. I believe one cell is 4 bytes (32 bits), so the array would take up 400000 cells in standard situations (200 max players with 2000 vehicles) and up to 1562 kilobytes. This is of no importance in terms of the computer memory as the heap has times more space available, but it will also make your AMX large and slow down compilation.
So it is without doubt that a standard PAWN array will not do. Even though a char array provides some relief, it would still be a pain and not very well scalable. So you'd have to look into some dynamic method of storage.

From C++, I can think of std::bitset, which would very much be your friend in such situation. For 200 players, having a bitset for 2000 vehicles would take up 400000 bits or 48 kilobytes, which is far less.


Some of my data may be a little off, it has been a while since I last did programming in PAWN.
Reply
#17

Considering that a player will at max open the hood every few minutes in average, the MAX_VEHICLES loop will be much more economic after all. Iterators might sound fast, but they will eat up a lot of RAM (as pointed out before), and depending on how youre realizing them they are really slow. Removing a vehicle from the iterator means finding its index first, and then shifting the index of all following vehicles (though the pointer relocation method is a good way for array shifting). And as there might be dozens of vehicles streaming in and out each streaming tick for each player this would cause a huge amount of extra work for the server, even if noone opens a hood.

Iterators are only useful for "slow data", like player joins or vehicle creations, but not for data that changes thousands of times every second.

Quote:
Originally Posted by AndreT
Посмотреть сообщение
From C++, I can think of std::bitset, which would very much be your friend in such situation. For 200 players, having a bitset for 2000 vehicles would take up 400000 bits or 48 kilobytes, which is far less.
A bitset actually would have little to no advantages compared to the common loop

pawn Код:
// Common attempt
for (new i = 0; i < MAX_VEHICLES; i++) {
    if (!IsVehicleStreamedIn(i, playerid)) continue;
}

// Bitset (some pawn/c++ pseudo mixup)
for (new i = 0; i < MAX_VEHICLES; i++) {
    if (!bitset_playervehicles[playerid].test(i)) continue;
}
Reply
#18

just delete this reply pls
Reply
#19

Quote:
Originally Posted by Crayder
Посмотреть сообщение
Have you heard of the new GetVehiclePoolSize? That function beats this recommendation by a mile. I recommend using just GetPlayerCameraTargetVehicle. It's quite realistic too considering the player MUST be looking at the vehicle. In all reality, do you stand backwards when you are opening your car's trunk? I think not! Either way, like Emmet said, 2000 is not a lot, it would take nanoseconds without any code in the loop (it's definitely not going to take much with the code, depending on the code of course).
Oh yeah, this can be used aswell. Forgot it.
Reply
#20

Quote:
Originally Posted by Mauzen
Посмотреть сообщение
A bitset actually would have little to no advantages compared to the common loop
pawn Код:
// Common attempt
for (new i = 0; i < MAX_VEHICLES; i++) {
    if (!IsVehicleStreamedIn(i, playerid)) continue;
}

// Bitset (some pawn/c++ pseudo mixup)
for (new i = 0; i < MAX_VEHICLES; i++) {
    if (!bitset_playervehicles[playerid].test(i)) continue;
}
I did not mention an advantage over looping with function usage. I mentioned a clear memory consumption advantage vs the regular PAWN array -- 32 times less memory usage (technically, I assume the container keeps some other properties to satisfy the standard requirements). That is, after all, if you're going to have an array around, if someone's an advocate of that approach. So my text about bitset was just in case someone is going to need an array for some situation, there's no need to allocate 32bits for what can fit in 1bit.

Back to the original point, as I said, it is an infrequent algorithm so don't spend time optimizing it if you're not going to get it back from run-time gains.

Good luck.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)