[http://sourceforge.net/p/ufoai/bugs/2124 Item 2124] imported from sourceforge.net tracker on 2013-01-28 19:22:20

Guess I found a major bug.
On fighter_crash.map I can walk to the 2nd tile of my favourite stairway from the *side* of it. That's a stepup of 10 !

Some debugging revealed that in certain outdoor situations on maps with less than 8 levels, RT_CalcNewZ() is indexing in the void, returning a z of 7, causing crazy values like an opening of 206 and a bonus_size of -79 that will drive things nuts later on.

My first approach was forcing ufo2map to do RT_CheckCell() for the empty levels, but as they are not even written to the bsp file...no go.

My second thought was:
RT_CalcNewZ() tries to calculate the resulting 'az' from the found opening.
Hey, why do we do that deep down in the calltree ?
We start from comparing the floors and ceilings of two cells, so we should know at which z we will end up *if* we find an opening at a much higher level of the calltree.
But I didn't find a nice solution.

Unfortunately it's late here and I'll be rather busy for the weekend. Maybe you have a good idea ?

Imho this bug has the potential to be responsible for nearly half a dozen pathfinding bugs, thus prio 8.



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

====== aduke1 (2009-06-12 22:30:00) ======

Correction: the upper levels *are* written to the bsp. They just don't show up in the CSV files.
Maybe my first approach wasn't implemented correctly :(
I'll try again on monday.
====== tlh2000 (2009-06-20 15:00:08) ======

this is a little bit offtopic - but speaking of the bsp "levels". it would be nice if you could document this a little bit. there is currently nobody on the team who has written this code and you two are the only ones that are really into it.

e.g. documenting the pathfinding "nodes and leafs", the "levels" and so on. or maybe write a little document describing the ideas behind it. to get a global view on the things.
====== aduke1 (2009-06-22 21:51:37) ======

@tlh2000 :
A little early imho - atm I feel we have to rethink parts of the concepts...

@wilminator :
Using place_t, I was able to transport the info about the 'z' of the floor down to RT_TraceOnePassage() and the resulting values are reasonable now. (rev 24799)
But to my surprise, that did NOT solve the problem.

Here's what happens:
- we start on the 2nd part of the stairway, facing in dir=2 which is PY
- we find that there's NO chance for an opening at z=0 by comparing the floors and ceilings
- so we try to get to the adjacent cell at z=1 and find enough opening
- we calculate correct values...except for the fact that...
- invstepup will have a BIG_STEPDOWN, which is wrong. (Not a biggie, I'll correct that soon)
- later on FillPassageData() will set those values found to all cells involved in the opening, *starting at z=0*, which is terribly wrong for ax/ay.

Bidirectional tracing is attractive, but at the same time very complicated (maybe much more than we thought).

====== wilminator (2009-06-24 04:05:38) ======

@aduke1 :
Which map and where are you trying this?
====== aduke1 (2009-06-24 18:44:09) ======

On fighter_crash.map.

Data is
data at cursor XYZ(152, 127, 0) Floor(1) Ceiling(16)
connections ortho: (PX=0, NX=15, PY=15, NY=111))
connections diago: (PX_PY=0, NX_NY=0, NX_PY=0, PX_NY=0))
stepup ortho: (PX=32, NX=0, PY=0, NY=64))
debug_path
data at cursor XYZ(152, 126, 0) Floor(11) Ceiling(128)
connections ortho: (PX=117, NX=17, PY=111, NY=0))
connections diago: (PX_PY=111, NX_NY=14, NX_PY=15, PX_NY=0))
stepup ortho: (PX=0, NX=2, PY=32, NY=32))

====== aduke1 (2009-06-26 23:18:23) ======

@tlh2000 :
I changed my mind about docs. You said it *would be nice* to have some. Sorry, I have to disagree.
It's *absolutely neccessary* to have certain things documented because I feel that the code makes inconsistent use of those things.

@wilminator :
Imho a good thing to start with are the values that we expect in routing_t depending on the situation.
I'd suggest we document that right next to the declaration.
I volunteer to document your decisions.

Investigating the 'harvester ramp prob', I have just found out the hard way that ufo2map can generate a floor of 16 for a cell at z=0.
So my 1st question is:
Do the floors that *belong to a cell* range from 0-15 or 1-16 ?? I'd vote for 0-15, coz we can more easily determine the z-level by simply dividing mapunits by CELLHEIGHT plus it's more C-ish.

====== tlh2000 (2009-06-28 14:59:12) ======

@duke: 0-15 is not good - we have a lot of maps that start the second level from 17 and goes up to 32. reworking all of them is .... well - not really an option. it would be error prone and a hell of a lot of work.

if you want to start at 0 - we should (but only for the first level) use 0-16 - but this is imo not very nice. we should just fix it in our maps imo.
====== aduke1 (2009-06-28 20:39:08) ======

Martin,
don't worry. I'm not talking about re-aligning the maps to a new grid.

My point is that we need a *consistent* way to convert mapunits into QUANTs and QUANTs into (z-)levels and the whole way back. I have a bad feeling that this is currently handled inconsistently.

If we already have a set way to do it, fine. Then it should be a) documented and b) placed into inlines or macros.

btw meanwhile I saw that floor=16 and ceiling=0 is an initialization value for 'filled' cells.
====== wilminator (2009-06-30 04:59:51) ======

OK, here goes...
Currently, each z coordinate measures its floor's height and ceiling relative to the lowest point OF THAT CELL. So 16 QUANTS in z=1 is also 0 QUANTS z=2. There is no way around this no matter how we measure this; the cells touch, so they share a common measurement unit at the point they touch.
So back to the issue of calculating z values. As long as our measurement is not at the point where cells touch, the calculation works fine in all circumstances: z = floor(absolute measurement from map 0 / CELL_HEIGHT), or newz = floor(relative measurement / CELL_HEIGHT) + currentz. Any relative measurement of 0 works fine. But 16 is going to trip things up [I see here you're going].
The problem with a "consistent" formula to calculate the z value comes from how we need to interpret the 16 value. When tracing up, for ceilings, that 16 value needs to bring us back into the lower z value. Technically, though, when the floor has a 16 value, it is supposed to bump up to the cell above, it is supposed to point to the floor the actor would stand on in order to stand at the same (x, y) with no z less than the current z (opposite of when the current (x, y, z) is open).
So then, since the floor only goes to the top of the current cell anyway, and any cell with a ceiling of 0 can't be walked into, maybe we change the code to recognize a ceiling of 0 as filled and set the floor to 0 in those cells?

I think originally, I was using the 16 value as a flag in older code that the actor would have to step up to get to the next cell.
====== wilminator (2009-06-30 05:01:17) ======

This would also fix the cursor jumping up above the actor every time you mouse over filled terrain.
====== aduke1 (2009-07-10 22:19:08) ======

I just fixed the 'harvester ramp'-problem.
See http://ufoai.ninex.info/forum/index.php?topic=3778.15

The prob was that the topmost part of the ramp is 62 mapunits high and in RT_CheckCell() 'bottom' was rounded down to calc fz, but rounded up to set RT_FLOOR.

I really don't like the concept that a surface of 16 QUANTs should belong to *both* the z=0 cell and the z=1 cell, but I still can't think of an easy way out :(.

Meanwhile, please take a look at my fix (R25090). I' quite sure it's the way to go, but it also has the potential to break other things. Can you think of any ?

====== wilminator (2009-07-11 22:28:31) ======

aduke1:
Great catch with the rounding- I never saw that coming. A few things:
1. All of our routing is based on QUANT units. I think that we should adapt all our routing functions to work in QUANT units as soon as possible, as switching back and forth with model units will give us headaches.
2. Looking back on our earlier posts about cell boundaries, I have a very clear way to sum up where boundaries belong: with floors, QUANT units 0-15 belong to the cell, and with ceilings, QUANT units 1-16 belong to the cell. It is because our floor and ceiling values are transition points between solids and the void between. We (should) round these values toward each other when converting from model units; rounding away causes use to place actors *in* solids.. So we have an opening where the floor is 15 and the ceiling is 16, even if we can't use it. But if the floor is 16, it really belongs to the cell above, and with a ceiling of 0, it belongs to the cell below.
3. To help with this, I'm writing in ModelFloorToQuant and ModelCeilingToQuant macros. I'm also adding a QuantToModel macro and adapting all the code in routing.c to use these macros instead of using *QUANT or /QUANT in formulas, to remind us of why we are converting to QUANT units. I'm hoping to post these macro changes by tonight. Long term, I plan on converting any use of QUANT to use the macros, when reasonable.
As far as your changes breaking anything, ther code is more mathematically sound now. I think anything this change would break needs to be addressed in the map and not in code.

====== aduke1 (2009-07-12 18:18:36) ======

1. Agreed. 3 different units to express height is one too much ;)
2. Makes sense to me :)
3. Would you mind to use inline functions instead of macros ? No debugger I know can handle macros well...
====== wilminator (2009-07-13 03:10:24) ======

I committed the macros last night. They are in mathlib.h. You are welcome to convert them to inline functions if you would like. Considering that the release version should be optimized, I can't see a performance reason to not do it.
====== aduke1 (2009-07-22 22:01:15) ======

Uhmmm...is there a specific reason why you put those macros into mathlib ??
Well, YES, it's math, but as they are only used in conjunction with routing, they should reside in routing.h for the sake of *encapsulation* imho !?!
In other words: why expose the rest of the code to them ? It only gives us additional compile time :(

====== wilminator (2009-07-23 03:37:26) ======

Are you sure that we don't use any QUANT values outside of the routing? If so, then we can move them. Yes, I did put them into mathlib because they are conversion functions ;)
====== aduke1 (2009-07-23 22:47:57) ======

Quote "Are you sure that we don't use any QUANT values outside of the routing?"
Other way round. We should *make* sure that no other part of the code needs to deal with QUANTs.

Currently, outside routing, only GridMoveMark() knows a little bit about QUANTs. I plan to move those parts of GridMoveMark() into 'accessor functions' in routing.
That's what encapsulation is all about, isn't it ?
====== aduke1 (2009-08-02 21:53:38) ======

Wilminator,
I've been thinking about this issue (bidirectional tracing) for quite a while now, but whatever I do, there always remains a 'blind spot' or two when making conclusions from the trace results about what's 'on the other side'.

Because routing is still on the 'critical path' of the project and I have learned that CONNCHECK is by far not the most time-consuming part of a map-compile, I'd like to make a suggestion:
Let's give up on bidirectional tracing for now, go back to plain unidirectional tracing and see if we can get that to work again (at the expense of being slower) *sigh*.

We could either remove the code (and keep the rev # in mind) or surround it by some
if (bidirectional) {...}

What do you think ?
====== aduke1 (2009-08-03 11:45:24) ======

One additional thought:
I think it's better to use the 'if (bidirectional)' variant. This way we can easily switch between uni- and birectional mode, compare the resulting csv files and eventually get bididrectional tracing to work in the end :)
====== aduke1 (2009-08-03 22:23:50) ======

I went ahead and made bidirectional tracing optional. Committed as R25543 (with bidir still active).

Some testing already revealed bugs in the unidirectional stuff that were 'covered' by the bidir logic :-/

====== wilminator (2009-08-06 04:22:24) ======

@aduke1 :
Moving back to unidirectional tracing makes the most sense right now, so I don't oppose it.

I have been out of the code for too long now- my life has kept me busy, and the next four months look to be real bastards to me. I will try to help where possible, but at this point I can honestly say that you will be driving this part of the code from here. I will always be available to bounce ideas of of, and if you have questions about anything I have contributed, my door is always open. In fact, if you have anything that you specifically want me to look at, I'd be happy to.

I will be leaving on vacation for 10 days. When I get back I hope I can get back in more than I have, but I can't promise anything.

For tonight, I will look at the code and see if I can identify anything that sticks out to me.
====== wilminator (2009-08-06 04:45:48) ======

BWT- I'm going to work in unidirectional tracing for now. What was broke when you tried it?
====== aduke1 (2009-09-07 20:02:42) ======

Unidirectional tracing is active in current trunk (since R26009 IIRC). That fixes the original problem, the 'giant stepup'.
The problem is still there in bidirectional tracing, but work on that will be postponed until 2.3 is out.
Reducing prio to 4.

====== aduke1 (2011-11-25 22:00:51) ======

The priority was adjusted according to the "bug priority rules". See
http://ufoai.ninex.info/wiki/index.php/Bugs#Bug_Priorities
====== aduke1 (2012-09-21 20:53:53.606000) ======

- **status**: open --> unread


- **status**: unread --> open

====== aduke1 (2012-09-30 23:57:45.738000) ======

- **milestone**: 2.3 --> 2.3.x