Windcatcher
03-01-2004, 10:56 AM
This is in response to a recent question about .WLD files. I don't know how practical this would be for the server team, but as many of us know there are issues regarding knowing accurate Z positions in the server code and other items, like knowing the proximity to water. I realized that my reply might be useful to others, so what follows is a more general treatise on BSP trees and what can be done with the BSP trees in .WLD files.
First off, I'm assuming that anyone who reads this has first read the .WLD reference I put out and is familiar with the basic anatomy of .WLD files. Specifically, I'm assuming that you know what "fragments" are and that fragments are identified by a hexadecimal number.
To make use of the information in .WLD files, at the very least you'll have to do the following (this assumes you can already load .S3D files and extract the .WLD files and their fragments):
1. There will be only one 0x21 fragment, which is the BSP tree. It's basically an array of records. Load this into a structure where you can access all nodes.
2. Make an array that points to all 0x22 fragments.
3. Make an array that points to all 0x36 fragments. If your .WLD-loading code is similar to mine, then, for each 0x36 fragment, there will be a 0x22 fragment that points to it. This does *not* mean that every 0x22 fragment points to a 0x36 fragment, since there might not actually be any polygons in the volume that a particular 0x22 fragment represents. However, an "empty" 0x22 fragment *can* be tagged as a water area (e.g. it's far enough below the water surface and far enough above the ocean floor). It's important to understand the hierarchy:
0x21
|
+----> xxx 0x22's
|
+-----> no more than xxx 0x36's (one 0x22 per 0x36).
Each 0x22 region fragment represents a *volume* in space. Each 0x36 fragment contains all the polygons in a particular 0x22 region. The flag field in each 0x22 will tell you whether it has a 0x36 (or if your .WLD code is like mine then you only have to check to see if the appropriate fragment pointer is null or not).
4. Load any 0x29 region lists you're interested in. A 0x29 fragment lists all regions that have a particular attribute. For instance, if the zone contains water, there will be at least one 0x29 fragment that lists all "water" regions (technically there could be more than one but it would be totally unnecessary and I've never seen it). There could be a 0x29 list for all lava regions, or one for zone points, or teleport areas. There will be at least one for each type, so if a zone has both water and lava then there will be at least two 0x29 fragments -- one listing water regions and one listing lava regions.
Once you have all this loaded, there are some interesting things you can do:
Determine an accurate Z position
This involves walking the 0x21 BSP tree to quickly locate the 0x22 region in which a player or mob is. Once you have this, you can immediately get the appropriate 0x36 fragment (if there is one) and get the appropriate Z position. It's a tricky thing to do -- it means running through all the polygons and finding the nearest up-facing polygon that doesn't have the "non-solid" flag set, and then make sure that it's not too far above the player/mob position. There are other issues when dealing with falling from one region to another, but it's possible to come up with a list of all regions that intersect a particular Z position, then iterate through all polygons in all such regions to find the best Z position (the newest version of the Admin Tool does something like this, but it only looks for the highest Z position). I have to point out that this is an expensive calculation and is probably not practical for the server code -- unless someone can figure out an efficient way to carry it out. Such a way would probably involve pre-calculating as much as possible.
Determine the proximity to an "interesting" region
You can determine the proximity to a particular region or set of regions (like water). You might want to take a deep breath here, because unless I explain what BSP trees are and how they're defined in .WLD files, you'll never get it.
BSP stands for "binary space partition". Basically, what a BSP tree does is divide space into a tree using mathematical planes. For example, consider a volume of space with a bunch of stuff in it. Then take a plane of infinite size and put it into your space, where the plane chops everything it touches, such that everything on one side of the plane is in one region and everything on the other side is in the other region. You've now divided your one region (which contained everything) into two separate regions (*binary* space partition). Now do the same thing to each of the two regions, so that you end up with four regions (you don't have to divide them in the same way, either). Now do it again to each "leaf" node -- and again -- and again, until you're satisfied with the result (the final regions are small enough, or whatever criteria you choose). This is the idea behind a BSP tree -- you get a binary tree of distinct volumes that *don't* intersect. In practice, after this has been done all resulting nodes are then subdivided further, usually along special areas. Examples of these are water areas, lava areas, PvP areas, zoneline areas (zonelines are actually volumes), teleport areas, special ambient lighting areas, etc.
Now, recall that each division is performed by using a plane of infinite size. The standard way of doing this (and this is the case in .WLD files) is to define the planes in what's known as Hessian Normal Form. You can find a good mathematical definition of this at http://mathworld.wolfram.com/Plane.html. Hessian Normal Form can be defined very succintly:
The standard equation for an infinite plane is: ax + by + cz + d = 0. This is *not* in Hessian normal form. In Hessian normal form, a plane is defined as it's normal vector and its distance from the origin (0,0,0). It's important to point out that the normal vector is not only perpendicular to the plane; it also defines it's "inside" and "outside". The equations for these are:
nx = a / sqrt(a^2 + b^2 + c^2)
ny = b / sqrt(a^2 + b^2 + c^2)
nz = c / sqrt(a^2 + b^2 + c^2)
D = d / sqrt(a^2 + b^2 + c^2)
This is how these dividing planes are stored in the 0x21 BSP tree, in the order above (nx, ny, nz, and D). Each entry in the 0x21 tree contains a plane definition and three additional numbers. Two of the numbers are the indices of the regions on either side of the plane (or zero if there is no region), and the third number is the region index if the entry represents a "leaf" node (that is, a region that isn't divided anymore). To determine whether a particular x,y,z position is on the "inside" side of a dividing plane (and therefore is in the region it describes), all you need to do is get the dot product of the position vector and the plane's normal vector, and then add D:
distance = x * nx + y * ny + z * nz + D, where the object in question is at (x,y,z).
If the result is positive then (x,y,z) is inside the region. If it's negative then it's outside, and if it's zero then the position is exactly on the dividing plane.
In this way you could also find out how far a position is from a region in which you're interested. If the result is negative (and therefore the point is outside the region), then the negative of that value represents the distance from the region boundary. So, to determine whether a player is near a water region, you'd have to do the following:
1. Make a list of all water regions, using the 0x29 water list(s)
2. For each region listed, walk the tree to that region, keeping the minimum distance found at each node in the tree.
In practice doing #2 above isn't practical, but the solution is simple. When you initially load the 0x21 tree, make it doubly linked, so that every node knows its parent node. Then all you have to do is quickly iterate through the tree to find the leaf node that corresponds to the water region you're testing -- and walk the tree *upwards*, keeping the smallest distance found until you reach the tree root. In practice, you could build a list of 0x21 indices for each 0x22 region when loading the .WLD file so that finding the right leaf node doesn't take any time when it's needed.
Wind
First off, I'm assuming that anyone who reads this has first read the .WLD reference I put out and is familiar with the basic anatomy of .WLD files. Specifically, I'm assuming that you know what "fragments" are and that fragments are identified by a hexadecimal number.
To make use of the information in .WLD files, at the very least you'll have to do the following (this assumes you can already load .S3D files and extract the .WLD files and their fragments):
1. There will be only one 0x21 fragment, which is the BSP tree. It's basically an array of records. Load this into a structure where you can access all nodes.
2. Make an array that points to all 0x22 fragments.
3. Make an array that points to all 0x36 fragments. If your .WLD-loading code is similar to mine, then, for each 0x36 fragment, there will be a 0x22 fragment that points to it. This does *not* mean that every 0x22 fragment points to a 0x36 fragment, since there might not actually be any polygons in the volume that a particular 0x22 fragment represents. However, an "empty" 0x22 fragment *can* be tagged as a water area (e.g. it's far enough below the water surface and far enough above the ocean floor). It's important to understand the hierarchy:
0x21
|
+----> xxx 0x22's
|
+-----> no more than xxx 0x36's (one 0x22 per 0x36).
Each 0x22 region fragment represents a *volume* in space. Each 0x36 fragment contains all the polygons in a particular 0x22 region. The flag field in each 0x22 will tell you whether it has a 0x36 (or if your .WLD code is like mine then you only have to check to see if the appropriate fragment pointer is null or not).
4. Load any 0x29 region lists you're interested in. A 0x29 fragment lists all regions that have a particular attribute. For instance, if the zone contains water, there will be at least one 0x29 fragment that lists all "water" regions (technically there could be more than one but it would be totally unnecessary and I've never seen it). There could be a 0x29 list for all lava regions, or one for zone points, or teleport areas. There will be at least one for each type, so if a zone has both water and lava then there will be at least two 0x29 fragments -- one listing water regions and one listing lava regions.
Once you have all this loaded, there are some interesting things you can do:
Determine an accurate Z position
This involves walking the 0x21 BSP tree to quickly locate the 0x22 region in which a player or mob is. Once you have this, you can immediately get the appropriate 0x36 fragment (if there is one) and get the appropriate Z position. It's a tricky thing to do -- it means running through all the polygons and finding the nearest up-facing polygon that doesn't have the "non-solid" flag set, and then make sure that it's not too far above the player/mob position. There are other issues when dealing with falling from one region to another, but it's possible to come up with a list of all regions that intersect a particular Z position, then iterate through all polygons in all such regions to find the best Z position (the newest version of the Admin Tool does something like this, but it only looks for the highest Z position). I have to point out that this is an expensive calculation and is probably not practical for the server code -- unless someone can figure out an efficient way to carry it out. Such a way would probably involve pre-calculating as much as possible.
Determine the proximity to an "interesting" region
You can determine the proximity to a particular region or set of regions (like water). You might want to take a deep breath here, because unless I explain what BSP trees are and how they're defined in .WLD files, you'll never get it.
BSP stands for "binary space partition". Basically, what a BSP tree does is divide space into a tree using mathematical planes. For example, consider a volume of space with a bunch of stuff in it. Then take a plane of infinite size and put it into your space, where the plane chops everything it touches, such that everything on one side of the plane is in one region and everything on the other side is in the other region. You've now divided your one region (which contained everything) into two separate regions (*binary* space partition). Now do the same thing to each of the two regions, so that you end up with four regions (you don't have to divide them in the same way, either). Now do it again to each "leaf" node -- and again -- and again, until you're satisfied with the result (the final regions are small enough, or whatever criteria you choose). This is the idea behind a BSP tree -- you get a binary tree of distinct volumes that *don't* intersect. In practice, after this has been done all resulting nodes are then subdivided further, usually along special areas. Examples of these are water areas, lava areas, PvP areas, zoneline areas (zonelines are actually volumes), teleport areas, special ambient lighting areas, etc.
Now, recall that each division is performed by using a plane of infinite size. The standard way of doing this (and this is the case in .WLD files) is to define the planes in what's known as Hessian Normal Form. You can find a good mathematical definition of this at http://mathworld.wolfram.com/Plane.html. Hessian Normal Form can be defined very succintly:
The standard equation for an infinite plane is: ax + by + cz + d = 0. This is *not* in Hessian normal form. In Hessian normal form, a plane is defined as it's normal vector and its distance from the origin (0,0,0). It's important to point out that the normal vector is not only perpendicular to the plane; it also defines it's "inside" and "outside". The equations for these are:
nx = a / sqrt(a^2 + b^2 + c^2)
ny = b / sqrt(a^2 + b^2 + c^2)
nz = c / sqrt(a^2 + b^2 + c^2)
D = d / sqrt(a^2 + b^2 + c^2)
This is how these dividing planes are stored in the 0x21 BSP tree, in the order above (nx, ny, nz, and D). Each entry in the 0x21 tree contains a plane definition and three additional numbers. Two of the numbers are the indices of the regions on either side of the plane (or zero if there is no region), and the third number is the region index if the entry represents a "leaf" node (that is, a region that isn't divided anymore). To determine whether a particular x,y,z position is on the "inside" side of a dividing plane (and therefore is in the region it describes), all you need to do is get the dot product of the position vector and the plane's normal vector, and then add D:
distance = x * nx + y * ny + z * nz + D, where the object in question is at (x,y,z).
If the result is positive then (x,y,z) is inside the region. If it's negative then it's outside, and if it's zero then the position is exactly on the dividing plane.
In this way you could also find out how far a position is from a region in which you're interested. If the result is negative (and therefore the point is outside the region), then the negative of that value represents the distance from the region boundary. So, to determine whether a player is near a water region, you'd have to do the following:
1. Make a list of all water regions, using the 0x29 water list(s)
2. For each region listed, walk the tree to that region, keeping the minimum distance found at each node in the tree.
In practice doing #2 above isn't practical, but the solution is simple. When you initially load the 0x21 tree, make it doubly linked, so that every node knows its parent node. Then all you have to do is quickly iterate through the tree to find the leaf node that corresponds to the water region you're testing -- and walk the tree *upwards*, keeping the smallest distance found until you reach the tree root. In practice, you could build a list of 0x21 indices for each 0x22 region when loading the .WLD file so that finding the right leaf node doesn't take any time when it's needed.
Wind