"Try of a new sprite sorter"-Patch

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Post Reply
frosch
OpenTTD Developer
OpenTTD Developer
Posts: 988
Joined: 20 Dec 2006 13:31
Location: Aschaffenburg

"Try of a new sprite sorter"-Patch

Post by frosch »

Hello

Inspired by http://bugs.openttd.org/task/119 I wrote a new sprite-sorter.
During my insufficient testing I did not encounter any of the standard sorting-problems. Well I wrote "insufficient", so you may now guess, what I want you to do...

Please test the attached patch with your savegames and search for glitches with bad sorted sprites. If you have found one, compare it to current trunk, and report if it's a new or a old one. I hope a screenshot with the glitch will be enough for now.

About the attachments:
1) For those who do not know the basic dilemma of sprite sorting, I have attached a small exercise for you.
2) The patch introduces a debuging feature: By pressing "Ctrl-B" you can toggle drawing of bounding boxes. Please do not report about residues of the bouding boxes of moving objects.
3) Well the patch file. If someone with a running BuildOTTD is around, I will be happy if you would post a Win32 executable, so more people can search for glitches.

Technical details:
1. Airports are a bit tricky. The bounding boxes of aircrafts on the floor are pretty wrong. But it is not obvious how to correct them. For now I got away with only modifying the bounding-boxes of the jetways.
2. The current code is only a experiment, if it may work. Please do not talk about efficiency, or code niceness.
3. The sprites are sorted in multiple steps:
I) First dependencies between sprites are created (in the source called "after"-list). These are always correct, but they can lead to cyclic dependencies (attachment 1).
II) Cycles are detected and broken at the weakest edge determined by a heuristic based on the barycenter of the bounding boxes.
III) All sprites that currently do not depend on other sprites, get additional dependencies based only of the Z-coordinates of their bounding-boxes. (This aims at glitches with foundations.)
IV) The remaining sprites are sorted by the barycenter-heuristic.
V) Every time a sprite is drawn, dependencies of other sprites to it are removed. If a sprite has no longer any dependencies, proceed with it like in III.


Somewhat unrelated changes in source:
First drawing lines could segfault. Second selection sprites on foundations can be drawn it a much more correct way, which removes the drawing of selections above vehicles etc.
I will post this changes on Flyspray later, when I get time.
Attachments
1) Exercise: Sort the three sprites in way, that produces the right picture. Good luck.
1) Exercise: Sort the three sprites in way, that produces the right picture. Good luck.
SpriteSorterDilemma.png (1.99 KiB) Viewed 2979 times
2) Toggle bounding boxes with Ctrl-B
2) Toggle bounding boxes with Ctrl-B
BoundingBoxes.png (169.09 KiB) Viewed 301 times
SpriteSorterTry_r10738.patch
3) the patch: look at the sticky topics about "How to apply a patch" and "BuildOTTD".
(25.47 KiB) Downloaded 224 times
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁
frosch
OpenTTD Developer
OpenTTD Developer
Posts: 988
Joined: 20 Dec 2006 13:31
Location: Aschaffenburg

Re: "Try of a new sprite sorter"-Patch

Post by frosch »

Reserved for possibly more attachments.
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁
SmatZ
OpenTTD Developer
OpenTTD Developer
Posts: 351
Joined: 03 Oct 2006 18:26
Location: Prague, Czech Republic
Contact:

Re: "Try of a new sprite sorter"-Patch

Post by SmatZ »

Hello, very nice try.

There are some problems, see attached files.

The wires over electrified railway are too high, they are higher than tunnels. There are many problems regarding heights of vehicles/wires/tunnels/bridges.

The idea with boxes after Ctrl+B is nice. Your algorithm sorts nice anyway, have you considered the speed too?

You should try save from http://bugs.openttd.org/task/906 to see how you cope with a non-simple el.rail situation.

(I am sorry I am not working at the patch atm - I am dooing something important for school or I am just at Holidays)
Attachments
station.png
(230.81 KiB) Downloaded 234 times
low_tunnels.png
(130.9 KiB) Downloaded 221 times
foundations.png
(176.93 KiB) Downloaded 221 times
Image
frosch
OpenTTD Developer
OpenTTD Developer
Posts: 988
Joined: 20 Dec 2006 13:31
Location: Aschaffenburg

Re: "Try of a new sprite sorter"-Patch

Post by frosch »

Thanks, nice catches.

Unfortunately in some cases the sprite sorter is indeed correct, in what it is doing. Originally I wanted to avoid changes in bounding-boxes, but now I think I have to.
The "station.png"- and "low_tunnels.png"-situations can be fixed that way, I hope. The third will be harder.
I will try...

About the speed: I have not thought a second about it. I first want to know if it can be done better at all. The current algorithm itself is quadratic in sprite count, but the implementation has a recursion that should be transformed into a loop, and it uses a lot of "new" and "free" which can be removed resp. changed into some kind of memory pool.

I will download the savegame, you pointed me at, and a savegame from #openttdcoop (that will stress it enough).
⢇⡸⢸⠢⡇⡇⢎⡁⢎⡱⢸⡱⢸⣭⠀⢸⢜⢸⢸⣀⢸⣀⢸⣭⢸⡱⠀⢰⠭⡆⣫⠰⣉⢸⢸⠀⢰⠭⡆⡯⡆⢹⠁⠀⢐⠰⡁
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 14 guests