13
Mar
2017
Code

Choosing the fastest route in Nantucket – 2D polygonal pathfinding in Unity

by DanieleBubb

In the last few weeks we reworked the pathfinding system in the world map scene. In this article we are going to explain how we implemented the new pathfinding system, and what are the improvements we got from it.

The old, tile-based pathfinding

As many other devs do, we used A-Star algorithm to traverse the navigation graph and pick the fastest route between two points in the map.

The navigation graph was generated using an offline process which defined nodes and edges following these rules:

  • The world map was split in squared tiles
  • We added a node in the graph for each traversable tile
  • We added an edge between two adjacent nodes

The graph looked like this, with the nodes represented by blue circles and edges by red lines:

The issues

We analyzed the problems we had with this system and came up with the following:

  • Too many nodes and edges, which led to poor performances
  • Rough choice of routes along the coast

The solution

To solve those issues we wanted to find a way to generate the graph differently, in order to:

  • Reduce the number of nodes and edges, especially in open areas, to improve performance
  • Move the nodes closer to obstacles, to achieve smoother routes around corners

The graph generation

We ended up changing the rules of generation of nodes and edges in the navigation graph. We defined obstacles as polygons and defined the new graph with the following rules:

  • Add a node per convex vertex of the obstacle polygon
  • Add an edge per couple of nodes visible in line of sight

Inspired by this article we generated the obstacle polygons by following these steps:

1. Draw the obstacles using the Graphics editor of your choice

2. Insert the obstacle image in a GameObject and add a PolygonCollider2D component to automatically define the outline.

3. Generate nodes and edges of the pathfinding graph

Since our obstacles are static the process is done offline, and data stored in a ScriptableObject.

The path calculation

When a route between given source and destination points has to be calculated the only computations left to be performed at runtime are:

  1. Add a node on the position of the source point
  2. Add edges from source node to every visible node in line of sight
  3. Repeat steps 1 and 2 for the destination point
  4. Calculate the best path using A-Start algorithm from source to destination node

Here is the pathfinding in action, you can notice how the graph changes when moving source and destination points:

The optimization

In order to improve the performance and let the pathfinding not impact the framerate, we implemented few optimization techniques.

We added a visibility cache, we used the tiles we had in the previous implementation, and stored all the visible nodes in line of sight for each tile. This let us save computation time when adding the edges between source and destination nodes, instead of performing a lot of expensive line of sight checks, we just use the nodes cached in the tile the node is in.

We reduced the number of edges by removing all edges between nodes of different polygons, except for special nodes marked by hand. We won’t go in detail about this, since is strictly tied to the nature of the map, and we didn’t find a way to automatically choose special nodes.

We then moved all the runtime part of the algorithm in a different thread to further save computation time.

The final result

Despite having hundreds of nodes and edges, the overhead is minimal and improved ~100 times over the previous implementation. It runs smoothly on all the machines we tested it in, and we are now able to run it every frame to show the potential route the player can currently set.

Here is the final result in Nantucket:

Hope you enjoyed this technical article, I thought it would be useful to share it since I didn’t see anything like that implemented in Unity.

Nantucket is in the late stages of development, we are putting the final content and internal testing is giving us useful feedback on game usability and balance. We’ll soon show more gameplay in a video on our Youtube Channel. Meanwhile don’t forget to follow us on Twitter and Facebook.

25
Oct
2016
News

NANTUCKET SUBMITTED FOR THE IGF 2017

by picaresque

Ahoy there!

It’s been a while since you’ve read of us. Last time we told you we were in need of some relax to prepare for the final rush. Well, the news of today is part of that:

igf_social

We are thrilled for this submission! It means a lot to us since the game will be judged by the bests and, moreover, that the game is a lot closer to its production end.

We believe in this game and we hope to get as far as possible in this competition. We will keep you updated about this, don’t worry. Wish us luck!

The Team

Save

Save

6
Aug
2016
News

Summer Holiday 2016

by picaresque

Ahoy mates!

Here at Picaresque Studio we keep working hard for the final goal. However, we feel that we need a little rest to recover our strength for the last push. For this reason, we leave you with a new illustration of our Ishmael doodling with wood, carving out whales while something is watching…

NantucketHoliday2016

Have a nice summer time and see you in September rested and ready for some juicy (or groggy) news!

The Picaresque Studio Team

Save

Save

18
Jul
2016
News

Devs Play Ep. 11: “Black Flag on the horizon”

by picaresque

Ahoy fellow Captains!

A new, shining, Devs Play video series episode is out!

Watch Episode 11:

In Nantucket Pirates can be a very dangerous foes and tough ones. Mex, our game designer, will show you how to spot their areas on the map and how to fight them. Remember that not always it will be a good idea to go for the battle but be prepared for their might!

Enjoy the video!

The Picaresque Team

18
Jun
2016
News

Devs Play Ep. 10: “Hunger for Blubber”

by picaresque

Ahoy there!

The new Episode 10 of our Devs Play video series is out!

Watch Episode 10:

Mex, our game designer, will show you how and where to look for sea creatures. A captain has to show to  well know the seven seas! Find information about whale areas and keep track of their migration routes.

Enjoy the video!

The Picaresque Team

4
Jun
2016
News

Devs Play Ep. 9: “Fighting Whales”

by picaresque

Arr!

The long awaited Episode 9 of our Devs Play video series is out!

Watch Episode 9:

Mex, our game designer, will show you how to fight against sea creatures. Now it’s time to see who’s the man! Learn how to challenge and win sea creatures avoiding damage and rescuing your ship mates.

Enjoy the video and let’s fight!

The Picaresque Team

21
May
2016
News

Devs Play Ep. 8: “Intro to Combat”

by picaresque

Ahoy!

The new Episode 8 of the series “Devs play” is out!

Watch Episode 8:

Mex, our game designer, will show you how to prepare fir combat. What’s the combat dice and how many types are on the game? Have a look at how to deploy your crew before a fight on the waters! Low the whaleboats and enjoy the video!

Action stations!

The Picaresque Team

7
May
2016
News

Devs Play Ep. 7: “Level Up & Quests”

by picaresq-admin

Ahoy!

The new Episode 7 of the series “Devs play” is out!

Watch the Episode 7:

Mex, our game designer, will show you how and when to level up your characters. Which are those aspects of the game affected by your level? Moreover, you’ll take a look at the quests system in Nantucket so, buckle up and enjoy the video!

Godspeed and may the fair wind be with you all!

The Picaresque Team

23
Apr
2016
News

Devs Play Ep. 6: “Manage Resources”

by picaresque

Ahoy!

Good news! Episode 6 of the series “Devs play” is out! .

Watch the Episode 6:

In today’s video Mex, our game designer, will show you how to manage your resources during navigation. How can we tackle a situation like, for instance, when food is scarce and your crew is at the brink of starvation?

Enjoy the video and hold fast!

The Picaresque Team

16
Apr
2016
DevBlog

UI Combat: Let’s fight!

by Capt_Eatbones

Drink, ye harpooneers! drink and swear, ye men that man the deathful whaleboat’s bow…

This will be the last article about the combat and before we start, I’d like to point out a couple of aspects of Nantucket. As you probably know, one main aspect of the game style is that is made of paper. It’s an experience played onto the Captain’s table, in his cabin and sometime is played in a harbor. Even so, the harbor is an illustration drawn on paper too.
When we thought of a combat style for this game, it came natural to us moving towards something mostly related with a table and a bunch of pieces of paper: a card game.
This combat is not a Trading Card Game. We’ve chosen a card style due to the context of this game: ship, crew, sailing. And, of course, we like playing card games too. Nantucket, per se, is not a card game, but includes a little card game played during the combat. Now, let’s move on with the article main subject.

Today, we are going to have a look at the actual combat phase UI. I want to share with you a first mock-up (this is a frame of an animated one):

CombatAnimMockupCombat 3.0 – Animated Mock-up (Still)

In the picture above you can see a still of the animated mock-up we prepared before starting the implementation. We needed this to define the timings of the overall combat experience. If you have red the previous articles (if you don’t, you can catch up here and here) you already know how the combat has evolved and how the previous Deployment phase works. Once you start the real fight, you have to roll the combat dices of the crew members you have in your whaleboats and decide which command is the best to win against your opponent.

CommandChoiceCombat 3.0 – Dice roll and Command choice

 As you can see, these images are from an early mock-up and the dices faces are not final. The main concept, though, is there: according to the crew members you’ve placed onto the whaleboats you’ll have several dices combinations. Each dice face, when rolled, will unveil a specific command. Once the the dices have been rolled the player can chose which command he/she prefers. When the command needs a target, ad arrow will appear to point the target the player wants.

Let’s have a look at the design of the crew card:

CARDSCombat 3.0 – Crew cards

Above you can have a look at the final version of the cards. I’ll show you each element from the top to the bottom:

  1. Combat states icons: Bleeding, Stunned, Poisoned, Blind and Surrender. These icons will appear according to the combat development. Except for the Surrender state, all the others are inflicted be the opponent. This label will appear and disappear according to the presence of states.
  2. Crew member information: Health, Name, Class and Level. In this case, I chose to use the heart icon to be sure everyone understands the meaning of it. Previously, we used a red/rope health bar but still it was not clear enough.
  3. Crew member picture: this is the same used in the whole game, whenever we access to the information of this man.
  4. Combat dice.
  5. Combat dice switcher.

The hearth of this card is the combat dice. In the above image, you’re looking at the Captain’s card which is special. Since the Captain has all 4 working skills (Hunting, Sailing, Science and Crafting) he will have 4 different combat dices: one per working skill. According to the evolution of the working skill the related combat dice will evolve too. The working skill faces are 3, no more. The remaining 3 faces are used in this way: 2 for specific skills in use and 1 for specific objects in use. This special dice faces will enable special combat commands.

During combat you can use the Dice Switcher to decide which working skill of your avatar you prefer to use. Simple crew members will only have 2 Dice Switchers: the one related to the working skill they are specialized on and a generic one (related to the Cabin Boy half-class).
Before the roll of the dices the player can chose which combat dice to use for the roll. This way, you can chose the best strategy combination to use each turn. Of course, its crucial that you placed the right men during the Deployment phase.

creatureCardsCombat 3.0 – Creature Cards

The Creatures card is a little simpler than the Crew one. First of all, there are 2 different cards: Standard and Special. Above, on the left, you can see the Standard card style while, on the right, you have the Special card style. As you can see, Moby Dick will be a Special card because its class is Legendary (and because it’s Moby Dick, I’d say!). From the left to the right, these are the elements of the Creature card:

  1. Creature type label: here you have the name of the species and the color of the card. The color is important because it lets you know which color will be its attack cards.
  2. Action/Instant card slot: here the creature can play two different type of cards. The effect of these cards is used for the creature itself.
  3. Creature picture: below the Action/Instant slot.
  4. Creature information: Health, special creature’s Name (or the species name instead), Category, Special ability (or the species shape instead) .
  5. Combat states icons: here will appear the same icons used for the Crew card, except for the Surrender.

CombatView_v3MockupCombat 3.0 – Mock-up

Remember that not always defeat the enemy all the enemies will be asked. The Victory conditions card, in the top left, tells the player the requirements to the success. Moreover, in the top right, there is the Random Combat Condition card that will be drawn each turn and will define the combat conditions each time (bonus, malus, etc.).

And what about the Crew VS Crew combat? Here you have it!

CombatCrewView_v3Combat 3.0 – Crew VS Crew mock-up

Here the combat will work the same, the only difference is the there will be less crew member on your side. Moreover, you will be able to see the combat dices of your opponents. The only real difference is in the opponent card: the colored label is placed at the bottom of the card. This way you have a reference to who is attacking who.

Well, I don’t want to spoil too much of this since we will have specific videos about the combat in our “Devs Play” series (watch it here).

Hope you’ve enjoyed like I did in sharing this with you.

Keep tuned and Godspeed, as always, from your Capt_Eatbones!