[glob2-devel] testing a gradient for explorers (was: additional feedback on Globulation 2 (long, with many topics))

[Joe Wells]

Joe Wells <address@hidden> writes:

> Obviously, explorers should follow a gradient based on exploring
> unknown and/or not-recently-seen locations.  The main difficulty with
> this is how to prevent all the explorers from going to the same
> destination.  I suggest the following idea.  Calculate some reasonable
> gradient for which locations would be good to explore.  (I will
> suggest one below.)  Then, for each explorer, make a copy of this
> gradient.  Flip the copy (i.e., consider 0 to be high and 255 (or
> whatever the highest possible value is) to be low).  Raise the
> location of each _other_ currently-exploring (i.e., not seeking
> food/healing or assigned to a exploration flag) explorer by some
> amount (e.g., 10).  (It is important that we don't do this for the
> explorer the gradient is for, because that would be likely to destroy
> the information about the unexplored thing that the explorer is
> currently "seeking".  The way I propose to do it will lower peaks that
> are in some sense "assigned" to _other_ explorers.)  Apply the
> gradient algorithm to make the gradient valid again.  Then flip the
> resulting gradient (undoing the first flip).  (Flipping doesn't have
> to modify the numbers for each location; you just switch which
> direction you consider up or down.)  I think this should do a good job
> of getting distinct explorers to explore distinct parts of the world.
> Comments?  Is my idea any good or does it suck?


> Anyway, here is my suggested gradient for explorers (which must be
> combined with the above idea to avoid sending all explorers to the
> same place).  First, establish as top priority unknown locations that
> are distance 2 away from a pair of known adjacent locations which are
> of distinct travelabilities (i.e., some globules can travel on one of
> the known locations but not the other, for example, a boundary between
> sand and water, or a boundary between sand/grass and a resource).
> Next priority are any other unknown locations distance 2 away from any
> known location, with corners being preferred (i.e., an unknown
> location is preferred if it is 2 away from known locations in
> directions that are at 90 degree angles, and in opposite directions
> are more unknown locations).  Next priority below that (probably _way_
> below) are not-recently-seen locations that are 2 away from recently
> seen locations.  (In the information recorded about what is not
> recently seen, do we know how long it has been since the location has
> been seen?)  Simply make a proper gradient after establishing these
> priorities.

I did not get any feedback on this, so I still don't know what people
think of this idea.  I wrote a quick test program in Perl to try this
idea out.  The explorers seem to explore the world pretty quickly.
The test program is attached below (inline so you should also see it).
I've simplified things for the test program, making explorers only see
one spot away and ignoring the need to go for food.  I didn't try to
implement the following of sand-water or sand/grass-resource
boundaries or seeking of not-recently-seen locations.  Try out the
test program and tell me what you think.  You just have to keep
pressing space.  Uncomment some of the “draw_gradient” commands if you
want to see the internals.

-- 
Joe

#!/bin/sh
# -*-Perl-*-
case "$PATH" in *:) ;; *) PATH="$PATH:";; esac
PATH="${PATH}/usr/local/bin:/usr/local/bin/apps" export PATH
exec perl -S -x -- "$0" "$@"
#!perl -w

# To prevent Emacs's indentation code from trying to parse the stuff
# above.
();

use English;
use strict;
use Curses;
use Dumpvalue;

my $d = new Dumpvalue();

my @world_lines = (
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++...+...+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++......+++++......+++...+',
    '...+++......+++++......+++...+',
    '...+++......+++++......+++...+',
    '...+++......+++++......+++...+',
    '...+++...+...+++.......+++...+',
    '...+++.......+++.......+++...+',
    '...+++.......+O+.......+++...+',
    '...+++.................+++...+',
    '...+++.................+++...+',
    '...+++.......+++.......+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
    '...+++.......+++...+...+++...+',
);

my @world;

#print STDERR "#world_lines: [$#world_lines]\n";
#print STDERR "world_lines[0]: [$world_lines[0]]\n";

my ($home_x, $home_y);

my $num_lines = scalar (@world_lines);
my $num_columns = length ($world_lines[0]);

for my $x (0 .. ($num_lines - 1)) {
    #print STDERR "x: [$x]\n";
    my $line = $world_lines[$x];
    if (length($line) != $num_columns) { die "bad data"; }
    #print STDERR "line: [$line]\n";
    for my $y (0 .. ($num_columns - 1)) {
        #print STDERR "y: [$y]\n";
        my $type = substr($line,$y,1);
        if ($type eq 'O') {
            $type = '+';
            $home_x = $x;
            $home_y = $y; }
        $world[$x][$y] = substr($line,$y,1); }}

#select STDERR;
#$d->dumpValue(address@hidden);
#select STDOUT;

sub assert_map {
    my $map = shift;
    if (scalar (@$map) != $num_lines) { die "bad data"; }
    for my $x (0 .. ($num_lines - 1)) {
        my $row = $$map[$x];
        if (scalar (@$row) != $num_columns) { die "bad data"; }}}

sub draw_map {
    my $map = shift;
    assert_map ($map);
    #print STDERR "num_lines: [$num_lines]\n";
    for my $x (0 .. ($num_lines - 1)) {
        #print STDERR "x: [$x]\n";
        my $row = $$map[$x];
        #print STDERR "num_columns: [$num_columns]\n";
        for my $y (0 .. ($num_columns - 1)) {
            #print STDERR "y: [$y]\n";
            addstr($x,$y,$$row[$y]);
        }}
    refresh();
}

my @known;

sub make_known {
    my ($x, $y, $map) = @_;
    for my $xo (-1 .. 1) {
        for my $yo (-1 .. 1) {
            $$map[($x + $xo) % $num_lines][($y + $yo) % $num_columns] = 1; }}}

make_known ($home_x, $home_y, address@hidden);

my @explorer_x;
my @explorer_y;
my @new_explorer_x;
my @new_explorer_y;

sub assert_explorer {
    if ((scalar (@explorer_x)) != (scalar (@explorer_y))) { die "oh no"; }}

sub update_knowledge {
    assert_explorer ();
    for my $i (0 .. $#explorer_x) {
        make_known ($explorer_x[$i], $explorer_y[$i], address@hidden); }}

sub new_explorer {
    assert_explorer ();
    my $i = (scalar (@explorer_x));
    $explorer_x[$i] = $home_x;
    $explorer_y[$i] = $home_y; }

sub is_explorer_loc {
    my ($x, $y) = @_;
    assert_explorer ();
    for my $i (0 .. $#explorer_x) {
        if (($x == $explorer_x[$i]) && ($y == $explorer_y[$i])) {
            return 1; }}
    return 0; }

sub is_new_explorer_loc {
    my ($x, $y) = @_;
    assert_explorer ();
    for my $i (0 .. $#explorer_x) {
        if ((defined $new_explorer_x[$i])
            && (defined $new_explorer_y[$i])
            && ($x == $new_explorer_x[$i])
            && ($y == $new_explorer_y[$i])) {
            return 1; }}
    return 0; }

sub neighbor_count {
    my ($x, $y, $want_known) = @_;
    my $neighbor_count;
    for my $xo (-1 .. 1) {
        for my $yo (-1 .. 1) {
            if (($xo != 0) && ($yo != 0)) {
                my $known = $known[($x + $xo) % $num_lines][($y + $yo) % 
$num_columns];
                if ($want_known) {
                    if ($known) {
                        $neighbor_count++; }}
                else {
                    if (! $known) {
                        $neighbor_count++; }}}}}
    return $neighbor_count; }

sub make_seed_gradient {
    my @gradient;
    for my $x (0 .. ($num_lines - 1)) {
        #print STDERR "x: [$x]\n";
        for my $y (0 .. ($num_columns - 1)) {
            #print STDERR "y: [$y]\n";
            my $value;
            my $unknown_neighbor_count = neighbor_count ($x, $y, 0);
            if ($unknown_neighbor_count) {
                $value = 46;
                if ($unknown_neighbor_count > 4) {
                    $unknown_neighbor_count = 4; }
                $value += $unknown_neighbor_count;
                if ($known[$x][$y]) {
                    for my $xo (-1 .. 1) {
                        for my $yo (-1 .. 1) {
                            my $nx = ($x + $xo) % $num_lines;
                            my $ny = ($y + $yo) % $num_columns;
                            if (! $known[$nx][$ny]) {
                                for my $xo2 (-1 .. 1) {
                                    for my $yo2 (-1 .. 1) {
                                        my $nx2 = ($nx + $xo2) % $num_lines;
                                        my $ny2 = ($ny + $yo2) % $num_columns;
                                        if ($known[$nx2][$ny2]
                                            && (($xo2 == $xo)
                                                || ($yo2 == $yo))) {
                                            $value++; }}}}}}}}
            else {
                $value = 0; }
            $gradient[$x][$y] = $value; }}
    return address@hidden; }

sub fill_gradient {
    my ($gradient, $rev) = @_;
    assert_map ($gradient);
    for (my $changed = 1; $changed;) {
        $changed = 0;
        for my $x (0 .. ($num_lines - 1)) {
            for my $y (0 .. ($num_columns - 1)) {
                my $maxmin;
                for my $xo (-1 .. 1) {
                    for my $yo (-1 .. 1) {
                        my $value = $$gradient[($x + $xo) % $num_lines][($y + 
$yo) % $num_columns];
                        if (($xo != 0) || ($yo != 0)) {
                            if ($rev) {
                                $value += 1; }
                            else {
                                $value -= 1; }}
                        if (! defined $maxmin) {
                            $maxmin = $value; }
                        else {
                            if ($rev) {
                                if ($value <= $maxmin) {
                                    $maxmin = $value; }}
                            else {
                                if ($value >= $maxmin) {
                                    $maxmin = $value; }}}}}
                if ($maxmin != $$gradient[$x][$y]) {
                    $changed = 1;
                    $$gradient[$x][$y] = $maxmin;
                    #draw_gradient ($gradient); sleep (1);
                }}}
        #draw_gradient ($gradient); sleep (1);
    }}

sub draw_gradient {
    my ($gradient, $cx, $cy) = @_;
    assert_map ($gradient);
    for my $x (0 .. ($num_lines - 1)) {
        for my $y (0 .. ($num_columns - 1)) {
            #print STDERR "y: [$y]\n";
            if (is_explorer_loc ($x, $y)) {
                attron(A_REVERSE);
            }
            if (is_new_explorer_loc ($x, $y)) {
                attron(green ());
            }
            if ($known[$x][$y]) {
                attron(A_BOLD);
            }
            if ((defined $cx) && (defined $cy) && ($x == $cx) && ($y == $cy)) {
                attron (red ());
            }
            addstr($x, $y, substr 
('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 
$$gradient[$x][$y], 1));
            attrset(A_NORMAL); }}
    refresh();
}

sub copy_map {
    my $old_map = shift;
    my @new_map;
    assert_map ($old_map);
    for my $x (0 .. ($num_lines - 1)) {
        for my $y (0 .. ($num_columns - 1)) {
            $new_map[$x][$y] = $$old_map[$x][$y]; }}
    return address@hidden; }

sub penalize_other_explorers_gradient {
    my ($gradient, $explorer_num) = @_;
    assert_explorer ();
    assert_map ($gradient);
    for my $i (0 .. $#explorer_x) {
        if ($i != $explorer_num) {
            $$gradient[$explorer_x[$i]][$explorer_y[$i]] -= 5; }}}

sub move_explorers {
    assert_explorer ();
    my $gradient = make_seed_gradient ();
    my $seed_copy = copy_map ($gradient);
    #draw_gradient ($seed_copy); delay ();
    fill_gradient ($gradient, 0);
    #draw_gradient ($gradient); delay ();
    @new_explorer_x = ();
    @new_explorer_y = ();
    for my $i (0 .. $#explorer_x) {
        my $gradient2 = copy_map ($gradient);
        penalize_other_explorers_gradient ($gradient2, $i);
        fill_gradient ($gradient2, 1);
        #draw_gradient ($seed_copy); delay ();
        #draw_gradient ($gradient2, $explorer_x[$i], $explorer_y[$i]); delay ();
        my $max = 0;
        my @best_xo;
        my @best_yo;
        for my $xo (-1 .. 1) {
            for my $yo (-1 .. 1) {
                my $value = $$gradient2[($explorer_x[$i] + $xo) % 
$num_lines][($explorer_y[$i] + $yo) % $num_columns];
                if ($value > $max) {
                    $max = $value;
                    @best_xo = ();
                    @best_yo = (); }
                if (($value == $max)
                    && (($xo != 0)
                        || ($yo != 0))) {
                    push (@best_xo, $xo);
                    push (@best_yo, $yo); }}}
        my $xo;
        my $yo;
        if (scalar (@best_xo)) {
            my $choice = rand (scalar (@best_xo));
            #my $choice = 0;
            $xo = $best_xo[$choice];
            $yo = $best_yo[$choice]; }
        else {
            $xo = (rand (3)) - 1;
            $yo = (rand (3)) - 1; }
        # *** should make sure this is not moving to same cell as another 
explorer
        ($new_explorer_x[$i] = $explorer_x[$i] + $xo) %= $num_lines;
        ($new_explorer_y[$i] = $explorer_y[$i] + $yo) %= $num_columns;
        #draw_gradient ($gradient2, $explorer_x[$i], $explorer_y[$i]); delay ();
    }
    for my $i (0 .. $#explorer_x) {
        if ((defined $new_explorer_x[$i]) && (defined $new_explorer_y[$i])) {
            $explorer_x[$i] = $new_explorer_x[$i];
            $explorer_y[$i] = $new_explorer_y[$i]; }}
    @new_explorer_x = ();
    @new_explorer_y = (); }

sub make_my_map {
    assert_explorer ();
    my @map;
    assert_map (address@hidden);
    for my $x (0 .. ($num_lines - 1)) {
        for my $y (0 .. ($num_columns - 1)) {
            if ($known[$x][$y]) {
                $map[$x][$y] = $world[$x][$y] }
            else {
                $map[$x][$y] = ' '; }}}
    $map[$home_x][$home_y] = 'O';
    for my $i (0 .. $#explorer_x) {
        $map[$explorer_x[$i]][$explorer_y[$i]] = 'E'; }
    return address@hidden; }

initscr ();
start_color ();
noecho ();
cbreak ();

init_pair (1, COLOR_GREEN, COLOR_BLACK);

init_pair (2, COLOR_RED, COLOR_BLACK);

sub green { COLOR_PAIR (1); }
sub red { COLOR_PAIR (2); }

sub delay {
    getch ();
    #sleep (1);
}

draw_map (address@hidden);
delay ();

for my $turn (1 .. 1000) {
    draw_map (make_my_map ());
    delay ();
    move_explorers ();
    if (($turn % 20) == 1) {
        new_explorer (); }
    update_knowledge (); }