CODEWITHSUNDEEP
phpgeometry
tampe125
tampe125

Reputation: 8523

Calculate circumference values

I have a rectangular map, stored as multidimensional array (ie $map[row][col]) and I have to track down which squares are seen by a player, placed anywhere on this map.

Player visibility is circular with unknown radius (but given at run-time) and I only need integer solutions.

I know that circumference formula is

x^2 + y^2 <= r^2

but how can I store everything?
I need these values since then I can "reveal" map squares.

The best would be a multidimesional array (ie __$sol[x][y]__).
This is a piece of code that I'm using. It's not corrected since it assumes that vision is a square and not a circle.

Calculating the square

$this->vision_offsets_2 = array();
//visibility given as r^2
$mx = (int)(sqrt($this->viewradius2));

$mxArr = range($mx * -1, $mx + 1);
foreach ($mxArr as $d_row)
{
    foreach ($mxArr as $d_col)
    {
         $this->vision_offsets_2[] = array($d_row, $d_col);
    }
}

This is how I apply that

    foreach($player as $bot)
    {
        foreach($visibility as $offset)
        {
            $vision_row = $offset[0] + $bot[0];
            $vision_col = $offset[1] + $bot[1];

            if(isset($map[$vision_row][$vision_col]))
            {
                if( $map[$vision_row][$vision_col] == UNSEEN) {
                    $map[$vision_row][$vision_col] =  LAND; }
            }
        }
    }

Here you can find the bot view: as you can see is a non perfect circle.
How can I track it? By the way, in this example radius^2 is 55, the orange circle is the player, brown squares are visible ones.

bot view

Upvotes: 4

Views: 661

Answers (4)

Jeff Ferland
Jeff Ferland

Reputation: 18282

Structure

You're already referencing terrain in a grid. Store terrain objects in those grid values. Apply attributes to those objects. Check with something like

$map[$x][$y]->isVisible($player);

You'll need some methods in there for setting vision and tests for checking the user that is passed against a list of users who can see it. While you're at it, setup other related methods in those objects (I see references to land... isLand() and isWater() perhaps?).

You can even have vision cascade within objects such that you only need to move the position of a user and the object takes care of triggering off all the code to set nearby plots of land to visible.

Math

We are given circumference.

double diameter = circumference / 3.14159
double radius = diameter / 2 //Normally done in one step / variable

Now we must know the distance between two points to compare it. Let's use map[4][7] and map[3][9].

int x0 = 4;
int y0 = 7;
int x1 = 3;
int y1 = 9;

double distance = Math.sqrt(
        Math.pow(x0 - x1, 2) + 
        Math.pow(y0 - y1, 2)
        );

System.out.println(distance); //2.23606797749979

Test distance > radius.

Testing each square

  • Put the above in a method: visibleFrom(Square target)
    • radius should be a globally accessible static variable when comparing.
    • Your Square object should be able to hand over its coordinates.
      • target.getX()
      • target.getY()
  • Some optimizations can be had
    • Only checking things for circular distance when they're in the square.
    • Not checking anything for circular distance when purely along the x or y axis.
    • Figuring out the largest square that fits inside the circle and not checking boxes in that range for circular distance.
  • Remember that premature optimization and over optimization are pitfalls.

Upvotes: 2

Whetstone
Whetstone

Reputation: 1199

I don't know exactly what you want, but here's some things that should help you along. As a warning these are untested, but the logic is sound.

 //You mentioned circumference, this will find out the circumference but I don't 
 //think you actually need it.
 $circumference_length = 2 * $visibility_range * 3.1415;

 //Plug in the player and target coordinates and how far you can see, this will
 //tell you if the player can see it.  This can be optimized using your object 
 //and player Objects.
 function canSee($player_x, $player_y, $vision_length, $target_x, $target_y){
      $difference_x = $target_x - $player_x;
      $difference_y = $target_y - $player_y;
      $distance = sqrt((pow($difference_x,2) + pow($difference_y, 2));

      if($vision < $distance){
          return false;
      } else {
          return true;
      } 

 }

Edit: In response to your clarification, you can use the above function to figure out if you should show the terrain objects or not.

foreach($player as $bot)
{
    foreach($terrain_thing as $terrain)
    {
        //ASSUMING THAT [0] IS ALWAYS X AND [1] IS ALWAYS y, set a third variable
        //to indicate visibility
        $terrain["is_visible"] = canSee($bot[0], $bot[1], $visibility_range, $terrain[0], $terrain[1])


    }
}

Upvotes: 0

nullpotent
nullpotent

Reputation: 9260

I think that Bresenham's circle drawing algorithm is what you're looking for.

Upvotes: 0

Jon
Jon

Reputation: 437336

A function like this would tell you if a map square is visible (using the distance of the centers of the squares as a metric; if you want to define visibility in another manner, which you probably would, things get much more complicated):

function is_visible($mapX, $mapX, $playerX, $playerY, $r) {
    return sqrt(pow($mapX - $playerX, 2) + pow($mapY - $playerY, 2)) <= $r;
}

You probably don't really need to store these values since you can easily calculate them on demand.

Upvotes: 0

Related Questions