Slick Forums

The tile-combining code you wrote a while back doesn't seem to scale up too well to larger levels, one of my testers has found. The levels aren't terribly large - they are about 100x100 tiles big, which isn't all that big.

Is there any chance you could look into optimizing this? Based on a brief assessment, it's not the size of the level or the number of tiles that matter - it's that when you start having a good number of land masses that is starts breaking down.

Perhaps the best way to put it is that it performs worst when there are simply a lot of parts in a level. If you want to make the algorithm die, a checkerboard pattern is the one to try if you want a quick way to repro this, though it's not real world usage.

I suppose I could "workaround" this by not automating combining and by having the user combine masses themselves, thereby distributing the processing, but that will be a hit to convenience and usability.

(Yeah, I still am using this code. I used an Adapter to make it work with Box2D, though this problem is based on pre-Box2D code.)

Which code do you mean? I've written a few tile combiners for different things - don't think any of them got included in the code base though?

Kev

You've written more than one tile combiner? I'm talking about this one:
http://slick.javaunlimited.net/viewtopic.php?t=664

To be really specific about the performance issue, it correlates directly with the number of disjoint shapes there are, hence the "checkerboard" pattern being a great way to expose it, but it shows up in real-world usage too.

Where's the code though, I can't even remember coding that one

Kev

From SVN.

https://bob.newdawnsoftware.com/repos/s ... mUtil.java

https://bob.newdawnsoftware.com/repos/s ... eTest.java

Ah, thats what confused me, it's part of Slick, I was searching through Phys2D code.

Kev

Sorry about that confusion. I somehow always thought it was part of Phys2D.

Have you been able to reproduce this yourself?

I've not had a chance yet, a lot of other stuff going on. I'll take a look asap.

Kev

Any luck with this?

Doh, slipped my mind with all this flash nonsense going on. I'll get on tomorrow night.

Apologies again,

Kev

Committed an update to GeomUtilTileTest.java that supports using a quad space (my fave ) to separate out the search domains for the combination. This works with the original test data with various settings so I'm thinking it probably works for all the cases it did before (let me know it thats not the case - there might be some corner cases between segments).

Performance wise it's a considerable improvement. I'm using the checker board case as probably the worst case. On my local test machine (dual core something or other):

50x50 Checker Board
Before with brute force: 1.8 seconds
After with quad space with 8x8 segments: 0.3 seconds

100x100 Checker Board
Before with brute force: 29.2 seconds
After with quad space with 8x8 segments: 1.9 seconds

With tiny maps that don't have much in the way of isolated bodies theres slight degradation due to having generate the quad space at all (I've left it so you can just swap between the two). The segment count needs tuning for the type of map but for 100x100 tiles 8x8 seems to be close to optimal.

HTH

Kev

Superb. I'll give this a hop and let you know if I run into any issues. Many thanks from me in advance.

I should also keep you more in the loop about what's going on too. My apologies for not doing that more often.

- Jon

Got a question for you. So I did a quick integration of this, and I've run into something interesting - should the output of this be exactly the same as that of the brute force method?

For me, it's not. It may have gone wrong with my integration, but I'm getting significantly more shapes outputted, a count that rises as the segments parameter rises.

So while the output does not affect gameplay (it's still "correct"), it's not the same. For that matter, what's interesting is that even with a segment count of 1, the output seems a bit different too. I'll post that up later today.

I tried the test case against the original test scene varying the segment count from 1->32, the visual output was the same each time. Is it possible the higher number of shapes in the output list are just duplicates of each other?

Kev

Yep, thats what it is, changing the end of combineQuadSpace() to this:



Resolved it here.

Kev