Crew Sprites, Pathfinding, and OOO

Hey Folks! With the ship layout and lighting starting to materialize, I decided to take a step back and do some thinking about how the simulation will interact with it. E.g. crew movement and physical properties.

One of the first questions I had was whether I could make the crew sprites consistent with the ship lighting. This would mean generating/painting normal maps for their sprites. I took my earlier prototype's idle sprite, and pieced together a normal map for it, then created an item using this sprite that I could place around the ship. Here's how it looks:

IMAGE( "Make sure you light my good side..."

They're not moving around yet, or hooked up to any AI. Just statues for now. However, I was happy to see that their highlights seemed to work okay, and the shadow casting as well.

I guess the real question is whether this will be sustainable when it comes to animations like the walk cycle, etc. And for that, I'm not sure. It wasn't hard to create this normal map using a reference normal map sphere smushed and stretched to fit head, shoulders, and body. But doing that for frames of an animation with irregularly-shaped parts may be tricky and/or tedious. I might have to explore more automated solutions.

In addition to this, I decided to look up Unity pathfinding, to see what was available. Unity's built-in pathfinding, NavMesh, appears to only work with rooms/terrain laid out in the editor. Since the ship is generated by the user at runtime, and they won't have Unity's editor/exporter, I'll have to try something else.

There are a million other ways to do pathfinding, many of which are in the Asset Store. However, I remembered one from HaxeFlixel which seemed pretty simple to build and had good performance. Namely, the heatmap pathfinding algorithm.

Roughly speaking, a heatmap pathfinding algorithm just uses a grid to keep track of which squares are closer to or further from a destination. You choose a destination square, and the algorithm walks away from that square to every other square, and records the number of steps in each square. Then, you're left with a grid of numbers telling you how far each is from the goal. The AI then just has to look at its current square, and the squares around it, and choose one with a lower number. It does this comparison each step until the grid it's standing on is 0 steps away.

It's not necessarily the most efficient, as the heatmap needs updating each time the goal changes. So a moving goal can be costly, and each AI with a different goal will need a different heatmap.

But it has some useful benefits. As already mentioned, it's super easy to implement. Also, it means anything on the ship can use the same heatmap if they share the same goal. (E.g. swarming) The heatmap can modify the "step" cost of each grid square based on things in it (so different "terrain" types can have different costs). And I might even be able to tweak squares as crew and other things pass through them, so AI avoids obstacles in real time.

But mostly, I'm choosing it because it's easy/fast :) And for the size of ship grid we're dealing with, generating a heatmap is so fast as to be negligible.

So far, I have the rough framework in place for calculating the heatmap, and I'm working out the bugs now so it steers around obstacles better.

Out of Office

One more thing. I'll be out of the office until Wednesday next week. So no devlog posts Monday/Tuesday, and I may be slow to respond to anything that comes up. I'll be back to normal on Wednesday, though.

Hope everyone has a good weekend, and I'll see you Wednesday!


Malacodor's picture

Sounds a bit like a recipe for characters getting stuck because all try to follow the same path. That's a typical situation where in many older games the second charcter is pissed and simply stops moving. In newer games with "improved" pathfinding the second character is still pissed, but passive-aggressively follows an alternative, way longer route. Long story short, if a character is blocked by another one, make a check if the blocking character is still moving, and if so let the second character just wait a bit instead of rerouting them. Furthermore, if the first character already stopped moving let the second one ask them to step aside. Perhaps you're already planning that, I just wanted to make sure it's done right, since so many games suck at pathfinding, and the next time I play a game with characters that are more stupid than ants I might throw my PC out of the window. Apropos ants, did you know that these use a quite clever algorithm?

As SciFi experts and players of WTF and FTL know, a space ship should consist of several sections seperated by airtight seals. You can use this and work with pre-generated heatmaps for the doors. If character A in room 1 wants to go to a goal B in room 2 and both rooms only have one door (to keep the example simple), the game can use the heatmap of door 1 to determine a path from A to door 1, the heatmap of door 2 to determine a path from door 2 to B and the heatmap of either door to determine the path between the doors. As long as B doesn't leave room 2 only the path between door 2 and B has to be recalculated when B moves, no heatmap updates needed. You could even generate a graph with doors as nodes and precalculated paths between them as edges, but that might be overkill.

One last thing, you shouldn't make life for you and us unecessarily hard and allow allied characters to move over each other. Looking at the above image, two people temporarily sharing a single tile isn't even unrealistic. This would result in less heatmap updates for the game and less tantrums for me. ;-)

P.S.: Don't miss my replies to the previous two news posts (was a busy day for me).

Ran around with a clown mask before it was cool

matsy's picture

Project Zomboid started out with sprite sheets but moved to 3D models for the Characters, and Zombies as it was too time consuming to do the sprites. From my limited game development experience, this was the most time consuming part for me!

Also, nice read on rock, papers, shotgun!

dcfedor's picture

@Malacodor, I agree with letting allied AIs pass through each other's tile without penalty. And in fact, I'll have to see how hard it is to update the heatmap for moving obstacles/AIs. It might not be as trivial as I originally thought.

And yeah, precalculated heatmaps for important goals are something I'm considering. The coffee maker is going to get accessed a lot :)

@matsy, I'll have to check out PZ again to look more closely at the sprites. I'm dreading the prospect of introducing more complex 3D assets to the game. Both for my own maintenance costs, and for modders. But drawing a million sprites isn't ideal, either!

And thanks for the RPS link! It seems I'll be having more eyes on this blog now. Guess I better look busy :)

Dan Fedor - Founder, Blue Bottle Games