laserbat/gist:1071295

## gistfile1.php
<!--

PHP MRPAS

Copyright (c) 2010 Dominik Marczuk

All rights reserved.


Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright

      notice, this list of conditions and the following disclaimer.

    * Redistributions in binary form must reproduce the above copyright

      notice, this list of conditions and the following disclaimer in the

      documentation and/or other materials provided with the distribution.

    * The name of Dominik Marczuk may not be used to endorse or promote products

      derived from this software without specific prior written permission.


THIS SOFTWARE IS PROVIDED BY DOMINIK MARCZUK ``AS IS'' AND ANY

EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

DISCLAIMED. IN NO EVENT SHALL DOMINIK MARCZUK BE LIABLE FOR ANY

DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

-->

<?php

  //sizes, positions...

  $mapWidth = 80;

  $mapHeight = 50;

  $playerPosX = 40;

  $playerPosY = 25;


  //map cell data

  class cell {

    public $fov, $transparent, $walkable;

    public function __construct() {

      $fov = false;

      $transparent = false;

      $walkable = false;

    }

  }


  //map data

  class map {

    public $width;

    public $height;

    public $nbcells;

    public $cells;

    public function __construct ($w, $h) {

      $this->width = $w;

      $this->height = $h;

      $this->nbcells = $w * $h;

      $this->cells = array();

      for ($i = 0; $i < $this->nbcells; $i++) {

        $this->cells[] = new cell();

      }

    }

    public function generate () {

      for ($i = 0; $i < $this->nbcells; $i++) {

        if (mt_rand(0,100) > 10) {

          $this->cells[$i]->transparent = true;

          $this->cells[$i]->walkable = true;

        }

        else {

          $this->cells[$i]->transparent = false;

          $this->cells[$i]->walkable = false;

        }

        $this->cells[$i]->fov = false;

      }

    }

    public function displayTile ($idx) {

      $c;

      if ($this->cells[$idx]->walkable) {

        if ($this->cells[$idx]->fov == true)

          $c = '<img src="ground-lit.gif">';

        else

          $c = '<img src="ground-unlit.gif">';

      }

      else {

        if ($this->cells[$idx]->fov == true)

          $c = '<img src="wall-lit.gif">';

        else

          $c = '<img src="wall-unlit.gif">';

      }

      if ($GLOBALS['playerPosY'] * $GLOBALS['mapWidth'] + $GLOBALS['playerPosX'] == $idx)

        $c = '<img src="pc.gif">';

      echo $c;

    }

  }


  //the fov itself

  class MRPAS {

    private function computeQuadrant ($m, $playerX, $playerY, $maxRadius, $lightWalls, $dx, $dy) {

      $startAngle = array();

      $endAngle = array();

      //octant: vertical edge:

      {

        $iteration = 1;

        $done = false;

        $totalObstacles = 0;

        $obstaclesInLastLine = 0;

        $minAngle = 0.0;

        $x = 0;

        $y = 0;

        //do while there are unblocked slopes left and the algo is within the map's boundaries

        //scan progressive lines/columns from the PC outwards

        $y = $playerY + $dy;

        if ($y < 0 || $y >= $m->height)

          $done = true;

        while (!$done) {

          //process cells in the line

          $slopesPerCell = 1.0 / ($iteration + 1);

          $halfSlopes = $slopesPerCell * 0.5;

          $processedCell = (int)($minAngle / $slopesPerCell);

          $minx = max(0, $playerX - $iteration);

          $maxx = min($m->width - 1, $playerX + $iteration);

          $done = true;

          for ($x = $playerX + ($processedCell * $dx); $x >= $minx && $x <= $maxx; $x += $dx) {

            $c = $x + ($y * $m->width);

            //calculate slopes per cell

            $visible = true;

            $startSlope = $processedCell * $slopesPerCell;

            $centreSlope = $startSlope + $halfSlopes;

            $endSlope = $startSlope + $slopesPerCell;

            if ($obstaclesInLastLine > 0 && $m->cells[$c]->fov == false) {

              $idx = 0;

              while ($visible && $idx < $obstaclesInLastLine) {

                if ($m->cells[$c]->transparent == true) {

                  if ($centreSlope > $startAngle[$idx] && $centreSlope < $endAngle[$idx])

                    $visible = false;

                }

                else {

                  if ($startSlope >= $startAngle[$idx] && $endSlope <= $endAngle[$idx])

                    $visible = false;

                }

                if ($visible && ($m->cells[$c - ($m->width * $dy)]->fov == false || !$m->cells[$c - ($m->width * $dy)]->transparent) && ($x - $dx >= 0 && $x - $dx < $m->width && ($m->cells[$c - ($m->width * $dy) - $dx]->fov == false || !$m->cells[$c - ($m->width * $dy) - $dx]->transparent)))

                  $visible = false;

                $idx++;

              }

            }

            if ($visible) {

              $m->cells[$c]->fov = true;

              $done = false;

              //if the cell is opaque, block the adjacent slopes

              if (!$m->cells[$c]->transparent) {

                if ($minAngle >= $startSlope)

                  $minAngle = $endSlope;

                else {

                  $startAngle[$totalObstacles] = $startSlope;

                  $endAngle[$totalObstacles++] = $endSlope;

                }

                if (!$lightWalls)

                  $m->cells[$c]->fov = false;

              }

            }

            $processedCell++;

          }

          if ($iteration == $maxRadius)

            $done = true;

          $iteration++;

          $obstaclesInLastLine = $totalObstacles;

          $y += $dy;

          if ($y < 0 || $y >= $m->height)

            $done = true;

          if ($minAngle == 1.0)

            $done = true;

        }

      }

      //octant: horizontal edge

      {

        $iteration = 1; //iteration of the algo for this octant

        $done = false;

        $totalObstacles = 0;

        $obstaclesInLastLine = 0;

        $minAngle = 0.0;

        $x = 0;

        $y = 0;

        //do while there are unblocked slopes left and the algo is within the map's boundaries

        //scan progressive lines/columns from the PC outwards

        $x = $playerX + $dx; //the outer slope's coordinates (first processed line)

        if ($x < 0 || $x >= $m->width)

          $done = true;

        while (!$done) {

          //process cells in the line

          $slopesPerCell = 1.0 / ($iteration + 1);

          $halfSlopes = $slopesPerCell * 0.5;

          $processedCell = (int)($minAngle / $slopesPerCell);

          $miny = max(0, $playerY - $iteration);

          $maxy = min($m->height - 1, $playerY + $iteration);

          $done = true;

          for ($y = $playerY + ($processedCell * $dy); $y >= $miny && $y <= $maxy; $y += $dy) {

            $c = $x + ($y * $m->width);

            //calculate slopes per cell

            $visible = true;

            $startSlope = ($processedCell * $slopesPerCell);

            $centreSlope = $startSlope + $halfSlopes;

            $endSlope = $startSlope + $slopesPerCell;

            if ($obstaclesInLastLine > 0 && $m->cells[$c]->fov == false) {

              $idx = 0;

              while ($visible && $idx < $obstaclesInLastLine) {

                if ($m->cells[$c]->transparent == true) {

                  if ($centreSlope > $startAngle[$idx] && $centreSlope < $endAngle[$idx])

                    $visible = false;

                }

                else {

                  if ($startSlope >= $startAngle[$idx] && $endSlope <= $endAngle[$idx])

                    $visible = false;

                }

                if ($visible && ($m->cells[$c - $dx]->fov == false || !$m->cells[$c - $dx]->transparent) && ($y - $dy >= 0 && $y - $dy < $m->height && ($m->cells[$c - ($m->width * $dy) - $dx]->fov == false || !$m->cells[$c - ($m->width * $dy) - $dx]->transparent)))

                  $visible = false;

                $idx++;

              }

            }

            if ($visible) {

              $m->cells[$c]->fov = true;

              $done = false;

              //if the cell is opaque, block the adjacent slopes

              if (!$m->cells[$c]->transparent) {

                if ($minAngle >= $startSlope)

                  $minAngle = $endSlope;

                else {

                  $startAngle[$totalObstacles] = $startSlope;

                  $endAngle[$totalObstacles++] = $endSlope;

                }

                if (!$lightWalls)

                  $m->cells[$c]->fov = false;

              }

            }

            $processedCell++;

          }

          if ($iteration == $maxRadius)

            $done = true;

          $iteration++;

          $obstaclesInLastLine = $totalObstacles;

          $x += $dx;

          if ($x < 0 || $x >= $m->width)

            $done = true;

          if ($minAngle == 1.0)

            $done = true;

        }

      }

    }

    public function computeFov ($m, $playerX, $playerY, $maxRadius, $lightWalls) {

      //first, zero the FOV map

      for ($c = 0; $c < $m->nbcells; $c++) {

        $m->cells[$c]->fov = false;

      }

      //set PC's position as visible

      $m->cells[$playerX + ($playerY * $m->width)]->fov = true;

      //compute the 4 quadrants of the map

      $this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, 1, 1);

      $this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, 1, -1);

      $this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, -1, 1);

      $this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, -1, -1);

    }

  }


  /* LET'S DO IT! */

  $m = new map($mapWidth,$mapHeight);

  $m->generate();

  $fov = new MRPAS();

?>


<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">

<html lang="en">

<head>

	<meta http-equiv="Content-Type" content="text/html;charset=UTF-8">

	<title>PHP MRPAS</title>

	<style type="text/css">

    body { font-family: monospace; background-color: black; color: white; line-height: 0; text-align: center; }

    img { border: 0; padding: 0; margin: 0; }

  </style>

</head>

<body>

<h1>PHP MRPAS</h1>

<h3>Hit "refresh" to generate another map.</h3>

<p>

<?php

  $fov->computeFov($m,$playerPosX, $playerPosY, 0, true);

  for($j = 0; $j < $mapHeight; $j++) {

    for($i = 0; $i < $mapWidth; $i++) {

      $m->displayTile($j * $mapWidth + $i);

    }

    echo '<br>';

  }

?>

</p>

</body>

</html>
	<!--

	PHP MRPAS

	Copyright (c) 2010 Dominik Marczuk

	All rights reserved.



	Redistribution and use in source and binary forms, with or without

	modification, are permitted provided that the following conditions are met:

	* Redistributions of source code must retain the above copyright

	notice, this list of conditions and the following disclaimer.

	* Redistributions in binary form must reproduce the above copyright

	notice, this list of conditions and the following disclaimer in the

	documentation and/or other materials provided with the distribution.

	* The name of Dominik Marczuk may not be used to endorse or promote products

	derived from this software without specific prior written permission.



	THIS SOFTWARE IS PROVIDED BY DOMINIK MARCZUK ``AS IS'' AND ANY

	EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

	WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

	DISCLAIMED. IN NO EVENT SHALL DOMINIK MARCZUK BE LIABLE FOR ANY

	DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

	LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

	ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

	(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

	SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	-->

	<?php

	//sizes, positions...

	$mapWidth = 80;

	$mapHeight = 50;

	$playerPosX = 40;

	$playerPosY = 25;



	//map cell data

	class cell {

	public $fov, $transparent, $walkable;

	public function __construct() {

	$fov = false;

	$transparent = false;

	$walkable = false;

	}

	}



	//map data

	class map {

	public $width;

	public $height;

	public $nbcells;

	public $cells;

	public function __construct ($w, $h) {

	$this->width = $w;

	$this->height = $h;

	$this->nbcells = $w * $h;

	$this->cells = array();

	for ($i = 0; $i < $this->nbcells; $i++) {

	$this->cells[] = new cell();

	}

	}

	public function generate () {

	for ($i = 0; $i < $this->nbcells; $i++) {

	if (mt_rand(0,100) > 10) {

	$this->cells[$i]->transparent = true;

	$this->cells[$i]->walkable = true;

	}

	else {

	$this->cells[$i]->transparent = false;

	$this->cells[$i]->walkable = false;

	}

	$this->cells[$i]->fov = false;

	}

	}

	public function displayTile ($idx) {

	$c;

	if ($this->cells[$idx]->walkable) {

	if ($this->cells[$idx]->fov == true)

	$c = '<img src="ground-lit.gif">';

	else

	$c = '<img src="ground-unlit.gif">';

	}

	else {

	if ($this->cells[$idx]->fov == true)

	$c = '<img src="wall-lit.gif">';

	else

	$c = '<img src="wall-unlit.gif">';

	}

	if ($GLOBALS['playerPosY'] * $GLOBALS['mapWidth'] + $GLOBALS['playerPosX'] == $idx)

	$c = '<img src="pc.gif">';

	echo $c;

	}

	}



	//the fov itself

	class MRPAS {

	private function computeQuadrant ($m, $playerX, $playerY, $maxRadius, $lightWalls, $dx, $dy) {

	$startAngle = array();

	$endAngle = array();

	//octant: vertical edge:

	{

	$iteration = 1;

	$done = false;

	$totalObstacles = 0;

	$obstaclesInLastLine = 0;

	$minAngle = 0.0;

	$x = 0;

	$y = 0;

	//do while there are unblocked slopes left and the algo is within the map's boundaries

	//scan progressive lines/columns from the PC outwards

	$y = $playerY + $dy;

	if ($y < 0 \|\| $y >= $m->height)

	$done = true;

	while (!$done) {

	//process cells in the line

	$slopesPerCell = 1.0 / ($iteration + 1);

	$halfSlopes = $slopesPerCell * 0.5;

	$processedCell = (int)($minAngle / $slopesPerCell);

	$minx = max(0, $playerX - $iteration);

	$maxx = min($m->width - 1, $playerX + $iteration);

	$done = true;

	for ($x = $playerX + ($processedCell * $dx); $x >= $minx && $x <= $maxx; $x += $dx) {

	$c = $x + ($y * $m->width);

	//calculate slopes per cell

	$visible = true;

	$startSlope = $processedCell * $slopesPerCell;

	$centreSlope = $startSlope + $halfSlopes;

	$endSlope = $startSlope + $slopesPerCell;

	if ($obstaclesInLastLine > 0 && $m->cells[$c]->fov == false) {

	$idx = 0;

	while ($visible && $idx < $obstaclesInLastLine) {

	if ($m->cells[$c]->transparent == true) {

	if ($centreSlope > $startAngle[$idx] && $centreSlope < $endAngle[$idx])

	$visible = false;

	}

	else {

	if ($startSlope >= $startAngle[$idx] && $endSlope <= $endAngle[$idx])

	$visible = false;

	}

	if ($visible && ($m->cells[$c - ($m->width * $dy)]->fov == false \|\| !$m->cells[$c - ($m->width * $dy)]->transparent) && ($x - $dx >= 0 && $x - $dx < $m->width && ($m->cells[$c - ($m->width * $dy) - $dx]->fov == false \|\| !$m->cells[$c - ($m->width * $dy) - $dx]->transparent)))

	$visible = false;

	$idx++;

	}

	}

	if ($visible) {

	$m->cells[$c]->fov = true;

	$done = false;

	//if the cell is opaque, block the adjacent slopes

	if (!$m->cells[$c]->transparent) {

	if ($minAngle >= $startSlope)

	$minAngle = $endSlope;

	else {

	$startAngle[$totalObstacles] = $startSlope;

	$endAngle[$totalObstacles++] = $endSlope;

	}

	if (!$lightWalls)

	$m->cells[$c]->fov = false;

	}

	}

	$processedCell++;

	}

	if ($iteration == $maxRadius)

	$done = true;

	$iteration++;

	$obstaclesInLastLine = $totalObstacles;

	$y += $dy;

	if ($y < 0 \|\| $y >= $m->height)

	$done = true;

	if ($minAngle == 1.0)

	$done = true;

	}

	}

	//octant: horizontal edge

	{

	$iteration = 1; //iteration of the algo for this octant

	$done = false;

	$totalObstacles = 0;

	$obstaclesInLastLine = 0;

	$minAngle = 0.0;

	$x = 0;

	$y = 0;

	//do while there are unblocked slopes left and the algo is within the map's boundaries

	//scan progressive lines/columns from the PC outwards

	$x = $playerX + $dx; //the outer slope's coordinates (first processed line)

	if ($x < 0 \|\| $x >= $m->width)

	$done = true;

	while (!$done) {

	//process cells in the line

	$slopesPerCell = 1.0 / ($iteration + 1);

	$halfSlopes = $slopesPerCell * 0.5;

	$processedCell = (int)($minAngle / $slopesPerCell);

	$miny = max(0, $playerY - $iteration);

	$maxy = min($m->height - 1, $playerY + $iteration);

	$done = true;

	for ($y = $playerY + ($processedCell * $dy); $y >= $miny && $y <= $maxy; $y += $dy) {

	$c = $x + ($y * $m->width);

	//calculate slopes per cell

	$visible = true;

	$startSlope = ($processedCell * $slopesPerCell);

	$centreSlope = $startSlope + $halfSlopes;

	$endSlope = $startSlope + $slopesPerCell;

	if ($obstaclesInLastLine > 0 && $m->cells[$c]->fov == false) {

	$idx = 0;

	while ($visible && $idx < $obstaclesInLastLine) {

	if ($m->cells[$c]->transparent == true) {

	if ($centreSlope > $startAngle[$idx] && $centreSlope < $endAngle[$idx])

	$visible = false;

	}

	else {

	if ($startSlope >= $startAngle[$idx] && $endSlope <= $endAngle[$idx])

	$visible = false;

	}

	if ($visible && ($m->cells[$c - $dx]->fov == false \|\| !$m->cells[$c - $dx]->transparent) && ($y - $dy >= 0 && $y - $dy < $m->height && ($m->cells[$c - ($m->width * $dy) - $dx]->fov == false \|\| !$m->cells[$c - ($m->width * $dy) - $dx]->transparent)))

	$visible = false;

	$idx++;

	}

	}

	if ($visible) {

	$m->cells[$c]->fov = true;

	$done = false;

	//if the cell is opaque, block the adjacent slopes

	if (!$m->cells[$c]->transparent) {

	if ($minAngle >= $startSlope)

	$minAngle = $endSlope;

	else {

	$startAngle[$totalObstacles] = $startSlope;

	$endAngle[$totalObstacles++] = $endSlope;

	}

	if (!$lightWalls)

	$m->cells[$c]->fov = false;

	}

	}

	$processedCell++;

	}

	if ($iteration == $maxRadius)

	$done = true;

	$iteration++;

	$obstaclesInLastLine = $totalObstacles;

	$x += $dx;

	if ($x < 0 \|\| $x >= $m->width)

	$done = true;

	if ($minAngle == 1.0)

	$done = true;

	}

	}

	}

	public function computeFov ($m, $playerX, $playerY, $maxRadius, $lightWalls) {

	//first, zero the FOV map

	for ($c = 0; $c < $m->nbcells; $c++) {

	$m->cells[$c]->fov = false;

	}

	//set PC's position as visible

	$m->cells[$playerX + ($playerY * $m->width)]->fov = true;

	//compute the 4 quadrants of the map

	$this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, 1, 1);

	$this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, 1, -1);

	$this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, -1, 1);

	$this->computeQuadrant($m, $playerX, $playerY, $maxRadius, $lightWalls, -1, -1);

	}

	}



	/* LET'S DO IT! */

	$m = new map($mapWidth,$mapHeight);

	$m->generate();

	$fov = new MRPAS();

	?>



	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">

	<html lang="en">

	<head>

	<meta http-equiv="Content-Type" content="text/html;charset=UTF-8">

	<title>PHP MRPAS</title>

	<style type="text/css">

	body { font-family: monospace; background-color: black; color: white; line-height: 0; text-align: center; }

	img { border: 0; padding: 0; margin: 0; }

	</style>

	</head>

	<body>

	<h1>PHP MRPAS</h1>

	<h3>Hit "refresh" to generate another map.</h3>

	<p>

	<?php

	$fov->computeFov($m,$playerPosX, $playerPosY, 0, true);

	for($j = 0; $j < $mapHeight; $j++) {

	for($i = 0; $i < $mapWidth; $i++) {

	$m->displayTile($j * $mapWidth + $i);

	}

	echo '<br>';

	}

	?>

	</p>

	</body>

	</html>