tree.klz think tank

This is for general discussion about Hidden & Dangerous 2, talk about what you liked or what you didn't like about the sequel. Talk about multiplayer games, setup matches etc.
User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

tree.klz think tank

Unread post by Ikaros » Fri Aug 05, 2011 4:05 pm

Hi everyone.
I've started looking at tree.klz to understand how collisions works. It seems a long and difficoult way, though. So I'll post every discovery I make here.. Maybe someone else will have ideas.

First of all, I advice to read how collision trees usually works:
http://en.wikipedia.org/wiki/Bounding_volume_hierarchy
http://en.wikipedia.org/wiki/Octree
http://en.wikipedia.org/wiki/R-tree
http://en.wikipedia.org/wiki/Kd-tree

I don't know which of these method is used in H&D2, but they share some principles.

The world is divided into sub-sectors, each sub-sector is divided into sub-sub-sectors, and so on.
So, given my position in game, with a quick tree research, the game can tell that I'm into sector A, but I'm also into sub-sector AB, and that I'm into sub-sub-sector ABC.

Then, each sector and sub-sector is linked to the objects that overlap that sector.
So, to detect collisions of my movements, the game has to intersect me with just the object linked by my sector, and does not have to intersect me with EVERY object present in the scene.

tree.klz is used to divide the world into sectors and sub-sectors and to associate each one to some objects from scene.4ds and scene.bin.

tree.klz is divided in at least 2 parts.
In the first part, there is a list of strings, which correspond to scene objects.
In the second part should be the division of space and linking of objects.
Last edited by Ikaros on Mon Aug 08, 2011 3:58 pm, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Fri Aug 05, 2011 4:16 pm

THE FIRST PART

I think I've hacked completely the first part.
Here is an excel that summarize it:
http://malgolan.altervista.org/forumImages/tree/first part.xls
(the part above the light blue line).

Here a detail (with examples taken by Alps 2):
First 8 bytes is an header (which is always the same, but different from
tree.klz of Mafia):
Image

Then, there is an INT (4 bytes) which tells the length of first part (Or the byte
where the second part begins, it's the same):
Image

Then, there is an INT (4 bytes) which tells how many objects from scene.4ds and
scene2.bin will be linked (879 for Alps 2):
Image

Then, there are 8 bytes unknown, usually 542 and zero.

Then, there is an array of INT, which is long 4 bytes * number of objects linked.
Every INT is an address, which points to a byte of the file itself.
It's almost an array of char*, for those who know c++

Addresses
So, @byte 24 there is the first address, which in Alps 2 is "3540":
Image

@byte 28 there is the second address, which in Alps 2 is "3560":
Image

And @byte 3536 there is the last address (only for Alps 2, which has 879 addresses),
which in Alps 2 is "18528":
Image

Labels
The first address contained the value "3540", so @byte 3540 there is the first label:
Image

The second address contained the value "3560", so @byte 3560 there is the second label:
Image

The last address contained the value "18528", so @byte 18528 there is the last label:
Image

Each label...
...has this structure:
- 4 bytes INT, which to my experience is either 1 or 2 (image A)
- A string, which match exactly an object from scene2.bin or scene.4ds
- 0x00, which tells where the string ends
- zero to N blanks which fills up the space to the next label. Each label's length (blanks included) is a multiple of 4.

Image A:
Image

@byte 18544, as predicted by value contained by byte 8, the second part begins:
Image
Last edited by Ikaros on Mon Aug 08, 2011 3:57 pm, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Fri Aug 05, 2011 4:18 pm

THE SECOND PART

The second part begins with 4 floats, which are the map boundaries.
I'll call them
- min X
- min Z
- max X
- max Z
It seems there is no hint to Y values (height).

Here, "min X" float is highlighted (~-23.013 for Alps 2):
Image

"Alps 2" X coordinate ranges from ~-23.013 to ~29.613
and Z coordinate ranges from ~-17.830 to ~31.441

Then there are 2 floats that I'll call:
- step X
- step Z
(we'll see later how they're used)

Here, "step X" float is highlighted (~3.289 for Alps 2):
Image
Step Z is ~3.079.

Then, there are 2 INT, which represent the number of portions along an axis, which I'll call
- Nr cubes X
- Nr cubes Z

In Alps 2, "Nr cubes X" is 16:
Image
and 16 is "Nr cubes Z"

Then there is a float which usually contains an "integer" value, and
that Mafia TreeRe calls "Additional collision".
In Alps 2 is 6.0 and I don't know what it means.

Then you find minY, maxY, stepY, Nr cubes Y!

The counters for next parts

Now skip the next 20 bytes (I don't know what they means)
and read the INT. For Normandy 2 mp zone is 35415 and is the number
of structures (type 1) found in third part (see below).
Image


Now skip the next 4 bytes (I don't know what they means)
and read the INT. For Normandy 2 mp zone is 209 and is the number
of structures (type 3) found in fifth part (see below).
YES: counter for 5th part precedes counter for 4th part. Why?
Image

Now skip the next 4 bytes (I don't know what they means)
and read the INT. For Normandy 2 mp zone is 79 and is the number
of structures (type 2) found in fourth part (see below).
Image

Then skip the next 88 bytes (I don't know what they means)
and go to byte 18708 (for Alps 2).
There is a row of floats values and then '#a->' repeated 4 times:
Image

If you check the float values, you'll notice that there are 3 series of
growing values.
I've highlighted the first serie:
Image

You can notice also that the serie of floats
- contains "Nr cubes X" + 1 values (*)
- begins from "min X"
- ranges to "max X"
- every value is equal to the previous one + "step X"

*Assumption: that's because each float identify a plane, which divide the space into 16
portions.

The same is valid for the third serie, that is referred to Z axis and is here highlighted:
Image

In between there is another serie, which I suppose refers to Y axis.
It contains "Nr cubes Y + 1" values that ranges from minY to maxY.
In Alps 2, they are 9 and range from ~-1.099 to ~24.727, with a step of ~3.288

I believe that these 3 series of planes along the 3 axis divide the space into small cubes.
"Nr cubes X" * "Nr cubes Y" * "Nr cubes Z", in Alps 2 is 16 * 16 * 8 = 2048 portions of space.

The three series end with a seemingly useless serie of 16 bytes.
I say useless because it's the same in every map I've inspected: "#a->" four times.

After that, the THIRD PART begins:
index.php/topic,2173.msg11104.html#msg11104
Last edited by Ikaros on Tue Aug 09, 2011 2:55 pm, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

hdmaster
Sergeant
Posts: 84
Joined: Thu Jan 27, 2011 9:31 pm
Location: Germany

Re: tree.klz think tank

Unread post by hdmaster » Fri Aug 05, 2011 5:28 pm

There are people out there who know the structure very well. I guess there names were ASM ( from the Mafia Modding Crew ) and Golod55, the author of TreeRE. Maybe they can help out, because it seems that HD2's .klz files are very similar to the ones Mafia uses.

I also think that a .klz file contains more than 2 parts. Have a look at offset 18948 in alps2\tree.klz. You can see a repeating structure ( 32 bytes long each, 14204x ) like the following:

[short]
[byte]
[byte]
[short]
[short]     increasing number, highest value is identical to number of objects -1 ( 880 in this case)
[short]
[short]     seems to be same as the increasing short value
[short]
[short]     again the same :O
[float]      -1.0 < value < 1.0
[float]      -1.0 < value < 1.0
[float]      -1.0 < value < 1.0
[float]

Here's an excerpt from a script I wrote to read that part:
                        Increasing up to 880 in alps2, 881 objects defined in the header
                          |
['002', 60, '018', '003', '001', '003', '019', '003', 1.0, -0.0, 0.0, -17.0724]
['002', 60, '001', '003', '018', '003', '000', '003', 1.0, 0.0, -0.0, -17.0724]
['002', 60, '020', '003', '000', '003', '018', '003', 0.9997, 0.026, 0.0, -17.1229]
['257', 60, '002', '003', '020', '003', '000', '003', 0.9997, 0.026, -0.0, -17.1229]
['002', 60, '021', '003', '002', '003', '020', '003', 0.9695, 0.2453, 0.0, -17.1528]
['257', 60, '003', '003', '021', '003', '002', '003', 0.9695, 0.2453, -0.0, -17.1528]
['002', 60, '022', '003', '003', '003', '021', '003', 0.8931, 0.4498, 0.0, -16.4279]
['257', 60, '004', '003', '022', '003', '003', '003', 0.8931, 0.4498, -0.0, -16.4279]
['002', 60, '023', '003', '004', '003', '022', '003', 0.7742, 0.6329, 0.0, -14.9883]
['257', 60, '005', '003', '023', '003', '004', '003', 0.7742, 0.6329, -0.0, -14.9883]
['005', 60, '024', '003', '037', '003', '036', '003', 0.6161, 0.7877, 0.0, -12.8699]
['259', 60, '006', '003', '024', '003', '037', '003', 0.6161, 0.7877, -0.0, -12.8699]
['005', 60, '025', '003', '006', '003', '024', '003', 0.4264, 0.9045, 0.0, -10.1717]
['259', 60, '007', '003', '025', '003', '006', '003', 0.4264, 0.9045, -0.0, -10.1717]
['005', 60, '026', '003', '007', '003', '025', '003', 0.217, 0.9762, 0.0, -7.0626]
['259', 60, '008', '003', '026', '003', '007', '003', 0.217, 0.9762, -0.0, -7.0626]
['005', 60, '027', '003', '008', '003', '026', '003', 0.0, 1.0, 0.0, -3.7248]
['259', 60, '009', '003', '027', '003', '008', '003', 0.0, 1.0, -0.0, -3.7248]
['005', 60, '028', '003', '009', '003', '027', '003', -0.217, 0.9762, 0.0, -0.2778]
['259', 60, '010', '003', '028', '003', '009', '003', -0.217, 0.9762, 0.0, -0.2778]
['005', 60, '029', '003', '010', '003', '028', '003', -0.4264, 0.9045, 0.0, 3.1599]
['003', 60, '029', '003', '011', '003', '010', '003', -0.4264, 0.9045, -0.0, 3.1599]
['260', 60, '030', '003', '029', '003', '011', '003', -0.6161, 0.7877, -0.0, 6.393]
['259', 60, '012', '003', '030', '003', '011', '003', -0.6161, 0.7877, 0.0, 6.3929]
['002', 60, '031', '003', '038', '003', '039', '003', -0.7742, 0.6329, 0.0, 9.2194]
['001', 60, '031', '003', '013', '003', '038', '003', -0.7742, 0.6329, -0.0, 9.2195]
['002', 60, '032', '003', '016', '003', '033', '003', -1.0, -0.0, -0.0, 14.1938]
['002', 60, '016', '003', '032', '003', '017', '003', -1.0, 0.0, 0.0, 14.1938]
['002', 60, '033', '003', '015', '003', '034', '003', -0.9997, 0.026, 0.0, 14.1326]
['257', 60, '016', '003', '033', '003', '015', '003', -0.9997, 0.026, 0.0, 14.1326]
['258', 60, '034', '003', '035', '003', '014', '003', -0.9695, 0.2453, -0.0, 13.1584]
['257', 60, '015', '003', '034', '003', '014', '003', -0.9695, 0.2453, 0.0, 13.1584]
['258', 60, '035', '003', '031', '003', '013', '003', -0.8931, 0.4498, -0.0, 11.497]
['001', 60, '035', '003', '014', '003', '013', '003', -0.8931, 0.4498, -0.0, 11.497]
['259', 65, '001', '004', '002', '004', '000', '004', 0.0, -1.0, -0.0, 0.5557]
['005', 65, '005', '004', '004', '004', '003', '004', -0.0, -1.0, -0.0, 0.5557]
['261', 14, '010', '005', '011', '005', '002', '005', 0.018, -0.9998, -0.0056, 1.0808]
['005', 14, '051', '005', '003', '005', '043', '005', 0.018, -0.9998, -0.0056, 1.0808]
['261', 14, '004', '005', '052', '005', '044', '005', 0.018, -0.9998, -0.0056, 1.0808]
['005', 14, '005', '005', '045', '005', '053', '005', 0.018, -0.9998, -0.0056, 1.0808]
['005', 14, '006', '005', '046', '005', '054', '005', 0.018, -0.9998, -0.0056, 1.0808]
['005', 14, '007', '005', '047', '005', '055', '005', 0.018, -0.9998, -0.0056, 1.0808]
['005', 14, '008', '005', '048', '005', '041', '005', 0.018, -0.9998, -0.0056, 1.0808]
['261', 14, '049', '005', '009', '005', '037', '005', 0.018, -0.9998, -0.0056, 1.0808]
['261', 14, '050', '005', '000', '005', '038', '005', 0.018, -0.9998, -0.0056, 1.0808]
['261', 14, '042', '005', '001', '005', '036', '005', 0.018, -0.9998, -0.0056, 1.0808]
['263', 14, '024', '005', '012', '005', '025', '005', 0.0398, -0.0049, 0.9992, -0.9919]
['007', 14, '012', '005', '025', '005', '013', '005', 0.0398, -0.0049, 0.9992, -0.9919]
['263', 14, '025', '005', '013', '005', '026', '005', -0.465, -0.0133, 0.8852, 10.0427]

and so one....

Hope this helps a little bit :)

After that part I have no clue how the rest of the data is stuctured, but it seems like there are 2 more parts.
I also have the assembler code of the function that reads the Tree.klz but there are parts that are too difficult to understand for me to get something useful from this
Last edited by hdmaster on Fri Aug 05, 2011 6:01 pm, edited 1 time in total.

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Fri Aug 05, 2011 11:57 pm

Hi Hdmaster!
Welcome back! Always a pleasure hearing from you :)

I had no time to write all I discovered, before.
I'll add the other informations as soon as possible.

Ok, let's say there are at least 2 parts, maybe more.
I've found out also where max / min values are stored, and a sort of 3-d grid with size of cells and number of cells.

Seems that just before the four '#a->' the whole map is divided into small cubes.
But I'll explain in detail as soon as I'll have time :)

By the way, your Alps 2 is slightly different from mine ;)
Good night.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Mon Aug 08, 2011 7:51 pm

I've tried some experiments.

First
Moving a solid object will make non-solid both where the object now is (new position), and where the object once were (old position).

This is my theory: tree.klz tells the game which objects to test for collision, regarding my position in game.

For example, if I am in the area near the fountain, the game checks collision between me and the fountain, the ground... but not with the wall at the other end of tha map. That's because of performarce.

If I move the fountain:
- when I am at the new location of the fountain, collision are not checked, because the game does not know that has to check collision with the fountain in that area of the map.
- when I am at the old location of the fountain, the tree.klz tells the game to check collision between me and fountain, but the fountain is there no more, so none collision is found.

Second
Renaming a label in the first part of tree.klz (it's equally to remove it, but preserve bytecounts and array positions) makes that object non-solid.
As expected.

Third
Changing the "increasing number" of the 32 byte structure pointed out by hdmaster (in every row where that number appears), makes that object non-solid.
As expected.

Changing the "increasing number" in just a row out of two, makes half-object solid, half-object non-solid.
Maybe the objects extends into two "cubes" (areas), and every row expresses solidity for one "cube"?

That number is repeated three times per structure, though. Changing just one or two in a single row, makes a little part of the object non-solid.
Ideas?

Moreover
The 32 bytes structure end with 3 floats, which contain values ranging from -1.0 to 1.0. Let's call them fX, fY, fZ.
I've noticed that SquareRoot( fX^2 + fY^2 + fZ^2) = 1.0, i.e. those 3 floats are a vector of length 1.0 ?
If so, they could be a direction.
The object I was experimenting with was a CEILING and the floats were 0.0 - 1.0 - 0.0, i.e. direction toward the top.
I've verified before that objects are solid from just one side...
http://malgolan.altervista.org/
Italian politicians - Not in my name!

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Tue Aug 09, 2011 7:53 am

THIRD PART

As preannunced by HdMaster, it is a serie of 32-bytes-long structures.

I copy it from his post (slightly modified), labeling the values for future use:

[byte]      b1
[byte]      b2
[byte]      b3
[byte]      b4
[short]     C1
[short]     O1 > increasing number, highest value is identical to number of objects -1 (878 in my Alps 2)
[short]     C2
[short]     O2 > seems to be same as O1
[short]     C3
[short]     O3 > seems to be same as O1
[float]      V1  > -1.0 -1.0 -1.0 < value < 1.0
[float]      RX

Let's call each of these structure a "line". Here is a picture taken from Alps 2, which shows these lines,
arranged properly (I've inserted the black highlighted serie of blanks):
Image

The O* values (O1, O2 and O3)

Apparently, O1=O2=O3 and they grow line after line, usually from zero or a small number, up to "number of objects linked" - 1. So O* are indexes of the array of labels loaded by the First Part.

For example, I've tried replacing all the O* = 877 with 876, and the 877th object becomes non-solid.

A certain O* value may appear in more than one line. In the image above, the number 3 appears in ALL the lines visible. Replacing the O* value of just a subset of lines, makes portions of the object solid and portions non-solid.

I think that, for every O value (i.e. for every object), there is a line for every cube of space the object is in.
So big objects will have multiple line, because they extends their boundaries into several portions of space (which I remind you, have side ~3.0)

In Alps 2, the serie of O* begins with 3, which appears in 34 lines. Then there is 4, which appears in only 2 lines:
Image

So the 5th object (5th and not 4th because the array starts counting from zero) should be a small one, while the 4th object a big one.

*I'll post an image of these objects taken from 3ds max as soon as I have it

The C* values (C1, C2 and C3)

Given a certain O (for example 4), and taking ALL the C* values of ALL the lines that have O*=that number,
they usually cover all the values from 0 up to "number of lines" * 3.

In the image above, for the two highlighted lines which have O*=4, the C* values are:
- 1, 2, 0 (first line)
- 5, 4, 3 (second line)
i.e.: 0, 1, 2, 3, 4, 5.

Many times, though, some values repeat more than once.

The V* values (V1,V2 and V3)

V* range from -1.0 to 1.0 and SquareRoot(V1^2 + V2^2 + V3^2) = 1.0
So I think that V1, V2 and V3 represent a vector of length 1.0, i.e. a "Unit Vector":
http://en.wikipedia.org/wiki/Unit_vector

This could express a direction.
For example, I've inspected an object which is a CEILING.
In its lines, V1,V2,V3 are 0.0, 1.0, 0.0, i.e. "toward the top" (assuming V1 is X, V2 is Y and V3 is Z).

the bytes

b1 takes a only a dozen of different values (seems 1,2,3,4,5,6,7)
b2 seems to be always 1 or zero.
b3 seems to be always zero.
b4 takes a only a dozen of different values. Usually, given a certain O*, the correspondent b2 is fixed. Material?
Last edited by Ikaros on Tue Aug 09, 2011 12:20 pm, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Tue Aug 09, 2011 1:14 pm

FOURTH PART

After the third part, there is another serie of 32-bytes structures, slightly different from the previous one
(Now I'm inspecting Normandy 2 mp zone):

[byte]      b1
[byte]      b2
[byte]      b3
[byte]      b4
[short]     O > increasing number, highest value is up to number of objects -1
[short]     C
[float]      F1
[float]      F2
[float]      F3
[float]      F4
[float]      F5
[float]      F6

These structure (third and fourth parts) may represent different wrap solid, for examples planes, boxes, cylinder or spheres.

This one has 6 floats, so it could be a box identified by two vertexes.
This theory has a solid basis...

In Normandy 2 mp zone,
minX                minY                minZ
-82,38436      -1,0381317      -113,25379

maxX              maxY                maxZ
77,90741        25,67128        52,407784

F1 ranges from  -60.7 to 71.5
F2 ranges from      0.0 to 12.2
F3 ranges from -101.1 to 45.5
F4 ranges from  -51.8 to 77.9
F5 ranges from      0.0 to 14.3
F6 ranges from -100.6 to 52.4

F1,F2,F3 (x,y,z) seems to be the lower vertex that identifies the box.
F4,F5,F6 (x,y,z) seems to be the higher vertex that identifies the box.
Last edited by Ikaros on Tue Aug 09, 2011 1:33 pm, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Tue Aug 09, 2011 2:47 pm

FIFTH PART

After the fourth part, there is a serie of 192-bytes structures.

However, the count of these structure in the "second part" precedes the count of structure in the "fourth part".
So, maybe, also a pointer to the serie beginning is needed (beyond the number of structures).

The structure looks like:
[byte]      b1
[byte]      b2
[byte]      b3
[byte]      b4
[short]     O > a pointer to the array of objects in "First Part"
[short]     C

[float]      X1 > a coordinate along X axis
[float]      Y1 > a coordinate along Y axis
[float]      Z1 > a coordinate along Z axis

[float]      X2 > a coordinate along X axis
[float]      Y2 > a coordinate along Y axis
[float]      Z2 > a coordinate along Z axis

[float]      Q1
[float]      I1
[float]      J1
[float]      K1 > maybe these 4 values are a rotation, but is seems not so


[float]      Q2 = - Q1
[float]      I2 = - I1
[float]      J2 = - J1
[float]      K2 = K1 ~ 0.0

32 more floats follow...

Any ideas about the meaning of these values?
If someone want to inspect them,
I'll upload several .csv which contains values extracted from a couple of maps:
malgolan.altervista.org/forumImages/tree/Tree-klz.zip

I've tested the positions of flagpoles in Normandy 2 mp zone, and both X1,Y1,Z1 and X2,Y2,Z2 correspond to the object pointed by O.
Last edited by Ikaros on Tue Aug 09, 2011 4:15 pm, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

hdmaster
Sergeant
Posts: 84
Joined: Thu Jan 27, 2011 9:31 pm
Location: Germany

Re: tree.klz think tank

Unread post by hdmaster » Tue Aug 09, 2011 5:00 pm

Very great work Ikaros !

Looks like b1 is used to identify the type/length of a structure:

0x80 length: 192
0x82 length:  32 ( none in normandy2_mp_zone but in sicily1 @ offset 1976984)
0x83 length: 160 ( similar to the one with length 192 )

lexov
Private
Posts: 6
Joined: Sun Aug 07, 2011 11:21 pm

Re: tree.klz think tank

Unread post by lexov » Tue Aug 09, 2011 10:46 pm

Hi,

I'm the ASM hdmaster referred to.

The tree.klz format seems to be similar to the one used by Mafia: City of Lost Heaven. Maybe some things are different, but even then it should give you a descent starting point. ;)

Code: Select all

//
// KLZ Header
//

uint32 Signature  // GifC
uint32 Version // 5

uint32 CollisionDataOffset
uint32 NumLinks

uint32 _Unknown[2]

//
// Links
//

uint32 LinkNameOffsetTable[NumLinks] // offsets relative from file start
{
  uint32 Flags
  char Name[]
} LinkNameTable[NumLinks]  // the entries are aligned to 4 byte boundaries, gaps are padded with 0x20

//
// Collision Data Header
//

float32 GridMinX
float32 GridMinY

float32 GridMaxX
float32 GridMaxY

float32 CellWidth
float32 CellHeight

uint32 GridWidth
uint32 GridHeight

uint32 Unknown

uint32 Reserved[2]

uint32 Reserved
uint32 NumFaces

uint32 Reserved
uint32 NumXTOBBs

uint32 Reserved
uint32 NumAAABBs

uint32 Reserved
uint32 NumSpheres

uint32 Reserved
uint32 NumOBBs

uint32 Reserved
uint32 NumCylinders

uint32 Reserved
uint32 NumUnknownType  // always 0

uint32 Unknown

//
// Collision Grid Cell Boundaries
//

float32 CellBoundariesX[GridWidth+1]
float32 CellBoundariesY[GridHeight+1]

//
// Collision Data
//

uint32 CollisionDataMagic // always 0x3E2D6123

// Notes on triangle collision data:
//  - the indices need to be sorted according to worldspace x in ascending order
//  - the SortInfo field provides info on the original order of the vertices as they appear in the mesh's index buffer for that face
//      0 - if the vertices are already in correct order or merely shifted
//      1 - otherwise

{
  uint32 Properties  // Material (8 bit) | Flags (8 bit) | SortInfo (8 bit) | 0 (8 bit)
  uint32 Indices[3]  // (Link (index into LinkNameOffsetTable) (16bit) | Index of vertex in mesh's vertex buffer (16 bit))

  // plane the triangle lies in
  vector3 Normal  // needs to point in opposite direction compared to the mesh face normal (IIRC!), i.e. if the mesh face normal is (1 0 0), the col face normal needs to be (-1 0 0)
  float Distance
} FaceColData[NumFaces]

{
  uint32 Properties // Material(8 bit) | Flags (8 bit) | 0 (8 bit) | 0x81 (8 bit)
  uint32 Link // index into LinkNameOffsetTable

  vector3 Min
  vector3 Max
} ABBColData[NumAABBs]

{
  uint32 Properties // Material(8 bit) | Flags (8 bit) | 0 (8 bit) | 0x80 (8 bit)
  uint32 Link

  // AABB
  vector3 Min
  vector3 Max

  vector3 Extends[2]
  matrix4x4 Transform
  matrix4x4 InverseTransform
} XTOBBColData[NumXTOBBs]

// height for cylinders is encoded in grid
{
  int32 Properties // Material(8 bit) | Flags (8 bit) | 0 (8 bit) | 0x84 (8 bit)
  uint32 Link

  vector2 Position  // cylinders only have a 2d position!
  float Radius
} CylinderColData[NumCylinders]

// Note that while OBB col data describes a regular OBB it may only be used for creating
// flat collision rectangles like for walls etc. For 'real' OBBs, use XTOBBs.
{
  uint32 Properties // Material(8 bit) | Flags (8 bit) | 0 (8 bit) | 0x83 (8 bit)
  uint32 Link

  vector3 Extends[2]
  matrix4x4 Transform
  matrix4x4 InverseTransform
} OBBColData[NumOBBs]

{
  uint32 Properties // Material(8 bit) | Flags (8 bit) | 0 (8 bit) | 0x82 (8 bit)
  uint32 Link

  vector3 Position
  float Radius
} SphereColData[NumSpheres]

//
// Collision Grid
//
// The primitives defined above are referenced by those cells of the grid that are intersected
// by the corresponding primitive.
//
// There're restrictions on the order in which references may appear in each cell:
//   - References to primitives (boxes, spheres, ...) need to be stored before references to triangles
//   - Triangle references need to be sorted according to worldspace x of first indexed vertex
//     note that first indexed vertex is always the one with smallest worldspace x of the triangle,
//     see face col data description above
//
// Failing to obey these rules causes certain collision data to be ignored

uint32 CollisionGridMagic // always 0x3E2D6223

{
  uint32 NumObjects
  uint32 Reserved[2]
  float32 Height

  uint32 References[NumObjects]  // Format: (Type (8 bit)) | (Offset into array of Type (24 bit)))
                  // Type can be
				  //   0x00 - Face
				  //   0x80 - XTOBB
				  //   0x81 - AABB
				  //   0x82 - Sphere
				  //   0x83 - OBB
				  //   0x84 - Cylinder

  ubyte8 Flags[NumObjects]  // needs to be aligned to 4 bytes, purpose unknown
} Cells[GridWidth*GridHeight]
This info is enough for building working tree.klz files from scratch, despite the Unknown/Reserved fields. Note that Mafia loads the tree.klz in one piece into memory which is why some fields need to be aligned to 4 byte boundaries. The Reserved fields (at least some of them) are overwritten in memory with pointers to certain objects.

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Wed Aug 10, 2011 7:59 am

Thank you ASM / lexov!  :eek:

What you post from Mafia matches what I discovered for Hidden,
except Hidden handles also the Y coordinate in the grid of cells.

So this shifts the second part of the file and makes it unreadable by Mafia editors.

Even so, if you have a "tree.klz generator" from Mafia (the source code),
I'll try to adapt it for Hidden purposes.

It would be very time-saving!

PS: a question..
How were tree.klz generated, for Mafia?
Completely manually?
Or maybe exported from a 3d-editor?
Or even automatically calculated?
Thank you very much! :)

Edit: Also the "DataMagic" is repeated 4 times in Hidden, instead of just once
Last edited by Ikaros on Wed Aug 10, 2011 8:01 am, edited 1 time in total.
http://malgolan.altervista.org/
Italian politicians - Not in my name!

hdmaster
Sergeant
Posts: 84
Joined: Thu Jan 27, 2011 9:31 pm
Location: Germany

Re: tree.klz think tank

Unread post by hdmaster » Wed Aug 10, 2011 12:09 pm

Wow, thanks lexov!  :cool:
This information will save us a lot of work! :D

There are just a few small differences I've encountered so far. Here some examples:

Code: Select all

// Header

[char4]			FourCC: GifC
[short]			Version major: 5
[short]			Version minor: 1
...
As Ikaros already mentioned H&D2 also handles the Z axis ( I always call it Z instead of Y because 3ds Max has a Z-Axis up coordinate system ). So the header looks a bit different like this:

Code: Select all

[float]			GridMinX
[float]			GridMinY

[float]			GridMaxX
[float]			GridMaxY

[float]			CellWidth
[float]			CellLength

[long]			GridWidth
[long]			GridLength

[float]			???
	
[float]			GridMinZ
[float]			GridMaxZ

[float]			CellHeight
[long]			GridHeight
...
The order of the cell boundaries is different

Code: Select all

[float]			CellBoundariesX[GridWidth+1]
[float]			CellBoundariesZ[GridHeight+1]
[float]			CellBoundariesY[GridLength+1]
The result of the grid of 'Africa1_mp\tree.klz' in 3ds Max. The grey lines are the terrain of Africa1.

Image

Uploaded with ImageShack.us

// Update

Collision faces have exactly the same strucure as in Mafia I. But what meaning/purpose has the value distance for each face?

Face collision of Af1

Image

Uploaded with ImageShack.us
Last edited by hdmaster on Wed Aug 10, 2011 1:57 pm, edited 1 time in total.

User avatar
Ikaros
Sergeant
Posts: 79
Joined: Wed Mar 23, 2011 11:30 am
Location: Italy
Contact:

Re: tree.klz think tank

Unread post by Ikaros » Wed Aug 10, 2011 6:17 pm

Ahahha :D you're a genius!

Now we should start thinking about an exporter!

I though it could be done with 3ds max:
- import a scene.4ds
- delete all non-solid objects (by user)
- define max, min and steps (by user)
- scan every face of every mesh left and create a tree.klz

Do you need help?
http://malgolan.altervista.org/
Italian politicians - Not in my name!

hdmaster
Sergeant
Posts: 84
Joined: Thu Jan 27, 2011 9:31 pm
Location: Germany

Re: tree.klz think tank

Unread post by hdmaster » Thu Aug 11, 2011 12:12 am

I need help :P

@lexov:
I have a few questions for you :)

What's the purpose of the 'vector3 Extends[2]' values?
The bounding boxes are built just from one lower and one upper vertex, right?
What effects do the different flags have?


// Update

I made a list with the materials and their IDs based on the hdmaterials.def file. It would be nice if someone would check the translation and correct the errors and add the missing ones (czech to english or german)

Code: Select all

Mat Czech				German					English

00  Neplatny				Ung?ltig				Not valid
01  Default
02  Default
03  Default
04  Default
05  Default
06  Default
07  Default
08  Default
09  Default
10  Default	
11  Tenk? plech, kapota auta 		D?nnes Blech, Motorhaube		thin sheet metal, hood
12  Plech 2-6mm				Blech 2-6 mm				sheet metal 2-6 mm 
13  Panc?? (6-20 mm) a jin? masivn	??? (6-20mm) ??? Massivholz		??? solid wood
14  Panc?? (20-40mm) a jin? masivn	??? (20-40mm) ??? Massivholz		??? solid wood
15  Panc?? (40 - 60 mm) a jin? mas	??? (40-60mm) ??? Massivholz		??? solid wood
16  Panc?? (60 -80 mm) a jin? masi	??? (60-80mm) ??? Massivholz		??? solid wood
17  Panc?? (80 - moc mm) a jin? ma	??? (80 und dicker) ???			??? solid wood
18  Trubky				Rohre					pipes/tubing
19  Plechov? ro?ty			verrostetes Metall			rusty metal
20  Pletivo				Gitter					lattice
21  Parkety				Parkett					parquet
22  Parkety - nepr?st?eln?		Parkett - kugelsicher			parquet - bulletproof
23  D?ev?n? schody			Holztreppe				wooden stairs
24  D?ev?n? schody - nepr?st?eln?	Holztreppe - kugelsicher		wooden stairs - bulletproof
25  D?evo 0 - 10 cm			Holz 0 - 10 cm				wood 0 - 10 cm
26  D?evo 10 -30 cm			Holz 10 - 30 cm 			wood 10 - 30 cm
27  D?evo 30 - 50 cm			Holz 30 - 50 cm				wood 30 - 50 cm
28  D?evo 50 - 100 cm			Holz 50 - 100 cm			wood 50 - 100 cm
29  Prkenn? podlaha - nepr?st?eln?	Dielenboden - kugelsicher		plank floor - bulletproof
30  D?ev?n? molo, masivn? d?ev?n? 	???					???
31  Voda brod?c?			Wasser (waten)				water (wade through)
32  Voda plavac? 			Wasser (schwimmen)			water (swim)
33  Led					Eis					ice
34  Sn?h				Schnee					snow
35  Hlubok? sn?h, ledovec  		Tiefschnee, Gletscher			deep powder snow, glaciers	
36  Sn?h - nepr?st?eln?			Schnee - kugelsicher			snow - bulletproof
37  Led - nepr?st?eln?			Eis - kugelsicher			ice - bulletproof
38  Koberec 				Teppich/Bettdecke			Carpet / blanket
39  Kamen? schody			Steintreppe				stone stairs
40  Kamen? schody - nepr?st?eln?	Steintreppe - kugelsicher		stone stairs - bulletproof
41  P?sek				Sand 					sand
42  P?sek - moc				viel Sand				much sand
43  Hl?na				Erde/Ton/Lehm				soil / clay / loam
44  Hl?na - moc				viel Erde/Ton/Lehm			much soil / clay / loam
45  Pytle s p?skem, hl?nou		Sandsack, ???				sandbag
46  Lesn? povrch (jehli??)		Wald					forest
47  Lesn? povrch (list?)		Wald (Bl?tter)				forest (leaves)
48  Cesta, silnice			Weg, Stra?e				way, road
49  ?t?rk				???					???
50  Tr?va				???					???
51  Sk?la 50 - 80 mm			Stein/Fels 50 - 80 mm			stone / rock 50 - 80 mm
52  Sk?la 80 -  moc			Stein/Fels 80 mm und dicker		stone / rock 80 mm and thicker
53  Beton 20 cm				Beton 20 cm				concrete 20 cm
54  Beton 50 - 80 cm			Beton 50 - 80 cm			concrete 50 - 80 cm
55  Beton 80 - moc			Beton 80 cm  und mehr			concrete 80 cm and thicker
56  Zdi dom? 15 cm			Hauswand 15 cm				wall 15 cm
57  Zdi dom? 30 -45 cm			Hauswand 30 - 45 cm			wall 30 - 45 cm
58  Zdi dom? 60 - 80 cm			Hauswand 60 - 80 cm			wall 60 - 80 cm
59  Zdi dom? 80 - 100 cm		Hauswand 80 - 100 cm 			wall 80 - 100 cm
60  Zdi dom? 100 - moc			Hauswand 100 cm und dicker		wall 100 cm and thicker
61  Su?					???					???
62  Sklo				Glas					glass
63  Panc??ov? sklo  (5 cm.- pr?zor	gepanzertes Glas (5 cm - ???)		bulletproof glass (5 cm - ???)
64  Kamenn? dla?ba			Steinfliesen				stone tiles
65  Kamenn? dla?ba - nepr?st?eln?	Steinfliesen - kugelsicher		stone tiles - bulletproof
66  ??iv? tvor, mrtvola (maso)		Lebewesen, Leiche (Fleisch)		living organisms, corpse (meat)
67  Pl?t?n? st?na stanu			???					???
68  Minov? pole - neodstraniteln? I	Minenfeld - ???				minefield - ???
69  Minov? pole - neodstraniteln? I 	Minenfeld - ???				minefield - ???
70  Studen? voda			Kaltes Wasser				cold water
71  Ohe?				???					???
72  Die
73  Die in pieces
74  Ladder - d?evo			Leiter - Holz				ladder - wood
75  Ladder - kov			Leiter - Metall				ladder - metal
76  Border				
77  Border - enemy filter		
78  Schody kovov? 			Metalltreppe				metal stairs
79  Schody kovov? - nepr?st?eln?	Metalltreppe - kugelsicher		metal stairs - bulletproof
80  Ta??kov? st?echa			Ziegeldach				tiled roof
81  Ta??kov? st?echa - nepr?st?eln?	Ziegeldach - kugelsicher		tiled root - bulletproof
82  Kachl?ky + st?na 15 - 40 mm		Fliesen + ??? 15 - 40 mm		tiles + ??? 15 - 40 mm
83  Kachl?ky + st?na 40 - 80 mm		Fliesen + ??? 40 - 80 mm		tiles + ??? 40 - 80 mm
84  Kachl?ky + st?na 80 - moc mm	Fliesen + ??? 80 mm und dicker 		tiles + ??? 80 mm and thicker
85  Pap?r				Papier					paper
86  Bahno				Schlamm/Dreck				mud / dirt
87  Matrace				Matratze				mattress
88  Kuze (nabytek)			Leder (M?bel)				leather (furniture)
89  Knihy				B?cher					books
90  Ostnat? dr?t 			Stacheldraht				barbed wire
91  Sn?h s travou - neprustr.		Gras mit Schnee bed. - kugelsicher	grass covered with snow - kugelsicher
92  Tr?va 2 (kvuli dekoratoru)		Gras 2 ???				grass 2 ???
93  Ba?ina				???					???
94  Morske dno				Meeresboden				seabed
95  Kameno-Hlinit? cesta		Lehm/Steinstra?e			dirt road / stone road
96  popadan? stromy 			umgest?rzte B?ume			fallen trees
97  ?t?rk na aktora			???					???
98  Tr?va 3 (minove pole)		Gras 3 (Minenfeld)			grass 3 (minefield)
99  Tr?va 4 (kvuli dekoratoru)		Gras 4 (???)				grass 4 (???)
100  Voda brod?c? - zvuk		durchs Wasser waten - Ton/Sound		wade through the water - sound

// Update 2

I have a problem with the 4x4 matrices. MaxScript handles only 4x3 matrices ( actually it's a 4x4 but the last column is filled in internally with [0, 0, 0, 1] ). But the last column of a klz 4x4 matrix is not [0, 0, 0, 1], so i need to convert the 4x4 matrix to a 4x4 matrix, where the last column has to be [0,0,0,1], to use it as an 4x3 matrix. But my mathematical knownledge of matrices is not that good :( Do you have any suggestions?
Mistake. Solved ;)
Last edited by hdmaster on Thu Aug 11, 2011 12:33 pm, edited 1 time in total.

Post Reply

Who is online

Users browsing this forum: No registered users and 10 guests