Summary

This latest build fixes a number of bugs in the engine related to rendering and makes some cosmetic changes to the UI. The big change in this latest build is in the NPC AI. I will discuss the overhaul of the NPC behavior in the long form discussion further below.  

Here are some of the highlighted changes in the latest build.

Engine Developments

• Precompute certain fixed routes on the map as part of the procedural generation as opposed to on the fly in-game.
• NPC behavior is now governed by finite state machine, in the future, each type of NPC will have its own directed graph of behaviors that they operate by.
• Player character won't lose the game when supplies reaches zero. Instead their movement speed takes a major penalty hit.
• Changed the way quest generation works to accommodate new NPC behavior.

Bug Fixes

• Fixed a bug where fog of war was not being properly displayed if the character is at an elevated position.
• Fixed a bug where fog effects was being drawn twice, this had the affect of making road tiles appear darker than they should be.
• Fixed some bugs related to pausing, now it should be possible to continue some limited in-game interactions while the game is paused.
• Fixed some contextual UI prompts that shouldn't appear unless certain conditions are met.

Trading Caravan Behavior

In Macrocosm there are wandering trading caravans that in principle function the same as the player avatar. In this build I introduce a more sophisticated behavior system for the non-player character trading entities. 

How it used to work

The current way that things work is NPC movement is random with two constraints:

• NPCs are restricted to movement on road tiles
• NPCs cannot repeat their last move

Therefore at each tile, the NPC only "sees" one tile ahead. In practice this usually works, and "propels" the NPC forward and with some custom logic, it's possible to have them interact when arriving at an settlement and (reverse) move away. It also has the advantage of being fast. However, not only is this not quite aesthetically pleasing, it's also buggy, as it is common for NPCs to get stuck in loops on the road.

In addition it isn't a sustainable way of developing AI code if we want to expand the scope to different types of NPCs. Therefore, I knew something had to be done.

Finite State Machine

As I was doing research on the topic of AI in games I realized there were a few approaches to the take. I have decided to follow the simplest model, using a finite state machine (FSM) to model the NPC behavior. A FSM is defined as a system such that:

• The entity can exist only in a single state at a time.
• A state can transition to any number of other states given some inputs and internal process of the state.
• There are only a finite number of possible states.

I choose to represent the states of the NPC caravans in C++ as a enumeration,

enum States{
 FIND_CONTRACT,
 BUY_GOODS,
 SELL_GOODS,
 TRAVEL_TO_SETTLEMENT,
 WAIT
};

part of the advantage of this representation is that it enforces the fact that the NPC can only be in one state at a time.

The state transitions form a directed graph:

in this design, every NPC keeps a history of its own states in a stack and every frame of the game loop we update its state by checking the top of the stack using a switch statement:

int returnFlag;
switch (stack.top()):
 case FIND_CONTRACT:
  returnFlag = FindContract();
  if (returnFlag == SUCCESS):
   stack.push(BUY_GOODS);
  else 
   stack.push(WAIT);
  break;
 case BUY_GOODS:
   ...
 case SELL_GOODS:
   ...
 ...  

To make this work involved a few changes to other systems and the introduction of some additional data structures. 

For one, since the NPC behavior is restricted to contract deliveries between settlements, it's possible to precompute the paths between settlements ahead of time and store them as part of the map data. Otherwise, for a large map with possibly hundreds of trading NPCs, it becomes computationally too expensive and will result in a massive frame rate hit, not to mention many redundant calculations.

In-game, when the NPC accepts a contract from the settlement, it only needs to look up a table between source and destination settlements to find the route and move along it. 

A second issue was to revise the contract and questing systems to allow NPCs to mirror the player behavior. In other words, the NPC traders can search up, take on and complete (a restricted range) of contracts just like the player. They have their own cargo inventory, which can be examined on the road. In the future this could form the basis for some gameplay mechanics. 

The user interface has already been revised to account for this. It's now possible in-game to "right-click" on a traveling NPC and examine it in more detail. Right now only the briefest outline of possible interactions is implemented. I am still brainstorming and toying with what interactions should be possible but at minimum - it might be interesting to allow the player to "swap cargo", i.e. barter and trade with the traveling NPC caravans.

Going forward I will use this model to introduce additional classes of NPCs (some of which can be potentially hostile). 

That is all for now. Until next time.

-K