Merrak's Isometric Adventures -- Dimetric Dilemna

@Merrak You want me to make your character in Blender?  I'll do it for free. Just hit me with the details.

I'v attached an image so you can see what kind of quality to expect.

Thanks! I appreciate the offer

I have a lot of particular requirements and would need a lot of frames (~40 animation states: walk, run, climb, hang, jump, etc.)--more than I would feel comfortable asking someone to do for free. I'm not really in the position to be able to offer to return the favor, either... at least for now. Once I get past the web-based game I had in mind, my vision for the full desktop game includes fluid animation--the style found in cinematic platformers. In fact, the earlier Thief of Vallas was of the style of Prince of Persia, but never released.

Your images look really good. I bookmarked your post "How the Undying City Was Made" to come back to later. At some point I need to learn to use Blender. I have MakeHuman characters and mocap files from CMU. I've never sat down and made a serious attempt to learn Blender, since the engine is a higher priority right now.

Something else I need to settle on is Marika's design. I've gone back and forth between a few drawings, generally following variations in my plans once I get through my current stage of development. Some of the older designs make her look too much like Link. I'm pretty happy with the latest version that was posted... but if I'm going to redo the 6-color Temple of Idosra, then I should make her a more cyan costume that would carry over to that color scheme.

How to Implement the Topological Sort. I now have a working map renderer. Hooray!  I don't have actors in it yet, so that is step 2. I'm confident the "topological sort" method is the ideal solution to my draw order problem, so I thought I'd share how to implement it.

As you'll see, there are some blanks I won't be able to fill in, since it comes down to how you implement actors, tiles, etc.

What is Advantage/Disadvantage to This Method? I can think of three ways to create an isometric scene. The first, and simplest, is to just place everything by hand.

The second I'll call the "origin method", and is the method discussed since the very first page in this thread. Every actor and tile is represented in 3D space by a single point (origin, located at (gx,gy,gz) in 3D space). The distance this point is from the viewer is (gx+gy+gz). One limitation to this method is that it only works reliably if every tile and actor is the same size. I mentioned this in a recant post, but the full discussion about this problem is here: (link). The workaround is to break larger structures up into tile-sized chunks--not hard to do for static structures like walls and buildings. Breaking moving actor sprites into tile-sized chunks is a manageable problem, but not a fun one to solve. The larger issue, though, is having a lot of tiles along with the performance issues that come with it.

Topological sort will allow you to solve the drawing order problem with arbitrarily sized structures. The disadvantage is that it is the hardest to implement.

What is Topological Sort? I wrote a brief summary a few posts ago, but the Wikipedia Article is more thorough. Since it's a graph-based solution, it's a perfect application of the AI Tools Extension.

How I Implemented It... Let's sort some structures. It starts out simple enough. I used the AI Tools' graph, but I don't see why you couldn't use maps or arrays.

Code: [Select]

Initialization Stage
1. Create a graph G.
2. For every structure S create a node N and add it to the graph G.
3. For every node N1
       For every node N2
           If N1 and N2 overlap*
               If N1 is in front of* N2 then create a (directed) edge from N2 to N1
               Else if N2 is in front of* N1 then create a (directed) edge from N1 to N2

The asterisk* is a function I'll get to later. Once the graph is built, sorting is easy. I implemented the "Depth First Search" approach in the Wikipedia article and had no issues with it. I might replace it later if I can find a faster method, but the Wikipedia version did the job.

Now for the hard part. How to detect if two objects overlap? I'll mention how I did it, but this is the part that comes down to the specifics of how objects are represented in your project.

In my game, walls have two sets of vertices: Grid vertices (3D space coordinates), screen vertices (2D space), and AABB vertices (2D space). Example: The AABB vertices and grid vertices are marked in green, and screen vertices in red.

Screen vertices are irrelevant for overlap detection, but needed to compute where on the screen to draw the image. AABB vertices are essentially the screen coordinates of the grid vertices and are used for shadow projections.

To determine if two walls overlap, compute the AABB vertices and construct a polygon for each wall. Then compute the intersection of the two polygons. There's a very long discussion about how I implemented this part toward the end of page 13 that ultimately came down to implementing Sutherland-Hodgman Algorithm.

If there is an intersection polygon then it has to be tested.

Code: [Select]

Intersection Test
For each vertex V on the intersection polygon
    Project V to (u1,u2,u3), the grid coordinates of the vertex on wall W1
    Project V to (v1,v2,v3), the grid coordinates of the vertex on wall W2
    Compute d1 = u1 + u2 + u3
    Compute d2 = v1 + v2 + v3
    If d1 and d2 are "close" then continue. ("close" will depend on the scale of your coordinates)
    If d1 > d2 then wall W1 is closer than wall W2
    If d1 < d2 then wall W2 is closer than wall W1

The projections use the same vector algebra functions that I wrote for the shadow projections. They were a pain to debug and involved a lot of linear algebra--so if you go for this kind of approach then this may be the step that consumes the most of your time. I shared the formulas I used here: (link). If you read the document, though, you'd see they're specific to my particular game.

Results. Despite the difficulties and effort that went into figuring all this stuff out, I'm happy with the results. The entire "Idosra Entry Hall" loads in about one second.

It might even take less than a second. The way I implemented the loading progress bar will make any scene take at least 60 frames to load. But compare to the older engine, which took almost a full minute to load this map. One second includes: Creating the walls, sorting the walls, casting shadows, rendering the walls. It doesn't include moving actors, though. When I get to that point, the entire plan I just wrote about may need modifications.

Here's the room south of the ballroom. The sun fully illuminates the ballroom and its light spills into this room.

For the first time I walked through all twelve sectors and found not a single rendering error. 

Next Steps. A lot of the wall graphics need to be redone, but I'm thinking of not bothering with the 16x32 scale full-color images. The more I think about it, the more I like my current plan of: Redoing Temple of Idosra and making a sequel with the 6-color graphics. The game I outlined a couple of months ago as "Temple of Idosra" will be renamed and become part of the full desktop game. I like the idea of using a simpler web-based game to explore ideas and develop a storyline. The stakes are much lower in a simpler game, which will make it easier to experiment with new ideas. So here is the six-color* heroine.

* Actually 8 colors, because I wanted to add a shade of red to the palette. My palette has a blue scale and an orange scale.

Wow a big step forward.

As always an amazing read. You should make this into one (or more) of your lectures at your dayjob!

" The entire "Idosra Entry Hall" loads in about one second."
Very cool as I indeed recall it taking way much more as you pointed out!

I'm always a little bit hesitant to point my students to anything I do online. I don't go out of my way to keep them separate either, though--but I do worry that if everything I do revolved around my teaching then I may burn out. I don't want that to happen because I'm fortunate to have a job in which I feel I'm doing something worthwhile. I take on a lot of hours (21sh this semester) because I believe in what I'm doing... but I also need time for myself and my own interests

But I am teaching Calculus III this semester and Wednesday is "Orthogonal Projection Day"... so getting a bit into the math behind this code. I might work in some of what I've done, and I usually share more with the math/math-ed majors since I get to know them pretty well. Most of the math better fits into Linear Algebra, though. That's another one of my usual courses, but it doesn't run this year.

I was happy to see the load time vastly improved, but I do have another problem... 2GB RAM consumption I think I know how to fix that, though. The bigger issue now is that I'm at another crossroads--how do I want to implement physics? I can go back to Box2D now if I want, because the problem I was having with it (too many tile actors) is now a non-issue. I'm leaning away from it, though... but then I need to do some serious planning so I don't end up writing then re-writing code so many times.

Collision Conundrum. Now that the map renderer is working, I recently turned my attention to the actor renderer. This should be an easier problem to solve, but there's a catch. I took out the original physics engine (which relied on Box2D). Because actor drawing order depends on collision resolution, the two systems have to work together. This means I need a working physics engine before I can complete the actor renderer.

Implementing Physics and Collisions. This problem has been tackled in a variety of ways. In older versions of the engine (2015, 2016), each actor was represented by two actors: a "peg" actor and an "image" actor. The "peg" actors existed on a 2D plane and were the actual actors as far as movement, hit detection, collision, etc., were concerned. The location of the "image" was computed based on the location of the "peg".

I wrote about using this approach way back in 2015 and it is pretty reliable. One benefit is that you can use Stencyl's existing options, Box2D or simple physics, without writing additional code. The drawback for me is that my maps don't exist on a 2D plane. They're split between multiple 2D planes, each representing one floor in a taller structure. When an actor changes floor, they are "teleported" from one region on the 2D scene to another. This complicates collision detection when the player is moving up or down as well as horizontally... for example, jumping off of ledge.

I think I can modify this solution, but using an approach closer to what rob1221 described for Isotiles. Rather than use collision shapes, I'll check for collisions using the graph that is constructed when the map is loaded.

Checking collisions on the graph solves a variety of problems. I don't need separate "image actors" for one. Also, the graph has all the necessary data needed for 3D collisions if I make the following assumptions:

* The collision solid for any moving actor is a cylinder (not necessarily of the same height, though)
* Every actor is represented by a single point.

These are the parameters I'm already used to, so I don't expect needing to change much of the code that depends on physics (such as enemy pathfinding, projectile collisions, etc.)

The difficulties, though, include handling drawing order resolution and writing my own collision detection system. The latter I'm working on, but I have a solution drawn up for drawing order resolution.

Resolving Actor-* Drawing Order. Because moving actors are presented by a single point, resolving the draw order between two actors or an actor and a wall is simple. Actor-actor drawing order can be resolved using the coordinate sum method already implemented. If actor 1 is located at (ux,uy,uz) and actor 2 at (vx,vy,vz), then compare the sum (ux+uy+uz) to (vx+vy+vz). The higher sum corresponds to the actor closest to the screen.

Resolving actor-wall drawing order isn't much more complicated. Every wall has a normal vector N, so I compute the dot product of the actor's position with N as well as the dot product of a vertex on the wall (any of them will do) and N. If the dot product for the actor is greater then the actor is in front of the wall.

The drawback of representing actors with a single point is that I can't have actors that are larger than one tile. This shouldn't break actor-wall resolution, but actors of arbitrary size will complicate actor-actor resolution. I could throw actors into the wall graph used for topological sort, but I'm not sure how efficient that will be. In any case, it doesn't matter because I simply don't need actors larger than one tile. The only exception would be the serpent I was planning for the original game--but that would require special coding anyway, and I think breaking it up into tile-sized chunks would be simple enough.

Doodling. While I've been researching collision systems, I took some time to sketch some mock-ups of the interface for the revised Temple of Idosra.

One of the first things I needed was a new title screen that better reflected the direction I'm planning to take the storyline. Current screen:

The original game had no real player-object interaction. While I want to keep to the spirit of the original game, I think I can also update it to better fit in with the design of the current engine. For one, I liked the card system I implemented for player-object interactions. The player's "inventory" (not limited to tangible objects) is represented by a deck of cards. The first card is the player character itself.

For reference, this was the amber-color version: (link)

I think I can improve the decor and the buttons, but I like the general layout. Cards are 72x72--large enough to draw an icon that zooms in on an important detail. I like the font. The original font was the NES font. I think I need a brighter color, though (note that these are 1x images, but the game is rendered in 2x resolution).

The original game was one big 113-room level. I still like the idea of leaving the game mostly open, but I also wanted to have distinct chapters or acts. I came up with the idea of displaying a short title screen whenever the player completes a significant objective.

This way I can still keep the game's map open, but also still use chapter divisions to manage the storyline (rather, put in a storyline, since the original game had none). I don't plan to give the game a narrator, but I do like the third person POV. This decision allows me to let Marika "talk" to the player when necessary. Plus, despite the RPG elements of the game, there's only one player character. First person POV feels more appropriate for either a game where you can make your own character (or choose from an extensive list), or a game like Doom where the protagonist is so generic that it's easy for just about anyone to put themselves in the player character's place.

2.1D Physics. After a few days of research and sketching ideas, I have an outline of my physics system nailed down. It's actually very similar to an old experiment I wrote about at the very beginning of this journal...  Ancient History

What I've outlined is as follows-- There are two collision checks: 2D collisions on the XY plane and 1D collision parallel to the Z axis. This isn't anything new. In fact, it's the same basic system that I already have. The main difference between then and now is that I'm not going to use Box2D for the XY collisions. Instead, I'm going to write my own system.

What is 2.1D Physics? I looked at either writing a 3D physics engine or using an existing library. But the more I thought about it, the more I realized I simply didn't need it. 3D is too resource intensive for what I need. Furthermore, I don't need full 3D since I can assume all actors and walls are orthogonal to the XY plane.

That assumption allows me to check Z-based collisions separately from XY. For XY collisions, Box2D is too much (Box2D's gravity simulation, for instance, is useless). But I do need more than Stencyl's "simple physics" mode provides.

The two main components of the physics engine are collision detection and collision resolution.

Collision Detection is, I think, underappreciated. Consider an example where you have ten actors in a scene and want to detect when one hits another. How do you code that from scratch? What you don't want to do is, for each ten actors, loop through the other nine and check their distances from each other. The problem with this approach is that the number of checks scales quadratically with the number of actors. With 10 actors in the scene, 90 checks are required. With 100 actors in the scene, 9900 checks are required. With 1000 actors in the scene, 999,000 checks are required.

Box2D has a spatial partitioning scheme in place so that it can eliminate a lot of unnecessary collision checks. If I'm going to write my own physics engine, I'll need such a scheme for myself.

In my case, I have two options. One, I can use the map graph. This would give me a tile-based solution. Two, I could build a new graph using walls. (Note: floors are "walls" as far as the rendering engine is concerned). Either system lets me partition the map.

What I need to know is when an actor moves from one partition to another. The nice thing about "Option Two" is that I have a ready-made and optimized solution to the point-in-polygon problem. Whenever an actor's position is changed, I test if it is still in its current partition. If it isn't, I loop through the neighbors and test if the actor is in (or near) any of the neighboring partitions. Note that an actor can be contained in multiple partitions simultaneously. Considering the small number of moving actors, the cost is trivial. I have the math worked out for both the "point in polygon" and "point near polygon" problem.

Now that I can maintain a list of actors inside a partition, I know I only need to check for collisions between actors within the same partition.

There's an optimization problem here. If the partitions are too big, then their populations could be very large, increasing the cost of checking collisions within a partition. On the other hand, if they are too small, more CPU time is spent moving actors between partitions.

Fortunately, for the number of actors I'm working with, I don't think it matters. In fact, I probably could get away with the entire map being one large partition, because the number of active moving actors at any given time will probably rarely exceed single digits. But there are some rendering-related reasons to invest in time choosing between "Option One" and "Option Two", so I might as well implement one of those. (This is why I said the physics engine and actor rendering engine go hand-in-hand).

Collision Resolution... To be continued, I suppose. I need to finalize detection before moving on the resolution. Luckily, I have solutions corresponding to both options mentioned above already drawn up, so it's just a matter of getting that first part done.

Physics Update. During the course of writing the basis for the physics engine I thought of a way I could work Box2D into my plans. So far I've written a few hundred lines of code, so I'd hate to abandon it. Then again, I really don't want to spend the next few weeks debugging this when I can make a tested solution work. One thing I've learned with the rendering engine is that these things always take longer than they seem at first. Did you know I scheduled one week to write the rendering engine? I think that was a bit ambitious

But the real reason I've started leaning back toward Box2D is this room, from the original game:

Temple of Idosra uses joints, of all things. The frustrating thing is I don't think I'm really going to have a good answer for the "to Box2D or not?" question without investing a lot of time. But trying Box2D to handle the "2" in the "2.1D Physics Engine" and realizing it won't work would take less time than writing my own 2D physics engine and realizing it won't work.

So I'll probably put my partially written 2D physics code aside for now. Besides, nothing is wasted if you learn something from it  But even if the code doesn't find a home in Idosra, I can always use it somewhere else.

Idosra Inspirations. From time to time I've mentioned the MUD-like influences on this game. (For those who don't know, MUDs are text-based MMORPGs that were popular in the 90's and early 00's). I ran my own MUD for a couple of years. It reached the peak of its popularity in the months leading up to the 2003 Iraq conflict, and an appreciable fraction of the players were military personnel (mainly, but not entirely, USA military).

The MUD had some quirky features, including areas that had platforming challenges. If you've played text-based games and are wondering how in the world that worked, well, it actually kinda did. I (being the coder) created a suite of room types that included closing walls (think Indiana Jones and the Temple of Doom), spike pits, cliffs, river currents and conveyor belts, and walls that shot fireballs at you to name a few. I built a large area that included all these traps and it was one of the more popular ones. Clever area builders made good use of these features as well.

Of course, these text-based action elements had significant limitations. So fast-forward thirteen years: Temple of Idosra took a lot of its action and platforming elements from that MUD, particularly the fireball walls and spike traps. I think that's one reason why this project has held my interest for so long--it's a new way to bring old ideas to life.

Physics Update 2. A few days later and now I'm leaning back toward scrapping Box2D. I fully expect I'm going to go back and forth a few more times on this. The problem is that there is no good solution without redoing a lot of code.

So what's the mess? Long story short, back in Summer 2016 I wrote the previous version of the renderer. But it was just that--the renderer. It had high CPU usage, so I set it aside to come back to later. That "later" was the Stencyl Jam 16. Since the summer version of the renderer had resource issues, I threw together a simple version that used the same ideas for z-axis management, but had no lighting or any other features. This was the "6-color" renderer.

After that, I also threw together a quick physics system. Since I only had 10 days for everything, I just went with whatever design worked. The problem is that when I started the post-jam rewrite of Vallas Engine, I merged the physics code with the summer version of the renderer. Since then I've been building on that physics system.

Simply taking it out is easier said than done. If you've poked around in the Stencyl engine, then imagine trying to completely remove Box2D from it. That would be a lengthy chore--as would be removing my 2-day physics engine from Vallas.

I thought I could get around it, but I think I'd be much better off taking the time to strip it out and write a new physics engine. Hence I'm leaning back to my original plan again. It's going to take a lot of work, but so did the new renderer and I think the result was worth it.

The disappointing thing, though, is that I thought I was close to done and ready to make the redo of Temple of Idosra. I've got a lot more work to do just to get to the point that the engine can support the second half of "DrawStack" (rendering moving actors). So... time to get to work. 

Instruction Booklet. I needed a bit of a break from coding, so I started working on a manual to attach to the redo of Temple of Idosra. It's a great way to procrastinate, because I can pretend I'm being productive on this project. But I don't think it's a bad thing. I took some of my line art sketches and made a manual reminiscent of a Game Boy cartridge manual. I still have my original Game Boy along with some of the manuals, so I had a nice reference for the look and feel of them.

So that there's something to look at in this post, here are some drafts of the manual pages.

Physics Breakthrough. After more than a week with wrestling options, I think I finally got a handle on what to do with physics. I can modify the usual solution to the circle-line collision problem.

Distance Checking Problem. The distance checking scheme (call it "simple" distance collision checking) basically works like this:

Code: [Select]

For every body A
    For every body B
        If distance from A to B is less than some threshold then the bodies collided
Simple distance collision checking worst case scenario (all bodies are moving) scales quadratically with the number of bodies: O(n²), so is not a good solution for a large number of bodies. In a single Idosra map there are a lot of bodies: walls, moving actors, and floors to name a few. But I only need to check against bodies within the node the player occupies or will move into.

There aren't many bodies in any one node. So even the worst case scenario would still produce a small number of checks.

Line-Circle Collision Problem. So... how to implement it? It's not quite as simple as checking 'distance from A to B' because the moving actors have a collision radius. But here's a sketch of the idea behind circle-line collision. In this example, the player moving through a sector with a wall and a pit.

The player currently occupies position g and will move along vector v1. Vector v2 is a vector parallel to v1 and with length (collision radius). Using vectors v1 and v2, it's easy to check if the player if the player will collide with a wall or walk near a wall. The hard part is checking if the player "brushes up against" the wall. (See illustration below)

The solution to this problem is well known. But the solution I'm currently working on takes a different route. I'm going to call it "orthogonal box" for now, although that's a bit of a misnomer. The name comes from the two lines that are highlighted: one representing the wall and the other a vector orthogonal to v1. A solution to the line-line intersection problem is already implemented.

Details to follow, but I think the solution is promising. A top-down view of a human fits better into a rectangle than a circle, so I think the shape is more appropriate. The reason I went with circles when I was using Box2D was so the actor would slide against the wall when moved into the wall at a diagonal (makes it easier to get into tight corridors). But I also have a solution to that problem in mind.

There are several other things to think about. If the player turns, they might be pushed further from the wall. In the long run, I'm inclined to keep that behavior if I can. After all, if you were standing in a tight corridor, up against the wall, and decided to turn--you would have to step a bit back from the wall. I just need the appropriate animations to play.

A simpler solution would be to keep the collision box aligned with the coordinate axes. This would probably work for the Temple of Idosra remake since the actors are so small.

A third solution would be to use the "orthogonal box" problem as a sub-step in an implementation of the circle-line collision problem. In the illustration below, an "orthogonal box" collides with a wall. Two of the sides of the box intersect with the wall, and their intersection points are calculated.

To get a circle, consider the line segment defined by the two intersection points. I compute the point on the line segment that is closest to g. If the distance d between the closest point and g is less than the radius, then I push g along a vector of length (radius-d) along the opposite direction of v1.

Great job, Merrak! This looks great!

Idosra Improvements. My physics system is finally starting to take shape. I ended up going with a hybrid of "orthogonal box" and line-circle, using the "orthogonal box" method as a pre-collision check and the traditional line-circle algorithm for the final check and collision response calculation. It didn't seem much more difficult than the other methods. This approach does have the advantage of being easily adaptable to a sector-style map system (as opposed to tile-based, as I currently have).

I realized, though, that there is another advantage to this physics system over Box2D: detecting when the player is near an edge. There was an older version of "Thief of Vallas" that was a 2D platformer of the style of Prince of Persia. It was plagued by a variety of problems, one of which was detecting when the player was near an edge.

If you've played the original Prince of Persia then you may have noticed the game helps you make difficult jumps. If you are running toward an edge and are near it when you press 'jump', then the player character will hold off jumping until he's at the edge. This makes it a lot easier to clear difficult jumps.

My first attempt to program this involved having a separate "feeler" actor attached to the player. Did it work? If you guessed "not very well", then you're correct! 

Isometric platforming is tricky, so I would like to have Marika "help" the player in small ways (such as being smarter about jumping). One thing I don't want is successful jumping to rely on split-second timing. There are some jumps in the original game that are hard to make (although most of them aren't necessary to win).

The way collision detection is set up, I can easily detect when a player is near an edge. If it's obvious the player is trying to make a run-jump, then I can hold off on the actual jump until the last moment.

Speaking of Jumps... I recently played through the original game. This room is terrible.

Bonus points if you can figure out its geometry.

Great job, Merrak! This looks great!

Thanks!

I'm often reminded of the article about Link's movement in Zelda 1, how it would automatically adjust him to move on the half-tile grid so that you would never unexpectedly collide with either side when passing through a 1-tile-wide area. It's good to see these things taken under consideration.

I'm often reminded of the article about Link's movement in Zelda 1, how it would automatically adjust him to move on the half-tile grid so that you would never unexpectedly collide with either side when passing through a 1-tile-wide area. It's good to see these things taken under consideration.

Was it this one? That's interesting. I never noticed the game did that before (granted, I never played the original Zelda much). My player character isn't limited to a half-tile grid, but the enemies are aligned to the tile grid when they're walking. That makes it easier to run A* calculations. The original game didn't use pathfinding at all, and in rooms with concave polygon floors, the enemies just walk out of the wall.

Yes, that's the one.

Speaking of Jumps... I recently played through the original game. This room is terrible.

Bonus points if you can figure out its geometry.

Thought you might be interested to know Terry Cavanagh made a really great puzzle game based around that: trying to figure out confusing ambiguous isometric geometry. http://terrycavanaghgames.com/nayasquest/

And whoa that's super interesting about Zelda.