Openkore.com

OpenKore Forums
It is currently 23 Jul 2018, 03:28

All times are UTC - 5 hours [ DST ]





Post new topic Reply to topic  [ 41 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next
Author Message
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 14:36 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
Reason 1 and 3 (needs testing) should be covered in terms of fld2 creation.
But what exactly do you mean by index size (reason2) Motivus?

conversion gat&rsw => fld2
Code:
#!/usr/bin/perl
# See http://www.openkore.com/wiki/index.php/Field_file_format
# for information about the file formats.
# GAT2FLD2
use strict;
use constant {
   TILE_NOWALK => 0,
   TILE_WALK => 1,
   TILE_SNIPE => 2,
   TILE_WATER => 4,
   TILE_CLIFF => 8,
};

my $i = 0;
foreach my $name (sort(listMaps("."))) {
   $i++;
   gat2fld("$name.gat", "$name.fld2", readWaterLevel("$name.rsw"));
}

sub listMaps {
   my ($dir) = @_;
   my $handle;

   opendir($handle, $dir);
   my @list = grep { /\.gat$/i && -f $_ } readdir $handle;
   closedir $handle;

   foreach my $file (@list) {
      $file =~ s/\.gat$//i;
   }

   return @list;
}

##
# float readWaterLevel(String rswFile)
#
# Read the map's water level from the corresponding RSW file.
sub readWaterLevel {
   my ($rswFile) = @_;
   my ($f, $buf);

   if (!open($f, "<", $rswFile)) {
      print "Cannot open $rswFile for reading.\n";
      exit 1;
   }
   seek $f, 166, 0;
   read $f, $buf, 4;
   close $f;

   return unpack("f", $buf);
}

##
# void gat2fld(String gat, String fld, float waterLevel)
#
# Convert a .GAT file to the specifid .FLD file.
sub gat2fld {
   my ($gat, $fld, $waterLevel) = @_;
   my ($in, $out, $data);
   
   # conversion (ex. $TILE_TYPE[0] = TILE_WALK = 1), (ex. $TILE_TYPE[1] = TILE_NOWALK = 0)
   my @TILE_TYPE = (   TILE_WALK,            # 0) Walkable
                  TILE_NOWALK,         # 1) Non-walkable
                  TILE_WATER,            # 2) Non-walkable water
                  TILE_WALK|TILE_WATER,   # 3) Walkable water
                  TILE_WATER|TILE_SNIPE,   # 4) Non-walkable water (snipable)
                  TILE_CLIFF|TILE_SNIPE,   # 5) Cliff (snipable)
                  TILE_CLIFF,            # 6) Cliff (not snipable)
                  TILE_NOWALK);         # 7) Unknown

   if (!open $in, "<", $gat) {
      print "Cannot open $gat for reading.\n";
      exit 1;
   }
   if (!open $out, ">", $fld) {
      print "Cannot open $fld for writing.\n";
      exit 1;
   }

   binmode $in;
   binmode $out;

   # Read header. Yes we're assuming that maps are never
   # larger than 2^16-1 blocks.
   read($in, $data, 14);
   
   my $width = unpack("V", substr($data, 6, 4));
   my $height = unpack("V", substr($data, 10, 4));
   my $size = $width * $height;
   # when y = height, we variate x from 0 to width
   # thus, we variate block offset from size - width to size
   my $max_Y = $size - $width;

   #print $out pack("v", $index);
   print $out pack("v", $width);
   print $out pack("v", $height);

   my $y = 1;
   my $x = 1;
   while (read($in, $data, 20)) {

      my ($a, $b, $c, $d) = unpack("f4", $data);
      my $type = unpack("C", substr($data, 16, 1));
      my $averageDepth = ($a + $b + $c + $d) / 4;

      # make upper blocks unwalkable
      if ($y > $max_Y ) {
         print $out pack("C", 0);
      # make rightern blocks unwalkable
      } elsif ($y == $x * $width) {
         $x++;
         print $out pack("C", 0);

      # In contrast to what the elsif-condition tells you,
      # we're actually checking whether this block
      # is below the map's water level.
      # Block is below water level.
      } elsif ($averageDepth > $waterLevel) {
         # add bitflag water to non-water blocks
         print $out pack("C", (($TILE_TYPE[$type] & TILE_WATER) == TILE_WATER) ? $TILE_TYPE[$type] : $TILE_TYPE[$type]|TILE_WATER);
      # Block is above water level
      } else {
         print $out pack("C", $TILE_TYPE[$type]);
      }
   $y++;
   }

   close $in;
   close $out;
}
(with $y i'm actually referring to the y'th block number) (with $x i'm actually referring to the x'th group of blocks) (so that $y = $x * width)

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 16:03 
Offline
Perl Monk
Perl Monk

Joined: 04 Apr 2008, 17:26
Posts: 811
Ported it to Python and considering using FLD2 myself. The resulting files should share the same MD5 hash, so it'll be easy to test.

_________________
cs : ee : realist


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 26 Jan 2009, 15:28 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
It is possible to just use the old pathfinding algorithm. (and eventually improve/change it)
The .dist files don't even change a bit, except for that we make the rightern and upper tiles non-walkable.
This is because they are created according to the walkable / non walkable block data and this data stays the same (almost).

Tho when implementing the fld2 format i've ran into one problem.
And after doing some further investigation, a bug in the current system was found.
BUG: Kore doesn't treat 'walkable water' as walkable in .dist generating. Read more about it here.
Only data[i] == 0 (old walkable) checks are possible.
The new format has 1 and 5 as walkable.
The solution would be doing a bitwise AND operation on data[i] with 1, but such operation seems not possible. (because of the datatype? 'unsigned char')

What do you guys prefer, i can either:
- post up all diff's here
- branch off a testing version

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 26 Jan 2009, 16:25 
Offline
Developers
Developers

Joined: 04 Apr 2008, 13:33
Posts: 157
unsigned char should &1 just fine, but if perl treats it as a string internally then it may be a problem

_________________
Oh no.


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 26 Jan 2009, 21:41 
Offline
Perl Monk
Perl Monk

Joined: 04 Apr 2008, 17:26
Posts: 811
I usually just check the data's type and act accordingly.
Code:
if blah.isdigit():
    print 'blah is a number'
else:
    print 'blah is not a number'

Technically, Perl itself has no concept of unsigned chars, etc. At least I don't think it does. Python has a theoretically infinite size for integers and I assume Perl's integer ceiling is really high as well, everything else is a string (or array, or hash, or what have you), but they can all be scalars. A quick Google search could probably confirm.

_________________
cs : ee : realist


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 27 Jan 2009, 01:19 
Offline
OpenKore Monk
OpenKore Monk

Joined: 04 Apr 2008, 10:10
Posts: 474
I haven't seen the sources yet, but I'd like to see the diffs first.

Dist files (iirc) are used for the wall avoidance algos. If there is a bug, it should show in maps with large amounts of water (byalan?) where it manifests in "wall-hugging" behavior.

_________________
Got your topic trashed by a mod?

Trashing topics is one click, and moving a topic to its proper forum is a lot harder. You expend the least effort in deciding where to post, mods expend the least effort by trashing.

Have a nice day.


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 27 Jan 2009, 12:02 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
A dist file, is nothing more than the minimal distance to a wall for each tile. (for nonwalkable blocks, this distance is 0 obviously)
The lower the distance to a wall, the higher the weight of that block.
When wall avoiding when routing is enabled,
kore will rather route the bot over blocks that have lower weight.

So if kore in the dist files thinks that walkable water is not walkable (wich now is the case: walkable water blocks have distance 0 aswell now!),
it will think that it is a wall and avoid them and the near walkable blocks, when routing to specific coordinates.

This could lead to an univocal routing pattern in maps that contain allot of walkable water. (like anolian map? or yea byalan)
With the result of encountering less mobs or for wizards that use waterball, with the result of not being able to execute waterball at times, if at all.
(maybe in that case a config option for them to avoid walking on non-water walkable blocks, but still do so when there is no other possebility)

Can anyone confirm this behaviour?

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 27 Jan 2009, 13:47 
Offline
Perl Monk
Perl Monk

Joined: 04 Apr 2008, 17:26
Posts: 811
Motivus wrote:
If we really wanted to we could do 4 bits per tile instead of the current 8 and halve map size, but there's not much of a point.

Actually, there's plenty of point to this. Erok's FLD2 pack is 49.4 megs, and OpenKore's is 53.5 megs. Using repetition and/or nybbles would cut size down dramatically. The alternative would be to bzip2 or gzip them by default.

Original
izlude.fld2: 71,828 bytes

Gzip
izlude.fld2.gz: 2,665 bytes
Savings: 96.29%

Bzip2
izlude.fld2.bz2: 2,256 bytes
Savings: 96.84%

Update: The entire Erok field pack is now 1.17 megs. That's 97.65% smaller.

_________________
cs : ee : realist


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 27 Jan 2009, 15:35 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
Amazing, thats huge compression.

Other than reducing the size the fld files use on the harddrive,
it would indeed also be rewarding to reduce their size in the RAM memory.
The size of the fld and dist are aproximately the same, and for the biggest map they take about 0.3 MB together.

Motivus wrote:
If we really wanted to we could do 4 bits per tile instead of the current 8 and halve map size, but there's not much of a point.

This would reduce size on HD and in this case RAM too right?

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 27 Jan 2009, 16:09 
Offline
Perl Monk
Perl Monk

Joined: 04 Apr 2008, 17:26
Posts: 811
Well, using a nybble per block instead of a byte would probably decrease memory usage, but probably not by very much. Like you said, we're talking about a total of 300k of memory for the largest map. Not really much to sweat considering the data simply has to be there or A* can't route. Compression the fields doesn't do anything but save disk space. It slows loading times and increases memory usage, but at such insignificant amounts that it's barely worth mentioning. The only overhead is created from having to repeat so many values so many times, which isn't really that much overhead. That also explains the incredible compression ratio (27:1).

That said, I'll gzip all the fields (since Kore doesn't support bzip2) and see what kind of size reduction I get from that. Kore has more fields than Erok at the moment, so it'll be larger by default. Not by much, though.

Which reminds me, need to write a FLD -> FLD2 converter.

Update: Kore field pack is 1.29 megs with gzip compression. Not to shabby.

_________________
cs : ee : realist


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 41 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next

All times are UTC - 5 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group