Something Big: Technical Work

As it turns out, there was a piece of technical work that I had forgotten about: Pathfinding on terrain. This in turn led to other changes in my pipeline–and yay, more work. In the end, though, I managed to use some sweet systems to cut out a lot of manual work.

(no demo)

Pathfinding is a huge part of a game that players often take for granted (myself included), requiring large amounts of  algorithmic code to provide good pathing. Way back in early development I had ironed out a manageable pathfinding system over the course of a week or so. I was using a very early version of Unity’s community project, A* Pathfinding by Aron Granberg, which didn’t have an automatic generation option that I found suitable. Therefore, so far I have only been using the manually placed walkable-node method–formally called the List Node method–which I explain in my older pathfinding blog post (this limitation is also the reason you haven’t been able to walk outside of the walls in past demos). Luckily, the A* Pathfinding project has progressed by leaps and bounds, integrated great automatic generation options, and is currently rated A for Awesome.

So, I started along my pipeline journey by removing all traces of the old pathfinding system and replacing it with the new A* Pro version that I ended up buying, which still had that good ol’ you-just-spent-$100 smell. It was worth it. After a few hours of learning the new system and trying to hook it up to test scenes, I had something working so well that I could even replace the List Node method with automatically generated pathfinding, even in close quarters! Amazing, and such a good time saver.

Then I tried to apply this to the landscape that I was building before this whole pathfinding business began. Unfortunately, I needed to convert the terrain to a mesh to use the pathfinding system (this would have been done later anyway, now that I think about it). The difference between the two technologies is that terrains are a flat plane who’s vertices’ height is altered according to a texture (aptly named a height-map, where the darkness of a pixel indicates a change in height). A mesh on the other hand works just like a normal 3D model, where a set of vertices who’s positions are defined in 3d space form connecting edges between themselves, and thus the polygons that make up the final shape. Thankfully, another system that I was working with earlier, Terrain 4 Mobile, will perform this conversion for me. Unfortunately, the demo that I am using will only perform within with a limited accuracy, capping out at 8100 vertices. You can see the effect this has on the definition of the terrain below. I’m also disappointed that the conversion doesn’t generate an efficient mesh that distributes more vertices to complicated areas (you can see A* doing this in images below). I’ll be on the lookout for a better algorithm, but it will have to do for now.

So, after a significant foray into technical geekiness, I ended up with half of a terrain that you can walk around in. It doesn’t look like much now, but I’m quite happy with it. It’ll be interesting to see the progression that this large piece of terrain takes in the coming week!

For more on the A* Pathfinding system, take a look at the images below. The first shows the automatically generated NavMesh in blue. Notice that it’s a full 3D mesh, and distributes more of its vertices to areas of complexity such as the river while reducing its vertex usage on areas like the unfinished left side of the terrain.

This final pictures shows the NavMesh edges in blue as well as the computed path from the player to the target in green. The target is invisible, but I have it selected. If you look closely along the path you’ll see that the end stretch is perfectly along one of the blue edges. This is a pretty good example showing how it A* works: taking the blue edges to form the initial path of least distance, and then applying some smart modifiers (smoothing and raycasting) to the path to end up with the green one.

Previous – Making Something Big

Next – The Finishing Touches (which is probably the most interesting part, seeing as this has been pretty technical)

This entry was posted in Townsend. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published, nor shared. Entering your website is optional, but good for networking!


Available HTML
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>