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.
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.
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….