Stencyl 3.4.0 is now out. Get it now!

Merrak's Isometric Adventures -- Box2D and Simple Physics

merrak

  • *
  • Posts: 1280
This bit from the blog you linked hits on the very problem I'm having.

Quote
Box2DWeb can create hundreds of 'b2Vec2' objects (to store an X and Y co-ordinate) per frame. This creates loads of work for the garbage collector, and can make games prone to jank as the collector goes about its business cleaning up the thousands of allocations that keep coming. (Scirra Blog)

I already tested the game with simple physics (raycasting and lighting disabled) and it made a noticeable difference. I worked out a new raycast routine, so all I need to do now is implement the second half of it and debug it. The first half of the problem, quickly determining when two lines intersect, is done. You can play with it.

<a href="http://static.stencyl.com/games/36386-0.swf" target="_blank" class="new_win">http://static.stencyl.com/games/36386-0.swf</a>

I posted the code in another thread. If anyone wants to use it, feel free.

Code: [Select]
    // Line segments are
    //  Line 1: (x00, y00) to (u01, v01)
    //  Line 2: (x10, y10) to (u11, v11)
    public static function linesIntersect( x00:Float, y00:Float, u01:Float, v01:Float,
                                           x10:Float, y10:Float, u11:Float, v11:Float ):Bool
    {
        var x01:Float = u01 - x00;
        var y01:Float = v01 - y00;
        var x11:Float = u11 - x10;
        var y11:Float = v11 - y10;

        var d:Float = ( x11 * y01 ) - ( x01 * y11 );

        if ( d == 0 )
            return false;

        var s:Float =      ( 1 / d ) * ( (      ( x00 - x10 ) * y01 ) - ( ( y00 - y10 ) * x01 ) );
        var t:Float = -1 * ( 1 / d ) * ( ( -1 * ( x00 - x10 ) * y11 ) + ( ( y00 - y10 ) * x11 ) );

        return ( s >= 0 && s <= 1 ) && ( t >= 0 && t <= 1 );
    }
(reference)

gurigraphics

  • Posts: 687
I get limit max of 1000 instance of images to browser crash with this example from LIBERADO

Just add this code to your player actor:
   


How do you get 60.000? You wrote that removes when overlapped. So does the limit remain the same?

merrak

  • *
  • Posts: 1280
To know for sure, you'd need to use hxscout or an equivalent tool to see what's going on when the number of instances approaches 1000.

Displaying 1000 images with semi-transparency can be taxing. In the example I wrote up, the theoretical maximum number of tiles that could be displayed at once, without any overlapping, is 88,179. But that's an extreme and very unlikely scenario. When I ran my test to 66,000 repetitions, I never saw the population of tiles exceed 750. That's not an excessive number of images. None of them have transparency.

gurigraphics

  • Posts: 687
Quote
When I ran my test to 66,000 repetitions, I never saw the population of tiles exceed 750. That's not an excessive number of images. None of them have transparency.

Does this code clear the memory?
Code: [Select]
Engine.engine.allActors.clr( a.ID );
Because, if does not exceed 750, why can not you get infinite repetition like my javascript example?

I updated the example.
http://canvas-test.bitballoon.com

layer1 = stencyl game
layer2= spawn particles
layer3= spawn mushroom green
layer4= spawn mushroom blue

P.s: I evolve from Spaghetti Code to multiple layers of Lasagna Code  :D

Edit: I tested , it's the block "remove from parent" that clean the instance images of memory.
I do not know if all browsers and users will have the same limit. But when get to 700add, can start deleting in sequence the first images add on the screen .

« Last Edit: April 05, 2017, 03:30:18 am by gurigraphics »

merrak

  • *
  • Posts: 1280
Engine.engine.allActors.clr( a.ID ) doesn't clear the memory. It's a bit of a hack to get parts of the Stencyl engine to ignore actors. The only use I can think for it is if you need an absurd number of actors in a scene... which is what I was working with :)

I put the Stencyl project file for the tile test as an attachment. There are easier ways to have a high number of overlapping images. The approach I took just lets you do it in a way that preserves the individual images, rather than merging them down onto one large image.

But my issue isn't wasted memory; it's garbage collection. CPU usage is reasonable when the player is just standing still. Moving around triggers all those raycasts. Box2D celebrates a successful raycast with b2vec confetti, and cleaning it all up lags the game.

The problem has gotten even worse since I started playing with more complex level designs. Here's an area I put together last night.


It may be a little hard to tell, but there's a whole network of twisty passages underneath the "main" rooms. I'm planning to use them in the early to mid stages of the game, where you're strong enough to defeat the low level enemies, but not strong enough to confront much else. The passages will give you a way to get around some of the tougher foes. Of course, the passages are really dark and you only have so much fuel for your lamp. So who knows what will be waiting for you in the shadows when the light goes out...  >:(

I was feeling pretty creative and more in the mood to build something with the code and tools I wrote, but the b2vec problem has gotten so out of hand I can't play the new zones. I was going to set the optimization problem aside and just live with it until I got some rooms on my todo list done, but I think I'm going to have to make fixing the code a higher priority.

The funny thing about all this is one of the students in the research methods class I'm teaching this semester chose to research and write her paper on computational complexity. I spent about an hour with her yesterday explaining what Big 'O' notation is and how to use it to analyze algorithms in computational linear algebra. And all this time I neglected to think about how the level load times and light computation times scale up with the size of the areas... particularly, the number of tiles.

Each area has four levels: three regular levels and a "basement" level. I didn't really use the "basement" level for anything until I added a few twisty passages. Adding a single level seems to have vastly exaggerated the problem with b2vecs, which leads me to believe the size of the various Box2D problems scale quadratically (or worse) with the number of tiles. But the solution I worked out scales linearly, so once I get it going I should notice a big improvement in the game's performance.

gurigraphics

  • Posts: 687
If you make a game you really like, surely others will like it.
But liking does not mean "thinking that liking."
Because people say one thing and do another.
What we really liking is what we more occupy time.

The harmony of your graphics and animations leaves no room for criticism.
If you solve the performance, you will be very close to a great game.
But you still have to face five other Boss: gameplay, level design, narrative, music and sounds.
And the last Big Boss: marketing.

That is why it is important do not leave this to the end, and already start gathering the army.
Even for those who say that they have no interest in money,
the Journals of development as you do is something that add value to game.
Because, how was said, the occupy time with something (or engagement) and liking (or desire) go together.

I studied the opposite that you: human sciences. My area is psychology. That's why I'm not very normal. ^^

merrak

  • *
  • Posts: 1280
If you solve the performance, you will be very close to a great game.
But you still have to face five other Boss: gameplay, level design, narrative, music and sounds.
And the last Big Boss: marketing.

That is why it is important do not leave this to the end, and already start gathering the army.

The game's narrative is something I have in the back of my mind, but I haven't fleshed out the details yet. In typical MUD fashion, all objects have descriptions, which can be used to help tell the story. I wrote up a few when I was testing the inventory system. Some of the objects are more telling of what has occurred in the temple, before Marika's arrival, than others. A couple of drafts:



There's not much room for text, which is probably a good thing in the long run. I have to think about what is the most important feature of any object and describe that. One thing I haven't settled on yet is what perspective--the player's, or Marika's, the descriptions should be written in. The latter is more interesting to me, since deciding on what things she'll notice is a good opportunity to build up her character. But this approach can also be restrictive. At the moment I have a mix. Inventory cards (like the two above) are not in the perspective of any characters. Marika can talk to the player through the status bar at the bottom of the screen. But I'm leaning toward moving to entirely third person limited.

MUDs and other text-based adventure games often have text descriptions of rooms and NPCs as well. I probably won't go that far. When would the player have a chance to sit down and study an NPC? While Marika may make the occasional comment when walking into a room, rooms are large enough to show important objects graphically.

I'm taking the novelist's approach to level design--getting something down as a rough draft and revise it later. One thing that often plagues new writers is the idea that the first draft has to be written well. Get your ideas down first, then revise. From the programmer's point of view, this means I need to have good tools to build, analyze, and rewrite levels. I haven't finished my toolset yet, but it's coming along. This is where the b2vec issue has slowed me down.

Speaking of which, I worked out a nice solution to the other half of the raycast problem: Bresenham's Line Algorithm (or rather, a variant that ensures all grid points touched by a line are marked).

I never knew the name of this algorithm until now. If you didn't either, you probably will recognize the use--mapping a line to pixels.


But you can use it to implement tile-based raycasting. Check all the tiles along the highlighted line. If any are walls, then the two endpoints cannot see each other. Coupled with the line intersection algorithm, you can also compute the exact point the line strikes a wall at.

Written in a C-like fashion with only data primitives, there should be no b2vec garbage left behind to collect.

« Last Edit: April 07, 2017, 11:13:02 pm by merrak »

merrak

  • *
  • Posts: 1280
Well, that didn't go according to plan.  :P

It turns out all sorts of little things were relying on Box2D. Stripping out the b2vecs did solve one of the major problems. But somehow the scene loading sequence was relying on collision detection  :o  And that's broken, too. So everything just kinda fell apart.


The root of the problem is that the code just needs a good overhaul. A lot of it was built on top of the original game I wrote for the 10-day Stencyl Jam, so there are band-aid fixes in need of replacement with a permanent solution. There are also some weird choices, like using .csv output from Tiled for levels... why not just use the native Tiled export format?

The results of code refactoring are usually worth it, so that'll be the next step. The first thing I need to do is really think about how to handle collision detection. Since that'll need to be re-written, this is the time to implement major changes.

The next major decision is how to hold the areas in memory. The dual actor model mentioned a couple of days ago is another trouble spot. I realized I can cut the total number of actors significantly by expanding on the graph data structure in the AI tools to hold all the level data.

I may need to put this aside until May, though. The end of the academic year and final exam period is a busy time for me, and I'm finding I don't have much time to sit and concentrate on major projects when I get home for the day. This may be a good opportunity to wrap up some smaller projects I've been meaning to finish up. But, I do want to at least get a road map down so I can hit the ground running when I get back to this project.

merrak

  • *
  • Posts: 1280
13. Roadmap For the (Near) Future


As expected, I didn't have much time to work on this project this week. But I did have some time to think about what all needs to be done.

The root of a lot of the optimization problems is the image actor/draw stack model I've been using since the very beginning. I finally got it to work pretty well, with one exception: loading all those actors. The b2vec problem was obscuring another problem--loading tens of thousands of image actors (with their sprites), trashing them, then reloading them. There are some major redundancies that need to be cleaned up. With the current tileset, there are 2,400 images that should only need to be loaded once. So why have 10,000+ image actors pop in and out of memory?

So revision #1 will be implementing an isometric tile system. For those of you familiar with Tiled, my goal will be to handle tiles the same way it does (where the tile image is larger than the actual tile dimensions). Rather than use image actors for walls and floors, I'll use bitmaps. There are a couple of big advantages to this--

First, I only need two layers for tiles: a background and foreground. Because I've gone out of my way to design levels so that walls aren't obscuring moving actors, I don't need to worry about z-order. The sector system I designed for the camera can handle hiding walls that block the action.


Second, I can generate the bitmaps when the game loads, rather than when the level loads. Or, I can generate the bitmaps at level load and just store them for future use. Either way, I shouldn't have long loading times on every scene change.

Revision #2 will be consolidating all level data structures into a modified version of the AI Tools graph extension. I have so many different classes for storing data that I can hardly keep them all straight. The graph structure is convenient for collision detection, since it provides an easy way to implement "pre-collision detection", something I gave up by dropping Box2D.

Both of these revision projects will take a while to implement, but I ran some preliminary tests that indicate the results will be well worth the investment. I threw together a quick renderer using a simple version of the tile system I have in mind, and was able to generate complex rooms and still keep CPU usage under 1%. In the current version, CPU usage while rendering a room is about 3-4%, and scales linearly with the number of tiles. The new version doesn't scale at all during play... so O(1).

« Last Edit: April 15, 2017, 09:32:35 pm by merrak »