Double-O-Seven

10/10/2011, 08:07 PM

Hi.

Maybe noone uses a vehicles streamer nowadays since you can already have 2000 vehicles.

Now I was thinking about a vehicle streamer.

I've already made such a streamer years ago.

This streamer had a naïve streaming algorithm:

Looping through all vehicles, and than looping through the players to check if there's a player in range.

Now my new idea for an algorithm:

- Keep a sorted array of all connected players (may include bots), sorted by x- or y-coordinate.

- You can update a players position in the array in OnPlayerUpdate. In most of the times, not much will happen (not many distance checks and swaps for this.)

- Now, you still need to loop through all vehicles to check if a vehicle should get streamed in or streamed out:

To do this, you can use binary search to search the two closest players in the array of players (just search for the vehicles x coordinate in the array of players which is sorted by x and you will automatically end up between the two closest players).

The good thing about this is, you only have two compare x coordinates, no distance calculation.

Next, you only have to check left and right at the position in the player array and see if any player is close enough.

This algorithm is much more efficient than looping through all vehicles and players because it uses efficient searching for players and range. It is also memory efficient.

The naïve algorithm has a runtime of O(n * m) where n is the number of vehicles and m the number of players.

While this new algorithm has a runtime of O(n * log m) (if you assume that the players are spread all over SA).

This is just for inspiration for interested people.

I wanted to make this myself but I can't find time for something like this.

Maybe someone else will try it?

Maybe noone uses a vehicles streamer nowadays since you can already have 2000 vehicles.

Now I was thinking about a vehicle streamer.

I've already made such a streamer years ago.

This streamer had a naïve streaming algorithm:

Looping through all vehicles, and than looping through the players to check if there's a player in range.

Now my new idea for an algorithm:

- Keep a sorted array of all connected players (may include bots), sorted by x- or y-coordinate.

- You can update a players position in the array in OnPlayerUpdate. In most of the times, not much will happen (not many distance checks and swaps for this.)

- Now, you still need to loop through all vehicles to check if a vehicle should get streamed in or streamed out:

To do this, you can use binary search to search the two closest players in the array of players (just search for the vehicles x coordinate in the array of players which is sorted by x and you will automatically end up between the two closest players).

The good thing about this is, you only have two compare x coordinates, no distance calculation.

Next, you only have to check left and right at the position in the player array and see if any player is close enough.

This algorithm is much more efficient than looping through all vehicles and players because it uses efficient searching for players and range. It is also memory efficient.

The naïve algorithm has a runtime of O(n * m) where n is the number of vehicles and m the number of players.

While this new algorithm has a runtime of O(n * log m) (if you assume that the players are spread all over SA).

This is just for inspiration for interested people.

I wanted to make this myself but I can't find time for something like this.

Maybe someone else will try it?