Re: [pygame] FastRenderGroup revised (update4)
Brian Fisher: We tested a lot of different approaches and tiling was by far the fastest we tried (in C++ anyways). In particular the fastest implementation for us was where each tile has it's own rect, and it does min/max ops on the cells rect to grow it to cover the overlap being the dirty rect and the cell area. Do you have any benchmark figures from these tests you could share? -- As I soared high into the tag cloud Xeni Jardin Nick Moffitt carefully put up for me, I couldn't help but wonder how [EMAIL PROTECTED] high we were above the blogosphere. -- Carlos Laviola
Re: [pygame] FastRenderGroup revised (update4)
On 6/30/07, Nick Moffitt [EMAIL PROTECTED] wrote: Do you have any benchmark figures from these tests you could share? No. we didn't keep around any benchmark figures, or code for the other approaches either, which is why I hadn't mentioned it before.
[pygame] FastRenderGroup revised (update4)
Hi Today I got the time to do the changes you have suggested in the last email. You can download it here: http://www.mypage.bluewin.ch/DR0ID/pygame_projects.html#fast_dirty1 or direct link: http://www.mypage.bluewin.ch/DR0ID/pygame/FastRenderGroup_v1.1.78.zip 1.) Change the name: yes, but to what? 2.) you really want to be able to pass in different get_ticks() functions? I can do it, but I do not see the benefit, because I'm still unhappy with the solution how to decide which method to use. Perhaps I could use a Exponential back off strategy (do not know how to implement it), but I'm not sure if that would be good. Any better ideas? 3.) naming of the attributes of the DirtySprite: we can change them, but to what? Are the current names already used? 4.) I don't think we can make it backwards compatible, so it will not replace RenderUpdates (unless the pygame.sprite.Sprite becomes the DirtySprite with dirty=2 as default, but that would be stupid). I have modified testsprite.py to use FRG, please test following configurations: testsprite.py testsprite.py -update_rects testsprite.py -FastRenderGroup testsprite.py -static testsprite.py -static -update_rects testsprite.py -static -FastRenderGroup What do you think? For that tests I have added a new image, as you can see. I have written a demo to demonstrate that all sprites have to be in the same FRG to be drawn correctly: multi_FRG_demo.py use the same arguments as for testsprite.py and you will see what happens when using the FRG. If you run the testsprite.py you will have the frame jerking too, so it is not a problem of the FRG. To avoid the jerking you will have to limit the Framerate to certain frames per second(or put a sleep(0.001) in there somewhere). I can not participate at the next minisprint, but in a week I will have time. ~DR0ID
Re: [pygame] FastRenderGroup revised (update4)
René Dudfield: What are the main features of FastRenderGroup? Since I have read earlier versions of this code, and chatted with DR0ID in the #pygame channel about the architecture (I suggested exponential back-off as worth exploring) I'd like to have a go at this. The core of it seems to be the chunk of code that tries two rendering methods every 75th frame and chooses the faster of the two as the method to use for the next 74 frames. It's a benchmark-based system, and could probably be called the BenchmarkingRenderGroup. The jerking stops for me when I make it not oscillate between update, and flip modes. I think maybe an Exponential back off strategy might work... not too sure. I think we should try a few different things when we meet up in two weeks. Some possible different strategies: - figure out the best rendering method in the first 1-3 seconds, then stick with that. - keep checking to see which is the fastest way. Only change modes at most once every 10 seconds. While writing the above, I thought that the name StochasticRenderGroup might be good. Then I stopped to look up the literal definition of a stochastic process, and realized that it did not apply. However, such a process might actually be the solution to removing the sampling jitter. gcide says: 3. (Statistics) of or pertaining to a process in which a series of calculations, selections, or observations are made, each one being randomly determined as a sample from a probability distribution. Consider that when you sample, you have a timing value for the fastest and the slowest method given a particular data set. Use this to calculate a threshold, and compare it against the current rendering time. Keep the rendering time for the previous frame as well, and do comparisons between successive frames and comparisons relative to the tests done earlier. You should also consider attack/sustain values for when to switch, so that you don't end up with bang-bang switching in cases where the two methods have similar speeds. -- How do you get mailings?... from the lists Nick Moffitt 1. suspects [EMAIL PROTECTED] 2. elbows -- Don Saklad
Re: [pygame] FastRenderGroup revised (update4)
Hello again René Dudfield schrieb: Hello, very nice work! I'm a bit busy myself for the next week. So in two weeks would be a good time to meet up and finish off the last things before we put it into pygame. 1.) Change the name: yes, but to what? Not sure. I'm afraid of using 'Fast' because too many times I have seen projects where there is a new FastSomething only for it to eventually not be fast anymore a year later. Your right, we should not use fast in the name. Perhaps OrderedDirtyGroup or DirtyOrderedGroup? Or DirtyLayeredGroup? What are the main features of FastRenderGroup? Well it has the layering system from the LayeredRenderGroup (ist that name ok?). Then it uses the dirty flag technique, so only things marked dirty will be redrawn. And the automatic switch between the two rendering modes is another feature (the idea of all that is that you stuff your sprites in there and forget about all the complicated rendering stuff, it will be just done for you). I think there are the 3 main features. Well clipping, you can set a clip, and it will only render in that area of the surface. We should definitely let people know in the docs that FastRenderGroup is the preferred group to use. Well not sure about that, I would say yes, but its a bit more complicated to use actually. You will be responsible to set the dirty flag whenever the sprite has to be redrawn (actually dirty=2 is a shortcut for sprites that are always dirty, so they do not need to set the dirty flag all the time, but this should be used with care, because if you set dirty=2 on every sprite then you can just use the LayeredRenderGroup). 2.) you really want to be able to pass in different get_ticks() functions? I can do it, but I do not see the benefit, because I'm still unhappy with the solution how to decide which method to use. Perhaps I could use a Exponential back off strategy (do not know how to implement it), but I'm not sure if that would be good. Any better ideas? So people can use their own game timers. Say the rest of the game uses either time.time, or even something from blender, crystalspace, a real time clock etc etc. Should definitely use a default timer though. That sounds like a good reason. I have just read Nick Moffitt mail: Consider that when you sample, you have a timing value for the fastest and the slowest method given a particular data set. Use this to calculate a threshold, and compare it against the current rendering time. Keep the rendering time for the previous frame as well, and do comparisons between successive frames and comparisons relative to the tests done earlier. You should also consider attack/sustain values for when to switch, so that you don't end up with bang-bang switching in cases where the two methods have similar speeds. Perhaps we should try one of these. I like the idea to store the values of preceding frames, but on the other hand I do not want to take a measure at every frame. Instead of counting the frame we could use a timevalue like Rene proposed, but perhaps not every 10 seconds (too long in my opinion, see some line below). Perhaps I should implement the possibility to make it stick with one rendering mode. The jerking stops for me when I make it not oscillate between update, and flip modes. I think maybe an Exponential back off strategy might work... not too sure. I think we should try a few different things when we meet up in two weeks. Strange that the jerking stops when you disable the decisioning. Perhaps another strategy helps here. Some possible different strategies: - figure out the best rendering method in the first 1-3 seconds, then stick with that. - keep checking to see which is the fastest way. Only change modes at most once every 10 seconds. 3.) naming of the attributes of the DirtySprite: we can change them, but to what? Are the current names already used? Haven't had a chance to research this. Let's look at it in two weeks. Let's talk about them next time we meet at the minisprint. 4.) I don't think we can make it backwards compatible, so it will not replace RenderUpdates (unless the pygame.sprite.Sprite becomes the DirtySprite with dirty=2 as default, but that would be stupid). Cool, that's fine if we can't. btw, Gustavo posted about some code he's done for fast sprite usage: http://renesd.blogspot.com/2007/06/pygame-weekly-mini-sprint-20070620.html#comments http://renesd.blogspot.com/2007/06/pygame-weekly-mini-sprint-20070620.html#comments I think his approach is to break the screen up into tiles of 8x8. Then in the sprite code mark each tile as dirty, if the sprite needs to be updated in those positions. This way there is a constant number of rectangles passed through to the update function every frame - and no over draw. Yes, I stumbled on that some weeks ago and I have already taken a look. I think we could just extend the rect class in pygame. Perhaps we should
Re: [pygame] FastRenderGroup revised (update4)
On 6/29/07, DR0ID [EMAIL PROTECTED] wrote: I think this is only a O(n^2) in worst case otherwise it is less (but I cant tell you what it is). The drawback of that method is, that in the worst case it ends up with a big rect covering the entire screen. Perhaps using Gustavos rect splitting thing would be better (? faster?). At work we use tiled rects for our dirty rect system for software rendering. It's a C++ engine, but the 2 really big wins for a tiling system is that you never need to merge rects (merging is in general O(n^2) unless you maintain some kind of partitioning system, then it can by n log n) and you don't need to manage a pool for allocating/deleting (a fixed size linked list pool can be constant allocation and deletion time, but naive object allocation and deletion from a variable sized heap/pool can be very very slow) We tested a lot of different approaches and tiling was by far the fastest we tried (in C++ anyways). In particular the fastest implementation for us was where each tile has it's own rect, and it does min/max ops on the cells rect to grow it to cover the overlap being the dirty rect and the cell area. So in cases with a fairly small number of objects, you oftenget a perfectly tight fit even though the cells are like 16x8, but it's still all O(n) where n is the number of objects.
