Hi guys,

I'm fiddling with yet another xi4n plugin (a fully automatic TV director) - but I want it to work properly on tracks without nodes (i.e. BL1X).

One problem I want to solve is how to predict when something interesting is about to happen. For that I kinda need nodes to make what I want do-able in a practical sense - calculating the distance and closing speed between close players on the track, and doing it for all racers is just ridiculous (if you're not seeing why I suggest you run the numbers of calculating the distance between every racer on a 32 slot server, assuming it's full).

So I've come up with 2 solutions thus far for creating pseudo-nodes;

1. A basic grid system that basically rounds the racers x,y,z coords to the nearest "chunk" (at the moment about 20x20 in-game units/meters) and then I query all racers in that chunk. The problem is that it's really dumb and doesn't take into account the shape of the track, or cross overs (I could make it cleverer, by making it a 3D chunk to solve). It's pretty quick, however, but the real issue is that a chunk might only have a very small amount of track in it, because it doesn't take into account the shape of the track. I've put together a quick prototype and it sort of works, but because of the shape issue it's not good enough in my opinion. Increasing the size of the chunk makes things more usable, but still suffers from the same problem.

2. A 3 dimensional KD tree, built when the track is loaded, from the relevant track or layout PTH file - i.e. I take every Nth x,y,z coord from the PTH file and use that as the center point for my node). Using this I can actually get the players nearest a particular node with minimal calculations (thats the point of a KD tree). By grouping the racers every update I can make a pretty good assumption that the racers in the same pseudo node are actually racing each other. The problem is I don't fancy writing a 3D KD tree implementation this afternoon unless I absolutely have to, plus it requires a PTH file. More over, if you're on a remote insim connection, you don't get the PTH file thats loaded, so it would need to be a manual process selecting it - this seems a little sucky. The major benefit is that you really do get a pseudo node, like you would normally, and it's reasonably quick to determine which node a player is closest to. Generating the KD tree might be a little slow, but I think it'll be acceptable since it can probably be pre-calculated, or calculated on track load.

So I ask you, if you've thought about this even a little have you considered any options that I might've dismissed?

Bear in mind I've not got a compsci degree, so I'm acutely aware that I'm lacking in some of my structures knowledge and I'm kinda expecting that I've missed something.

Or have I just got hung up trying to create pseudo nodes and I'm missing something really obvious?

What about just shipping the PTH files with the application? Would that not just solve your second problem out right? Or is it that you want an always available fall back mechanism, should a third part connect to a server they don't own? Like how your using XI4N on the cargame server.

So, going with the calculation of 32 clients on the server and getting closing speed of all of them even just 1 time a second is not really feasible. So that's out of the question. (For those wondering, it's like 26313083700000000000000000000000000 calculations to get the information for every player vs every other player.) I think that, using each MCI cords, finding the number of client's within a 25 meter radius of each player and prioritizing by the group the has the most amount of players in each area. Then from there, you only have to find the closing distances of the players within these radius giving you the a much less to calculate. However, if you find that there is more then say 10 clients in a single 25 meter radius of a single client, then you should just look at that group. Closing distances are not really needed, and would become problematic to calculate. But making that a 'threshold' variable might be a good idea so that you can play with it while you develop it. Doing the same for the radius search would be good too.

Just a sidenote, mutual distances of 32 cars would need 496 calculations (because when you know A->B you also now B->A) which is rather bad, but perhaps not as bad to justify the usage of a K-D tree plus it will give you the most accurate information about closure speeds and distances...

I admit I can't really imagine what sort of logic are you planning to use to check if "there is something going on", but wouldn't you need a rather dense tree to get any useful data?

EDIT:
I didn't really think this through, but perhaps an algorithm working solely with distances could be optimized even further. Imagine a following situation:

There are 6 cars on the track (A - F) and we want to know of some of them are close enough to be considered fighting for position. A fully unoptimized junk needs 30 calculations to get all the distances, assumption A->B == B->A gets it down to 15. This is OK for 6 cars, but still too much for 32. A following idea crossed my mind.

1) Calculate distances from A->B to A->F
2) If (abs((A->N - A->(N+1)) < threshold)), add cars N and N+1 to a "preliminary" group
3) Check if car A could belong to some group
4) Run distance checks for all preliminary groups and remove too distant cars.

Checking the distance AND the direction to increase the accuracy of "preliminary" groups sounds like too much of an overhead to me because of the floating point maths that's involved (this algorithm could work only with ints). I'm really sorry I don't have time to try to implement such an algorithm, but I reckon it could be reasonably efficient with larger grids (or I missed something stupid and you're trying hard not to chuckle right now).

Quote from Dygear :

always available fall back mechanism, should a third part connect to a server they don't own? Like how your using XI4N on the cargame server.

Pretty much, but tbh I can't see a solution, so I'm with you on just shipping the PTH files with it tbh Sorry, I kinda dumped my brain out on that bit of the post and never went back to edit it before posting

Quote from Dygear :

I think that, using each MCI cords, finding the number of client's within a 25 meter radius of each player and prioritizing by the group the has the most amount of players in each area.

Pretty much what I'm trying to solve with a pre-calculated KD tree of track points at the moment - on paper it should be quicker than finding and grouping for each player But, you never know - I'll mock something up and see if it really is faster - I'm notorious for cocking up math sometimes

Quote from MadCatX :

Just a sidenote, mutual distances of 32 cars would need 496 calculations (because when you know A->B you also now B->A) which is rather bad, but perhaps not as bad to justify the usage of a K-D tree plus it will give you the most accurate information about closure speeds and distances...

From what I had tested it seemed to be worth while fiddling with some sort of tree, but it's really without actually having written a full tree implementation yet. Bear in mind I'm not planning on making a tree of racers, just points on the track and then finding their nearest known point on the track in order to group vehicles and then doing the logic from the groupings. I'm reasonably confident that can be fast enough to run every few seconds - after all you don't want the camera hopping about too much

Quote from MadCatX :

I admit I can't really imagine what sort of logic are you planning to use to check if "there is something going on", but wouldn't you need a rather dense tree to get any useful data?

I'm more interested in grouping vehicles and then focusing on the largest group, as stage 1 - then trying more complex things from there, plus it gives me a good option for chopping down the number of calcs for the *interesting* stuff pretty quickly I hope.

Quote from MadCatX :

There are 6 cars on the track (A - F) and we want to know of some of them are close enough to be considered fighting for position.

I'd dismissed something like this early on because I'm also interested in lapping vehicles (which I could get from IS_FLG I suppose) and much faster vehicles coming through the field after an accident/pit stop/whatever - I couldn't see a reasonable way of supporting this with little extra work at the time, which is why I'd landed on grouping using pseudo-"wide" nodes. However I've realised I've kinda missed the obvious..

However, I will be honest your idea has me interested.

I'll see if I can find the time for some rough prototyping and see what comes out in a head to head battle between the 4 ideas

Cheers for taking the time to respond guys, I really do appreciate it <3

So something I wished that I had realised much, much earlier on is the rather obvious fact that some of these ideas are only as good as the quality of your pth files - which for my purposes are sometimes appalling it turns out.

I'm aware of the solution, but this 'ere head to head is taking longer than I planned