PDA

View Full Version : An algorithm for vehicle streamers


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?

Joe Staff
10/10/2011, 08:17 PM
Should also consider the Grid System. Think of it as standard location except much smaller. Example, X coordinates 0 through 100 is 0, 100 through 200 is 1. By setting the 8 grids surrounding each player for streaming, you could search through vehicles and stream the ones who Grid corresponds with grids set for streaming

Example:
v = Vehicle not streamed
V = Vehicle is streamed
P = Player
S = Streaming no vehicles


5 [ ][ ][ ][ ][ ][ ][ ][ ][ ]
4 [S][S][S][ ][ ][ ][S][S][S]
3 [S][P][S][v][ ][ ][V][P][V]
2 [S][S][S][ ][ ][ ][S][P][S]
y 1 [ ][ ][ ][ ][ ][ ][S][S][S]
x 1 2 3 4 5 6 7 8 9


Using this, you don't have to determine distance, just stream the 8 grids around a player's grid

Example:
Player X,Y = 300,400
Convert X,Y = 300/100,400/100 //If X or Y coordinate is negative, subtract 1 for consistency
Grid X,Y = 3,4

So player grid = 3,4
just stream the surrounding grids

6 [ ][ ][ ][ ][ ]
5 [ ][S][S][S][ ]
4 [ ][S][P][S][ ]
3 [ ][S][S][S][ ]
2 [ ][ ][ ][ ][ ]
y 1 [ ][ ][ ][ ][ ]
x 1 2 3 4 5

Streamed Grids:
2,3
2,4
2,5
3,3
3,4 -- Player's Grid
3,5
4,3
4,4
4,5


ADDITIONAL:
Also note that you only have to stream vehicles that players are not in, which means you only need to obtain their coordinates once a player has exited the vehicle or if the vehicle spawns.


I used this system to create a 3D Text streamer, worked flawlessly but was never able to stress test it properly