Page 2 of 5

Re: FLD2 proposal [for the future]

Posted: 23 Jan 2009, 14:36
by Technology
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: Select all

# See
# for information about the file formats.
use strict;
use constant {
	TILE_WALK => 1,

my $i = 0;
foreach my $name (sort(listMaps("."))) {
	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) {
			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]);

	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)

Re: FLD2 proposal [for the future]

Posted: 23 Jan 2009, 16:03
by sli
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.

Re: FLD2 proposal [for the future]

Posted: 26 Jan 2009, 15:28
by Technology
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 == 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 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

Re: FLD2 proposal [for the future]

Posted: 26 Jan 2009, 16:25
by Motivus
unsigned char should &1 just fine, but if perl treats it as a string internally then it may be a problem

Re: FLD2 proposal [for the future]

Posted: 26 Jan 2009, 21:41
by sli
I usually just check the data's type and act accordingly.

Code: Select all

if blah.isdigit():
    print 'blah is a number'
    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.

Re: FLD2 proposal [for the future]

Posted: 27 Jan 2009, 01:19
by kali
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.

Re: FLD2 proposal [for the future]

Posted: 27 Jan 2009, 12:02
by Technology
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?

Re: FLD2 proposal [for the future]

Posted: 27 Jan 2009, 13:47
by sli
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.

izlude.fld2: 71,828 bytes

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

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.

Re: FLD2 proposal [for the future]

Posted: 27 Jan 2009, 15:35
by Technology
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?

Re: FLD2 proposal [for the future]

Posted: 27 Jan 2009, 16:09
by sli
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.