Porting to Unity IV: Pathfinding


Fairly straightforward work this week, porting pathfinding code from C++ to C#. The first two ports were of the basic low-level pathfinding functionality, namely A* on a grid (SearchGrid) and a graph (SearchGraph). This is the code shown in this post

The other ports were of the higher level wrappers that utilize both of the above. There’s a “basic” wrapper and an “overworld” wrapper. The basic wrapper is used as a reference to evaluate other wrappers and uses a dense grid, so it takes the longest but it would return the best results.

The overworld wrapper is the one in this post.

The performance currently, without any sort of profiling, is about 1ms per overworld path, in the Unity Editor where I’m working all the time. Compared to 0.22ms for Release/C++ and 3.37ms for Debug/C++ it’s not bad at all!

Porting to Unity III: Caching 2D Arrays

So far, I’ve ported the biome map, resource map, city basics, faction generation, and a few more things. They all pale to the effort that I’ve put for a seemingly simple process:

“Ok, we generated a large 2d array of data after a lot of calculations, now how do we save and load it from disk?”

There are a lot of issues, pitfalls, etc that resulted from this question and associated actions, that have lasted for almost 2 weeks. So:

How do we represent Array2D?

Question number one. Enchanted by the simplicity of SomeType[,] , I started using that. There are a few issues:

  • Serializers have issues with multidimensional arrays, there’s a zoo of serialization options out there, each with their own little problems and idiosyncracies. Ugh
  • Indexing is [y,x] like Matlab (and I presume other things). I can understand why, but for my computer graphics brain and muscle-memory, this is a no-no (I’ve been always using [x,y] and [width,height] ) and could be a cause for a billion bugs.
  • Cannot cast to 1D array, so operations applicable to 1D arrays are not applicable here. This would mean re-writing code for 2D case ( e.g. max element in array, max value in array, etc etc)

So, I decided to nip it in the bud early and use my own class, which is a simple wrapper of 1d array, and thus can play along with everything. Hooray. For access it uses [x,y] or [Vector2Int].

Array2D for structs and classes

Yet another potential cause with structs or classes. Everybody keeps hammering “use structs for immutable types” and for a good reason. For my simple Array2D wrapper it’s impossible to do the following with a struct Foo:

var foo = Array2D<Foo>(2,2); foo[0,1].someField = 32; // Forget about it.

What we’ve done here with foo[0,1] is return a copy of the element and set .someField to that copy, that will be immediately destroyed. We can’t set just someField, we need to replace the entire struct, because we can’t return references to structs in Unity C#. So, the best alternative is to disable this altogether otherwise hello insidious bugs. We can add an extension method for the array ( e.g. at( int x, int y) ) that restricts the type to be a class and returns a reference.

How do we serialize Array2D?

That’s easy, right? Use Unity facilities, add a few [Serializable] attributes and we’re good to go. Well, not so easy. What-a-waste. So using standard serialization facilities, we’re serializing every object individually, and that contains a crapload of redundancies. So, a simple 512×512 map of uint32 takes 12 megabytes instead of 1. Lovely. The “Biome” map class that uses enums (it used to be bitfields) now takes 60 megabytes. No thanks. I went on a journey to find a nice way to do cheap serialization for at least these use-cases, without using some XYZ serialization library that will be broken with the next Unity update or will go unsupported, or has those other weird limitations. Therefore I wrote some code to be able to serialize classes into a stream of bytes, this being a pain on its own. Error prone? Yes, but at least testable. Fast? Oh yes. Space-efficient? Oh yes. Using the binary serializer, I jumped from 60Mb down to 1MB, and the serialize/deserialize performance improved by 30x. So, back to reasonable-land again. The only “issue” Is that I have to implement an interface for every new type that can be used in an Array2D that’s going to be cached, so no big deal really.

Random: System or Unity

So this is the last thorn, I started using Unity’s as it’s usable, but there’s only a single one so that’s not future proof, as I’d like to have a bit more control (maybe multiple rngs, alternate algorithm, etc). So, I started extending System.Random with convenience functions. So far so good, but I ended up with a several-hour bughunt where I’d create a copy of the rng, replace the original during a caching operation, and then using the (by now unique) copy, leading to different behaviour with seemingly same parameters. Takeaway: don’t make copies of the rng, get refs to it.

Next TODO

Next in the port party is Pathfinding, Movement, Territory systems and some visualizations to make sure everything is working as expected