We've learned the basic concepts concerning the structure of map, so now we can begin to analyze specific phenomena, and the first one is pixelwalk. From practice we know that this technique is somewhat reminiscent of a slide performed at the junction of a regular brush and a brush entity (or at the junction of two brush entities). However, firstly not every such junction is suitable for pixelwalking and secondly you need to fall onto such a junction from a certain height. The easiest way to do this is to perform a doubleduck followed by duck from the same height as the desired joint. In this case, we will first be thrown 18 units up, and then the crouched player model will gradually descend 36 units down, exactly on the height of the joint. For the article, I created a map project hull_pixelcheck.jmf (archive with files can be downloaded here), from which I compiled the map hull_pixelwalk.bsp. It is a default room created by the J.A.C.K. map editor, where I placed two brushes, turning the top one into a func_wall. From the bottom brush you can do a doubleduck followed by duck on the joint on the left and “slide” with D held along the joint:


At the same time, the right joint between the brushes does not allow pixelwalking. Let's try to figure out why this happens.

As we saw earlier, every frame CS engine calculates the new position of the player and calls the function PM_PlayerTrace , which actually checks if the line connecting the old and new positions intersects any of the planes of the surrounding brushes. To do this, it needs to iterate through all the models on the map (in the code the models are designated as physents):


You can clearly see how the resulting trace changes its end point if it intersects a closer plane. The search for this point for a specific model occurs in a more sophisticated way, with a recursive pass through clip nodes. Let's look at this process step by step, looking inside PM_RecursiveHullCheck (code is cut down cause for simplicity we examine planes with normals directed along the basic axes):


The points p1 and p2 (the beginning and end of the trace) can lie either on the same side of the plane of the corresponding clipnode or on different ones. We find out this using the signs of t1 and t2, the modules of which are actually equal to the distance from p1 and p2 to the plane. If both points are in a half-space with a positive normal direction, then we take the left child clipnode and go to the next step of the loop. If both points lie on the other side of the plane, then take the right child clipnode for the next step. If the signs of t1 and t2 are different, then we need to find the coordinates of the point [/code]mid[/code] of intersection with the plane:


Note that this point does not lie on the plane itself. If p1 is spaced from the plane by more than DIST_EPSILON = 0.03125 (hereinafter, to be short, we will call this value eps), then the corresponding coordinate of the point mid is selected exactly at a distance eps from the plane. If p1 is closer, then the coordinate of p1 itself is selected as the mid coordinate:


Why do we need this eps indentation? The answer lies in the next step:


Let’s say the point p1 was in a half-space with a positive normal direction (side = 0), then PM_RecursiveHullCheck is called for the left child clipnode, and the trace goes from p1 to mid. In other words, we are trying to find an intersection point in this half-space that is closer to p1 by treating everything below the child clipnode as a separate subtree. If we didn’t find anything interesting in the left subtree, we move on to the right child clipnode. However, before going into the right subtree, we call the PM_HullPointContents function for the point mid, which goes through this subtree in order to find out whether the point mid lies outside of the model for any of its planes. This is where we need an indentation of eps, cause without it we simply would not have been able to figure this out. If the point mid for at least one plane of the right subtree lies outside the model, then we go to the next step of the cycle, selecting the right child clipnode and replacing p1 with mid (if there are no intersections with planes in the right subtree, then the point mid will not become the end point of the trace, that is, a collision with the model did not occur). If mid lies inside, then there is no sence in going into the right subtree, and we finally move on to filling out the information on the trace by storing there the last intersected plane and the point mid as the end point (preliminarily using PM_HullPointContents for the entire clip-tree as a safe check to see if the point mid lies inside the model).

At first glance, such a recursive pass through the clip tree gives quite correct results, but the indentation on eps hides several insidious peculiarities, one of which makes pixelwalk possible. Let's return to our map hull_pixelwalk.bsp and schematically depict a cross-sectional view of the func_wall and the lower brush along with its clipnodes for a sitting player (the planes of the clipnodes in the picture limit the orange area, and the eps-area is shown in pink):


When we stand on the bottom brush, thanks to PM_RecursiveHullCheck there is a non-zero gap of eps or less between the player model and the brush. By performing a doubleduck we fall down in duck to exactly the same height above the level of the top plane of the brush (and not exactly to the level of the junction of the brush and func_wall, as we thought at the beginning of this article). At the same time, by clinging to the side plane of func_wall during the fall, we also maintain a gap of eps or less between the player model and func_wall. When we pass the junction, our center will be at the intersection of the eps-areas, that is, in the red square:


Here we took point p1 exactly at a distance eps from both planes (this is the most common case), and point p2, where we want to be, lies lower and to the right on the other side of the planes, since we fall and at the same time hold down the D key. Based on the downloaded map data (see hull_pixelwalk.txt in the archive with the project files), we build a cliptree:


The trace from p1 to p2 intersects the planes of clipnodes #24 and #27, at that PM_RecursiveHullCheck when passing through the cliptree first encounter a clipnode #24, receive the point mid (it coincides with p1), and then reach the clipnode #27 (the point p1 will again be taken as mid). As a result, the horizontal plane of clipnode #27 will act as the collision plane only because it was encountered later when traversing the cliptree. The vertical velocity will be zeroed, and only the component along the X axis will remain (func_wall does not allow us to move along Y), so our movement will look like sliding along the joint. If we try to make a pixelwalk on the right side, then the trace there will affect clipnodes #27 and #29, and the function will get to #29 later, which means here the result of the trace is the vertical plane, hence we won’t be able to do any pixelwalk.

Another important condition for pixelwalk here was that the top brush was turned into a func_wall, not the bottom one. In PM_PlayerTrace, the first model in the cycle was the room itself along with the lower brush, and the total trace gave it a fraction equal to zero. The func_wall trace that followed it also gave zero fraction, but the resulting trace was not updated, and the collision plane remained horizontal. Thus, pixelwalk is only possible if the index of the lower model at the junction is less than that of the upper one. That is, there can be a regular brush below, and a brush entity on top, or both models can be brush entities, but the lower one should have a smaller index.

It would seem that the secret has been revealed, but that’s not all yet. Firstly the order of the corresponding clipnodes in the tree is not necessarily the same for standing and sitting player models, and secondly the order within each tree can change with each map compilation. For example, having compiled the same project hull_pixelcheck.jmf again, I got another map hull_nopixelwalk.bsp (see archive with files), where pixelwalk can be done neither on the right nor on the left sides.



Let's determine the fall heights suiting for a pixelwalk (we are also talking about a fall after a doubleduck or some specific bhop). We have already made a similar calculation of heights for JumpBug, but this time it should be taken into account that at the moment of the trace the speed has already decreased by 4 units/s in the function PM_AddCorrectGravity:


To get into the eps-area, you need to get the integer height h, and to do this it is enough to count the number of frames N multiple of 5. For example, after 30 frames we will go down by h = 36 units, which is exactly what we get after the doubleduck followed by duck we did on our test map.

Finally let's highlight one more important nuance. You may have noticed that on some maps pixelwalk is very unstable. The fact is that when calculating the end point of the trace, the PM_FlyMove function uses the [ifloat[/i] variable type, and its accuracy is approximately 7 significant digits. This means that if, for example, during the fall we wanted to drop to a height of 123.03125 units, then due to an float error we may end up at a height of 123.031265 units. It would seem like a small difference, but we no longer get into the eps-area, hence we can’t do a pixelwalk. And after a minute of attempts, the calculation may turn out to be correct, and pixelwalk will work. Here is another randomness in an already non-obvious technique.

We've figured out pixelwalk, but in the next article the eps indentation will continue to bring surprises.