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:
- 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.
- 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).
-
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.