This is what game programming is like.

October 4, 2018 | Dukus | 19 Comments

Earlier in the week I reached a point where I was adding the first characters to the game. When I start some new feature I generally type out a description of the things I think will be needed, and modify the document as I work to remember changes I need to make and to keep track of random things I think of that are related. I often get interrupted or it's the end of the day and I want to remember what I was doing when I resume.

So the first few lines of the document read like this:

• - get character model setup, initial component setup.
• - make a basic walk animation, idle animation
• - write a simple wander. Pick random x, y path to it.
• - need an AI action to Follow Paths.
• - need to get height above terrain and set it.
• - ...

I went merrily on my way doing this, and since the last game had the AI follow path action, I figured I'd be done in no time. Especially since I have my dynamic navigation mesh working and can already find paths through it. Alright!

Well.

I coded for about 13 minutes, then I really started thinking about it, and realized there were some issues. The last game ignored a lot of things. The animation drives the forward movement of the character, so I don't actually know how far the character has moved until that happens, and the AI update happens way before animation. There could be 3 or 4 animations blending that cause the forward movement. And I have to know the forward movement before I can query the height above terrain so that the character stands in the right place. There's also the problem that I have to evaluate the path for the direction to walk in and make sure the character turns to face that direction somewhere. Ok, more on the list.

• - need an AI action to Follow Paths.
  • - write a hierarchy controller to set x, y movement, get height from collision, and set orientation.
  • - controller will update right after animation so move offset is known.
  • - maybe call it CharacterComponent and CharacterController - add to Entity namespace? Easily reusable for all moving entities.
  • - set height over terrain after getting animation offset and moving!
  • - maybe put path following into the CharacterController too. That moves it into hierarchy update, so it can be parallelized later!
  • - keep call to path finding in the action, so it can play idle animations, then walk if pathfinding is delayed due to waiting for the result from another thread.

Ok, a few more minutes of coding and I think of some additional problems. What if the path gets blocked halfway through walking there? What if an item gets placed on top of the character and they are stuck in the navigation mesh? Or placed at the destination and the character can't get there anymore?

I briefly consider just doing a collision check when the character moves forward to handle these cases, but for 100's of characters that will be slow, and won't actually do anything in 99.99% of cases.

So I make a pot of tea and sit down to eat some lunch. And think. Then. More on the list.

• - need an AI action to Follow Paths.
  • - write a hierarchy controller to set x, y movement, get height from collision, and set orientation.
  • - controller will update right after animation so move offset is known.
  • - maybe called CharacterComponent and CharacterController in Entity namespace? Easily reusable for all moving entities.
  • - set height over terrain after getting animation offset and moving!
  • - maybe put path following into the CharacterController too. That moves it into hierarchy update, so it can be parallelized later!
  • - keep call to path finding in the action, so it can play idle animations, then walk if pathfinding is delayed due to waiting for the result from another thread.
  • - want to know when paths are interrupted
    • - bad case, character is now in an area they shouldn't be - have to path out to safe location before proceeding.
      • - could search collision mesh for places near edges that are safe and towards target?
      • - could manually add 'safe points' to mesh?
    • - bad case, destination is no longer reachable. Cancel task and replan.
    • - good case, can repath from current location to destination and continue
    • - best case, path was modified behind the character and no repath is required.
    • - these can all be handled in the AI follow path action, just need to know when they occur.
    • - So need an active path manager / path cache.
      • - when navigation mesh changes - (add/remove) - need to test active paths to see if they are affected.
      • - this is a walk across the navigation triangulation...? or just use the dirty rectangle as that's already known for agent radius computation...?
      • - higher level needs some sort of handle to the path that can be released when done.
      • - this is actually a cool idea, common paths that are used frequently can be cached for a long time and will auto regenerate if invalidated. Been looking for a solution to this.
      • - Path cache is also a good fit for all of path finding being put in its own thread. Keep thread safety in mind!
      • - Cache makes it easy to draw all active paths for debugging purposes alongside the navigation mesh.
      • - need some spacial subdivision structure to put paths in so only paths in the area of change are tested and invalidated.
        • - Consider consolidating all spacial subdivisions? There are a lot - graphics, collision, nav mesh, audio, etc. And now paths.
    • - add a way to add/remove things from path scene en mass - so less recomputation happens when major events occur, otherwise agent radius and path invalidating will happen for each add/remove to the navigation mesh.

Wow that's a lot of stuff. And this is possibly where I've gone too far. Everything here is new and probably required, except:

• - Consider consolidating all spacial subdivisions? There are a lot - graphics, collision, nav mesh, audio, etc. And now paths.

Changing my spacial subdivision structures is a major refactor, it would touch lots of major systems, and I'm just trying to get path following to be robust and fast and the two are really unrelated. I'm pretty sure I'm about to Shave a Yak if I go down that road. So for peace of mind I check the memory usage of the subdivision structures, and it's silly low. Alright, no reason for that to be considered again.

Now I work through the list, getting simple things working, then adding all the details until path following works and characters can handle events like getting stuck, tasks canceled, and repathing around new obstacles. None of this is that hard or will take that long (maybe), it just needs to be done right. Phew.

This is what developing the game will be like until the core game loop and engine code solidifies. Even after it does, the new features that seem so simple on the surface can have far reaching design and implementation problems when you get into them.

So what was next on that list again...?

More Posts