Maxhaus
Responsible for: front-end programming (flash), backend-programming (python)
Maxcasa, a Brazilian construction company is launching a new housing project: Maxhaus. A fresh, open approach: the apartment comes bare - no walls - with a beautiful concrete floors and ceiling. From there buyers can customize walls and many aspects of their apartment.
Gringo created a campaign that allows user to create their own "virtual apartment". Users can add walls, furniture, paint, rotate and position them to their liking. The apartment can be viewed in 4 different angles, in a closer or further away look. Each user creates their own virtual floor on an imaginary building.
I was responsible for the virtual apartment section. Created from scratch it's a fake 3d world. Technically, it's all 2D, with a fake isometric projection. We toyed with the idea of having a real 3d scene, but the low poli constrains would not have worked. We wanted the furniture to look good, high poly renderings. This was a very challenging project for me. I'd never done any isometric world coding before, and there was a lot of learning to be done: projection, depth sorting, collision detection and so forth. All in a user friendly web interface. Depth sorting turned out to be much, much harder that anticipated. Since objects can occupy different number of tiles, the standard methods just don't cut it. I am in great debt to Zeh who has helped me out, and implemented a great sorting algorithm. If I find the time, I'd love to write a detailed blog entry explaining his solution.
The site was built using AS3, and there are lots of performance tuning to it. A whole lot of computation has to happen real time: collision detection, depth sorting, masking, scaling and so forth. AS2 wouldn't have cut it.
I was responsible for the back-end also. With quite a few features:
- User management: login, registration, pass recovery, logout, authentication.
- Social apps: comments, ratings
- Search.
- Saving and retrieving each apartment configuration: furniture, position, rotation, color and so forth.
- A heavy weight admin interface that allowed us to add 3d objects from a user friendly web interface.
- A RESTful architecture that serializes data with JSON.
This was a pretty large back-end, and I couldn't have done it without Django. Without Django, the back-end alone would take me longer than the front end.
The whole project was completed in about 2 months, and it was very intense. Given time constrains, some features didn't make it to the first version, but all in all it's a very exciting project.
Unfortunately, the website hasn't been localized yet, and it's Portuguese only. If you are interested in seeing it, just click on the larger button to the right of the navigation bar that reads "Usuário novo?" and from there you can take a shot of making your own apartment.
The website was awarded an FWA site of the day for December the 03rd, 2008.
getting a third opinion
Hi Arthur,
I found your side searching about depth sorting, and what I see about your - very very impressive - Maxhaus project, you seem to have found a solution.
I am working for about a week now over the depth sorting problem and as you write, it's a very hard problem. I would like to ask you if you maybe would explain the solution to me, just the main ideas.
I tried some different approaches, like using some points of the bounding box and calculating a depth from that (like x+y+z and so on), or using a comparator that implements a in-front-of relation and sorting the scene, but nothing works. The problems are the walls inside of the szene and thinks that are over other thinks like a book on a table.
I am a german software developer and working alone on a relaunch of a small german browser game.
Best Regards Sebastian Baltes
Hi Sebastian.
Yup, it's very, very tricky. I took me several tries to make an algorithm to almost always worked, but would break on some strange inputs.
It took Zeh do implement the final version that is correct.
Basically you have to project the vectors towards the camera and compare object by object on your scene (with a bubble sort or some other sorting algorithm). The really tricky issue here is that the comparation can yeld a yes, no and maybe answer and you must know what to do with it.
I am really swamped right now, but when I have the time I'll post the solution with a few explanations.
Cheers Arthur
Hi Arthur,
thank you very much for this response and that you found the time to reply.
I'll try to figure it out with a comparation. If you could find the time, it would be very nice - maybe too much to ask for - if you could share the solution, and just the comparator part in plain, uncommented code would be enough and a very big help. Or maybe you could give a hint what to do with the maybe - cases.
Do I see it right that a order between two objects only exist if their projected bounding boxes overlap and all other cases are maybe? Could maybe be interpreted as equal for bubblesort?
Sorry for asking again...
Cheers Sebastian
Sebastian: basically, depth sorting in an isometric grid is very, very simple; something like x+y of the center of the bounding box (with some inversions depending on the direction the camera is looking at; ie, it could be "(width-x)+y" instead).
However, with Maxhaus, since objects weren't divided in 1x1 tiles, you had to sort the object as a whole. This mean you couldn't simply take the center of the object in consideration; sometimes the center of object A was closer to the "camera" than the center of object B, but object A was still behind object B. Think of an object with a longer bounding box - like a long wall - next to some small object like a chair. It breaks that kind of straight numeric sort.
I don't have the code here in my hands (it's already backed up on an external drive that I store somewhere else). I can say, however, that the algorithm used in Maxhaus was the result of several different approaches - many of them which worked almost perfectly - until we got it right.
Well, the end result has two important parts:
First, it's implemented as a sorting algorithm. Think of the way a bubble sort works, like Arthur mentioned. It compares every object to every object, and find out what should be on front of what. But the important thing is, when comparing two objects, instead of the common results - "A should be in front of B", or "B should be in front of A" - it also has an additional result: like Arthur said, the "maybe", or we can also call it "I don't know, so whatever". This is the result of a comparison of two objects who aren't directly in front of each other, so no comparison can be done between them, and sorting for that pair is skipped for that step.
If I remember well, that algorithm works a bit differently to the way bubble sort does; first, it keeps a list of unsorted objects. He start looping on that list and add objects to a new list (the "sorted" one) on their new order by doing the depth comparisons. If an object can't be compared to any other object - the "'maybe" - he's bypassed for this iteration of the loop. That goes on until the list is empty.
If the list loop reaches a point where none of the remaining objects can be compared to any of the objects already sorted (when there are two "groups" of objects with no direct depth relation between the two groups) one of the remaining objects is added at the end of the sorted list since their direct relation doesn't matter (then the process starts on the remaining objects).
Second, the comparison algorithm itself. This checks the corners of the rectangles of the bounding box of each of the two objects and determines which one is in the front of which. Mathematically this is just a lot of IFs, but if you think visually it's quite easy to understand. Just draw two random tiles on an isometric grid - you, as a human, can easily determine which one is in the front. We just translate that to code by comparing the position of the corners.
It's important that, if the position of the corners don't collide in any way - if the horizontal projected size of the bounding boxes never overlap (considering an infinite vertical size) - then the algorithm returns the "maybe" result, because it doesn't have enough parameters for an accurate comparison. While there would be some room for guessing in that case, it's not worth it because other objects can radically alter the correct depth.
In the end, there's no guessing or approximation on the algorithm; it's a pretty brute force comparison of everything. It's also not very fast. I think the full sorting took somewhere around 40ms for an standard room. So it's not thaaaat slow, but also not real time.
When the room is rotated, sorting is re-done by remapping the positions and widths of the objects to the new axis.
Hopefully that helps, and hopefully it's accurate. It's been a while.
Thank you very much, Zed! I have a very similar situation like in Maxhaus with tiles of an unknown size. In the meantime I developed a very similar aproach like yours:
I build a complete graph of the object-behind-relationships and sort it topologicaly, so I can detect Escher like cycles at design time, but this is done in O(n^2). Your sort algorithm sounds faster than that, so I will test it with your algorithm.
The compare method looks like this:
public boolean behind(Qube a, Qube b) { return projectedRectanglesOverlap(a,b) && projectedRhombusOverlap(a,b) && ( layerBehind(a,b) || (!layerBehind(b,a) && ( slideBehind(a,b) || (!slideBehind(b,a) && ( xBehind(a,b) || (!xBehind(b,a) && ( yBehind(a,b)))))))); }
I don't have a seperate "maybe" at the moment, just behind or not. Not means "maybe" and "in front of" together, so it's similar. Like in your approach I just check overlapping projected bounding boxes. But I guess it would be better to distinguish between maybe and in front of, like you do, because then I could (maybe) save one comparation.
I made a test program that visualises the bounding boxes in real 3D in order to find the right details of the comparation cases, and I bullet-proove this algorithms with randomized scenes. What I found difficult is to make the compare method realy antisymetric. I'm nearly finished with that, I just need to work out non-horizontal objects like stairs.
40 ms seems to be ok, I will have moving sprites, but I think it shouldn't be necessary so resort everything again because those sprites wouldn't be that large, and maybe I could use some sort of space partition or some kind of grid so just a few comparisons per movement would remain.
Thank you very much for sharing, Zed! If you could find and share the comparation method, that would be great. I still have problems to decide what to do if two bounding boxes intersects, but maybe this can't be done nicely.
Hi Joe.
That's a tough one ;-); Estimating development time is notoriously difficult.
Usually, the backend is pretty fast (this one, which is pretty complex took me a couple of days, thanks to django). I've found that I work best by assigning milestones for builds and work closely to the time alloted to that task. This means that many times I can check something off as completed, even thought it lacks polish. On the last week or so of development, I do some fine tuning parts that are still a bit rough. And of course, always pad your estimates by 30% or so (bugs never show up during planning ;-)), but your milage may vary.
Cheers Arthur
Arthur, Zeh, you guys have made a wonderful application. I am amazed at the level of interactivity and complexity of this app. Again, great job. Regarding the whole z-sorting issue:
The if..else statement sounds like you are using Filmation Mathematics (http://bannalia.blogspot.com/2008/02/filmation-math.html). The as3isolib uses this as its default layout algorithm along with the Array.sortOn (quicl sort) and works fine for most cases however...
The default array sorting mechanism uses the quick sort which is super efficient, but not without its faults. It doesn't necessarily compare every object to every other object. I can see why you guys use the Bubble sort method. I have considered using it, but feel that it may be performance prohibitive in most isometric game applications.
Thoughts?
Hi as3isolib.
The problem is, my initial design was wrong. Instead of having 3d coordinates and doing isometric projection, I choose to have a 2d grids and do the depth sorting by hand, which is not the best plan of action, unless all objects occupy the same amount of tiles.
Then you cannot determine depth unless you compare all objects, since there is not one calculus alone to solve it. It can't be projected to a linear amount and sorted with quicksort at all. That's the reason for bubble sort, since object can have a "maybe" status, situations where you need to compare to everything else to determine the projection depth.
Performance wise, it's got it's share of issues really. You simple have to keep the number of objects down.
Also, you can get smart and group a few areas that never intersect, sort amongst those, and only sort the isolated area that is changing. In this project's case, it was hard to do that, since it's a small grid with potentially many objects.
Cheers
Arthur Debert
p.s.: gotta look into as3isolib , looks nice!
Arthur I just realized you are the genius behind the BulkLoader. Man I gotta heap praise upon you for this little library. I use it ALL THE TIME. It has been a godsend for many projects including some of the testing apps for the as3isolib. so.... THANK YOU!!!!!
I came back to this post to see any updates had been posted and to see if I missed something written here. I am still on the quest to find a suitable z-sorting algorithm and have given up on trying to keep within the confines of the Array.sort() methods. You wouldn't be able to maybe drop some pseudo code for your bubble sort specific to isometric implementation would you?
Hi Arthur and Zeh,
I believe I independently developed the same algorithm as you guys. It does sound like mine is slightly different, but the premise is the same. Comparing objects gives a front, back, or "side" answer. But instead of saving the side objects to a separate list I add them to the list. The algorithm is O(n^2) as well, but it seems to run pretty quickly in realtime for me. My application is culling the objects in the world and I'm able to sort 200+ objects on screen in realtime while maintaining a good frame rate.
I just wanted to say thanks to Zeh though since he's essentially written the blog I was going to write on the topic in his forum posts.
Heya,
This is some very usefull information! Thanks everybody!
I am exactly in the same situation but I am using quicksort at the moment for sorting by objects. It works a little but it still has a lot of fault depth sorting issues. I figure using bubble sort I'll fix most faults?
Have the last word