Painters algorithm in Point and click

Problem Statement:

How to render out everything in your world so that when when a character is behind an object then parts of that character are not visible and when you are in front of an object then you are completely visible?

In 3D engines it is sort of easy, the rendering is done with the help of a ZBuffer. And in Libgdx actually everything is rendered with a 3D engine, although you will not immediately notice.

In 2D Engines you need to start laying out how your scene should be drawn with the help of some data structure. Mostly your scene contains a background, a part of that background that is more of a backdrop of your character and some parts of the scene are only in the foreground. The tricky bits are the objects where the character can move in front of or move behind it.

The best way to display my world is to use the good old ‘Painters algorithm’ that basically says. Start with the stuff that’s farthest away, they layer each other part that is closer to your eye. The eye in your game is the camera.

The best way to display my world is to use the good old ‘Painters algorithm’ that basically says. Start with the stuff that’s farthest away, they layer each other part that is closer to your eye. The eye in your game is the camera.

The famous painters algorithm that go way…. way… back. Ancient algorithm actually…

One way to identify the order of painting is with some kind of number. You could say that, the higher the number , the farther it is away from the eye (camera).

    {
        name: "painting"
        usedir: "DIR_BACK"
        zsort: 109
        animations: [
            {
                name: "painting"
                frames: [
                    "painting"
                ]
            }
        ]
        hotspot: ((-30,-22),(31,22))
        pos: (253,178)
        usepos: (0,-86)
    }

The Wimpy tool’s output has a field zsort that allows me to identify a sort of ordering number and also a usedir that I can use to indicate it is part of the backdrop. I think that the property is actually useable for the direction in which the character should face when it is (for example) looking at the painting.

The same I could do with objects that are always show in front of anything else. Those objects can have a usedir with “DIR_FRONT”. For example the next picture shows that the character always is behind of the chandelier, but always in front of the mirror.

Chandelier is always in front and the mirror is always show in the back.

But those objects that are present IN the room. How should these be handled? You could restrict those objects to have a rectangular form so that it is easy to check if the character overlaps on the front part or overlaps on the back part.

But that is restrictive when you have some interest perspective angles on certain items.

When rendering goes bad…. and character seems ‘crushed’ and flattened by the big sofa.

But luckily there is a way to do it…. Let’s show the strategy with two pictures :

First : cast a ray to the polygon that is defined for the ‘big sofa’

Remember the MINIMUM Y-Position for all the intersected points with ray and the polygon.

Second : Cast the same ray to the bottom of the character

Remember the MINIMUM Y-Position of the characters ‘base’ (can be derived from the bounding box)

If the characters Y-Pos is lower than the objects Y-Pos, than the character is in front of the object, otherwise it the character is behind it.

This works really well and of course it is not perfect as the character could stand between the two legs in front of the big sofa. But you could either restrict movement there or make the polygon closed and more convex.

Finally a video where Zsorting and the surrounding ‘hidden’ world that makes it happen.. is shown:

Updates on LibGdx Point and Click engine

Lately I revisited my LibGdx Point and Click engine. I was stuck for a long time because I was not happy of my pathfinding algorithm.

Navmesh Polygon Lines

But after a long investigation I finally found the way to do it. With the help of a Navmesh that a lot of point and click games use. This is actually a flattened area polygon that you are able to edit in an 3D editor like Blender. It is also often referred as a Walkbox.

Top view of the polygon Navmesh in Blender that represents the room
The no move areas are the big sofa,dinnerplate with hamburgers, fireplace, and the dinnertable

But….. I had a lot of things to find out :

  • How to edit the Navmesh?
  • How to subdivide the Navmesh into quads?
  • How to cut some parts out of the Navmesh where the player cannot walk to?

Well there is actually a tool that helped me very much. It’s a tool that was released a while ago that allowed people to make Point and Click games for the Thimbleweed Park engine. See the great tutorial here. It is called Wimpy and it’s hard to find because you will get a lot of hits on ‘Diary of a Wimpy Kid’

What I am getting out of this tool is a list of polygon points that represents the walkbox. If the points are inside another walkbox, than it is assumed to be holes and those are the areas the player cannot walkto (Negative walkboxes).

Those points are then fed into a Javatool called Earcut4J. This tool is very good at creating a set of faces and vertices that make up a polygon. These list of faces and vertices are written into a Wavefront obj file that can be conveniently viewed by Blender as seen in above picture.

The code for an algorithm to do pathfinding on the Navmesh , I found here. It was a great inspiration of how to it as it also had a viewer so I could easily test out the obj file I generated with Earcut4j.

There is also a youtube vid here

That was a lot…. Next time I will talk about ZIndex, ZSort, Zordering or whatever it is called. And all the challenges involved as I still have to fix this….