More heightlevels disabled for 1.5

[frosch]

OpenTTD is approaching 1.5, and beta releases will start soon. So, it is time to look at the status of current trunk, the new features, and the bugs. While the current amount of bugs on Flyspray is at an all-time high, the individual bugs differ in quality.

Generally the number of reported bugs depends mostly on the number of players using a feature. Stable releases have factor 100 more players than betas, which have factor 100 more players than nightlies, ...
So, a bug, which was introduced 5 years ago and went through 5 stable release branches before being noticed, could be considered hardly important: Whether it is fixed or not is equally unlikely to be noticed. (Mind that this only applies for gameplay/usability issues. Security issues use a different scale )
A big share of bug reports are actually by new players, who use features in non-intended ways, which an experienced player would not do; just that OpenTTD is unable to tell the player what is wrong.

However, new features cannot be granted that kind of slack. A bug which is noticed within 10 days in a nightly, is noticed within 1 day in a beta, and is reported by 10 people within 3 days in a stable release (only some people check whether the bug is already reported).

More heightlevels is currently in such a state. FS#6156 ("Top of tall(?) buildings appear/disappear at random") first looked like it only needs fixing some inconsistencies in some constants (which were actually introduced by extra-zoom 2 years ago). But when I looked at it in more detail, the analysis of the code quickly derailed.
You can find a detailed analysis below, but the short story is: It likely cannot be fixed, unless it is rewritten. Unfortunately, the current code looks more like doing trial-and-error until it passes a few tests, rather than truly understanding what needs doing.

So, how to progress from here?
It does not seem likely that anyone is going to fix the current code before 1.5. The amount of work is just too big, especially with all the added work-arounds in the new code.
We also cannot release an OpenTTD version where buildings glitch all over the place, even in old maps.

The only available option is to pull the emergency brakes.
If there are no convincing ideas that the drawing is fixed before 1.5, more heightlevels will be disabled before beta 1.

• The setting will be restricted to the old value of maximum height 15.
• The viewport drawing implementation will be reverted.
• Other parts of more heightlevels remain in trunk, in particular savegames are not changed.

For a player this means:

• You can no longer create new games with more heightlevels (that is, the max height becomes 15 again).
• Savegames created with more heightlevels will load fine, but glitch all over the place to an extent that is no longer playable.
• If patch packs continue to provide the old implementation, the savegames will be compatible.
• If a new implementation reaches trunk, the savegames will work again (without glitches).

The basic idea of more heightlevels is not invalid, it's the rendering that is not working properly. The rendering code is reverted to the previous state of 15 height levels, since that worked correctly.
The internal game structures of 256 height levels will stay, it's just not usable above height level 15 because the render code does not understand how to draw those height levels without glitches.

For a coder this means:

• You can start from a simple drawing algorithm (the one that works for 15 levels from before MHL) to implement more heightlevels, instead of having to refactor a complex renderer that fails for every map.
• With implementing a new drawing algorithm you get the praises for making MHL return to main OpenTTD, instead of being an unnoticed bug fixer.

Final words:
Sorry for the mess. If you miss MHL, you can likely continue playing with it in a patch pack, resp. finish your current game without updating the nightly.
There is nothing bad in using a patch pack, the smaller and more experienced user-base enables them to provide more experimental features.
Stable OpenTTD cannot get away with that (sadly).
Just use the version you have fun with



Detailed analysis of the MHL drawing algorithm and the issues with it:
Basic idea:
[list]
[*] Drawing viewports in OpenTTD happens by drawing tiles and stuff on them.
[*] To do this, it is first determined which tiles have graphics that potentially reach into the viewport, and thus need to be considered for drawing.
[*] The old implementation before MHL just extended the drawing area by a fixed amount of pixels to account for tall buildings and bridges on tiles, which are below the viewport by themself.
[*] With more height levels this strategy becomes nonviable. Bridges can be way above the actual tile, so in the worst case you have to consider bridges on tiles 255 height levels below the viewport border.
[*] MHL solves this by scanning tiles below the viewport for bridges, and only consider these tiles for drawing if there actually is a bridge. Unlike the old algorithm which just always drew them.
[*] In the details you also have to account for the height of building sprites on tiles, and the height of bridge sprites above the actual bridge level.[/list]

The implementation:
When analysing the details of the code in order to fix FS#6156 I encountered this piece at the core of the algorithm.
[code]
/* Calculate, how many tiles below upper_tile, a worst case bridge intersecting upper_tile in
* terms of painting can be located. Lets inspect that formula in detail:
* ... - 5: The magic constant near the beginning of ViewportAddLandscape accounts for 5 harmless heightlevels a bridge can have. Thus subtract them.
* ... / 2: Four heightlevels account for one tile height. On the other hand, if landscape ascends from upper_tile southwards, this can account for
* as many additional heightlevels as we step southwards. In combination: A division by two gains the number of tiles to step southwards.
* ... + 1: Avoid rounding errors, and fall back to the safe side.
*/
int worst_case_steps_southwards = max(0, ((int)_settings_game.construction.max_bridge_height - 5) / 2 + 1);
[/code]Honestly, this is kind of jaw-dropping. For context, the first item refers to:
[code]
int viewport_bottom = _vd.dpi.top + _vd.dpi.height + 116;
[/code]The "-5" corresponds to the "116".

For the non-coders, what happens here is fixing by adding more duct-tape (add a "-5") rather than removing all duct-tape (remove the "+116" so you don't need to add the "-5") and handle the problem properly.
Adding a single number may not look very bad to you, but this is happening at a lot of places (at many places because elsewhere a constant was added too), and the new duct-tape is indistinguishable from the old duct-tape, and from the numbers that should really be used. It's like making a package, but it doesn't close correctly, so you start adding more and more rope until it seems to stay together. This is fun as a surprise gift to keep the receiver busy for a long time, but for code that needs to stay clean and maintainable, this is deadly as you cannot get in and understand the structure any more.

A second problem is that numbers themselves don't tell how they were derived. An example you may know is the "The hitchhikers guide to the galaxy" book, where they know the answer is 42, but they don't know the question that resulted in this answer.
The entire OpenTTD code is filled with numbers, but in the form of names like TILE_HEIGHT or TILE_PIXELS. This makes the code readable and understandable so you can change things and understand how that will affect the result. The drawing code of the MHL code does not do this, so to fix this code from its current state, a long journey is ahead. Note that in many cases, a number is not a single name, but the result of a calculation. For example, 56 could be 5 * TILE_HEIGHT + TILE_PIXELS / 2, but also many other expressions. Needless to say this makes deriving the formula from the number a lot harder.

To summarise the issues with this piece of code (which is just a representative example, there are many more):
[list]
[*] The "-5" should not be there is the first place. Instead the "116" should be removed. There is no point in reverting constants from other places, if there is nothing inbetween that relies on them.
[*] There are many magic numbers here. The code does not use symbolic constants like TILE_HEIGHT or TILE_PIXELS.
[*] The constants are not expressed as terms of symbolical values, instead the terms are evaluated and the result is inserted as plain new magic value.
[*] Height of buildings and height of bridge sprites above the actual bridge level are not handled by the current code.
[*] The rounding towards a specific direction at the end is to be expected. But there are about 5 other places above and below that code, which apply another level of rounding. Rounding is needed, but only once at the end. Not after every intermediate step.[/list]

Conclusion:
The basic idea of the MHL algorithm is correct. But the implementation of the drawing part suffers from bad practices which make it hard to maintain and impossible extend further with new features. Some issues are not addressed at all.

This slipped the attention of all of us and it likely will need some time to figure out a right way. This means we need to pull the emergency brake now, so that the 'stable branch' keeps to deserve its name.

Reverting back to 15 height levels is not nice, but by doing it before the 1.5 release means that only users of the nightlies are affected, which is better than all OpenTTD users (most users only play stable releases).
Secondly, reverting the drawing code gives a stable and working starting point for fixing, which is better than starting from mostly but not quite fully working code, where nobody knows what part is good and what part is not.

[ic111]

Ok, some things to mention:

First of all, two months ago, I had a very detailed look on the code where the 116 exists. My results can be found here:

http://www.tt-forums.net/viewtopic.php? ... 0#p1135613

The result of my reasoning was, that 128 corresponds to a tile height of one; I did the analysis on the basis of the constants being around in code. My picture of the whole thing was, that one needs to

(1) define a maximum allowed building height in terms of number of tiles (in vertical direction) that may be shadowed by a building
(2) replace that 116 by x * 128 [128 expressed in terms of the mentioned constants], where x is the number of tiles that may be shadowed in vertical direction.

How I came to 128, I described in the post linked above in detail.

The last post in the mhl thread is from November 5th, by me. At that point in time I thought that the solution to this issue would be straightforward, and as no one really objected against my reasoning to introduce a max building height, I thought you would discuss this internally and eventually fix it

Regarding the "-5", at the time I wrote that code I admit I had a misconception about the scaling at that point of code, and I also admit that when I wrote the post linked above, I seem to have forgotten about that issue being relevant for that point of code.

On the other hand, the basic idea at that point of code is rather simple: We extend the to-be-painted area in order to be able to cope with a certain building height, thus a bridge whose height is within that height boundary is harmless.

Why didn´t I fix it myself? Well, I am no dev, and as I didn´t receive clear feedback on the intended solution but at the same time thought the solution described above would be rather small in terms of code, I thought you would implement it after that discussion without further patch from outside necessary. After all, your posts read like you having a quite concrete picture of the situation either.

That seems to have been a misconception.

That leads me to my next point: Is this your approach of communicating in such a project? If you feel that you have some severe problem, and someone (me?) doesn´t deliver what you want / need, then please tell the outside world.

I did a quite detailed analysis before November 5th, and after there was silence with me being the last poster, I simple didn´t know that you came to the conclusion that you have a severe problem. Now, we don´t have November 5th, but December 14th, and honestly, now I actually am in the situation that I don´t have much time for such issues in the next four, maybe more, weeks.

Such a post from your side 4 weeks ago, and maybe now there wouldn´t be a rivers patch, but I am quite sure that we would have a solution to this by now.

I even wrote a PM in the quite early stages of the rivers patch, informing that I have another project, and if my help is needed for mhl then devs should ask.

Last, to your concrete points:

(which is just a representative example, there are many more):

You could have asked earlier about them. All that code went through a review of Rubidium, thus my expectation was that things not being marked, but committed to trunk by him are ok, both in terms of coding style and understandability. This especially applies to the constants.

The "-5" should not be there is the first place. Instead the "116" should be removed. There is no point in reverting constants from other places, if there is nothing inbetween that relies on them.

As I have said, I thought I ruled out what the reasoning behind that numbers is.

Height of buildings and height of bridge sprites above the actual bridge level are not handled by the current code.

For the bridges, there is a new max bridge height setting. The comment you quoted above is part of the description of the reasoning behind it.

The rounding towards a specific direction at the end is to be expected. But there are about 5 other places above and below that code, which apply another level of rounding. Rounding is needed, but only once at the end. Not after every intermediate step.

One would have to have a look on this in detail, but my approach here always was rounding to the safe side, I think I described that in source code comments also. Also, it unfortunately is an issue with integer arithmetics that you quite often have to think about rounding things.


My conclusion:
If you feel the need to revert this, do it.

But please do me a favour and provide a patch of reverting the whole thing (i.e. a patch file that can be used to re-apply the changes you reverted in an easy manner). Now, at least we don´t have an issue with savegame compatibility any longer, and the changes should be rather local ones (i.e. mostly in viewport.cpp), so managing that patch should be much easier than it was before.

[planetmaker]

Of course you feel bad. So do we. It's a dis-satisfying situation for everyone involved, and there is no-one in particular to take more blame than anyone else. We will have to face the s*** to come. And sadly seem to a have angered a decent contributor.

The main point is: this is the wake-up call, the communication you basically ask where it has been. https://bugs.openttd.org/task/6156 is the show stopper; and it's been around for about 6 weeks now - unresolved. There's the other thread you linked which discussed some of it - but no follow-up patch was presented either. What obviously happened: The hope that someone else will do the work everyone could do, resulted in noone doing which anyone could have done - and that includes you.

Thus there has been no satisfying solution by anyone since that issue was brought up. The issue 6156 manifests itself in the code relating to the determination of the drawing rectangle with the issues as lined-out by frosch above. The current analysis and state of the problem is now summarized exactly here - and to draw back the attention to this pressing issue.

Re communication: We all work on a free-to-do-what-we-like basis as do you - we have no policy to assign a bug to someone. Bug can only be actively claimed by oneself. So how can we tell you to do XX or YY? And a possible way to go and improve on the situation was exactly, and in detail, discussed in the thread you linked yourself. How better can it be except writing the patches oneselves? Also, frequently informal communication happens on IRC. You chose not to be around or available.

However: No code changes have been done yet, no revert has been committed - yet. And there is still some time.

[ic111]

The main point is: this is the wake-up call, the communication you basically ask where it has been. https://bugs.openttd.org/task/6156 is the show stopper; and it's been around for about 6 weeks now - unresolved. There's the other thread you linked which discussed some of it - but no follow-up patch was presented either.

Yes, maybe I should have presented one. However, I´m not the one who can decide on an issue like introducing a maximum possible building height. I´m lacking detailed knowledge of the whole NewGrf system, nor am I a dev.

In the end, my impression then was that we talk about correcting a single numeric constant, that you have the impression that there is quite a bit more to do is the new thing for me.

Re communication: We all work on a free-to-do-what-we-like basis as do you - we have no policy to assign a bug to someone. Bug can only be actively claimed by oneself.

Yes, I know. And my real-world-situation in the next weeks will indeed be one with not-too-much time.

My point is a bit different: The devs are the one with the commit access, who can actually fix a bug; they make decisions like introducing something like a max building height or not. Thus, I actually see them in the role of at least keeping a look on such issues, in terms of "who does it", and also in terms of "how is it solved".

If I invested that much time into a patch, then you of course may ask me in a direct way wether I intend to fix some issue.

The nature of such a project is that people only communicate over the net, thus maybe a bit more such communication is needed than in other projects before everyone is clear about what other people expect and what one should do oneself.

And a possible way to go and improve on the situation was exactly, and in detail, discussed in the thread you linked yourself. How better can it be except writing the patches oneselves?

You are right, would have been better.

But, I read sentences like

To summarise the issues with this piece of code (which is just a representative example, there are many more):

"Many more" is a rather fundamental critics, that goes beyond one particular problem. This was the main reason for me to react in the way I did.

And regarding things like constants being explicitely written: They have been there since the beginning, and are an obvious thing one sees the first time one looks into the code. Being notified that something like this is seen as a severe problem that late is not that fortunate.

However: No code changes have been done yet, no revert has been committed - yet. And there is still some time.

I´ll see what I can do. But please, detail the "many more" down to concrete issues.

[HackaLittleBit]

Quick and really dirty

patch "trunkincheight_21915.patch"
revert viewport.cpp to version 26482

patch "trunkincheight_21916.patch"
Add two procs to stop complaining.

patch "trunkincheight_21917.patch"
Fix glitches

Last patch is to show where problem is.
Now you can play 64 height levels

To test:
Use this heightmap in scenario editor.
You will see that you don't have glitches till level 66

If you take out patch 21917 you get glitches from about level 26.

Hope this helps.(No more black tiles etc.)
In my opinion 64 height levels is enough. 2 x dword == 64.

I have no time now. Only from this weekend on.
Regards HackalittleBit

[ic111]

Ok, after some debugging I hope I have found the remaining problems. Patches:

010_ExpandDirtyRegionToSouth: This one replaces the "116" constant by the result of the result of the calculation as discussed, in terms of the constants being around (as far as available). This should fix the high building issue. Also, it adds an extensive comment, which hopefully makes clear what we do in that line.

020_CorrectBridgeHeightTreatment: Corrects the bridge height treatment (where the "-5" was located), and also improves comments at that point. Should fix higher bridges; my test case was max bridge height 30, and a bridge of that height, in scenario editor between two high mountains.

030_FixIntegerOverflow: This is probably the most important patch in the patch queue: In one of the last optimizations I introduced as a result of feedback before going to trunk, I introduced an integer overflow (by passing an uint that could be UINT32_MAX by design, and comparing using min). This had various bad effects:
(1) Bad performance - this basically broke the binary search for the tile at hand
(2) The bridge height treatment code wasn´t entered at all.
(3) Maybe more.

The fix is simple: Simply make the argument an int instead of an uint.

040_RemoveUnnecessaryOffset: Removes the "-16" offset that was present above the "+116" offset. I have not seen any bad effects in my test cases, so I doubt that it had any relevance any longer. According to the discussion referenced, it was equivalent to 1/8 painted height of a tile, i.e. not that much.

I introduced some new constants.

The only thing I did not do out of the post of Frosch is touching the rounding. My policy is and was always rounding to the safe side, and if I round twice to the same, safe, side, then I maybe paint a bit more than necessary, but can be sure that I paint enough.

In contrast, if I try to round only at one, final, place, then I also have to take care about things like that rounding errors might be multiplied while being propagated through the calculation; in the end I don´t see that this can make code actually better.

In case there are issues left: I have some, limited, time until December 26th, and then hardly any time until about January 10th.

Decision needed I set the max building height constant to 5 tiles that may be shadowed. I leave it up to anyone familiar with the NewGrf world to decide upon the actually required value.

[Digitalfox]

I have to say ic111, no one can point the finger to you for the lack of trying to fix the problem!

[frosch]

(I started writing this before your last post, and I am not going to look at it today.)

First of all, two months ago, I had a very detailed look on the code where the 116 exists. My results can be found here:

Yes, I read that, and I replied to it by explaining MarkTileDirtyByTile vs. ViewportAddLandscape, because that apparently escaped.

How I came to 128, I described in the post linked above in detail.

Fine, but why are there so many more places where the area is extended again?
1355: The "- 5" reverting the viewport extension for bridges.
1472: "top_row[x - left_column] -= 3;" Another 3 tiles to the top.
1474: "bottom_row[x - left_column]++;" Another 1 tile to the bottom.

... November 5th ... now I actually am in the situation that I don´t have much time for such issues in the next four weeks ...

Yes, sorry, things can take long here, I do not work 40 hours per week on OTTD, nor does anyone else. Compared to work time scale: 4 weeks here are hardly a few days at work scale, and I doubt you get responses within days at work either.
Anyway, that's the whole point of the "disable for beta". We don't want a quick solution. We want a correct solution.

HackaLittleBit: This is also a response to you: It does not need a quick solution. Disabling it in beta gives us lots of time.

For the bridges, there is a new max bridge height setting.

The bridge height setting controls the height between the tile and the floor of the bridge.
But a bridge does not stop at the floor. Like a house it extends upwards, that's why the "-5" is wrong.

... but my approach here always was rounding to the safe side, ...

And exactly that's what I consider bad about the current solution. It does so much rounding, that it does not show the actual bugs.
What does a building of height 5 matter, if the rounding already involves 3 tiles? It conceals bugs, instead of pressing them.
FS#6156 is not the only issue here. I am of the opinion that the whole thing needs to be rewritten, instead of shifting even more rounding and numbers around.
This implies that I do not expect you to do it; it would be silly to request a rewrite from the same guy (unless I request myself to rewrite something), it needs an independent vision on the problem. (actually it puts the pressure on me, to rewrite it myself)
The solution should be aware of when to add what constants, and it should also consider the reverse viewport area extension in MarkTileDirtyByTile resp. bridge construction and destruction.

Is this your approach of communicating in such a project?

Yes, I am all for open and honest discussion. I do not conceal my opinions on code, and I do not make things sound nicer than they are.
I appreciate feedback, especially if I am wrong, because I can only learn by my mistakes. If noone finds an issue in my patches, it is kind of disappointing, and sometimes I even distrust the reviewers, if they do not find something ...

Anyway, this is the development forum, not twitter, it targets programmers and people who play with nightlies (which are in particulary adressed by the first post).
Code is discussed on IRC (with public logs), or here. There is no point in E-Mail or PM discussions about code, if you expected that, noone can read them.
Private discussions are only required for moderation and administration issues.

And to reply to your post on the other forum: Almost all OTTD developers are also professional programmers. Though honestly that does not mean anything.
Software developers are rare, if you can get hold of one, hire him. So, there is essentially no lower limit to the skill of a professional programmer.
I work with about 100 software developers (not counting the managers) of different age, origin/language and educational background. I have no particulary good impression of the average level.

At work decisions are also made entirely different. You write yourself, that you have to solve a big task in a very short time, and that you have to do temporary hot fixes, just to keep things going. Exactly that is, what professional programming is about.

OpenTTD does not try to solve issues as fast as possible, and such that it works just as long as the warranty lasts. I consider OpenTTD development as counter-balance to programming at work (and there is at least one another dev, who also kind of does that).
At work you delay quality in favour of getting things done till the deadline. Here we delay getting things done in favour of making them correct. We have a time-deadline for releases (otherwise they would never happen), but not about what they contain.
Applying the work-metrics to OpenTTD almost offends me.

[ic111]

(I started writing this before your last post, and I am not going to look at it today.)

Just a short answers to some points that still remain valid.

How I came to 128, I described in the post linked above in detail.

Fine, but why are there so many more places where the area is extended again?
1472: "top_row[x - left_column] -= 3;" Another 3 tiles to the top.
1474: "bottom_row[x - left_column]++;" Another 1 tile to the bottom.

Ok, here you have found a point that I did not inspect yesterday evening. My guess is that here, we talk about the mapping between rectangular viewport and isometric landscape (the viewport <--> tile mappings select one point inside a tile, but the tile has some extent).

... November 5th ... now I actually am in the situation that I don´t have much time for such issues in the next four weeks ...

Yes, sorry, things can take long here, I do not work 40 hours per week on OTTD, nor does anyone else.

I know that. My point was rather, four weeks silence, and then such a long post (it must have costed you hours to write it) instead of writing a concise list of remaining technical problems, together maybe with the question, are we able to fix them by <date by your choice>, or we have to revert the thing.

But, anyway, I don´t think we need to blame each other on this topic...

For the bridges, there is a new max bridge height setting.

The bridge height setting controls the height between the tile and the floor of the bridge.
But a bridge does not stop at the floor. Like a house it extends upwards, that's why the "-5" is wrong.

IMHO, the setting is:
- I have the bottom viewport_y
- I add some offset to the south for buildings => bottom_viewport_y + offset
- At the former "-5" (replaced in my patches), I decide on the range I have to inspect additional to bottom_viewport_y + offset, i.e. [bottom_viewport_y + offset ... bottom_viewport_y + offset + bridge_offset]

But the range [bottom_viewport_y .... bottom_viewport_y + offset] already is outside map. Thus, the additional range to be inspected shrinks accordingly - this was the "-5".

... but my approach here always was rounding to the safe side, ...

And exactly that's what I consider bad about the current solution. It does so much rounding, that it does not show the actual bugs.
What does a building of height 5 matter, if the rounding already involves 3 tiles? It conceals bugs, instead of pressing them.

If you mean the "-=3" above, I don´t consider this rounding, this IMHO is just applying an offset. The question is, wether there is a valid background for that offset.

With rounding, I mean "division by two", conceptionally I might end up 1.5, thus I take 2 instead of 1 to be safe to have a big enough value.

FS#6156 is not the only issue here. I am of the opinion that the whole thing needs to be rewritten, instead of shifting even more rounding and numbers around.
This implies that I do not expect you to do it; it would be silly to request a rewrite from the same guy (unless I request myself to rewrite something), it needs an independent vision on the problem. (actually it puts the pressure on me, to rewrite it myself)

You are free to do it...

(if you do it, maybe in the end we even have two implementations one can benchmark-compare)

Anyway, this is the development forum, not twitter, it targets programmers and people who play with nightlies (which are in particulary adressed by the first post).
Code is discussed on IRC (with public logs), or here. There is no point in E-Mail or PM discussions about code, if you expected that, noone can read them.

No, I didn´t expect that.

At work decisions are also made entirely different. You write yourself, that you have to solve a big task in a very short time, and that you have to do temporary hot fixes, just to keep things going.

No, I did not write that.

I do not provide temporary hot fixes.

I just have to face the situation that I have to move a complex project to a new technical base within some time range, and one of the problems that makes the time range quite short is that we want do things the right way this time.

[ic111]

The result of some fact-finding mission in the mhl code. See the attached pdf, I created a small figure to explain easier.

Where I did not yet succeed with finding a detailed explanation is for the lines

Code: Select all

/* Correction to avoid glitches when approaching the left edge of the map. */
left_column--;
(...)
right_column++;

... and ...

Code: Select all

top_row[x - left_column] -= 3;
(...)
bottom_row[x - left_column]++;

For all of them, I can say that one actually gets glitches when removing them.

Regarding the latter, I suspect that the motivation for increasing the bottom_row by one is that the lower end of a row of tiles behaves like a saw blade.
In terms of the pdf: I suspect that the problem is that if you end up in A, you miss some tiles in the row of C that intersect the row of A.
Regarding the -= 3 I have some (far away) reminiscence, that it might be related to the tile images actually be somewhat bigger than the tile you see (do they extend to the north by some amount beyond what you see?).

But both might be wrong.

At least one correction step (the one in the pdf) should be explained by that.

[ic111]

Just a short notice on a bit further inspecting / thinking about those added / subtracted offsets:

- I think that always taking the upper tile at the end of the binary search caused a need to expand the region
===> Taking the lower tile in case I search the lower bound of a region avoids this.

- I suspect the transition between binary search and stepping tile-by-tile further outwards as a cause of needing to expand the region.
===> Probably, I can switch to using binary search with an expanded region, as I know how the tiles outside map descend anyway (i.e. I can derive an upper bound how far away from map the last invisible (imaginary) tile with height > 0 is located)

Both are not triggered by actually visible glitches / bugs in my last released version, they are just potential ways to improve the code.

[ic111]

The previous insights into the algorithm, transformed into patches.

Patches 010 to 040: Exactly the same patches as in the previous release, see there.
Those patches are as far as I know sufficient for getting rid of the glitches.

Patch 050: As explained choose the lower tile when using GetRowAtTile for finding out the lower end of a region.
Patch 060: Improve the binary search in GetRowAtTile, in order to get rid of the stepping one-by-one outside map.
Patch 070: Now, we can get rid of that asymmetric -= 3 for expanding the region to the north.
Patch 080: Improved comment describing the tile_coord.y-- / tile_coord.y++ I explained in the pdf.

Now, beyond the offset change explained in patch 080, I expand the repaint region by one row/column into each direction, i.e. things are symmetric now with respect to that.

To everyone interested: I think, this should now be a state worth testing, wether I am right with my expectation that all glitches (beside maybe those resulting from a too small MAX_BUILDING_HEIGHT) are fixed.

[ic111]

After another bugfixing session, I now got completely rid of the offsets mentioned above I didn´t understand myself.

Changes:
Patch 020: Of course, Frosch was right with the height a bridge consumes above its base level, I missed the point when I answered that post

New:
Patch 070: When calculating the middle tile in the binary search, I trapped into the problem of integer division with negative numbers: -1 / 2 = 0 = 1 / 2. This is corrected.

Patch 080: Basically the same problem, this time in GetTileCoordFromScreenCoord.

Patch 085: I have to use TileHeightOutsideMap instead of GetTileMaxZOutsideMap in GetViewportY, as I need the height of the northern corner.

Patch 090: Finally removes the unnecessary offsets for expanding the region.

(not in the queue: Patch 110 with some DEBUG statements that are only active on 64x64 maps (to avoid DEBUG logs from the start game) that can be useful to find out what the algorithm paints why in which order).

While Frosch was right with the diagnosis that there are bugs around, all problems were detail problems somewhere inside the algorithm, such as off-by-one because of the integer division issue mentioned above. I did not need to change anything about the basic idea of the algorithm.

I think that I now addressed all issues that were around. Please test, and report if you find anything that does not look like it shoulds. If I don´t receive any further bug reports, there will be no further release from me, simply because I have no open issues left to the best of my knowledge.

[ic111]

Ok, I found a bug myself:

If you scroll outside the map by more than <maximum heightlevel> tiles, then you will get glitches.

I think I know how to fix it, and the fix will even make the GetRowAtTile algorithm simpler (I just realize, that in fact, I don´t need to do anything but binary search anyway).

Patch will follow during the weekend.

[ic111]

Changes this time:

- Patch 060: Improved binary search such that it is also always used when being outside the map. This fixes the glitches far outside map I reported above.
- Patch 030: Removed, since the function doesn´t exist any longer thanks to the new changes to patch 060
- Patch 010: Made that long term "viewport y per tile" a #define in viewport_type, as it contained only constants anyway

Additionally, there is a new patch 105: The smallmap scrolled to the wrong location when the user clicked a high mountain in the smallmap. This is fixed in this patch. Needs the #define introduced in patch 010.

Again, no further patch unless there are bugreports.

[adf88]

Patch 080: Improved comment describing the tile_coord.y-- / tile_coord.y++ I explained in the pdf.

Even perfectly commented this is still hack-ish and unclear. The base concept is simply wrong.

You want to find the leftmost tile column visible in a given viewport. OK. But you are doing this by roundabout means. You are firstly converting screen coordinates to a tile, secondly you convert the tile to tile column. This middle step (the tile) is unnecessary.

As you described, a given screen point may be located at left or at right side of the tile. When you are converting a screen point to a tile, this information is lost (was is the left or the right side?). Then, to compensate this loss of information, you are adding an arbitrary offset (tile_coord.y--).

Screen coordinates should be converted directly into row/column coordinates. It can be realized by introducing a diagonal tile coordinate system - set of functions allowing to convert coordinates between tile row/column system and other systems (tile x/y, screen x/y). This is something that you implemented but only partially and and you hid this inside internal viewport.cpp functions. It would be better if the concept of row/column coordinates would be complete and generic. A line of code may tell more then thousand words so I will give an example:

Code: Select all

/* Convert X/Y tile coordinates into vertical tile coordinate. */
int XYToVert(int x, int y)
{
	return y + x;
}

/* Convert X/Y tile coordinates into horizontal tile coordinate. */
int XYToHorz(int x, int y)
{
	return y - x;
}

/* Convert vertical/horizontal tile coordinates into X tile coordinate. */
int VertHorzToX(int vert, int horz)
{
	return (vert - horz) >> 1;
}

/* Convert vertical/horizontal tile coordinates into Y tile coordinate. */
int VertHorzToY(int vert, int horz)
{
	return (vert + horz) >> 1;
}

/* Convert vertical/horizontal tile coordinates into screen coordinates. */
Point RemapVHCoords(int vert, int horz, int z)
{
	Point pt;
	pt.x = horz * 2 * ZOOM_LVL_BASE;
	pt.y = (vert - z) * ZOOM_LVL_BASE;
	return pt;
}

/* Convert screen coordinates into vertical/horizontal tile coordinates. */
void InverseRemapVHCoords(int x, int y, int *vert, int *horz, bool round_up = false)
{
	if (round_up) --x, --y;
	*vert = pt.y >> (ZOOM_LVL_SHIFT + 1);
	*horz = pt.x >> ZOOM_LVL_SHIFT;
	if (round_up) ++*vert, ++*horz;
}

etc.

With this approach, calculating column boundaries in ViewportAddLandscape is trivial:

Code: Select all

int vert, horz;

InverseRemapVHCoords(_vd.dpi.left, _vd.dpi.top, &vert, &horz, false);
int left_column = FloorDiv(horz, TILE_SIZE);
int top_row_ignoring_height = FloorDiv(vert, TILE_SIZE);

InverseRemapVHCoords(_vd.dpi.right, _vd.dpi.bottom, &vert, &horz, true);
int right_column = CeilDiv(horz, TILE_SIZE);
int bottom_row_ignoring_height = CeilDiv(vert, TILE_SIZE);

The concept of diagonal tile coordinates can clarify the code in other places too:
- diagonal tile iterators
- DiagonalTileArea.Contains
- SetSelectionTilesDirty (marking diagonal tile area as dirty)

[ic111]

Patch 080: Improved comment describing the tile_coord.y-- / tile_coord.y++ I explained in the pdf.

Even perfectly commented this is still hack-ish and unclear. The base concept is simply wrong.

You want to find the leftmost tile column visible in a given viewport. OK. But you are doing this by roundabout means. You are firstly converting screen coordinates to a tile, secondly you convert the tile to tile column. This middle step (the tile) is unnecessary.

As you described, a given screen point may be located at left or at right side of the tile. When you are converting a screen point to a tile, this information is lost (was is the left or the right side?). Then, to compensate this loss of information, you are adding an arbitrary offset (tile_coord.y--).

While you are right that one can think the way you do, and maybe ends up with clearer code than I do: No, those offsets are not arbitrary. The tile coordinate system of OpenTTD has some very basic properties, and the property that tiles are north, northwest, ..., northeast of each other, arranged along vertical lines is certainly one of them.

And I am certain, that within those properties you could prove that those two offsets do the right thing, simply because by decrementing y, I decrement both column and row by one, and given the way tiles are arranged, this is enough.

Screen coordinates should be converted directly into row/column coordinates. It can be realized by introducing a diagonal tile coordinate system - set of functions allowing to convert coordinates between tile row/column system and other systems (tile x/y, screen x/y). This is something that you implemented but only partially and and you hid this inside internal viewport.cpp functions. It would be better if the concept of row/column coordinates would be complete and generic. A line of code may tell more then thousand words so I will give an example:

Christmas is ahead. For some of us, this is probably a time where they have relatively much time, for me it is a time where I have much less time than during the last week. Since Monday, I spent about 10 hours for taking that algorithm where it is now.

What does this mean?

At this point, I can just say: You are perfectly free to take that patch, modify it along the draft you gave above, test it, and release it as an improved version. I personally, will not be able to do such a basic refactoring for at least several weeks, and after this time has gone, we will be too late for the time constraints of OpenTTD releases anyway. [ and the first months of 2015 will be quite busy for me anyway ].

If you cannot do that either, it is up to the devs to decide wether the state we have now is enough. I personally can just say, if this would be rejected because of a single offset where you can easily draw a draft on a sheet of paper, that the result is correct, then I would regard this as quite strange (and not quite encouraging either).

Sorry that I have to answer this way, but as Frosch said, we all don´t work 40 hours per week for that project, and at some time there is a point reached where I have to say, my tests and thoughts about this indicate that it works now, we don´t discuss wether the algorithm produces a incorrect result any longer, if you find a bug that is fixable with small codechanges within the current concept I will do my very best to fix it, but for such a big codechange I simply don´t have enough time.

[frosch]

Since I had already spent so much thought on the topic, I eventually wrote a replacement algorithm. I did not try fixing the algorithm, but rewrote it from scratch, since I came to the conclusion that the problem should be solveable with way less code.

While doing so I encountered some unrelated issues with the smallmap and zoom levels and generally stuff about transformations between screen-, world-, and tile coordinates; so the attached queue also deals with some other issues.

I am gone for a week, so I leave the queue here for public review. Don't hold back with criticism
The splitting of the patches can likely be improved, and I have some profiling tasks left, but the general algorithm should be reviewable.

10:
* Pixel dimensions passed for marking viewports dirty were not always scaled by the zoom level, in one case otoh even twice.
* Rounding wrt. zoom-out levels is now done in a single place in MarkViewportDirty instead by the callers.
* MarkTileDirtyByTile now operates based on the tile's north corner with some fancy MAX_EXTENT constants, instead of some imaginary corner (XY of north corner, but Z of tile) with plain integer offsets.

20:
* Construction/destruction/changes of/to bridges now mark the viewports dirty, which contain the pillars and top of the bridge, not only those viewports which contain the base tiles under the bridge.

30:
This just deletes a bunch of code which is reimplemented in the later patches. The result of this diff does actually not compile.
The later patches are easier readable this way, however.

40:
Use TranslateXYToTileCoord to translate from screen to tile coordinates, instead of reinventing the wheel in various forms.

50:
Use ScrollWindowTo to scroll to a tile, instead of reinventing the wheel.

55:
TILE_SIZE is an unsigned integer constant, some divisions with signed integers just failed.

60:
The actual rewrite of the drawing algorithm. Together with 30 this replaces about 400 lines of code with about 40.
* The basic idea is to check visibility of tiles using the same limits as used by MarkTileDirtyByTile.
* The row/column loop then gets away with some simple lower limit for the start row, while the details are checked consistently with MarkTileDirtyByTile.
* Compared to the old version: The loop likely iterates over more tiles, but draw_tile_proc is called for less tiles. In theory this should be faster overall (needs profiling for proof). The "/* Not visible yet */" part could in theory skip multiple rows, but before profiling I just claim that that is not relevant.
* In the (today) unusual case of freeform-edges being disabled, the north border of the map is drawn again.

[Alberth]

Very much better!
Comments in http://devs.openttd.org/~alberth/diffs/topic72107 , look for ">>>" at the start of the line.

[HackaLittleBit]

Impressive.

Some details though.
position 1. Spot on!.
position 2. 1 pixel below target activates industry info screen.
position 3. Click in black space activates industry info screen.
position 4. 1 pixel inside target activates industry info screen.


Somewhere you have to shift 1 pixel to the left (NW).

Smoke from power station functions flawless at highest level.



Edit:
I am shure you know but...
There is also that thing with the bounding box.
High buildings don't have it correct.
see arrow in bounding box.png

Edit2
In smallmap
move cursor slowly along red direction.
You will see that square does not consitantly follow map edge.
It is already much better than trunk.
It gives a wobbely feeling.