Reflection/Serialisation

One feature that C++ does not provide out of the box is the ability to get information about a class at runtime. We might want to know how many members it has, their names and types, and where they are stored in memory. Known as reflection, this would be very useful, for example, when initialising objects from a file.

I absolutely need to have the game data stored outside the program. Possibly external tools will be used to edit it. I also need to be able to change it while the game is running. As a minimum I need serialisation if not a full reflection system.

While there are a lot of reflection and serialisation systems for C++, none of them have exactly the feature set that I need, which is:

• Serialisation/Deserialisation to text or binary files.
• Non-intrusive code (i.e. I don’t have to change the classes to support serialisation).
• Human readable/editable file format.
• Tolerance to missing/extra data.

And most are a lot more complicated than I would have a use for.

So I wrote something that looks a bit like Boost serialisation but without all the complicated bits, and uses JSON as a file format. Rather than having version numbers (not human-friendly) I match data when loading based on the name.

It’s not reflection, yet, but it’s enough to get started.

Pathfinding

Having created a maze, I knew at some point I would need a way to navigate around it. This might be as an aid to player movement, or part of the AI system. In any case it’s a nice self-contained problem to solve as the next step in development.

The star of all search algorithms in game programming is A*. It finds the shortest path through a network of nodes, and does so in a quite efficient manner (especially if the path is very simple). So this looks like the place to start. There is one issue to resolve first though.

Essentially, the map is not really a network of nodes. It’s actually made up of connected rectangular areas forming corridors and rooms. I could put a node on every grid square, but that seems like a lot of nodes and the path would end up with a lot of stepping.

How about a node at the centre of each rectangle? The final path would need to be constructed through the connected edges, but it could be done. However, the distance between the nodes would not be accurate due to all the possible paths through the rectangles.

Back to the grid squares then, but this time only on the connected edges of the rectangles. This is enough to find an accurate shortest path, and there’s no need to pathfinding inside the rectangles.

Here’s a good description of the algorithm:

http://www.policyalmanac.org/games/aStarTutorial.htm

The only problem I had with this page is that the operations on the open set (insert/delete nodes yet sort by node distance) are not covered by any single STL data structure (assuming you don’t want to do a linear search every time). If you didn’t think about this you might end up using doubled-up maps or (god forbid) something from Boost, but actually it’s possible to defer the tricky deletions and use a simple sorted list.

It all works fine, except that the paths are still a bit steppy when passing between zones. I’ll wait until I see them in use before trying to fix what seems a minor cosmetic issue.

Is A* the end of the story? I doubt I’ll have any performance issues, but I will also need avoidance of dynamic obstacles, and it’s not clear how that will fit in. I’ll see how it goes.