This is what game programming is like.

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…?

15 Comments

    Tqwet
    October 4, 2018 10:48 am

    Awesome post, really interesting listening to your thought process 🙂

    nathan
    October 4, 2018 11:24 am

    Awesome insight as always!

    But what is the game concept? Dying to learn about the direction your game will be taking.

    Nonetheless, good luck!

    Louis W.
    October 4, 2018 11:35 am

    Amazed and envious that you are able to manage your task list in comments. I have to use full-blown systems like Asana. Else, I can’t even remember what file to open to find my notes.

    Joe
    October 4, 2018 12:58 pm

    OK…maybe I DON’T want to program games. 😛

    François-Xavier Talg
    October 4, 2018 1:00 pm

    I definitely agree with other comments. Very interesting flow of thoughts. I’m eager to read more! Thank you for sharing.

    Gongo
    October 4, 2018 1:41 pm

    Hi Luke, i’m so glad to See again At work!!!good luck My friend

    Jeff
    October 4, 2018 1:46 pm

    Can’t wait to see some progress visually! From a programming perspective, your post hits home in so many ways!

    Red Ketchup
    October 4, 2018 2:10 pm

    Please Luke, this time, while at the path coding, you should make it 3D and not a 2D pathing like Banished has.

    If the tile in front of him has more than 0,X tile more higher, thats like a wall !
    No way a citizen should jump 100 tile high because the floor in the tile in front of him is 100 tiles higher !!!! and then having the citizen faling 100 tiles down after if the next tile after is 100 tile lower than the floor it stands.

    A Lot of game has better 3D coding. Take warcraft ! super easy fast game, if the slope in front of you is too big, you dont pass, even while jumping !

    so please, while query the height of next tile, place a if condition. if too big slope = no pass

    Gordon Dry
    October 4, 2018 2:20 pm

    Awesome…

    Did you consider dynamic blocking of the path like landslides occuring prone to deforestation of slopes?
    😉

    Snoopy
    October 4, 2018 2:35 pm

    I love reading this and the whole process to Banished was amazing to follow and I love the game. Can’t wait for the next instalment.

    Geo
    October 4, 2018 3:27 pm

    @Joe – one of the reasons Luke struggles with this? Luke’s coding a game engine from scratch (or, from a previous engine coded from scratch). Game engines/tools like Unity (which comes with its own share of issues!) and Godot have built-in navigation and pathfinding. Hit up google re: “Godot Navigation” and “Unity Pathfinding” to see a bit of this.

    I’m not saying that using an existing engine is better – it’s neither better nor worse. But, Luke has intentionally chosen to do more work (and have more control and insight into the internals of the game engine). Is it the right decision for everyone? Nope – especially not for individuals. A 20+ person game studio? Sure!

    Costas
    October 5, 2018 4:02 am

    Great post. But, now consider curving paths and roads too!

    JosEPh
    October 5, 2018 9:08 am

    Here is wishing you great success. Love Banished, will be watching to see what you come up with next.

    OpblaasHaas
    October 5, 2018 2:38 pm

    Hahahah, this was such a fun read, please keep doing these. I can kinda relate so i’m having a blast reading this.

    Pharaonkheops
    October 8, 2018 1:52 pm

    I bought about 4 or 5 games in “early” mode. Of those, Banished is the only one I didn’t regret and at wich I still play regularly.
    I am so happy to see that you are back at business! No doubt I will make the CC heat a bit to help that new project be given birth…
    (by the way, please be kind and helpfull with the modder’s community, because there are some very talented people therein. It would be too bad if their creative spirit is limited ^^ )

Post a Comment

Your email is kept private. Required fields are marked *

*
*