Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
I am working on an online game. Within this game, almost every action will need to generate a circle to see what is within that area. Some actions will need to modify a circular area on the map.

The problem I'm having is generating the circle in the Perl data structure. Not only does it miss certain points on larger circles, my code is fairly slow.

My basic algorithm for drawing a "ring" of a circle is this:

for my $i (0 .. $radius ** 2) { # See "1" below # Rounded values, see "2" below my $x_val = int($radius * cos($i) + $center_x + 0.5); my $y_val = int($radius * sin($i) + $center_y + 0.5); $circle{$x_val} ||= {}; $curpass{$x_val} ||= {}; $circle{$x_val}{$y_val} ||= 0; $curpass{$x_val}{$y_val} ||= 0; unless($curpass{$x_val}{$y_val}) { $circle{$x_val}{$y_val}++; $curpass{$x_val}{$y_val}++; } }
A few notes about this:
  1. If I change the $radius ** 2, I can trade speed for accuracy. I thought something like ($radius + 1) ** 2 would catch every possible point, but not even close.
  2. If I remove the rounding, I miss fewer points within the circle. However, the circle becomes lopsided.

I wrote a CGI script to visualize this which makes the flaws very visible.

#!/usr/bin/perl use strict; use warnings; use CGI (); my $q = CGI->new; # use CGI::Carp 'fatalsToBrowser'; my %circle; my $prev_data; # Read the previous circles my @prev_circles; { my @x_vals = $q->param('x'); my @y_vals = $q->param('y'); my @r_vals = $q->param('r'); for(my $i = 0; $i < @r_vals; $i++) { foreach ($r_vals[$i], $x_vals[$i], $y_vals[$i]) {die "All valu +es must be positive integers!\n" if /[^\d\.]/} push(@prev_circles, { r => $r_vals[$i], x => $x_vals[$i], y => $y_vals[$i], }); } } # 'Draw' the circle in the hash. foreach my $circle (@prev_circles) { my $rmax = $circle->{'r'}; my $center_x = $circle->{'x'}; my $center_y = $circle->{'y'}; $prev_data .= qq~<input type="hidden" name="r" value="$rmax" /><in +put type="hidden" name="x" value="$center_x" /><input type="hidden" n +ame="y" value="$center_y" />\n~; my %curpass; for my $radius (0 .. $rmax) { for my $i (0 .. $radius ** 2) { # Rounded values my $x_val = int($radius * cos($i) + $center_x + 0.5); my $y_val = int($radius * sin($i) + $center_y + 0.5); $circle{$x_val} ||= {}; $curpass{$x_val} ||= {}; $circle{$x_val}{$y_val} ||= 0; $curpass{$x_val}{$y_val} ||= 0; unless($curpass{$x_val}{$y_val}) { $circle{$x_val}{$y_val}++; $curpass{$x_val}{$y_val}++; } } } } my $output = q~<html> <head> <title>A circle as a table</title> <style type="text/css"> body {background: #888;} .c1 {background: #000;} .c2 {background: #008;} .c3 {background: #00f;} .c4 {background: #08f;} .c5 {background: #0ff;} .c6 {background: #8ff;} .c7 {background: #fff;} </style> </head> <body> <table> ~; foreach my $rowid (0 .. max(keys %circle)) { my $row = $circle{$rowid}; $output .= "<tr>"; foreach my $columnid (0 .. max(keys %{$row})) { my $column = $row->{$columnid}; my $class = ''; $column = 7 if $column > 7; $class = qq~ class="c$column"~ if $column; $output .= qq~<td$class></td>~; } $output .= "</tr>\n"; } $output .= qq~</table> <br /> <br /> <form method="post" > $prev_data <br />New circle's radius: <input type="text" size="10" name="r" value +="20" /> <br />New circle's center: (<input type="text" size="10" name="x" valu +e="50" />, <input type="text" size="10" name="y" value="50" />) <br /><input type="submit" /> </form> </body> </html>~; print $q->header, $output; sub max { my $max = 0; foreach (@_) {$max = $_ if $_ > $max} return $max; }

When running this, circles with a radius larger than 100 show the flaws very well. The circle is more ovular in Internet Explorer. Also note that this generates a large amount of HTML which can make a browser unstable. I won't be using the HTML generating portion; it's just a nice way to visualize how this would affect a data structure. I intentionally cut off any negative coordinates, and the coordinates aren't real graph coordinates. But that's not relevant to my problem.

I would greatly appreciate any ideas on how to improve this algorithm, or any other ways to approach this. I need to be able to modify any coordinate within the circle, since any other circle could overlap it (as this example shows if you overlap two circles).

In reply to Creating a circle in a data structure by AK108

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (4)
As of 2024-05-25 08:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found