Day 3

allefant on 2012/05/08 17:02 of Yellow and Dangerous

I spent all night yesterday trying to fix a bug in my isometric sorting but couldn't figure it out. And then had to think of it all day today. When I finally got home I added lots of print() statements throughout my code and eventually figured it out.

Floating point numbers don't work as you would expect at all. Just because x = a + b doesn't mean that x >= a + b, apparently. After using x + 0.1 >= a + b it suddenly started working...

Unfortunately I hit another problem. My algorithm creates a mask for each block it draws and then draws all other blocks in front of it with the mask active. So for a map with 100 blocks I might end up drawing several thousand blocks... which is too much for Python and/or my GPU. So next is figuring out a way to optimize this, probably by trying to pre-sort the blocks and cache the overlapping ones...

(log in to comment)

Comments

Cosmologicon on 2012/05/08 19:11:

Just because x = a + b doesn't mean that x >= a + b, apparently.

Er... that's not how floating point numbers work. If the first condition is true, the second one will be true. Your issue must have been somewhere else.

allefant on 2012/05/08 19:27:

Oh yes, I was as surprised as you. It's why it took me so long to find the problem - it's the last thing I would ever have expected.

Try this in a Python shell, it's essentially what my bug boiled down to:

>>> s = 96 / 2 ** 0.5
>>> S = -4.75
>>> x0 = S * s
>>> x1 = (S + 1) * s
>>> x0 + s >= x1
False

I "fixed" it by now using:

>>> x0 + s + 0.000000000001 >= x1
True

gcewing on 2012/05/09 00:24:

My algorithm creates a mask for each block it draws and then draws all other blocks in front of it with the mask active. So for a map with 100 blocks I might end up drawing several thousand blocks.

Not sure why you're making it so complicated. When you have an isometric grid, you can just iterate over the grid in back-to-front order and it should work out.

Digitalis on 2012/05/09 07:01:

Why are the masks necesary? Couldn't it be done as a simple Painter's Algorithm?

allefant on 2012/05/09 09:27:

See blocks x, y and z in this picture. Which order would you draw them in? y is behind z, z is behind x, x is behind y. Of course you are both right and in 90% of blocks just sorting is enough. But in my game I have moveable and stackable blocks like x and y and the player is modeled like z so it would glitch all the time.

BlueDragon on 2012/05/09 09:45:

I think z should be split into two halves, each one 1 tile high.
If all blocks are rectangular and have the same height, you could just paint each plane (from floor to ceiling, x before y, b before m, etc.) in ordered manner (from back to front, y before higher half of z, I before O, etc.) and have no problems.

This is just a guess I've never done 3D :)

spirulence on 2012/05/09 11:30:

I "fixed" it by now using:

>>> x0 + s + 0.000000000001 >= x1 

You've just encountered a well known phenomena in floating-point math - the order of operations taken on a floating point number can influence the last few bits of the number enough to throw off any kind of an equality comparison. Normally, that additional factor you're using would be called an "epsilon".

There's an excellent (if rather long) series on floating-point math here:
http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm 

richard on 2012/05/09 11:54:

BlueDragon's advice is spot on - blocks should not span cells. Doing otherwise invites the pain you're encountering. You may need to logically split your "model" data (which includes 2-cell entities) from your "view" data (which only contains 1-cell entities).

allefant on 2012/05/09 12:35:

Nothing is different if z has the exact same cube shape as x and y (and is not on the floor then but hovering in mid-air). What would work is to dynamically split everything as it crosses grid borders and at the same time allow only one (part of a) block per grid cell. But since I allow pushing blocks the second condition is not possible. And the splitting would be a lot of complex code even if it would help.

Cosmologicon on 2012/05/09 17:18:

For what it's worth, I appreciate that you're willing to tackle a difficult problem that most PyWeekers would not. Best of luck!

mauve on 2012/05/09 17:53:

What if you only mask blocks that span horizontal layers? You could use a chevron shaped mask - like a v - to draw the section in each layer in the appropriate order for that layer. The top layer would have a block-shaped mask (hexagonal), so that the "top" is drawn. This would give each layer a total order, so you can draw it with painter's algorithm. And you only need to use a mask for objects that straddle layers.