AI 2008 FLD2 & Pathfinding

Wrote new code? Fixed a bug? Want to discuss technical stuff? Feel free to post it here.

Moderator: Moderators

Message
Author
Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#11 Post 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

#!/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!

sli
Perl Monk
Perl Monk
Posts: 811
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#12 Post 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.
cs : ee : realist

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#13 Post 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
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!

Motivus
Developers
Developers
Posts: 157
Joined: 04 Apr 2008, 13:33
Noob?: Yes

Re: FLD2 proposal [for the future]

#14 Post by Motivus »

unsigned char should &1 just fine, but if perl treats it as a string internally then it may be a problem
Oh no.

sli
Perl Monk
Perl Monk
Posts: 811
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#15 Post by sli »

I usually just check the data's type and act accordingly.

Code: Select all

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

kali
OpenKore Monk
OpenKore Monk
Posts: 474
Joined: 04 Apr 2008, 10:10

Re: FLD2 proposal [for the future]

#16 Post 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.
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.

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#17 Post 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?
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!

sli
Perl Monk
Perl Monk
Posts: 811
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#18 Post 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.

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

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#19 Post 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?
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!

sli
Perl Monk
Perl Monk
Posts: 811
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#20 Post 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.
cs : ee : realist

Post Reply