playing 40.000 unit army for game [closed]

Question

SOLVED!! (look at my last edit)

I want to make an army fight of 20.000 vs 20.000 units on canvas. So, for every unit data is:

{ 
'id' => 17854,
'x' => 1488, 
'y' => 1269, 
'team' => 'red', 
'health' => 10,
'target' => [1486, 1271]
}

And i would to see this fight in real time (25 frames per second). If i generate 1 frame with Json and save on file, it is 2.5mb size (40k such units with this data).

1 second(25 frames) = 62.5 mb file size. And the fight could last about 30 minutes, so it should use 112gb. This is bad. If i would make the file as binary data, it should take 27 times less place, or 4gb for 30 mins. That's still bad. 2 hrs movie takes 700mb.

I need to save many fights on server. Real players should make their armies and fight each other, so i need the fights to be saved. Every fight is unique, because every damage of every unit is random 0~10 and after unit kills an enemy, it regenerates 1 health. I'm doing calculations with PHP and saving files on server. All 40.000 units are on one screen, all can be visible at once, i want it like that. For now, units are single 2x2 pixel cubes, red and blue teams, its easy to load for javascript.

But, to generate file with PHP i need about 1 hour. That's another problem. Because for every frame i need to iterate these 40.000 units (for updating x/y, searching for nearby enemies or friends, then for doing damage and returning target or killed enemy coordinates), then iterate over again to unset killed units, and before putting all that into file, i need to iterate over everything and remove unused data that was used for calculations. And to finish this 30 mins fight i need to repeat it 45000 times. Also, every minute there are less and less units. But my point is somehow to make all that file generating in less than a minute, just need a logical way, if some exist.

Questions:
1) What is the best way to save my files on server and make the files much less on size? (so far is to use binary data and compress to zip)
2) what is the fastest way to calculate my fights? (so far is to compile with C++)

// Edited. Here is my whole game code, just like that :)

This is main action:

class Simulator
{
    private $units;
    private $places = [];
    private $oldPlaces = [];

    public function initiateGame() {
        $this->createUnits();
        $this->startMoving();
    }

    private function createUnits() {
        foreach(range(0, 150) as $column) { // i like exact army formation to look nice, so its 150x140=21000 units
            foreach (range(0, 140) as $row) {
                $this->setUnits($column, $row);
            }
        }
        $this->oldPlaces = $this->places;
    }

    private function setUnits($column, $row) {
        $beginning_of_team_A = 6; //starting point on canvas for A unit to look nice on screen
        $unit_size_and_free_place = 6; //unit size= 3x3 (look js), and free place between each unit is 3 pixels.
        $beginning_of_team_B = 1100; // next side where enemy army starts appearing
        $x_a = $beginning_of_team_A + $column * $unit_size_and_free_place; // team A
        $y = $beginning_of_team_A + $row * $unit_size_and_free_place; // same for both teams
        $unitA = new Unit($x_a, $y, 1); // 1 is team A (it goes always +1 pixel every frame)
        $this->units[] = $unitA;
        $x_b = $beginning_of_team_B + $column * $unit_size_and_free_place;  // team B
        $unitB = new Unit($x_b, $y, -1); // -1 is team B (it goes always -1 pixel every frame)
        $this->units[] = $unitB;
        $this->places[$x_a.','.$y] = 1; // now that way tracking units, and calculating their next move
        $this->places[$x_b.','.$y] = -2;
    }

    private function startMoving() {
        set_time_limit(30000); // by default after 1 minute it throws exception
        foreach(range(0, 400) as $frame) { //giving 400 frames is like 400/40=10 seconds of action
            $this->places = [];
            foreach($this->units as $unit) {
                $returned = $unit->move($this->oldPlaces); //giving whole units list to every unit to look forward
                $this->places[$returned[0]] = $returned[1]; // returns (next x/y position as string ['1514,148'] ) = ( id as int [15] )
            }
            file_put_contents('assets/games/'.$frame.'.json', json_encode($this->units)); // writing into file  every frame and it uses ~2mb
            $this->oldPlaces = $this->places; //resetting old positions
        }
    }

}

This is unit:

class Unit
{
    public $x = 0;
    public $y = 0;
    public $team = 1;
    public $stopped;

    public function __construct($x, $y, $team, $stopped = false) {
        $this->x = $x;
        $this->y = $y;
        $this->team = $team;
        $this->stopped = $stopped;
    }

    public function move($places) {
        $this->checkForward($places);
        return [$this->x.','.$this->y, $this->team];
    }

    private function checkForward($places) {
        $forward = $this->x + $this->team; // TODO: find out formula to replace the 4 ifs
        $forward1 = $this->x + $this->team*2;
        $forward2 = $this->x + $this->team*3;
        $forward3 = $this->x + $this->team*4;
        if(isset($places[$forward.','.$this->y])) {
            $this->stopped = true;
        } else if (isset($places[$forward1.','.$this->y])) {
            $this->stopped = true;
        } else if (isset($places[$forward2.','.$this->y])) {
            $this->stopped = true;
        } else if (isset($places[$forward3.','.$this->y])) {
            $this->stopped = true;
        } else {
            $this->stopped = false;
        }

        if($this->stopped == false) { // move forward it is not stopped
            $this->x = $this->x + $this->team;
        }
    }
}

This is js:

var app = angular.module('app', []);

app.controller('game', function($scope, $http, $interval) {
    var canvas  = document.getElementById("game"),
        context = canvas.getContext("2d");
    var frame = -2;
    $scope.attacking = false;
    var units = [];

    function start_animation_loop() {
        $scope.promise = $interval(function() {
            if($scope.attacking == true) {
                frame ++;
                if(frame >= 0) {
                    downloadFile();
                    animate();
                }
            }
        }, 40 );
    }

    function downloadFile() {
        $http.get('assets/games/'+frame+'.json').success(function(response) {
            units = response;
        });
    }

    function animate() {
        clear_canvas();
        draw();
    }

    function clear_canvas() {
        context.clearRect(0, 0, 1800, 912);
    }

    function draw() {
        for(var a=0; a<units.length; a++) {
            context.beginPath();
            context.fillRect(units[a]['x'], units[a]['y'], 3, 3);
            if(units[a]['team'] == 1) {
                context.fillStyle = 'red';
            } else {
                context.fillStyle = 'blue';
            }
        }
    }
    start_animation_loop();

});

SOLVED! Thx to my colleague in my work! He gave me brilliant idea!

To get the result i needed i just need for every next battle to generate random number (0~10000) and place it into single MySQL database. In addition also put there formations, units, their starting strength, health and everything else.
And all the calculations do with javascript:
With one constant number (given from backend) i make a formula to always reproduce same army fight -> every unit will move forwards and they always stop at the same time anyways no matter what the calculation. The uniqueness is the random damage every unit gives and what process after. And all the damage will be just their "x/y position somehow compared to constant number" and do whatever to get single damage, random for every unit because they all are in different map positions, but damage will always be 0~10. With the same constant number, all units will always do the same damage after calculation and always will move same at every replay, die and do same damage at every replay. All the hardest work will be on javascript - to make calculations using this constant number.
My random number can be any. If first fight i generate random number "17", and next battle i generate random number "19666516546", it will not mean that battle with number "17" will do less damage - they all will do the "random" damage 0~15 to every unit, but replays with same formations, unit numbers, starting position and this random generated number will be always the same -> no more need to save any files! And i can add various spec effects, add something like defences, evasions, and all will fit in two MySQL rows - for every team :) Cool!!

Answer 1

id can be implicit in the storage medium. Sure, that means you have to save gaps, but you can compress said gaps.

'x' => 1488, 
'y' => 1269, 

depending on the canvas size, this can be compressed. If the canvas is 1e6 x 1e6 (a million by a million), there are 1e12 locations, which fits in ~40 bits.

'team' => 'red', 

with 2 sides, this is 1 bit.

'health' => 10,

the vast majority of units have a low health. So what we can do is that units with a health < 15 are stored in 4 bits. If all the bits are set, we have to look up the units health elsewhere (with an id->health table).

'target' => [1486, 1271]

We could store an independent target for each unit, but that probably doesn't match how the UI works. You probably select a pile of units, and tell them to go somewhere, no? ~40 bits for a location, ~24 bits for a reference count, for 8 bytes per target.

If we give each side a limit of ~65k targets, that is 16 bits.

16+4+1+40 = 61 bits. Which means we have 3 more bits to play with to pack them into a 64 bit per unit.

At 64 bits per unit, that is 160k per side. Plus up to half-a-meg of target data, but that can be handled dynamically.

Plus a health overflow table (that maps id to health), which should usually be close to empty. If you do this sometimes, you can set up before-after id maps to maintain a consistent history (say, when half the units are dead, you do a compression pass with a before-after id mapping).

If id need not be consistent, you can compress the units down so that they are no longer sparse.

The target trick -- the target could be a unit ID if less than 40,000, and if above that value it would be a waypoint. That reduces your waypoints to ~15k ones. (I was assuming target was set by the UI, where someone would select a chunk of units, an order them to go somewhere).

You'd want to iterate over the packed data, skipping "dead" units (bitmask on health), unpacking them into a usable structure, evaluating their action, and writing them back. Double-buffering is an option (where you read from one buffer, and write to another), but it has a modest cost. Because units are fixed size, you can lookup other units fast (and unpack them), which helps if your targets are other unit ids, and with things like doing damage.

Single-buffering makes things easier, because things like simultaneous damage are tricky. It does mean that lower-id units act first -- you can fix this by flipping a coin each turn to determine if you iterate forward or backwards (and stick one side in low-ids, the other in high-ids), or make that an initiative check at the start of combat.