Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature: ability to build overlapping bridges on different axes #9043

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

@perezdidac
Copy link
Contributor

@perezdidac perezdidac commented Apr 16, 2021

Motivation / Problem

OpenTTD doesn't support building a bridge that crosses another bridge perpendicularly.

Description

This change introduces the ability to build bridges on top of other bridges in the opposite axis.

image

This are the major changes made as part of this PR:

  • GetNorthernBridgeEnd removed, replaced by GetNorthernBridgeEndAtAxis, which require the axis to be passed
  • GetSouthernBridgeEnd removed, replaced by GetSouthernBridgeEndAtAxis, which require the axis to be passed
  • `GetBridgeAxis can now return more than AXIS_X or AXIS_Y, so made sure all callers handle that
  • Took care of all callers of the functions above to work properly in all scenarios
  • Implemented some helper functions, for instance one that gets the lowest height of a bridge within a tile in case it has two bridges, used for drawing stuff mainly
  • Made sure bridges cannot cross other ones at the same z!
  • Tested as many terraform actions as I could to verify nothing is broken
  • Tested as many combinations of bridge over bridges as I could to make sure it functions well
  • Used SubSprite to clip the bottom bridge middles properly

Limitations

This change doesn't implement the ability of stacking bridges on the same axis as demanded here: JGRennison/OpenTTD-patches#245.

However, here are my findings to do so.

Today, the type byte within the Tile struct has 2 bits reserved for tunnelbridge information, bits 2 and 3, one for each axis (X and Y). For that reason, there is no straightforward way of implementing the ability of stacking bridges on the same axis. The way OpenTTD knows where the tunnelbridge heads are based on a given bridge tile is by iterating through the axis until it hits the head (see GetNorthernBridgeEndAtAxis()). A tunnelbridge head is defined as a tile of a given type. Tile type is stored in bits 4 to 7, that is there are up to 16 tile types, one of them being MP_TUNNELBRIDGE.

With that being said, there is no current way of stacking bridges on the same axis without either using more of the bits from Tile or from TileExtended. For that reason, I'd rather get this PR in first, and eventually work on stacking bridges, which would require a good amount of work. I don't even know where the documentation for TileExtended is and what those bits mean.

This is the approach I'd go with to get this one:

I'd pick a max number of stacked bridges, let's say 2 per axis, so a total of 4.
I'd pick spare bits from TileExtended enough to be able to represent the number of stacked bridges.
The current bits within Tile's type would be used to determine whether there is or there is not a tunnelbridge on a given tile and axis, as it's done now.
The new bit from TileExtended for instance would be used to describe whether there is one bridge on that axis (bit set to 0) or two (bit set to 1). Viola, one single bit to get this done. Less than I expected.
But hold on, we still need to draw everything right, just like the problems we have in this PR.
To find the bridge heads it would be easy, the new bit will tell us if we have to iterate until we find one bridge head or a second one too.

I have a pending commit to achieve so, still WIP, that will be published as a draft once this one gets in.

Checklist for review

Some things are not automated, and forgotten often. This list is a reminder for the reviewers.

  • The bug fix is important enough to be backported? (label: 'backport requested')
  • This PR affects the save game format? (label 'savegame upgrade')
  • This PR affects the GS/AI API? (label 'needs review: Script API')
    • ai_changelog.hpp, gs_changelog.hpp need updating.
    • The compatibility wrappers (compat_*.nut) need updating.
  • This PR affects the NewGRF API? (label 'needs review: NewGRF')
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 16, 2021 Inactive
@LordAro
Copy link
Member

@LordAro LordAro commented Apr 16, 2021

I am generally -1 to this change. There is 0 possibility (without significantly extending the bridge spec) of doing this without the drawing looking ridiculous and causing (visual) issues

But it can't hurt to have a play with it :)

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 16, 2021

I am generally -1 to this change. There is 0 possibility (without significantly extending the bridge spec) of doing this without the drawing looking ridiculous and causing (visual) issues

But it can't hurt to have a play with it :)

I think everyone agrees that this won't get in unless it looks perfect for all the bridges out there :)
And yep I am just trying, I made the PR to show the code to some people that asked in Discord, but my intention is to keep trying and getting a clean solution if possible. If not, won't get in.

Loading

@nielsmh
Copy link
Contributor

@nielsmh nielsmh commented Apr 16, 2021

For bridges-over-bridges and bridges-over-stations to look good, I think you need two parameters per bridge tile: clearance above, and clearance below. Station tiles would need a clearance above. Only allow building bridges where there won't be conflicts in the clearances.
Of course the built-in objects could have the clearances added, to make it work out of the box, but all NewGRFs would need to be assumed to be incompatible until they have the appropriate properties specified.

Loading

@LordAro
Copy link
Member

@LordAro LordAro commented Apr 16, 2021

Just for fun...

image

Loading

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Apr 16, 2021

For bridges-over-bridges and bridges-over-stations to look good, I think you need two parameters per bridge tile: clearance above, and clearance below. Station tiles would need a clearance above. Only allow building bridges where there won't be conflicts in the clearances.
Of course the built-in objects could have the clearances added, to make it work out of the box, but all NewGRFs would need to be assumed to be incompatible until they have the appropriate properties specified.

I would suggest that "clearance below" is necessary but not sufficient for stations. Bridge pillars coming through the middle of the default station curved roof for example looks bad, even if the vertical clearance is sufficiently high.
I've got bridges above stations in my own branch, and have got station layout properties for vertical clearance and which bridge pillars are disallowed, and bridge layout properties for which pillars are present.

It may be that pillars don't matter for bridges over other bridges, but it's worth bearing in mind.

Loading

@nielsmh
Copy link
Contributor

@nielsmh nielsmh commented Apr 16, 2021

I mean, stations don't need clearance below, since stations are always built on ground.

Loading

@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 18, 2021 Inactive
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 18, 2021 Inactive
@LC-Zorg
Copy link

@LC-Zorg LC-Zorg commented Apr 18, 2021

perezdidac: I think everyone agrees that this won't get in unless it looks perfect for all the bridges out there :)

I think even in this form it could come up with cheat functions. :) If that doesn't cause an explosion, why in an offline game forbid a player to do potentially unreasonable things? :)

Maybe it's a question of a different approach, but I don't think you need ground clearance information. Rather, the one with the height is enough.
Perhaps everything on the map should have this information (objects, stations, buildings, trees, ships etc.). Objects that don't have a specific height would default to the specified value. Then even the older NewGRFs would be compatible at times. Most bridges are lower than 4 levels (from the road / track level) so here that would be the default value.

Loading

@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 18, 2021 Inactive
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 18, 2021 Inactive
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 19, 2021 Inactive
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 19, 2021 Inactive
@James103
Copy link
Contributor

@James103 James103 commented Apr 21, 2021

Does this PR allow for stacking two bridges vertically in the same horizontal axis such that at least part of their middle sections occupy the same tiles horizontally?

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 21, 2021

Does this PR allow for stacking two bridges vertically in the same horizontal axis such that at least part of their middle sections occupy the same tiles horizontally?

It does not. That requires using extra bits from TileExtended or Tile or wherever there are spare bits. It's possible and I plan to try getting it done after this PR gets in, if it ever does.

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 21, 2021

Hi @frosch123 ,
I asked on Discord whether someone knows how to draw sprites partially to get this into an OK state. @TrueBrain suggested asking you.

TL;DR: I am trying to limit the drawing of bridge sprites up until the height of the bridge above, if there is any.

In tunnelbridge_cmd.cpp's DrawBridgeMiddleAtAxis I have a variable that holds whether there is a bridge above and what its height is. Ideally I would use those to only draw the middle bridge tile up until the bottom of the bridge above, but I am having a really hard time understanding how AddSortableSpriteToDraw works.

I just uploaded the latest snapshot of the code I have so far. If you could help me out with this that would be awesome as we are trying to make this to look nice in order to get it approved.

Loading

@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 21, 2021 Inactive
@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 24, 2021

I don't plan to include it in this PR but... I managed to make stacked bridges...

image

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 24, 2021

Latest status.
I talked to @frosch123 and gave me some suggestions on using SubSprite. I did some experiments but haven't succeeded yet.
Even using a SubSprite of -INF -INF INF INF nothing gets drawn. I wonder if the sprite sorter penalizes sprites with SubSprite set? or I wonder if there is something gfx.cpp does for when SubSprite is set.

If I remove the condition within GfxBlitter() that checks whether sub is nullptr it then renders the whole thing. I suspect if subsprite is passed it probably calculates things right but does something else that ends up causing the issue where nothing gets drawn.

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 24, 2021

OH BOY I think I know what's happening. I am creating a SubSprite that ends up being freed since I am creating it on the stack... Well I wasted 2 hours but at least I know how all this works now.

Loading

@perezdidac perezdidac marked this pull request as ready for review Apr 30, 2021
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 30, 2021 Inactive
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Apr 30, 2021 Inactive
@PeterN
Copy link
Member

@PeterN PeterN commented Apr 30, 2021

How does the sprite sorting look/behave when you start sticking vehicles on every part?

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Apr 30, 2021

How does the sprite sorting look/behave when you start sticking vehicles on every part?

Not well.

image

And if the bridge has catenary it also glitches.

image

So still needs more work. Do you believe this glitches are due to sprite sorting? Any advice you can give me on how to address these?

Loading

@perezdidac perezdidac changed the title Feature: ability to build overlapping bridges on different axes Feature: ability to build overlapping bridges on different axes (WIP) Apr 30, 2021
@frosch123
Copy link
Member

@frosch123 frosch123 commented Apr 30, 2021

General sprite sorting tips:
Make sure that on every height level, there are only two bounding boxes: One behind the vehicle, one in front of the vehicle. (The bounding boxes depend on the track direction on that height level.)

You can put all sprites behind/in front of the vehicle into a single bounding box each using Start/EndSpriteCombine. Currently bridges already do that to combine bridge sprites, track overlay, catenary pylons and wires.
In addition, bridges do currently have a helper bounding box (without any visible sprites) between height levels, to separate the sprites. (see SPR_EMPTY_BOUNDING_BOX)

Generally, make sure that no bounding boxes overlap.

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented May 1, 2021

General sprite sorting tips:
Make sure that on every height level, there are only two bounding boxes: One behind the vehicle, one in front of the vehicle. (The bounding boxes depend on the track direction on that height level.)

You can put all sprites behind/in front of the vehicle into a single bounding box each using Start/EndSpriteCombine. Currently bridges already do that to combine bridge sprites, track overlay, catenary pylons and wires.
In addition, bridges do currently have a helper bounding box (without any visible sprites) between height levels, to separate the sprites. (see SPR_EMPTY_BOUNDING_BOX)

Generally, make sure that no bounding boxes overlap.

Thank you @frosch123 for the hints. I am looking into the code to understand how sprite sorting works. It seems to sort sprites by xmin+ymin. I still don't quite understand the bounding box stuff. My latest theory is that the bounding boxes of both bridge middles might overlap somehow to a point where sorting those sprites becomes indeterministic?
Observation 1: if there is no catenary in the bottom bridge it doesn't glitch.
Observation 2: if I make all DrawMiddleBridge method be executed in a single Start/EndSpriteCombine block it renders well but not vehicles on it... And also it renders a blue circle with a white question mark inside. What is that?!

So I guess I need to figure out the way of not overlapping bounding boxes, but I don't quite yet understand how they work.

I'll keep trying... :-D any help appreciated!!

Loading

@PeterN
Copy link
Member

@PeterN PeterN commented May 1, 2021

Roughly, bounding boxes work on the inner tile coordinates in 3D space, but they are always aligned to the internal grid. 0x0x0 is the top of the tile, 16x16x0 is the bottom of the tile. When mapped to 2D space the logical bounding boxes can easily overlap so... illogical boxes are needed sometimes.

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented May 1, 2021

Roughly, bounding boxes work on the inner tile coordinates in 3D space, but they are always aligned to the internal grid. 0x0x0 is the top of the tile, 16x16x0 is the bottom of the tile. When mapped to 2D space the logical bounding boxes can easily overlap so... illogical boxes are needed sometimes.

Thanks Peter for the info. I understand the 3rd coordinate is Z and goes up positive, right?
Do bounding boxes need to be as large as the whole sprite? Of so, bounding boxes overlap naturally, right? For this particular case I am trying to achieve I am kinda confused about how I should get it done right. My understanding is that sprite groups get sorted by their corresponding bounding box xmin+zmin? That's why there is a sprite combine around the bridge floor and one for the roof, so the train is in between them? Am I getting this right?
But those assumptions don't work for multiple bridges and that's what we gotta fix here, that's my understanding...
Oh boy. Anyway, if you can look into my changes and suggest what to try that would be awesome.
Again thank you so much for the info. All help helps ^_^ especially since I want to keep going and making stacked bridges next.

Loading

@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 May 1, 2021 Inactive
@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented May 2, 2021

Update: I now understand how sprite sorting works, thank you @dp and @PeterN for explaining some stuff on Discord.

The sorting for when sse4 is enabled seems to happen here: https://github.com/OpenTTD/OpenTTD/blob/master/src/viewport_sprite_sorter_sse4.cpp#L121
or https://github.com/OpenTTD/OpenTTD/blob/master/src/viewport.cpp#L1572 if not enabled.

Sorting then relies on X+Y+Z of a given sprite. that means sprites that are closer to the bottom of the screen and sprites that are taller get rendered first. Is that an OK assumption?

Also, I've been playing around with drawing the bounding boxes and it looks quite weird in some situations. I am still digesting and learning all this stuff. The next thing I want to try is to change the bounding boxes used for lower bridges if there are bridges above, since that might do the trick. Does it make sense?

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented May 3, 2021

Alright, here is the current status of things. I've been making some changes and adjustments to bounding boxes and stuff and so far I got it down to three visible issues.

image

  1. train wagon bounding box drawn after bridge above
  2. catenary of bridge below being drawn on top of bridge above
  3. pillar of bridge above getting drawn after bridge below

I think those are all fixable but require some work. Suggestions appreciated :)

Loading

@VacuumBreather
Copy link

@VacuumBreather VacuumBreather commented Jun 14, 2021

Looking good. Let's hope you can figure this out :) Also regarding the "this can never be in trunk before it looks perfect..." wellll... considering the dutch signals stick through bridges sometimes with vanilla... :D

image

There are already some sprite sorting issues in trunk. Doesn't make this any less worth of pursuing :)

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Jul 19, 2021

Looking good. Let's hope you can figure this out :) Also regarding the "this can never be in trunk before it looks perfect..." wellll... considering the dutch signals stick through bridges sometimes with vanilla... :D

image

There are already some sprite sorting issues in trunk. Doesn't make this any less worth of pursuing :)

Hi @VacuumBreather , I really appreciate your message. I have been busy for a few months and haven't worked on OpenTTD at all, but I wish I could complete this feature at some point. I see your point that at trunk existing cases show sprite rendering issues. I am not sure if, despite this, code reviewers will be happy with this PR. I really like this change and I have a second PR (not on Github yet) to have multiple overlapping bridges in the same axis, and it is so amazing.

With that being said, I want to mention again that I am looking for someone to help out at trying to address the existing rendering issues. I will work on trying to pull rebase my PR since I see there are conflicts at this moment, and try to push for help again. If you are good at this, and want to help, please let me know asap and maybe we can figure this out together. Thank you!

Loading

@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Jul 19, 2021 Inactive
@DorpsGek DorpsGek temporarily deployed to preview-pr-9043 Jul 19, 2021 Inactive
@perezdidac perezdidac changed the title Feature: ability to build overlapping bridges on different axes (WIP) Feature: ability to build overlapping bridges on different axes Jul 19, 2021
@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Jul 30, 2021

Update. Can't figure out yet.

I think it might be worth it to create a debug tool or way to see overlapping sprite boxes to understand what the problem is.

Loading

@glx22
Copy link
Contributor

@glx22 glx22 commented Jul 30, 2021

Loading

@perezdidac
Copy link
Contributor Author

@perezdidac perezdidac commented Jul 30, 2021

IIRC, there's a tool to show bounding boxes.
https://wiki.openttd.org/en/Development/NewGRF/Debugging#bounding-box-viewer

Thanks! Yeah I knew about it. It's just hard to visualize and see where BB overlap. I was building a tool to hide sprites and to highlight where overlaps happen but it's not easy at all :-S

If you are interested in helping out, let me know and maybe we figure this out together.

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Linked issues

Successfully merging this pull request may close these issues.

None yet