<?php

ini_set("display_errors", "Off");

const ZERO_TOLERANCE = 1.0e-06;
function near_zero($value) : bool
{
    return $value > -ZERO_TOLERANCE && $value < ZERO_TOLERANCE;
}

// Generate a random value between 0 and 1
function bzfrand() : float
{
    return mt_rand() / mt_getrandmax();
}






class SimulationMath
{
    static function segmentIntersectsCircle($circleX, $circleY, $circleRadius, $lineX1, $lineY1, $lineX2, $lineY2)
    {
        // From: https://stackoverflow.com/a/1090772

        // compute the triangle area times 2 (area = area2/2)
        $area2 = abs( ($lineX2-$lineX1)*($circleY-$lineY1) - ($circleX-$lineX1)*($lineY2-$lineY1) );

        // compute the AB segment length
        $LAB = sqrt( pow($lineX2-$lineX1, 2) + pow($lineY2-$lineY1, 2) );

        // compute the triangle height
        $h = $area2/$LAB;

        // if the line intersects the circle
        return $h < $circleRadius;
    }

    // Ray-casting algorithm
    // Source: http://rosettacode.org/wiki/Ray-casting_algorithm#PHP
    function containsPoint($bounds, $x, $y)
    {
        $count = 0;
        $bounds_count = count($bounds);
        for ($b = 0; $b < $bounds_count; $b++) {
            $vertex1 = $bounds[$b];
            $vertex2 = $bounds[($b + 1) % $bounds_count];
            if (self::rayIntersectsSide($vertex1, $vertex2, $x, $y))
                $count++;
        }

        return $count % 2;
    }

    function rayIntersectsSide($A, $B, $x, $y)
    {
        if ($A[1] <= $B[1]) {
            if ($y <= $A[1] || $y > $B[1] ||
                $x >= $A[0] && $x >= $B[0]) {
                return false;
            }
            if ($x < $A[0] && $x < $B[0]) {
                return true;
            }
            if ($x == $A[0]) {
                if ($y == $A[1]) {
                    $result1 = NAN;
                } else {
                    $result1 = INF;
                }
            } else {
                $result1 = ($y - $A[1]) / ($x - $A[0]);
            }
            if ($B[0] == $A[0]) {
                if ($B[1] == $A[1]) {
                    $result2 = NAN;
                } else {
                    $result2 = INF;
                }
            } else {
                $result2 = ($B[1] - $A[1]) / ($B[0] - $A[0]);
            }
            return $result1 > $result2;
        }

        return self::rayIntersectsSide($B, $A, $x, $y);
    }
}


class BZFS {
    private $worldSize;
    private $wallSides;
    private $wallStartAngle;
    private $customWallVertices;
    private $tankRadius;

    private $xMin;
    private $xMax;
    private $yMin;
    private $yMax;

    // Statistics tracking
    private $numberOfSpawnPoints = 0;
    private $numberOfSpawnAttempts = 0;
    private $maximumNumberOfSpawnAttempts = 0;

    public function __construct()
    {
        $this->worldSize = 800.0;
        $this->wallSides = 4;
        $this->wallStartAngle = $this->customWallVertices = null;
        $this->tankRadius = 0.72 * 6.0;
    }

    public function getStats() : Array
    {
        return [
            'numberOfSpawnPoints' => $this->numberOfSpawnPoints,
            'numberOfSpawnAttempts' => $this->numberOfSpawnAttempts,
            'maximumNumberOfSpawnAttempts' => $this->maximumNumberOfSpawnAttempts
        ];
    }

    public function getTankRadius() : float
    {
        return $this->tankRadius;
    }

    public function setWorldSize(float $worldSize)
    {
        $this->worldSize = $worldSize;
    }

    public function getWorldSize() : float
    {
        return $this->worldSize;
    }

    public function setWallSides(int $wallSides)
    {
        $this->wallSides = $wallSides;
        $this->updateMinMax();
    }

    public function setWallStartAngle(float $wallStartAngle)
    {
        $this->wallStartAngle = $wallStartAngle;
        $this->updateMinMax();
    }

    public function setCustomWalls($vertices)
    {
        $this->customWallVertices = $vertices;
        $this->updateMinMax();
    }

    public function setTankRadius($tankRadius)
    {
        $this->tankRadius = $tankRadius;
    }

    private function updateMinMax()
    {
        $vertices = $this->getWallVertices();
        $this->xMin = min(array_column($vertices, 0));
        $this->xMax = max(array_column($vertices, 0));
        $this->yMin = min(array_column($vertices, 1));
        $this->yMax = max(array_column($vertices, 1));
    }

    public function getWallVertices()
    {
        // Custom convex polygon wall boundary
        if ($this->customWallVertices)
            return $this->customWallVertices;
        else {
            $halfSize = $this->worldSize * 0.5;

            // Perfect square on 90 degree rotations
            if ($this->wallSides === 4 && ($this->wallStartAngle === null || $this->wallStartAngle % 90 == 0)) {
                return [
                    [$halfSize, -$halfSize],
                    [$halfSize, $halfSize],
                    [-$halfSize, $halfSize],
                    [-$halfSize, -$halfSize]
                ];
            } // Regular polygon
            else
            {
                // Fit the regular polygon inside a circle the size of the world size
                $radius = $halfSize;
                $centerAngle = 2.0 * M_PI / $this->wallSides;
                $startAngle = deg2rad($this->wallStartAngle);
                if ($startAngle === null)
                {
                    if ($this->wallSides % 2 == 0)
                        $startAngle = M_PI / 2.0 - ($centerAngle / 2);
                    else
                        $startAngle = M_PI / 2;
                }
                else
                {
                    $startAngle -= $centerAngle / 2;
                }

                $vertices = [];

                for ($w = 0; $w < $this->wallSides; ++$w)
                {
                    $angle = $startAngle + ($w * $centerAngle);
                    $vertices[] = [
                        round($radius * cos($angle), 2),
                        round($radius * sin($angle), 2)
                    ];
                }

                return $vertices;
            }
        }
    }

    public function isCircleWithBoundaries($x, $y, $radius)
    {
        // If this is a square world without rotation, use a simple check
        if ($this->customWallVertices === null && $this->wallSides === 4 && ($this->wallStartAngle === null || $this->wallStartAngle % 90 == 0)) {
            $halfSize = ($this->worldSize * 0.5) - $radius;
            return $x > -$halfSize && $x < $halfSize && $y > -$halfSize && $y < $halfSize;
        }

        // If it's on or outside of the rectangular boundary of the polygon, it can't be within
        // TODO: Should we account for the radius here?
        if ($x <= $this->xMin || $x >= $this->xMax || $y <= $this->yMin or $y >= $this->yMax)
            return false;

        // TODO: Do an inner circle or circumcircle check for regular polygon mode, which will be much faster than the ray casting?

        $vertices = $this->getWallVertices();

        // If the point is near any of the vertices, it can't be within
        foreach($vertices as $vertex)
        {
            if (sqrt(pow($x - $vertex[0], 2) + pow($y - $vertex[1], 2)) < $radius)
                return false;
        }

        // Use ray casting to determine if the point is within
        return SimulationMath::containsPoint($vertices, $x, $y) && !$this->isCircleNearEdges($x, $y, $radius);
    }

    public function isCircleNearEdges($x, $y, $radius)
    {
        $vertices = $this->getWallVertices();

        $lastVertex = null;
        foreach($vertices as $vertex)
        {
            if ($lastVertex !== null)
            {
                if (SimulationMath::segmentIntersectsCircle($x, $y, $radius, $lastVertex[0], $lastVertex[1], $vertex[0], $vertex[1]))
                    return true;
            }
            $lastVertex = $vertex;
        }
        if (SimulationMath::segmentIntersectsCircle($x, $y, $radius, $lastVertex[0], $lastVertex[1], $vertices[0][0], $vertices[0][1]))
            return true;

        return false;
    }

    public function getRandomPointInsideBoundaries($notNearEdges = false)
    {
        if (!$this->customWallVertices && $this->wallSides === 4 && ($this->wallStartAngle === null || $this->wallStartAngle % 90 == 0)) {
            $size = $this->worldSize;

            // This method always find a valid location on the first try, 
            $this->numberOfSpawnPoints++;
            $this->numberOfSpawnAttempts++;
            $this->maximumNumberOfSpawnAttempts = 1;

            if ($notNearEdges)
            {
                // don't spawn close to map edges in CTF mode
                return [
                    (bzfrand() - 0.5) * $size * 0.6,
                    (bzfrand() - 0.5) * $size * 0.6
                ];
            }
            else
            {
                return [
                    (bzfrand() - 0.5) * ($size - 2.0 * $this->tankRadius),
                    (bzfrand() - 0.5) * ($size - 2.0 * $this->tankRadius)
                ];
            }
        }
        // For regular or freeform polygons, generate a random point within a rectangular bounding box and check if
        // it is within the polygon.
        else
        {
            // Calculate the bounding box size
            $size = [
                $this->xMax - $this->xMin,
                $this->yMax - $this->yMin
            ];

            // Limit the number of attempts
            $maxAttempts = 1000;
            $attemptsRemaining = $maxAttempts;

            // Attempt to find a spawn point within the boundaries.
            // Skip the 'not near edges' handling for freeform polygon boundaries because the math doesn't work well.
            do {
                $x = (bzfrand() * ($size[0])) + $this->xMin;
                $y = (bzfrand() * ($size[1])) + $this->yMin;
                --$attemptsRemaining;
            } while(!$this->isCircleWithBoundaries($x, $y, (!$this->customWallVertices && $notNearEdges)?0.2*min($size[0], $size[1]):$this->tankRadius) && $attemptsRemaining > 0);

            // TODO: How should we handle this in the game? Abort the spawn?
            if ($attemptsRemaining <= 0)
                throw new Exception("Exceeded maximum attempts to find spawn location");

            $this->numberOfSpawnPoints++;
            $this->numberOfSpawnAttempts += $maxAttempts - $attemptsRemaining;
            $this->maximumNumberOfSpawnAttempts = max($this->maximumNumberOfSpawnAttempts, $maxAttempts - $attemptsRemaining);

            return [$x, $y];
        }
    }
}


$bzfs = new BZFS();

switch($_GET['mode'] ?? 0)
{
    // Square
    case 1:
        $bzfs->setWorldSize($_GET['worldSize'] ?? 800);
        break;
    // Regular polygon
    case 2:
        $sides = $_GET['wallSides'] ?? 8;
        if ($sides < 3 || $sides > 64)
            $sides = 8;
        $bzfs->setWorldSize($_GET['worldSize'] ?? 800);
        $bzfs->setWallSides($sides);
        if (strlen($_GET['wallStartAngle']))
            $bzfs->setWallStartAngle((float)$_GET['wallStartAngle']);
        break;
    // Freeform polygon
    case 3:
        switch((int)$_GET['customShape'])
        {
            case 2:
                $shape = [
                    [-300, 150],
                    [-200, 300],
                    [0, 350],
                    [350, 250],
                    [400, 0],
                    [250, -150],
                    [0, -250],
                    [-250, -150],
                    [-350, 0]
                ];
                break;
            case 3:
                $shape = [
                    [-200, 0],
                    [-150, 250],
                    [0, 0],
                    [150, 250],
                    [200, 0],
                    [100, -100],
                    [-100, -100]
                ];
                break;
            default:
                $shape = [
                    [350, 200],
                    [400, -100],
                    [250, -250],
                    [50, -250],
                    [-200, -150],
                    [-300, 200],
                    [0, 300],
                    [200, 300]
                ];
                break;
        }
        $bzfs->setCustomWalls($shape);
        break;
    default:
        die("Invalid mode");
}

if (!headers_sent()) {

    $imageSize = 1200;

    $image = imagecreatetruecolor($imageSize, $imageSize);
    if (function_exists('imageantialias'))
        imageantialias($image, true);
    $offsetX = $offsetY = 600;
    $colorLines = imagecolorallocate($image, 127, 127, 255);
    $colorLines2 = imagecolorallocate($image, 255, 255, 127);
    $colorPoints = imagecolorallocate($image, 0, 255, 0);
    $colorPointsBad = imagecolorallocate($image, 255, 0, 0);

    $worldSize = $bzfs->getWorldSize();
    $halfWorldSize = $worldSize * 0.5;
    /*
    imagerectangle(
        $image,
        $offsetX - $halfWorldSize,
        $offsetY - $halfWorldSize,
        $offsetX + $halfWorldSize,
        $offsetY + $halfWorldSize,
        $colorLines2
    );
    /**/
    //*
    if ($_GET['mode'] == 2)
        imageellipse(
            $image,
            $offsetX,
            $offsetY,
            $worldSize,
            $worldSize,
            $colorLines2
        );
    /**/

    $points = [];
    try {
        for ($i = 0; $i < 500; ++$i)
            $points[] = $bzfs->getRandomPointInsideBoundaries(!!($_GET['notNearEdges'] ?? false));
    }
    catch (Exception $e) {
        imagefttext($image, 24.0, 0.0, 30, 30, imagecolorexact($image, 255, 0, 0), '/usr/share/fonts/truetype/dejavu/DejaVuSansMono.ttf', "Error: {$e->getMessage()}");
        header("Content-type: image/png");
        imagepng($image);
        imagedestroy($image);
        exit;
    }
    $vertices = $bzfs->getWallVertices();
    $firstVertex = null;
    $lastVertex = null;
    foreach ($vertices as $vertex) {
        if ($firstVertex === null)
            $firstVertex = $vertex;
        else {
            imageline(
                $image,
                $lastVertex[0] + $offsetX,
                $offsetY - $lastVertex[1],
                $vertex[0] + $offsetX,
                $offsetY - $vertex[1],
                $colorLines
            );
        }
        $lastVertex = $vertex;
    }
    imageline(
        $image,
        $lastVertex[0] + $offsetX,
        $offsetY - $lastVertex[1],
        $firstVertex[0] + $offsetX,
        $offsetY - $firstVertex[1],
        $colorLines
    );
    $pointSize = $bzfs->getTankRadius() * 2;
    foreach ($points as $point) {
        imagefilledellipse(
            $image,
            $point[0] + $offsetX,
            $offsetY - $point[1],
            $pointSize,
            $pointSize,
            $colorPoints
        );
    }

    $stats = $bzfs->getStats();
    imagefttext($image, 24.0, 0.0, 30, 30, imagecolorexact($image, 255, 0, 0), '/usr/share/fonts/truetype/dejavu/DejaVuSansMono.ttf', "Spawn Points: {$stats['numberOfSpawnPoints']}\nAverage Attempts Per Point: ". ($stats['numberOfSpawnAttempts'] / $stats['numberOfSpawnPoints']) ."\nMaximum number of attempts for one point: {$stats['maximumNumberOfSpawnAttempts']}");

    header("Content-type: image/png");
    imagepng($image);
    imagedestroy($image);
}