Entry 7 - Third Party Assets. Part 3

A* Pathfinding Pro

Path finding is an important component of artificial intelligence, which allows monsters to run from one point to another bypassing obstacles. There are 2 main approaches to finding a path - mesh-based and grid-based. Unity has its own pretty good mesh-based algorithm. However, such algorithms have several disadvantages. Mesh-based approach is universal and well suited for complex maps, with overlapping layers and bridges, but it is more difficult to adapt to a frequently changing world. In addition, the data structure in this approach is able to operate only the monsters of the same size. If the game has creatures of different sizes, then you need to generate and maintain a data structure for each size. Grid-base algorithms are more predictable and are easier to control. They easily adapt to changes in the map, but handle only one layer (it is difficult to use them for multi-level maps). For these reasons, RPG and strategy games commonly use grid-based algorithms. Therefore, this is exactly the algorithm I wanted for my game, which means that the built in path-finding did not work for me.


The most reted algorithm in the Unity store is A * Pathfinding Pro. Having purchased it, I first studied its code. It turned out that this algorithm does not use memory very efficiently and is poorly suited for large locations. Having contacted the author, I got more accurate data - in order to store a grid for a map of size 1000 by 1000 (the approximate size of locations in my game), the algorithm will need about 400 megabytes of memory. In the end, I developed my own solution for pathfinding. I took the algorithm from the first part and rework it significantly. I am very happy with the result - the data structure is very compact and supports monsters of any size. And it is several times faster than A * Pathfinding Pro. I can’t say that A * Pathfinding Pro is bad. It was simply designed to be as universal and easy to use. My algorithm, although it turned out to be quite optimized, is not very easy to use. However, it allows me to process hundreds of enemies at the same time, and I also have complete freedom in it, since this is my own code.


Screen Frost FX

For the effect of cold, I used the Screen Frost FX asset. This asset offers a nice animated effect of covering the screen with frost and also contains a good sound effect. However, the animation is implemented by simple frame-by-frame playback of individual generated images. To play this effect, it is necessary to keep 64 textures of 512 by 512 pixels each in video memory. Specially for this effect I wrote a small program that analyzed all the frames, and for each pixel determined the graph of its animation and approximated this graph with a function with 4 parameters. To play the animation of this effect, I also needed to write a small shader, which is able to restore the color of each pixel using the 4 function parameters and frame number. However, this allowed me to reduce the number of required textures of size 512 by 512 to 2 - the final color of the effect in one texture and the function parameters for each pixel in another.


Hidroform Ocean System

Hidroform Ocean System is an ocean surface modeling system. I used this effect to create a menu screen. One of the few effects that I used "out of the box". That's what the main menu of the game looks like at the moment. This is a working version, the logo I took from the first part and will change it in the future.

Write a comment

Comments: 2
  • #1

    Conan (Sunday, 20 October 2019 11:29)

    I read a Factorio blog about pathfinding and thought you might find it interesting:


  • #2

    Kemble (Thursday, 24 October 2019 05:13)

    Would like to Alpha/beta test !!