[http://sourceforge.net/p/ufoai/patches/424 Item 424] imported from sourceforge.net tracker on 2013-01-28 20:39:33

I'm still not convinced about the code that resets the connection below the tracing level in case of a BIG_STEPDOWN.
So I created a visualization of the situations (see attached file). I can think of similar, but still different situations, but I'm not yet sure about their relevance.

It seems rather obvious to me that we should *not* reset the connection for S1 and we don't need to reset it for S2-S4 coz the z=0 pass would *not* have detected one.
Also, it's not clear to me how can distinguish between S3/S4 and S2 regarding the B0-values.

I hope the visualization will help us both to find the solution :)

===== Comments Ported from Sourceforge =====

====== aduke1 (2009-05-18 22:21:07) ======

various stepdown drawings
====== nobody (2009-05-19 06:21:29) ======

Here goes nothing- this is the stuff I keep running over in my head and on paper:
For S1, moving from A to B, we have a *falling* condition from z=1 to z=0. The difference between a falling condition and a BIG_STEPDOWN condition is that with BIG_STEPDOWN, we imply that the actor is walking and not falling, and thus should be able to walk back (stepup height and terrain permitting.) Technically, the falling condition exists when an actor drops more than MAX_STEPUP in a microstep. So S1 will not (or should not) have a BIG_STEPDOWN flag. The reverse trace works correctly for both. Even though B z=1 will connect back to a z=1, this is the correct connection for fliers, and a non-flying actor will never be able to get to B z=1 in a way that they can "walk" to A z=1. Unless we see the "I saw an alien" error.

For S2, there is an obstruction at z=0, so no loss. But at z=1, the same applies as above- a falling condition and not a BIG_STEPDOWN condition, because of the extreme drop. Since we detected an obstruction, the reverse trace works at z=0 because of the obstruction and at z=1 like shown above.

S3 becomes ugly quickly, and showcases the biggest limitation of our engine, imho. The cell floor at column B z=0 is the higher brush, and its ceiling is infinite. We can only use one brush in a given cell as a floor, and I decided to make it the highest floor that a crouching actor can fit into, in order to ensure "hollow" brushes could be used as stairs (like in both your example and the catwalk in the water of wilderness.map). I refer to this as the "one actor in a cell" effect. So A z=0 is open but not connected to B z=0, A z=1 is BIG_STEPDOWN into B z=0, and b z=1 is open. On initial reverse trace from A to B, z=0 will set an obstruction. But when z=1 is traced, the BIG_STEPDOWN condition causes the B z=0 value to be set to BIG_STEPUP into A z=1.

For my sanity, to mirror S3, the forward trace from B to A, the z=0 trace will cause a BIG_STEPUP into A z=1 and B z=1 will be open. For the reverse trace, there should be a BIG_STEPDOWN from A z=1 to B z=0 and an obstruction from A z=0 to B z=0.

S4 is S3 with no floor beneath or at least no floor at z=0.

I hope to clarify your concerns about the BIG_SETPUP/DOWN and the reverse trace; I am uploading an S5. It shows what I consider the hardest condition: potential "infinite" stairs. I had to design the whole STEPUP/DOWN concept around the fact that if an actor could move through an opening between steps that the actor could not step up or down from them, but must rather fall. In the case of a fall where the z coordinate does not change, it is still a fall if the actor cannot get back by walking to the originating cell, but does not manifest itself visually as a fall. What STEPUP/DOWN was designed to do was to either 1) tell the game that the actor was walking down and not falling down when z coordinates change, or 2) that the actor would rise a z level if moved in a given direction.

Now, if there is an opening that the actor can pass through, the actor will (should) not get a STEPUP when forward tracing or a STEPDOWN when reverse tracing. Even if the actor cannot use the opening (like in S3), MIN_OPENING is larger than MAX_STEPUP and the opening, even if unusable because there is no valid floor, will prevent microtracing from finding steps to elevate on.

If the opening is not big enough, then there is the possibility that whatever is obstructing the opening will act as a step. However, if a BIG_STEPUP/DOWN condition occurs, there *will* be an obstruction between the cells at the lowest z coordinate.

Last, there is one last limit because of the "one actor in a cell" effect. If there is an opening under a floor that an actor *should* be able to use that would cause him to fall, the move is disallowed. The actor must be able to occupy the cell at the same level in order to fall to the level below. However, since there is a floor in that cell at a higher level and the actor cannot STEPUP onto it, the move is disallowed. However, if the actor is normally able to STEPDOWN into the adjacent cell, then the move is allowed.

I know this is a long post, but it is a thorough brain dump for the design goals of STEPUP and STEPDOWN. I hope this helps, and also gives you a chance to validate my logic.
====== wilminator (2009-05-19 06:23:48) ======

S5 stepdown drawing
====== aduke1 (2009-05-20 22:11:49) ======

Your explanations can never be long enough for me ;)
Although I already knew some70-80% of the concept, it also contained the *one* important difference:
From looking at the code, I was under the impression that BIG_STEPDOWN is merely an indicator for a z-change because it seems to be *handled* that way. So I think I already saw the bug and just have to remember *where*.

We DO have situations where falling down one floor creates a BIG_STEPDOWN.
See attached files and this part of the log:

debug_path
data at cursor XYZ(146, 124, 0) Floor(1) Ceiling(16)
connections ortho: (PX=15, NX=13, PY=0, NY=14))
connections diago: (PX_PY=15, NX_NY=13, NX_PY=0, PX_NY=13))
stepup ortho: (PX=0, NX=0, PY=32, NY=1))
debug_path
data at cursor XYZ(146, 124, 1) Floor(1) Ceiling(16)
connections ortho: (PX=15, NX=15, PY=15, NY=15))
connections diago: (PX_PY=15, NX_NY=15, NX_PY=15, PX_NY=15))
stepup ortho: (PX=0, NX=0, PY=64, NY=0))

Note the PY-values.

As a first step I'll move the setting of BIG_* out of MicroTrace() into RT_TraceOnePassage().
====== aduke1 (2009-05-20 22:22:00) ======

Sorry atm I'm too stupid to upload screenshots with my brandnew Vista :(
The Upload func here simply doesn't offer the AppData folder where the screenies reside *grumbles*.
====== nobody (2009-05-21 06:27:35) ======

sidenote: on vista it should be c:\Benutzer\<user>\.ufoai resp. c:\Users\<user>\.ufoai, no?
====== aduke1 (2009-05-22 19:34:55) ======

groundfloor
====== aduke1 (2009-05-22 19:35:38) ======

1st floor
====== aduke1 (2009-05-22 19:43:04) ======

No, it&#039;s "C:\Users\<me>\AppData\Roaming\UFOAI\2.3-dev\base".
I moved the files to the root dir and it worked for now :/
====== aduke1 (2009-05-22 22:46:11) ======

The problem is that MicroTrace is focussed on stepping *up*. It has NO way to express that we are walking down (stepup is always >= 0). Maybe we should think about negative stepup values ?

The best way to distinguish between S1 and S3 I found was to check invstepup.
That seems to fix the zig-zag, so I committed it as rev24471.
====== wilminator (2009-05-25 05:05:49) ======

I seem to recall thinking something along those lines- needing to use the inverse stepup for something. That may be exactly it. I&#039;m looking into it further (slowly); my time is being taken up again.
====== aduke1 (2009-11-17 22:15:07) ======

This patch has made it into the trunk in some other way ;)