Creating pathways in Goblins of Elderstone

Goblins of Elderstone is primarily a village simulation game, and one of the interesting technical challenges in bringing the village to life is pathing.  Not just traditional pathfinding (although that’s a big part of it), but also constructing walkways and bridges to bind buildings into a cohesive network that goblins can easily traverse to go about their daily business.  The picture below gives some idea of the overall effect that the designer wanted to create:

Goblin village pathing mockup

The pathing system must accomplish a number of things. First, it has to connect each new  building in the village to one or more neighbouring buildings. Second, it has to create paths that either route around or travel over obstacles in the level such as rocks or trees.  Third, it has to be able to accommodate changes in ground elevation with features such as stairs, ladders and bridges.  And last but not least, it has to look cool!

This post will give a little bit of info about how the pathing system has been created to date, and how it uses some of the Unreal Engine systems to achieve the goals stated above.

Nodes and Endpoints

When the player places a new building in the village, we need to figure out how to connect that building with a pathway of some kind to existing nearby buildings.  After some experimentation, we settled on a system that uses PathNode components in conjunction with an overall PathManager.  The PathNode component automatically registers its existence with the PathManager in its BeginPlay() method, and conversely unregisters on EndPlay().  The PathManager is responsible for keeping track of live nodes and how they connect to each other, and is able to forge new path connections upon request.

Each building is set up as an Actor Blueprint containing a PathNode component, which in turn has one or more PathEndpoint components that indicate where paths can connect to and from the building.  Both PathNode and PathEndpoint are subclassed from USceneComponent – this allows us to position endpoints in the Editor at locations that suit the design of each building.   One nice aspect of this component-based design is that we can potentially add PathNodes to other types of Actor in the future – for example, a junction point in a path could have its own PathNode component, thus allowing paths to fork and join.

An example building blueprint showing the path node/endpoint setup

Connecting buildings

When the player decides to construct a new building in the village, they must place it down in a location that can be reached by goblin villagers.  In this situation the pathing system dynamically plans potential path connections as the player moves the new building around the level, and displays if a given building site is valid or not based on whether path connections can be made.  The system has to be fast enough to recompute new path connection plans every frame without noticeably lagging the game.

Each time a connection planning request is given to the PathManager, it starts by identifying candidate pairs of currently unused PathEndpoints, one on the building being placed, and another on some existing building in the village.  The closest pairs of endpoints get investigated first, then more distant ones are considered until a viable plan is created (or some maximum number of attempts is exceeded).

Path endpoint pairs are investigated in order of distance

To perform the actual connection planning between two endpoints, the PathManager queries Unreal’s Navigation subsystem.  Normally you’d use this system for things like moving Pawns and Characters around in the level, but it turns out that the Navigation system is very flexible and can also be used for arbitrary pathfinding queries.

A NavigationQueryFilter is used when querying to exclude certain navigable areas from consideration, as we don’t want to create paths that cross over buildings or other paths. Building and pathway static meshes are marked with their own custom NavArea classes, and then the query filter prevents the navigation system from returning pathfinding results that would use those nav areas.

Constructing paths

Once we’ve successfully identified one or more potential routes between buildings, it’s time to actually construct the paths.  This is done by taking a pathfinding result from the previous step and ‘drawing’ each linear section of the path (from one waypoint to the next) by spawning a sequence of PathSegment actors.  Each PathSegment is attached to a ‘Next’ transform marker on its predecessor, with the very first segment being attached to the RootComponent of the path itself.

A straight section of path showing the origin and Next transforms.

A good portion of the path is generally made up of straight sections like the one above stacked end to end, but there are also a number of angled joining pieces that come into play if the path changes direction from one waypoint to the next, and other special segments such as landings that are used when the path joins with a building, or stairs that allow goblins to access the path midway between buildings.  Each segment is defined with a Blueprint Actor class, as shown below. This allows us to introduce custom behavior on certain segments such as vertical ‘elevator towers’, which are needed for goblins to be able to traverse large elevation changes.

Some of the other segments used in the construction of pathways

Each path segment is configured with a simplified collision mesh and assigned a custom NavArea class that lowers the cost of travelling over paths significantly compared to walking over normal ground.  This encourages goblins to preferentially select routes that make use of paths when travelling from one building to the next.

A completed path constructed from multiple segments

Obstacle avoidance

One of the nice things about using Unreal’s built-in navigation and pathfinding facilities is that paths will automatically be routed around obstacles, as long as those obstacles are configured with the appropriate collider setup.  Unreal does a very nice job of selecting appropriate paths, and seems to give stable results as you move a building around looking for a suitable construction site during the placement phase.

Some examples of paths being routed around various obstacles

Elevation changes

To allow goblins to travel up and down over uneven terrain, we have implemented a system that detects height changes and spawns special segments such as Stairs, Ladders and Elevator Towers to allow the path to cover the gap.  Since the Unreal navigation system won’t automatically generate a path that travels up a change in elevation, we detect where the terrain height changes along the proposed route and then split the path route into multiple ‘sub-path’ queries. The sub-paths are then joined up by stairs or one of the other bridging techniques based on the difference in height.

Future work

We now have a system in place that does a decent job of connecting the buildings into a basic village network, but there’s still a lot of tweaking and polish work to do as the game progresses. One major area of work is adding suspension bridges that can connect the second floors of adjacent buildings and also span valleys.  Another idea is to add junctions that allow more organic forked paths to be formed as the village grows.  It should be a lot of fun seeing how the system evolves into its final form over the coming months!  Stay tuned for further updates..

Steve Salmond

@stevesalmond

When we first starting prototyping up our Goblins of Elderstone game I was very new to unreal and UMG was just leaving the realm of experimental.  So when it came to getting some functional GUI into our game I didn’t take much time to think through a system – I just hammered in a basic system where all our GUI popups ( of which we have a lot as our game is a strategy game ) were added to a main GUI widget which could then show and hide the individual popups as it needed.  I knew this would not scale well and by the end of our prototype phase we had a monster of a main gui widget which had to control about 20 individual context specific GUI and know far too much about the context of each GUI to keep everything clean.

HideAllHuds functionality needed to know about every single widget that could have been visible… maintenance knightmare…

So as we have now moved out of the prototype stage into full production one of the first major tasks was to overhaul the system, so I thought I would share what I did.

Our new system is pretty straightforward and is focused on two main custom UMG widgets, BaseGUI and BaseWidget.  BaseGUI is the main control for our GUI, it handles creating widgets to show to the user and controlling which widget has focus if needed.  BaseWidget is the base of all of our actual visible GUI widgets and has functions which handle removal of the widget which can be overridden when needed on an individual basis.

BaseGUI

BaseGUI is simply a UMG UserWidget that has a blank canvas panel that all our BaseWidgets are added to.  It has variables for the current modal and nonmodal widgets that have been added.  Also for convenience we have added the ingame HUD’s (to shows resource totals and build buttons etc) directly to the BaseGUI.

It has functions to:

AddGUI – which adds the widget to the correct place and in the case of non modal dialogs tells an existing widget to remove itself.

RemoveGUI – calls the OnRemove event of the widget and handles removing the references to the widget

SetActiveGUI – when a modal dialog is added we set the other visible GUI to hit test invisible so that they can not be interacted with until the modal is resolved.  This function turns that on and off.

Finally the BaseGUI has custom events to handle the user interaction, this is where it will create individual widgets, add them and call their correct setup functions.

BaseWidget

BaseWidget is a UMG UserWidget that all of our actual game GUI widgets derive from, it has a variable to know if it is modal which is set as a spawn pin.

It has functions to:

CloseGUI – simply gets the BaseGUI and calls RemoveGUI with itself as the widget

OnRemove – Custom event which is called by BaseGUI on all widgets it removed.  In this widget it simply removes itself from its parent but this is the event that is overridden in our actual GUI classes if it needs further functionality ( like cancelling a specific action that was being set up )

To create one of these we simply create a UMG UserWidget normally then change its base class to BaseWidget

If we need specific funcitonality at the OnRemove stage we override the function and it gets called whenever this widget is removed.

This system has only been in for the last couple of weeks so it’s a bit early to tell if it handles everything we need but it certainly has reduced the overheads of adding new GUI dialogs and needed to know all the little catches which is good.