🔒 Speedup Algorithm w/Pandas + Numpy (Optimization)

[timid solar]

I have a piece of code which parses a large JSON containing ~30000 shot events (a list of dicts) occurring in a Battle Royale match and returns the shots with intent to hit an opponent. It estimates this using heuristics.

I'm working with two separate event logs for the same match:

1. match_shot_events.json: all the shot events throughout the match (sparse data)
   • Relevant fields: timestamp, (x, y, z) of the impact
2. match_movement_events.json: the movement events (positions) of every player recorded at ~400 ms intervals throughout the match (dense data)
   • Relevant fields: timestamp, (x, y, z) of the player

Current algorithm:

• Go through the movement events (positions) once, mapping each player ID to a list of their movements events sorted by timestamp
• For each shot event
  • Get position of shooter at time of shot (binary search)
  • For each opponent player:
    • Get position at the time of the shot (binary search)
    • Compute direction vector and bullet ray
    • Surround position in sphere
    • Check if ray intersects sphere (constant time) and if it does, add it to the return list

The current implementation uses plain python and takes 15 minutes to run. I'd like to speed that up if possible, but I'm not sure how to. Any help would be appreciated.

[gloomy nest]

Please react with ✅ to upload your file(s) to our paste bin, which is more accessible for some users.

[gloomy nest]

@timid solar

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[dire oasis]

could you send samples of the data?

you might also have better luck if you ask in #algos-and-data-structs

[timid solar]

Example of movement event:

    {
      "matchId": "832ceecc424df110d58e3e96d3dff834",
      "serverId": "84036a6372404c5f9334a94ec2f38f25",
      "syncPartitiontime": 1745706109435908,
      "timestamp": 1745704850671112,
      "epicId": "c17bac91e57e4ab58cc5c4e9d846afc5",
      "npcId": 0,
      "movementData": {
        "isSprinting": false,
        "isCrouching": false,
        "isAiming": false,
        "isSkydiving": false,
        "isGliding": false,
        "isSwimming": false,
        "isJumping": true,
        "isInteracting": false,
        "isEmoting": false,
        "isInBus": false,
        "isInVehicle": false,
        "rotationYaw": 196.49348,
        "location": {
          "x": 13692.67,
          "y": -49364.51,
          "z": 2214.6
        },
        "rotationPitch": 0.31860837
      }
    },

Example of shot event:

    {
      "matchId": "832ceecc424df110d58e3e96d3dff834",
      "serverId": "84036a6372404c5f9334a94ec2f38f25",
      "syncPartitiontime": 1745706109435908,
      "timestamp": 1745704867536878,
      "epicId": "34009ee20b024cfb843d984e5b9b30aa",
      "weaponId": "WID_Harvest_Pickaxe_WinterCamo_Athena",
      "damage": 50,
      "harvest": true,
      "hitPlayer": false,
      "hitCritical": false,
      "hitPlayerBuild": false,
      "hitEpicId": "",
      "hitFatal": false,
      "hitShield": false,
      "hitBallistic": false,
      "destroyedShield": false,
      "location": {
        "x": 3585,
        "y": -60959,
        "z": 3181
      },
      "hitResult": "HIT_UNKNOWN",
      "itemEntryGuid": "B01E7A59-F84F-4612-9852-BB5BF046E957",
      "actualDamage": 50,
      "hitActorId": 0
    },

[dapper copper]

So how are positions determined @timid solar , is it with ticks? For example, can you calculate the position of all players at each tick?

Or are you calculating the positions yourself based on movements at timestamps and initial position?

There are two directions we could go:

1. We can vectorize the process, and utilize numpy. This requires us to put the data in a certain structure.
2. The process is highly sequential, we could use numba.

[timid solar]

get_closest is used to get the position of every player closest to the shot timestamp
so yes, I can effectively get the "last known" position of a player for a tick in logarithmic time

[dapper copper]

Do you want the closest timestamp position?

Not the one closest "Before*" ?

I assume the position is valid until another event has happened right?

[timid solar]

It goes both directions, I just want the nearest one within a certain tolerance.
For example, if a shot occurs at 5000 milliseconds, and the position of player A was recorded at 4600 and 5100 milliseconds, I want to use the second movement event.

[dapper copper]

So player position is tracked at certain intervals, not when the player moves?

[timid solar]

I think the game tracks the positions at regular time intervals while they are moving

[dapper copper]

Also, one quick improvement I see is that your get_closest is not log, its linear. :
timestamps = [e["timestamp"] for e in events]

Consider making an array once, and not for every function call

[timid solar]

Good catch, thanks

[dapper copper]

How many timestamps are there in total for a game (ballpark guess)? And are the positions know for all players for these timestamps?

And did you run a profiler to see what part is slow? It may just be reading a json with move events f.e.

[timid solar]

❯ jq '.hitscanEvents | length' data/raw/match_shot_events.json
33552
❯ jq '.events | length' data/raw/match_movement_events.json
176671

[dapper copper]

11 players?

A movement event for each player for each timestamp?

[timid solar]

where did you get 11 players from

[dapper copper]

176671 is divisible by 11. It could hint towards my second question

[timid solar]

there are 98 players

[dapper copper]

Ah alright, that is not the case then

[timid solar]

but some died during the match and no movement events were recorded for them afterwards

[dapper copper]

Right

[timid solar]

also this could be another speedup by no longer evaluating dead players as candidates but I'll get to that later

[dapper copper]

My idea would be to make a (n_players, n_timestamps, n_dims) matrix with the positions. (n_dims would be 3, xyz)

So if you could fill such a matrix. Then we could very quickly query it later on with timestamps

Can I ask what this is for btw? Could I perhaps get that json with the positions to see what the data is like?

[timid solar]

This is just Fortnite hobby related, a company called Osirion wrote a parser for Fortnite's .replay files and I got the data through their API. I can send you the jsons

[dapper copper]

Send me a json in Dms, and maybe a link to the API for the description.

[timid solar]

I might not be able to though because it's like over 100 MB. Also, their API isn't free.

[dapper copper]

The movement event one is 100MB>?

[dapper copper]

1s

import json
from pathlib import Path
from typing import Any, Dict, List


def filter_to_timestamp_and_location(records: List[Dict[str, Any]]) -> List[Dict[str, Any]]:
    filtered: List[Dict[str, Any]] = []

    for record in records:
        if not isinstance(record, dict):
            continue

        timestamp = record.get("timestamp")
        movement_data = record.get("movementData")
        location = movement_data.get("location") if isinstance(movement_data, dict) else None

        if timestamp is None or not isinstance(location, dict):
            continue

        x = location.get("x")
        y = location.get("y")
        z = location.get("z")
        if x is None or y is None or z is None:
            continue

        filtered.append(
            {
                "timestamp": timestamp,
                "location": {"x": x, "y": y, "z": z},
            }
        )

    return filtered


if __name__ == "__main__":
    with open("match_movement_events.json", "r") as f:
        data = json.load(f)

    filtered = filter_to_timestamp_and_location(data)

    with open("match_movement_events_filtered.json", "w") as f:
        json.dump(filtered, f)

Could you run this to filter the data?

Make sure to change the path to the input data if your script is not in same folder as the data

[gloomy nest]

Python help channel closed for inactivity

This help channel has been closed. Feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.