### Merrak's Isometric Adventures -- Drawing Order Algorithms

#### merrak

• Posts: 1835
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: 688
I get limit max of 1000 instance of images to browser crash with this example from LIBERADO

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

#### merrak

• Posts: 1835
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: 688
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

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: 1835
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: 688
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: 1835
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: 1835
Well, that didn't go according to plan.

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    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: 1835
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 »

#### merrak

• Posts: 1835
I recently picked this project up again and began making the required improvements.

First up on the chopping block is reworking the entire way scenes are represented. My current approach is the same as in the original 2015 version of the rendering engine--pretty much keeping to the default actor/scene model Stencyl provides. As the map data is loaded, actors are created. The problem with this timeline is that this is a bad time to be doing optimizations. Optimizations should occur before actors are created.

So I rebuilt the entire map loading routines. This included writing myself a map editor. If you've played around with the demo version, you've probably seen the "command prompt" at the start of the game. One of the commands, "edmap", now actually does something.

What it's showing is a graph representing the entry hall level

The notable part is that this graph is constructed when the game is loaded--not when the scene is loaded--so before any actors are placed. Different colors represent sectors that are visible when the player is inside them. (For instance, if the player is in a green sector, only tiles in the green sector are visible). The graph will let me implement some kind of partitioning scheme.

I looked at using a binary space partitioning tree (like the Doom engine used), but I don't think I'll need something that complicated.

I'm betting I can use a simpler approach that takes advantage of the "overlapping triangle phenomenon":

but do a better job of it than I'm currently doing, since I can work out redundant actors before the scene is loaded. Most importantly, since all computations will be performed on the graph, I can go back to Box2D for physics (if I want to, that is), since I won't need raycasting. But I don't plan to go back to Box2D. Rather, I'll write my own collision handling routines. I already wrote my own for z-direction collisions (checks for falling to the floor, stairs, etc.), and it works pretty well.

In the meantime, I'm also playing around with a new title screen. I haven't done much digital painting in a while, so I'm pretty rusty. I sketched some line art, which took me way too long.

I need to think of a monster to put in the frame on the right. The left side will stay mostly blank, since that's where the menu buttons and information will go.

#### merrak

• Posts: 1835
I would've liked to have more to show for my efforts over the past couple of days, but I now have a proper partitioning graph.

This is the graph for the same scene as in the previous post--which is the area the player starts in. Each node represents a tile coordinate (row, col, level) in the scene, and connections represent tiles which will be drawn on top of each other. It's an important part of the solution to the clipping problem.

The other part of the solution is how to interpret the graph and translate it into an actual rendering of a room. What I've worked out so far is a back-and-forth approach. Wall segments can be divided into triangles. Starting from the front-most node, I work my way back, computing which triangle segments of each tile are visible. Once every triangle has been filled, I now know the first tile to render and how much of it to draw. I can then fill in the triangles from back to front.

So I'm hoping that taking advantage of the isometric perspective will give me just enough efficiency to render a scene in a full 60 FPS.  At the very least, this approach pushes a lot of the computation time to when the program is first loading, when the player is likely to be most patient.

I'm very glad I took the time to write this little visualization tool. Trying to debug the graph generation and rendering at the same time would've been a mammoth task. Now that I have half the problem solved and verified, it'll be easier to focus on drawing the actual room.

#### merrak

• Posts: 1835
Sketch Saturday

I began work on the scene rendering algorithms, which will be a significant chore. But since I was feeling creative, I took some time to sketch a few concept drawings for the game. In addition to helping my sanity, it'd also help to stay focused on what the end product should be. It's easy to lose sight of the big picture while working on these low-level code routines.

So, a couple of sketches!

For today, I thought of a monster for the opening scene. Sadly, I lost track of time and never got something put together for the mechanics jam. But I suppose that's okay, since I didn't have a spectacular idea and everyone else came up with much more interesting things than I did. However, the joint rope did give me the idea for a mechanical snake.

Putting that kind of monster in the game would be a real challenge. I'd have to work around one of the limits of the current rendering engine--every tile and actor must fit inside the same sized box. I could break larger monsters up into pieces--hence the appeal of the snake.

I also drew a new pose for Marika, since the current one made it look like she was about to stumble into the abyss. Art is not my strong suit, and I just noticed I messed up the perspective in the stair well. Oops.

I think the snake monster would be a great addition to the game as a final boss. Of course, the real thing wouldn't have a big "on/off" switch on its back.

#### merrak

• Posts: 1835
If you remember the graph from a few posts prior, here's what it looks like as an actual room: (I left a pre-debugged room screenshot to fill in the array )

But... how is this different than what I had before? The screenshots won't show it, but these images don't exist in any scene. No actors were used in their construction, and their CPU footprint is essentially zero. These will let me cut down the number of actors in a scene two entire orders of magnitude, from thousands to dozens.

At one point early in this thread (so... two years ago) I mentioned the roots of the "image actor" model were based off of an idea presented by captaincomic. This is the first real departure from that model. Although for movable actors (player, enemies, etc), I'll still use it.

If all works according to plan, in addition to improved CPU usage, this model will support several other new features, including:

* Multi-color lighting
* Much easier to implement new tiles in the game. I'm still using the tileset from the original Temple of Idosra, with the images replaced with multi-color ones.
* Blend modes and other features provided by the Image API

In fact, these images were put together using the same functions the Image API calls. So, in theory, everything could be done in design mode using blocks. I think the number of blocks would exceed what is practical to manage in design mode, though.

So what's next? I need to take these images (well, the three good ones) and mix them together. All this is still taking place at game load, not scene load. So that means I don't have Box2D and its built-in raycasting routines (which I'm trying to avoid anyway). Instead, I'll use my own  raycasting routines built off of the variation of Bresenham's Line Algorithm I put together last month.

« Last Edit: May 24, 2017, 11:27:17 pm by merrak »

#### mdotedot

• Posts: 1369
Hey Merrak,

Great information as always.

Since I’m trying to follow what you are doing I kind of am lost what the use of the Bresenham's Line Algorithm is.
Am I correct that you use it for line of sight = what to draw  and what face of an object you need to draw?

Or is it for collision detection ?

Or both ?

I have used the algorithm for pathfinding, not knowing what it was called
Hanging out in the Chat:  http://www.stencyl.com/chat/

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.

#### merrak

• Posts: 1835
I only recently learned this was called Bresenham's Line Algorithm  It's funny how many little histories get lost over time. I'm using it for line of sight problems... although for my purposes it's only part of the solution.

In a purely tile-based game (some of those old RPGs like Exile, Vampyr, Talisman of Invocation, ...), this algorithm is all you need (although I don't know what those games actually used).

Can Tile A see Tile B? Just use Bresenham to highlight all the tiles from A to B and see if any are walls.

It's harder to figure out if Tile C can see D or E. The red box is a box that would be highlighted by Bresenham for either path, but further investigation would be needed to see if the rotated tile actually lies on either line. There's a line segment intersection demo at the very top of Page 12 of this thread. This second problem is what I need that code for.

So, here's the goal. Determine if line segment CD or CE intersects with any line segment making up any collision box. I don't want to loop through all the line segments in the entire scene because in a large scene there could easily be thousands. Instead, I use Bresenham to see which line segments are worth checking out.